6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Ragnar Jun 20 '14 at 22:03
  • $\begingroup$ Note that once you roll $1$, you will always roll $1$ from then on. $\endgroup$ – Ragnar Jun 20 '14 at 22:04
  • $\begingroup$ 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. $\endgroup$ – user139000 Jun 20 '14 at 22:06
  • 1
    $\begingroup$ 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. $\endgroup$ – user139000 Jun 20 '14 at 22:12
  • $\begingroup$ 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)$ $\endgroup$ – Ragnar Jun 20 '14 at 22:12
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy