Probability Puzzle: Mutating Loaded Die

Question

Take an (initially) fair six-sided die (i.e. $P(x)=\frac{1}{6}$ for $x=1,…,6$) and roll it repeatedly.

After each roll, the die becomes loaded for the next roll depending on the number $y$ that was just rolled according to the following system:

$$P(y)=\frac{1}{y}$$ $$P(x)=\frac{1 - P(y)}{5} \text{, for } x \ne y$$

i.e. the probability that you roll that number again in the next roll is $\frac{1}{y}$ and the remaining numbers are of equal probability.

What is the probability that you roll a $6$ on your $n$th roll?

NB: This is not a homework or contest question, just an idea I had on a boring bus ride. Bonus points for calculating the probability of rolling the number $x$ on the $n$th roll.

Answer 1

The transition matrix is given by $$\mathcal P = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ \tfrac{1}{10} & \tfrac{1}{2} & \tfrac{1}{10} & \tfrac{1}{10} & \tfrac{1}{10} & \tfrac{1}{10} \\ \tfrac{2}{15} & \tfrac{2}{15} & \tfrac{1}{3} & \tfrac{2}{15} & \tfrac{2}{15} & \tfrac{2}{15} \\ \tfrac{3}{20} & \tfrac{3}{20} & \tfrac{3}{20} & \tfrac{1}{4} & \tfrac{3}{20} & \tfrac{3}{20} \\ \tfrac{4}{25} & \tfrac{4}{25} & \tfrac{4}{25} & \tfrac{4}{25} & \tfrac{1}{5} & \tfrac{4}{25} \\ \tfrac{1}{6} & \tfrac{1}{6} & \tfrac{1}{6} & \tfrac{1}{6} & \tfrac{1}{6} & \tfrac{1}{6} \end{bmatrix}.$$ It is fairly easy to get numerical values for the probability distribution of being in state $6$ after $n$ steps, but a closed form solution appears difficult.

Answer 2

Find the transition matrix and diagonalize it. Taking nth power should be easy...

Answer 3

From the matrix given by heropup, we can proceed to get the generating function for the entries in the transition matrix by computing $\left(I-x\, \mathcal P\right)^{-1}$, and the required generating function is in the first column of the final row:

\begin{align*} P(x) &= \frac{2 \, x^{5} - 85 \, x^{4} + 1050 \, x^{3} - 4625 \, x^{2} + 6250 \, x}{2 \, x^{6} - 176 \, x^{5} + 3579 \, x^{4} - 26105 \, x^{3} + 77075 \, x^{2} - 91875 \, x + 37500} \end{align*}

From $P(x)$, we can then get a closed form by partial fractions (not exactly closed -- a numerical approximation, don't know whether it can be expressed as radicals)

\begin{align*} p_n &= 1 -\frac{0.693982819959272}{62.5850370771749^{n + 1}} - \frac{0.092005459392035}{14.08514740967338^{n + 1}} - \frac{0.0523322928368}{6.21661835066233^{n + 1}} - \frac{0.05617730006359}{2.95554722545701^{n + 1}} - \frac{1.10550212774831}{1.15764993703234^{n + 1}} \end{align*}

and a recurrence

\begin{align*} p_{n} &= \frac{29}{20}\, p_{n-1} - \frac{227}{375}\, p_{n-2} + \frac{227}{2500}\, p_{n-3} - \frac{29}{6250}\, p_{n-4} + \frac{1}{18750}\, p_{n-5}+\frac{216}{3125} \\\\ p_0 &= 0 \\ p_1 &= \frac{1}{6}\\ p_2 &= \frac{57}{200}\\ p_3 &=\frac{13813}{36000}\\ p_4 &=\frac{1684933}{3600000} \end{align*}