# Probability Puzzle: Mutating Loaded Die

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.

• Just curious: Have you found/tried anything interesting yourself yet? It should be solvable using Markov Chains: en.wikipedia.org/wiki/Markov_chain (although that is more or less a brute force approach) – Ragnar Jun 20 '14 at 22:03
• Note that once you roll $1$, you will always roll $1$ from then on. – Ragnar Jun 20 '14 at 22:04
• I've calculated the probability distributions for the first few rolls more or less by doing all branching by hand on paper. While we are clearly dealing with a Markov Chain here, I did not see how this could help me with computing the probability at all, which is why I decided to post the puzzle here to see whether there is a simple pattern to what I observed. – user139000 Jun 20 '14 at 22:06
• One immediate observation is that the probability for rolling a $6$ on your $n$th roll decreases as $n$ increases, since the lower numbers are "attractors" in a probability weight sense. – user139000 Jun 20 '14 at 22:12
• Just realized it isn't going to work :( easily summing over all possible path to the end situation won't work because $(2,3,2,3)$ doesn't have the same probability as $(2,2,3,3)$ – Ragnar Jun 20 '14 at 22:12

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.

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

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*}