Question

Four People (A, B, C, D) are having a conversation. When one person finishes speaking, it is equally likely that any of the other three begins. Under this assumption, the transitions from one speaker to the next follow the rules of a Markov chain. Let T be the number of transitions it takes for conversation to return A. Find the mean of T.

Answer 1

Let the states of the Markov chain be A, B, C and D.

When one person finishes speaking, it is equally likely that any of the other three begins. Then the transition probability from any state is 1/3 to other three states. Thus, the transition probability matrix is,

Let = [a, b, c, d] be the stationary distribution vector. Then P = and a + b + c + d = 1 --(1)

From P = ,

(b + c + d)/3 = a => (c + d)/3 = a - b/3 --(1)

(a + c + d)/3 = b => (c + d)/3 = b - a/3   --(2)

(a + b + d)/3 = c => (a + b)/3 = c - d/3 --(3)

(a + b + c)/3 = d => (a + b)/3 = d - c/3 --(4)

From (1) and (2),

a - b/3 = b - a/3

=> 3a - b = 3b - a

=> 4a = 4b

=> a = b

From (3) and (4),

c - d/3 = d - c/3

=> 3c - d = 3d - c

=> 4c = 4d

=> c = d

From (4), (a + b)/3 = d - c/3

=> 2a/3 = d - d/3 (a = b and c = d)

=> 2a/3 = 2d/3

=> a = d

Thus, a = b = c = d

From , a + b + c + d = 1

a + a + a + a = 1

=> a = 1/4 = 0.25

and a = b = c = d = 0.25

Mean of T = 1/a = 1/0.25 = 4