[Math] Supply the transition matrix for these (possible) Markov chains

markov chainsprobabilitystochastic-processes

Reading Grimmet, Stirzaker: Probability and Random Processes, which unfortunately doesn't have solutions. Trying to make sure I understand Markov chains.

A die is rolled repeatedly. Which of these are Markov chains? For those that are, supply the transition matrix.

a) the largest number $X_n$ up to the n:th roll

This is a Markov chain, since $X_{n+1}$ only depends on $X_n$.

$P_a =
[1/6, 1/6,1/6…] \\
[0,1/5,1/5,…] \\
[0,0,1/4,1/4,…]
$

b) The number $N_n$ of sixes in $n$ rolls.

This is Markov, $P(X_{n+1}=j|X_n=i) = 1/6$ for $j=i+1, = 5/6$ for $ j = i, P=0$ otherwise. For a fixed n, $[P_n]$ would be $n\times n$ and have rows of $[…,0,0,5/6,1/6,0,0,…]$ but will this matrix not grow for each iteration, or be infinite-dimensional?

c) At time $r$, the time $C_r$ since the most recent six.

Also Markov since we only need to look at the last iteration to get complete information. Similar problems with supplying $[P]$ here.

d) at time r, the time $B_r$ until the next six.

This is not Markov since it's dependant on more than the last iteration.

Best Answer

Here is a complete solution to (d), which is provided in the hope that the OP will emulate it for the other items. Consider the results $(Z_n)_{n\geqslant1}$ of the die, these are some i.i.d. sequence and, for every $n$ and $k$, $$[B_n=k]=[Z_{n+k}=6]\cap\bigcap_{i=1}^{k-1}[Z_{n+i}\ne6].$$ The dynamics of $(B_n)$ is as follows:

  • If $B_n=k$ with $k\geqslant2$, then $B_{n+1}=k-1$ with full probability.
  • If $B_n=1$, then $Z_{n+1}=6$ and one is interested in the next $6$ after time $n+1$. Note that $[B_n=1]=[Z_{n+1}=6]$ and that, conditionally on $Z_{n+1}=6$, $(B_k)_{k\leqslant n}$ depends on $(Z_k)_{k\leqslant n}$ only and $B_{n+1}$ depends on $(Z_k)_{k\geqslant n+2}$ only.

This is Markov property with transition probabilities $P(1,k)=P(X_1\ne6)^{k-1}P(X_1=6)=5^{k-1}/6^k$ for every $k\geqslant1$ and $P(k,k-1)=1$ for every $k\geqslant2$.

Related Question