Changing-sided dice probability problem.

Question

Suppose you roll a fair $6$-sided dice, and that the number you roll is $m$.

If $m=1$, stop. Otherwise, roll an $m$-sided dice. The number you roll is $n$. If $n=1$, stop. Otherwise roll an $n$-sided dice... etc.

What is the probability it will take exactly $x$ rolls to roll a 1?

So far I see a pattern, but I'm wondering if there's a better way of expressing these nasty sums, or if it's even possible?

$$P(1)=\frac{1}{6}$$ $$P(2)=\frac{1}{6}(\frac{1}{6}+\frac{1}{5}+\frac{1}{4}+\frac{1}{3}+\frac{1}{2})$$ $$P(x)=\underbrace{\frac{1}{6}\sum_{j_1=2}^{6}\left(\frac{1}{j_1}\sum_{j_2=2}^{j_1}\left[\frac{1}{j_2}\sum_{j_3=2}^{j_2}(\ldots)\right]\right)}_{x-1 \mbox{ sigmas}}$$

Answer 1

This looks like a classic Markov Chain problem.

There are 6 states (6,5,4,3,2,1), and you start at 6 and end at 1. The transition matrix is:

$P=\left(\begin{array}{cccccc} \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6}\\ 0 & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5}\\ 0 & 0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4}\\ 0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2}\\ 0 & 0 & 0 & 0 & 0 & 1\\ \end{array} \right)$

So the probability that the state will be 1 after n terms can be read off using matrix multiplication (which is basically a neat way of organising your summations!)

$(\begin{array}{cccccc} 1 & 0 & 0 & 0 & 0 & 0\end{array}) \cdot P^n$

Actually, this will give you the probabilities that the state will be [6,5,4,3,2,1] after n turns.

Edit: to ensure that the final state is captured on exactly $n$ throws:

$P=\left(\begin{array}{ccccccc} \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & 0\\ 0 & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & 0\\ 0 & 0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & 0\\ 0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0\\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{array} \right)$

Then figure out:

$(\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0\end{array}) \cdot P^n$

The 6th number should be the probability that you're after (and the 7th number will be the cases where it reached 1 before $n$)

It can be confirmed that this spits out the 29/120 answer for n=2 at wolfram alpha here: Wolfram Alpha Calculation (change the power if you want)

Answer 2

It's not necessary to add a 7th state to be able to read off the probability that it was at 1 on the nth throw and not earlier. Just use the original 6x6 for P above except change the last row to all 0's as nathan suggested. We don't need a separate output for the absorbing state, so that last row need not sum to 1. It's OK to use the 7x7 also, but the 7th output value will simply be 1 minus the sum of the other 6 values.

Also it should be P(2) = 29/120.