1
$\begingroup$

An $n$-sided dice is rolled until the cumulative sum of the top faces becomes $\ge n$. If $n$ is sufficiently large, what is the expected no. of rolls required? It appears that expected no. of rolls approach $e$. I don't know how to prove it.

This problem is a variation of this problem.

http://www.cseblog.com/2014/12/expected-number-of-attempts-broken.html

The solution is mentioned in the comment section. It is indeed $e$.

$\endgroup$
  • 1
    $\begingroup$ I had taken a different approach assuming things. I modified the answer, but it isn't 100% formal. Let's hope someone else can take it from there. $\endgroup$ – Cehhiro Oct 21 '16 at 10:13
2
$\begingroup$

For $n=1,2,\dots$ and $k\in\{1,\dots,n\}$ let $\mu_{n,k}$ denote the expected number of rolls needed to get a sum $\geq k$.

You are after expressions for $\mu_{n,n}$ and $\lim_{n\to\infty}\mu_{n,n}$, and we have:$$\mu_{n,k}=1+\frac{1}{n}\sum_{i=1}^{k-1}\mu_{n,i}$$


This equation appears if you work out the following:

If $X_{n,k}$ denotes the number of rolls needed to get a sum $\geq k$ and $D$ denotes the outcome of the first toss then:

$$\mu_{n,k}=\mathbb{E}X_{n,k}=\sum_{i=1}^{n}\mathbb{E}\left(X_{n,k}\mid D=i\right)\Pr\left(D=i\right)$$

Note here that $\mathbb{E}\left(X_{n,k}\mid D=i\right)=1+\mu_{n,k-i}$ if $i<k$ and $\mathbb{E}\left(X_{n,k}\mid D=i\right)=1$ otherwise.


This leads to:$$\mu_{n,k+1}=1+\frac{1}{n}\sum_{i=1}^{k}\mu_{n,i}=1+\frac{1}{n}\left(\mu_{n,k}+n\left(\mu_{n,k}-1\right)\right)=\left(1+\frac{1}{n}\right)\mu_{n,k}$$

And finally to:$$\mu_{n,n}=\left(1+\frac{1}{n}\right)^{n-1}$$

Then evidently: $$\lim_{n\to\infty}\mu_{n,n}=e$$

$\endgroup$
  • $\begingroup$ That's a pretty clever way to find the result recursively. I tried to think of something this cool, but I'm guess I'm stuck with sums. $\endgroup$ – Cehhiro Oct 22 '16 at 1:49
  • $\begingroup$ @O.VonSeckendorff Golden rule in probability (you might know it allready): if you are looking for expectations then first try to find them without paying much attention to the underlying distribution. Quite often that saves you a lot of "trouble". $\endgroup$ – drhab Oct 22 '16 at 7:08
0
$\begingroup$

The way the cumulative sum behaves is like a random walk with steps of size $D$. (This is simplified. You might need to use Wald's Identity.) More easily, maybe, it's to say that we want to find the minimum number of throws before the expected sum is $N$.

$\mathbb{P}\left(\sum_{i=0}^{k}D_i < N \right)$ is the probability we're looking for.

Now we do

$$ \mathbb{P}\left(\sum_{i=0}^{k}D_i < \lim_{N \to \infty} N\right) = \mathbb{P}\left(\sum_{i=0}^{k} \frac{D_i}{\lim_{N \to \infty} N} < 1 \right) $$

If $D_i$ is a uniform distribution over $N$ values, we have

$$ \mathbb{P}\left(\sum_{i=1}^{k} \frac{D_i}{\lim_{N \to \infty} N} < 1 \right) $$

We need to show that $\frac{D_i}{\lim_{N \to \infty}} \sim \text{U}(0,1)$. That way the problem is easier to deal with.

$$ \mathbb{P}\left(D_i \leq a\right) = \frac{a}{N},\ a \in \{1,…,N\} $$

Dividing by $N$ in the probability we get

$$ \mathbb{P}\left(\frac{D_i}{N} \leq \frac{a}{N}\right) = \frac{a}{N},\ a \in \{1,…,N\} $$

Taking limits, $\lim_{N \to \infty} \frac{a}{N} = b,\ b \in (0,1]$. $\frac{D_i}{N}$ should be worked in a similar fashion. Maybe by showing the cumulative up to $a$ tends to $a$. Let $I_i = \lim_{N \to \infty} \frac{D_i}{N}$. Then

$$ \mathbb{P}\left(\sum_{i=1}^{k} I_i < 1 \right) = \frac{1}{k!} $$

Since the sum is a simple case of the Irwin-Hall distribution. If we define $S_J=\sum_{j=0}^{J}I_j$, we calculate the expected value as $\mathbb{E}[J] = \sum_{j=1}^\infty \mathbb{P}(J = j) \cdot j = \sum_{j=1}^\infty \frac{1}{\left(j-1\right)!}$ = e.

Once again, if there are flaws in the argument, I'd very much appreciate it if someone made note of them. This time I was more rigorous.

$\endgroup$
  • $\begingroup$ The answer is $e$ as the description states. You can verify this with a simple simulation. The mistake happens when you use the expected value of the dice as a representative value to count throws. $\endgroup$ – Thanassis Oct 21 '16 at 8:39
  • $\begingroup$ @Thanassis Thanks for noting. $\endgroup$ – Cehhiro Oct 21 '16 at 8:39
  • $\begingroup$ @Thanassis I pretty much redid the whole thing. There's a step between going from a countable set to an uncountable set which I don't know how to justify but seems to be intuitive. $\endgroup$ – Cehhiro Oct 21 '16 at 10:12

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.