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

Question

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

Answer 1

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}<k] $$

and note that the sum on the right is finite as $\Pr [S_n<k]=0$ 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]} $$

Answer 2

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.