# Expected number of dice rolls until the sum of the outcomes is more than $k$

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 𝑘.

• 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. Oct 9, 2022 at 21:11
• 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$. Oct 9, 2022 at 21:51
• @ProperIllumination: Good! Can you put that context into your original post? Oct 10, 2022 at 0:13
• @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)$ Oct 11, 2022 at 11:16

Sketch for a solution for the first question: let $$\tau :=\min\{n\in \mathbb{N}: S_n\geqslant k\}$$ 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}

and note that the sum on the right is finite as $$\Pr [S_n when $$n\geqslant 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=0}^5 (k+j)=k-1+\operatorname{E}[X_1]$$

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

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

• $E[X_1]=3.5$, so I don't get why you left it as $E[X_1]$ Oct 17, 2022 at 20:17
• 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. Oct 17, 2022 at 20:20
• @ProperIllumination observe that $S_{\tau }\in\{k,k+1,\ldots ,k+5\}$, therefore $\operatorname{E}[S_{\tau }]\in[k,k+5]$ and I'm guessing that for large $k$ we have that $\Pr [S_{\tau }=k+j]$ is almost the same for all $j\in\{0,\ldots ,5\}$. In any case you have the bound $\operatorname{E}[\tau ]\in [k/\operatorname{E}[X_1], (k+5)/\operatorname{E}[X_1]]$ Oct 17, 2022 at 22:42

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.