The Grandfather Paradox with a Markov Chain

The YouTube video “Solution to the Grandfather Paradox” does a great job discussing the Grandfather Paradox.

Interestingly, at a point, the narrator states: “And a similar paradox-free solution can be obtained by viewing the problem as a steady-state solution to a Markov chain. But I won’t go to that here.” while displaying the following video frame:

Initial

In this blog post, I am going to explain the above statement and video frame. Actually, you can understand everything by reading about State Diagrams and Markov Chains, or by reading my analysis below.

What the video frame depicts is:
On the left: a state diagram with 4 states (a.k.a. a Markov chain with 4 states), using a directed graph to picture the state transitions and their corresponding probabilities.
On the right: The transition matrix P that corresponds to the state diagram.

Named

We have 4 states: A, B, C, and D. I named the states so that the name (letter) order will produce the matrix on the left exactly as depicted.

State A: Grandfather is alive.
State B: Grandfather is dead.
Stare C: You are not born.
State D: You are born.

The transition probabilities from each state to the others are shown with arrows and numbers. Let p denote probability and p(X->Y) denote the probability to transition from State X to State Y. Then the transition probabilities are as follows:

From state A, you can only go to State D.
(If your grandfather is alive, then you are born.)
Thus, p(A->A)=0, p(A->B)=0, p(A->C)=0, p(A->D)=1.

From State B, you can only go to State C.
(If your grandfather is dead, then you are not born.)
Thus, p(B->A)=0, p(B->B)=0, p(B->C)=1, p(B->D)=0.

From State C, you can only go to State A.
(If you are not born, then your grandfather is alive.)
Thus, p(C->A)=1, p(C->B)=0, p(C->C)=0, p(C->D)=0.

From State D, you can only go to State B.
(If you are born, then your grandfather is dead.)
Thus, p(D->A)=0, P(D->B)=1, p(D->C)=0, p(D->D)=0.

Matrix P has the following layout:
Each row corresponds to the initial state in a transition.
Each column corresponds to the final state in a transition.

Thus matrix P is comprised of 4×4=16 cells, each denoting a transition probability:

Matrix

The above table (matrix) has to fulfill the following statement: For each row (independently of the others) the sum of the probabilities of all the cells of the row equals 1 (where 1 is 100%). This is easy to understand: From each State, you have certain probabilities to transition to other states, or to remain at the current State. All these probabilities should add up to 1 (where 1 is 100%).

Matrix P is equal to:

p(A->A)    p(A->B)    p(A->C)   p(A->D)
p(B->A)    p(B->B)    p(B->C)   p(B->D)
p(C->A)    p(C->B)    p(C->C)   p(C->D)
p(D->A)    p(D->B)   p(D->C)   p(D->D)

Thus, matrix P is equal to:

0  0  0  1
0  0  1  0
1  0  0  0
0  1  0  0

What all this means is that the transitions are as follows:

A->D->B->C->A and so on.

Which is equivalent to saying:

If your grandfather is alive, then you are born.
If you are born, then your grandfather is dead.
If your grandfather is dead, then you are not born.
If you are not born, then your grandfather is alive.
And so on.

Advertisements

About Dimitrios Kalemis

I am a systems engineer specializing in Microsoft products and technologies. I am also an author. Please visit my blog to see the blog posts I have written, the books I have written and the applications I have created. I definitely recommend my blog posts under the category "Management", all my books and all my applications. I believe that you will find them interesting and useful. I am in the process of writing more blog posts and books, so please visit my blog from time to time to see what I come up with next. I am also active on other sites; links to those you can find in the "About me" page of my blog.
This entry was posted in Science. Bookmark the permalink.