2
$\begingroup$

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?

1 Answers 1

5

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!

  • 0
    @wnvl That's a lot of dice :)2012-02-03