2
$\begingroup$

Given a natural number $k$, roll a fair die until the sum of the outcome is more than $k$.

  1. What is the expected number of rolls?
  2. What is the expected number of rolls if we stop after $t$ times even if we did not reach the desired sum?

I've been asked to clarify that this is not homework. Ways I've tried to takle this: I've tried to use the law of total expectation to develop a recurrence formula but I did not reach far enough, and also if I had known that the sum is 𝑘 I could used some combinatorics for the number of rolls that sums to 𝑘.

$\endgroup$
5
  • 3
    $\begingroup$ Hi! To avoid down-votes and close-votes, please provide us some context for this question, such as: (a) Is this homework? (b) If so, what course are you taking? (c) What specific topic are you covering at the moment? (d) What do you know that you think might be connected? (e) If you're stuck, what are you stuck on? For example, do you know what to apply, but don't know how to apply it, or do you not know what to apply? Please put these facts in your original post, not as responses to this comment, as comments may be deleted without warning. $\endgroup$
    – Brian Tung
    Commented Oct 9, 2022 at 21:11
  • $\begingroup$ It is not homework, just an interest. Regarding the topic: I'm not sure, I've tried to use the law of total expectation to develop a recurrence formula but I did not reach far enough, and also if I had known that the sum is $k$ I could use some combinatorics for the number of rolls that sums to $k$. $\endgroup$ Commented Oct 9, 2022 at 21:51
  • 2
    $\begingroup$ @ProperIllumination: Good! Can you put that context into your original post? $\endgroup$
    – Brian Tung
    Commented Oct 10, 2022 at 0:13
  • $\begingroup$ @Masacroso I don't think that Wald's Theorem is relevant, it says that $\mathbb{E}\left(\sum_{i=1}^{N}X_i\right)=\mathbb{E}(N)\mathbb{E}(X_i)$, where $X_i$ are i.i.d. and $N$ is a random variable. I'm asking how to compute $\mathbb{E}(N)$ $\endgroup$ Commented Oct 11, 2022 at 11:16
  • $\begingroup$ The average value of a fair dice throw equals $\frac{7}{2}$, so I would think the expected number is somewhere around $\frac{2N}{7}$ (or is this too easy? :-) ) $\endgroup$
    – Dominique
    Commented May 29 at 14:21

3 Answers 3

2
$\begingroup$

Let $X_n$ be the $n^{th}$ roll, and let $S_n$ = $\sum_{j=1}^{n} X_j$ with $T_k = \inf\{j \geq 1 : S_j \geq k\}$.

Also, define $h_k = \mathbb{E}(T_k)$. Then by conditioning on the first roll, we have the simple recurrence:

$$h_1=1, h_k = 1 + \frac{1}{6}\sum_{i = 1 }^ {k-1} h_i \ \text{when}\ 1 < k \leq 6 \\ h_k = 1 + \frac{1}{6}\sum_{i = k - 6 }^ {k-1} h_i \ \text{when}\ k \geq 7 $$

which of course determines $h_k$ completely $\forall k \geq 1$.

The first equation determines $h_{i}$ for $ 1 \leq i \leq 6$, and from there $h_k$ is determined entirely by :$$h_{k+6} = 1 + \frac{1}{6}\sum_{i = k }^ {k+5} h_i \ \text{when}\ k \geq 1 $$

A particular solution is given by $h_n = 2n/7 = n/\mathbb{E}(X_1)$.

The characteristic polynomial is given by $c(t) = 6t^6 - 1 -t -t^2 -t^3 - t^4 - t^ 5$, and has six distinct roots approximately given by the set $\{1,-0.670332,-0.375695 \pm 0.570175 i, 0.294195 \pm 0.668367 i\}$

Hence, the recurrence has general solution : $h_n = 2n/7 + a_1 + a_2(-0.670332)^{n}+a_3(-0.375695)^{n}\cos(0.375695 n) + a_4(-0.375695)^{n+1}\sin(0.375695 n) + a_5 (0.294195)^{n}\cos(0.294195n) + a_6(0.294195)^{n}\sin(0.294195n) $

,where the coefficients are determined by the known values $h_1,h_2, h_3, h_4, h_5$ and $h_6$.

Note that for large $n$ this is linear, and it agrees with Masacroso's answer.

$\endgroup$
2
$\begingroup$

Sketch for a solution for the first question: let $\tau :=\min\{n\in \mathbb{N}: S_n\geqslant k+1\}$ for $S_n:=\sum_{k=1}^n X_k$, then

$$ \operatorname{E}[\tau ]=\sum_{m\geqslant 1}\Pr [\tau \geqslant m]=\sum_{m\geqslant 1}\Pr [S_{m-1}\leqslant k]\tag1 $$

and note that the sum on the right is finite as $\Pr [S_n\leqslant k]=0$ when $n>k$. By last you can use this answer to compute every probability of this sum.

An approximated solution could be found using Wald's theorem and the approximation

$$ \operatorname{E}[S_{\tau }]\approx \frac1{6}\sum_{j=1}^6 (k+j)=k+\operatorname{E}[X_1]\tag2 $$

what is fine for enough large $k$, then you will get

$$ \operatorname{E}[\tau ]\approx \frac{k+\operatorname{E}[X_1]}{\operatorname{E}[X_1]}\tag3 $$


The justification for this approximation is the following: note that $S_{\tau }\in [k+1,k+6]$, then I guess that for large $k$ we will have $S_\tau$ uniformly distributed in this set, from where (2) follows. Anyway, if we want to be more precise, we can say that

$$ \frac{k+1}{\operatorname{E}[X_1]}\leqslant \operatorname{E}[\tau ]\leqslant \frac{k+6}{\operatorname{E}[X_1]}\tag4 $$

$\endgroup$
3
  • $\begingroup$ $E[X_1]=3.5$, so I don't get why you left it as $E[X_1]$ $\endgroup$ Commented Oct 17, 2022 at 20:17
  • $\begingroup$ I don't get the first line of the approximation. Here is what I have I don't get the first line of the approximation. Here is what I have $$ \mathbf{E}[S_\tau]=\mathbf{E}\left[\sum_{k=1}^{\tau}X_k\right]=\mathbf{E}[\tau]\mathbf{E}[X_1]=6\sum_{m\geqslant 1}\Pr [S_{m-1}<k]= 6 \sum_{m\ge1}^{ }\sum_{\ell=1}^{k-1}\Pr[\ell,m-1,6), $$where Pr[𝑆,𝑛,𝐷] is from the source you cited, and the second equality follows from Wald's Theorem. $\endgroup$ Commented Oct 17, 2022 at 20:20
  • $\begingroup$ @ProperIllumination I added an explanation for this approximation $\endgroup$
    – Masacroso
    Commented May 29 at 23:32
1
$\begingroup$

There are exact solutions provided already, however, I will present a way to estimate the answer to the first question.

Note that the question asks about the number of rolls until the cumulative sum is "more than k" which means we stop if and only if we exceed k (we will still roll if our cumulative sum so far is exactly k).

We can see that if we are at the cumulative sum = k, the possible outcomes on the one final die roll are $1, 2, 3, 4, 5$ or $6$ which will increase our cumulative sum to $k+1, k+2, k+3, k+4, k+5$ or $k+6$. Call these as our prospective stopping points. Note that $k+6$ is also a stopping point since if we are at the sum = $k$ and get $6$ on our final die roll our sum gets to $k+6$ and then we stop rolling. The question says "....more than $k$, " meaning our first stopping point is $k+1$ instead of $k$. If we were stopping at sum = $k$ then the maximum stopping point would have been $(k - 1) + 6 = k + 5$

We know those stopping points have the respective probabilities of $6/21, 5/21, 4/21, 3/21, 2/21$ and $1/21$ (source: https://math.stackexchange.com/a/12553/1204464).

Therefore, our expected stopping point (or the cumulative sum at which we are expected to stop) is given by:

$$(k+1)*\frac{6}{21} + (k+2)*\frac{5}{21} + (k+3)*\frac{4}{21} + (k+4)*\frac{3}{21} + (k+5)*\frac{2}{21} + (k+6)*\frac{1}{21}$$

which comes from the definition of expected value.

Using the renewal theory result from the cited link above, we divide the above expectation by the expected value of a single die roll ($7/2$) to get the expected number of rolls needed:

$$\frac{2k}{7} + \frac{16}{21}$$ which can be re written as $$\frac{2(k+1)}{7} + \frac{10}{21}$$.

Thus, the expected number of rolls for the cumulative sum to get to at least N can be approximated by $$\frac{2N}{7} + \frac{10}{21}$$ for large values of N since the derivation in the above-cited link takes that as an assumption.

The exact solution can be found in the pdf "A Collection of Dice Problems with solutions and useful appendices by Matthew M. Conroy" accessible from the link https://www.madandmoonly.com/doctormatt/mathematics/dice1.pdf [problem number 35].

The author there shows how close this estimate is to the actual value.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .