6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ You want to count dice of 2 or 3 sides? They are unreal dices but, you want? $\endgroup$ – Masacroso May 31 '15 at 3:10
  • $\begingroup$ @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.) $\endgroup$ – nathan.j.mcdougall May 31 '15 at 3:12
3
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ I have heard of Markov chains before, but I've never used them. I'll have to start reading! Thank you. $\endgroup$ – nathan.j.mcdougall May 31 '15 at 3:17
  • 1
    $\begingroup$ 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$. $\endgroup$ – nathan.j.mcdougall May 31 '15 at 3:40
  • $\begingroup$ 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}$). $\endgroup$ – Satish Ramanathan May 31 '15 at 4:16
  • $\begingroup$ 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. $\endgroup$ – Dr Xorile May 31 '15 at 5:18
  • 1
    $\begingroup$ I've added to the solution to separate this out, including a link to the matrix calculation at wolfram alpha $\endgroup$ – Dr Xorile May 31 '15 at 5:35
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Satish Ramanathan May 31 '15 at 9:20
  • $\begingroup$ 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/… $\endgroup$ – BruceZ May 31 '15 at 10:48
  • 1
    $\begingroup$ 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$. $\endgroup$ – user164118 May 31 '15 at 11:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.