Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we roll m dice, remove all the dice that come up 1, and roll the rest again. If we repeat this process, eventually all the dice will be eliminated. How many rolls, on average, will we make?

The solution to this problem is $$ \sum_{n=1}^{\infty}n \cdot \left( \left(1-\left(\frac{5}{6}\right)^n \right)^m -\left(1-\left(\frac{5}{6}\right)^{n-1}\right)^m\right)$$

which can be rewritten to

$$\sum_{n=1}^{\infty}\sum_{k=0}^{m}n(-1)^{k} \left (1-\left (\frac{5}{6} \right )^{-k} \right )\binom{m}{k}\left (\frac{5}{6} \right )^{nk}$$

For small values of m I can calculate it using Wolfram Alpha, e.g. for m=8

Sum[n*((1 - (5/6)^n)^8 - (1 - (5/6)^(n - 1))^8),     {n, 1, Infinity}]   

http://www.wolframalpha.com/input/?i=Sum%5Bn*%28%281+-+%285%2F6%29%5En%29%5E8+-+%281+-+%285%2F6%29%5E%28n+-+1%29%29%5E8%29%2C+++++%7Bn%2C+1%2C+Infinity%7D%5D++++++++

but this does not work for large values of m. Which approximations could I use to calculate a value for m=1000000?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

We are looking for the mean $\mathbb{E}(Z_{(m)})$ of the $m$th order statistic (maximum) of $m$ independent geometric random variables $Z_1,\dots, Z_m$ with mean $6$. The exact value is $$\mathbb{E}(Z_{(m)})=\sum_{j=1}^m (-1)^{j+1}{m\choose j}\, {1\over 1-(5/6)^j} $$

Here's an idea. If you replace each $Z_i$ with an exponential random variable $Y_i$ with the same mean, then there is an exact formula $$\mathbb{E}(Y_{(m)})=6\left(1+{1\over 2}+{1\over 3}+\cdots+{1\over m}\right)\approx 6(\log(m)+\gamma).$$

I haven't thought seriously about how close $\mathbb{E}(Z_{(m)})$ and $\mathbb{E}(Y_{(m)})$ are, but for small $m$ the results look OK.

Update: A better approximation is obtained by replacing "$6$" above with $1/\log(6/5)$. In fact, we get the following bounds $${1\over\log(6/5)} \left(1+{1\over 2}+{1\over 3}+\cdots+{1\over m}\right)\leq \mathbb{E}(Z_{(m)})\leq {1\over\log(6/5)} \left(1+{1\over 2}+{1\over 3}+\cdots+{1\over m}\right)+1$$ and taking the midpoint gives the approximation $$ \mathbb{E}(Z_{(m)})\approx {1\over\log(6/5)} \left(1+{1\over 2}+{1\over 3}+\cdots+{1\over m}\right)+{1\over 2}.$$ With $m=10^5$ this gives $66.81221$, which is very close to the exact result.

The average number of throws needed is approximately the logarithm base $6/5$ of $m$. Intuitively, this is very sensible since each throw eliminates about $5/6$ of the dice. By the way, this idea was already suggested by another user who then deleted it. He or she should get some credit for good intuition!

share|improve this answer
    
For m=100000 an exact calculation (based on an iterative solution) results in 66.81. Your solution $\sum _{n=1}^{100000} \frac{6}{n}$ results in 72.5409. Not bad. Thanks! –  wnvl Feb 3 '12 at 22:33
    
@wnvl That's a lot of dice :) –  Byron Schmuland Feb 3 '12 at 22:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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