Question

Consider a circular board game with 4 spots along its circumference. Each time, tosstwo fair coins. For each Heads you obtain, move one spot clockwise. If you do not get any Heads, then move one spot counterclockwise. Repeat.

a) Define your states to model this game a discrete-time Markov chain (DTMC).

b) Verify that process {Xn, n = 0, 1, 2, ...} is a discrete-time Markov chain. Briefly discuss.

c) Derive a transition probability matrix P. Briefly explain how you obtained the probabilities.

Answer 1

Ans a)  The states in the discrete time Markov Chain are the 4 spots along the circumference. Let's name these states as 1, 2, 3 and 4.

The Markov Chain with corresponding state transition probabilities, looks as follows (the diagram on the right shows the 4 states along the circumference and HH, HT, TH, TT are the 4 possible outcomes of the 2 coin tosses)

Ans b) For any state Xn, probability that the above process transitions to this state only depends on the state that it is transitioning from. This can be seen above, for example, probability of transition to State 2 only depends upon the state it is transitioning from (i.e., 1 or 3 or 4), and not on the previous states or the exact trajectory it follows for reaching 2. Hence, this process is a Markov Chain.

Ans c)  The transition probability matrix can be obtained from the above state transition diagram as follows:

The transition probabilities above are obtained by realizing that the set of possible outcomes of the 2 coin tosses are {HH, HT, TH, TT}, which gives

P(Occurrence of 1 Head) = 2/4 = 1/2, P(Occurrence of 2 Heads) = 1/4, P(Occurrence of No Heads) = 1/4 ----- (1)

Using (1), we can easily see that, for example, if we are in State 1 and get 1 Head, we transition too State 2 with probability of 1/4, to State 3 with probability 1/2 (i.e. when we get 2 Heads), or to State 4 with probability 1/4 (i.e. when we get 0 Heads, we move 1 step backward/counterclockwise on the circle).

The probabilities for other states can be worked out similar to above.