# Supply the transition matrix for these (possible) Markov chains

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.

• The reasons you give are most unconvincing. It seems you are essentially paraphrasing the situation but that the part after "since" of your "reasons"is unsubstantiated and that why exactly these should imply the statements before "since" is unclear. // In b-c-d the state space is $\{0,1,2,\ldots\}$ and the fact that it is infinite is irrelevant to decide the Markovianity (or not) of the process. // Why the reason for c ("only need to look at the last iteration to get complete information", whatever that means) could not be applied to d as well? – Did Aug 12 '14 at 8:47
• It seems you're implying that my definition of a Markov chain is naive in some way. My definition was that $X$ is Markov if $P(X_n = k)$ is only a function of $X_{n-1}$ and not of $X_0,X_1,...X_{n-2}$. Is that mistaken? – Benjamin Lindqvist Aug 12 '14 at 9:33
• I see now how d can be Markov, thanks to your answer. Thank you. I understand how that makes my reasoning 'sloppy', but is my definition 'in need of clean up', or plain wrong? Also, the issue with constructing a transition matrix still eludes me :( – Benjamin Lindqvist Aug 12 '14 at 9:40
• "My definition was that X is Markov if P(Xn=k) is only a function of Xn−1 and not of X0,X1,...Xn−2." This is no definition at all. Note that P(Xn=k) is a number, how could it be (or not) a function of some random variables? " the issue with constructing a transition matrix still eludes me" Please explain precisely what eludes you. – Did Aug 12 '14 at 9:50
• Ok, $P(X_n=k | X_{n-1}) = P(X_n = k | X_0,X_1,...,X_{n-1})$ is the definition in my book. I interpreted that as 'if you want to know $P(X_n=k)$, you only need to condition on $X_{n-1}$. If you can do that, then $X$ is a Markov chain". Is that wrong? – Benjamin Lindqvist Aug 12 '14 at 9:57

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$.