# Changing-sided dice probability problem.

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

• You want to count dice of 2 or 3 sides? They are unreal dices but, you want? May 31, 2015 at 3:10
• @Masacroso I know it's a bit silly, but yes, I do. (If you are so inclined you can think of the 3 sided dice as a 6 sided dice with each number from $\{1,2,3\}$ twice labelled and the 2 sided dice as a fair coin flip. It doesn't really matter.) May 31, 2015 at 3:12

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)

• I have heard of Markov chains before, but I've never used them. I'll have to start reading! Thank you. May 31, 2015 at 3:17
• This solution is very good, but it does assume that once you reach state $1$ you stay there, and start rolling a one sided dice. The calculated probability for $n=2$ is $\frac{49}{120}$ with this method, but I would like that, minus the probability for $n=1$, which is $\frac{29}{120}$. To fix this, I think it would be correct to set the final entry of the 6th row to a $0$ in $P$. May 31, 2015 at 3:40
• The summation of all rows in the transition matrix should be equal to 1 for this to work. Your P(2) should include (+1) in the parenthesis. Dr Xorile solution is absolutely correct. To restate, P(2) should P( 1). and the answer is ofcourse ( $\frac{49}{120}$). May 31, 2015 at 4:16
• I see what you're saying. I'd suggest adding a 7th state in, where it goes to after reaching the 1, and stays there. That way, you'd be able to read off the probability that it was at 1 on the $n$th throw, rather than on or after the $n$th throw. May 31, 2015 at 5:18
• I've added to the solution to separate this out, including a link to the matrix calculation at wolfram alpha May 31, 2015 at 5:35

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.

• The absorbing state is a state that charaterizes the fact that once on that state it cannot move out in a typical Markov Chain. Usually that state gets a 1 in a markov chain. I agree to the fact that P(2) should not contain P(1) only if the problem states that the game stops only in the second roll which in this case is true. Had the problem states " what is the probability that it 1 is reached by the second roll". In this case, you need to include the probability P(1). May 31, 2015 at 9:20
• Oops, I didn't mean to make that a separate answer. The absorbing state here is entered on any number rolled after we roll a 1. But that doesn't contribute to the probability we're looking for, so we can ignore it in our state-transition matrix. All that matters is that we update the state 1 probability correctly from the other states. Here is another example where this is ignored under phase type distribution. en.wikipedia.org/wiki/… May 31, 2015 at 10:48
• It might be interesting to note that a nice explicit expression can be given for the expected number of rolls needed. Let $\mu_d$ be the expected number of rolls until a 1 is rolled starting with a symmetric $d$-sided die. Then, by conditioning, $\mu_d=1+\frac{1}{d}\sum_{k=2}^{d}\mu_k$ for $d\geq 2$. Using induction, we obtain the explicit result $\mu_d=1+\sum_{k=1}^{d-1}\frac{1}{k}$ for $d \geq 2$. May 31, 2015 at 11:20