3

Problem 2 in section 6.1 of Grimmett and Stirzaker (G+M) asks: a die is rolled repeatedly which of the following are Markov chains, and supply the transition matrix for those that are:

a.) the largest number up to the nth role

I'm stuck on the first one, I've seen the solution but obviously I am failing to understand it.

$ p_{ij} = \left\{ \begin{array}{ll} 0 & j<1\\ \frac{1}{6}.i & j=i\\ \frac{1}{6} & j>i \end{array} \right.$

The first transition seems to be straightforward if j < i then there is 0 probability that the process will transition to j from i, is this reasoning correct?

I think that the rational for the second transition prob is that the probability that if j = i then the probability that this is the max value to date is simply equal to it's value relative to the max value. Is this correct?

I'm confused by the third transition probability? Why is it that if j is more than i then it's probability of being the maximum is only $\frac{1}{6}?$ This means that if j = 5 and i = 5 then the probability of j being the max would be $\frac{5}{6}$ but if i = 5 and j increases to 6 it's probability of being the maximum is only $\frac{1}{6}?$

for $j>i$, they also give $p_{ij}(n) = (\frac{j}{6})^n-(\frac{j-1}{n})^n$

But I don't understand this either!

Can someone please explain?

Bazman
  • 899
  • Two great answers, I understand the first part now, but I'm still struggling to see where the second part comes from: or $j>i$, they also give $p_{ij}(n) = (\frac{j}{6})^n-(\frac{j-1}{n})^n$ Can anyone shed any light on this? – Bazman Jun 21 '18 at 15:19
  • What does the notation $p_{ij}(n)$ mean? – saulspatz Jun 22 '18 at 16:13

3 Answers3

3

I don't think you're looking at this right. $p_{ij}$ is the probability that the maximum number, after the next roll will be $j$, given that it is presently $i$.

If $j<i,$ this probability is $0$, since there is no way for the maximum to decrease.

If $j=i,$ we are looking for the probability that the maximum doesn't change, which happens if the next roll is one of the numbers $1,2,\dots,i,$ giving a probability of $i/6$.

If $j>i$ the maximum increases to $j$ precisely when the next roll is $j,$ which happens with probability $1/6$.

saulspatz
  • 53,131
  • Gonna give you the credit and ask the last part again in a separate question thanks again for your help. – Bazman Jun 22 '18 at 08:22
2

The $n$-th roll has equal probabilities of $\frac16$ of being any of the numbers $1$ through $6$. If the highest roll so far was $i$, the probability that it remains $i$ is $\frac i6$, since there are $i$ different values, each with probability $\frac16$, that will make it so. On the other hand, all values $j\gt i$ only have a probability of $\frac16$ of becoming the new high mark, since this happens only if the roll is exactly $j$, with probability $\frac16$.

joriki
  • 238,052
0

I am new here, so this needs to be an answer and not a comment. A quick remark about the equation. And there is (I hope) a typo:

$p_{ij}(n) = \left( \frac{j}{6}\right)^n - \left( \frac{j-1}{6}\right)^n$

You get to the solution when you use the matrix power $p_{ij}(n) = (P^n)_{ij}$. This is easy to compute when you know that the eigenvalues are $1,5/6, 4/6, 3/6, 2/6, 1/6$ and the corresponding eigenvectors $(1,1,1,1,1,1), (1,1,1,1,1,0), \ldots, (1,0,0,0,0,0)$

Technically $p_{ij}(n)$ is the probability that $n$ steps later the maximum has changed from $i$ to $j$. For $n=1$ you get back the values for $P$.

As for an intuitive explanation:

Say after $n$ steps the maximum has changed from $i$ to $j$. The chance for this is then the probability that, during all $n$ steps, only values from 1 to j appeared $(j/6)^n$ minus the (less likely) probability that only values from 1 to j-1 appeard, in which case the new maximum would not be $j$ but smaller.

For completeness:

$p_{ij}(n) = \left( \frac{j}{6}\right)^n, j = i$

$p_{ij}(n) = 0, j < i$

jhp
  • 101