Choose a random number between $0$ and $1$ and record its value. Do this again and add the second number to the first number. Keep doing this until the sum of the numbers exceeds $1$. What's the expected value of the number of random numbers needed to accomplish this?
[Math] Choose a random number between $0$ and $1$ and record its value. Keep doing it until the sum of the numbers exceeds $1$. How many tries do we need
expectationprobabilityprobability theory
Related Solutions
Let $u(n)$ be the expected value of the first roll that makes the total $\ge n$.
Thus $u(n) = 7/2$ for $n \le 1$. But for $2 \le n \le 6$, conditioning on the first roll
we have $$u(n) = \left( \sum_{j=1}^{n-1} u(n-j)
+ \sum_{j=n}^{6} j \right)/6$$
That makes
$$ u_{{2}}={\frac {47}{12}},u_{{3}}={\frac {305}{72}},u_{{4}}={\frac {1919}{432}},u_{{5}}={\frac {11705}{2592}},u_{{6}}={\frac {68975}{15552
}}$$
And then for $n > 6$, again conditioning on the first roll,
$$u(n) = \frac{1}{6} \sum_{j=1}^6 u(n-j)$$
The result is
$$u(51) = \frac {7005104219281602775658473799867927981609}{1616562554929528121286279200913072586752} \approx 4.333333219$$
It turns out that as $n \to \infty$, $u(n) \to 13/3$.
EDIT: Note that the general solution to the recurrence $\displaystyle u(n) = \frac{1}{6} \sum_{j=1}^6 u(n-j)$ is $$ u(n) = c_0 + \sum_{j=1}^5 c_j r_j^n$$ where $r_j$ are the roots of $$\dfrac{6 r^6 - (1 + r + \ldots + r^5)}{r - 1} = 6 r^5 + 5 r^4 + 4 r^3 + 3 r^2 + 2 r + 1 = 0$$ Those all have absolute value $< 1$, so $\lim_{n \to \infty} u(n) = c_0$. Now $6 u(n+5) + 5 u(n+4) + \ldots + u(n) = (6 + 5 + \ldots + 1) c_0 = 21 c_0$ because the terms in each $r_j$ vanish. Taking $n = 1$ with the values of $u_1$ to $u_6$ above gives us $c_0 = 13/3$.
At each step, four cards are removed from the deck, so a deck is exhausted in $13$ steps. Let's call that a 'round'.
The game you propose can be restated as follows. At each round, we draw $13$ ordered cards from the deck, and add up the values of the cards that came before the first ace in our $13$ drawn cards. If no ace is drawn, we add up the values of all $13$ drawn cards, shuffle them into the remaining $39$ cards (the ones which were not drawn), and repeat the process.
There are $\binom{48}{13}$ sets of $13$ cards which do not contain an Ace, and so there are $\binom{52}{13}-\binom{48}{13}$ sets of $13$ cards which contain at least one Ace. Hence, the probability that the game ends in a given round is
$$p=1-\frac{\binom{48}{13}}{\binom{52}{13}}=\frac{14498}{20825}\simeq69.62\%$$
Now, if the game has not ended in a given round, then the expected sum of the cards drawn is $13$ times the expected value of a card drawn (by linearity of the expectation). Since no card drawn was an ace, the expected value of a card drawn is
$$\frac{2+3+4+5+6+7+8+9+10+11+12+13}{12}=\frac{15}2,$$
and hence the expected sum is $l=13\cdot\frac{15}2=\frac{195}2=97.5$.
Now, we need to calculate the expected sum of the cards drawn before the first Ace in a round where the game ends. Here, we will break the thing into cases.
$\qquad$Number of Aces in cards drawn: $1$
There are $\binom{48}{12}\cdot\binom{4}{1}$ sets of $13$ cards which contain exactly one Ace. Therefore, given that the $13$ cards drawn contain at least one ace, the probability that we fall in this case (exactly one Ace drawn) is
$$a_1=\frac{\binom{48}{12}\cdot\binom{4}{1}}{\binom{52}{13}-\binom{48}{13}}=\frac{9139}{14498}\simeq 63.04\%$$
The expected position of the lone ace is $\frac{1+2+3+4+5+6+7+8+9+10+11+12+13}{13}=7$, so on average $6$ non-Ace cards will be drawn before it. The expected sum for this case is hence $s_1=6\cdot\frac{15}2+1=46$.
$\qquad$Number of Aces in cards drawn: $2$
There are $\binom{48}{11}\cdot\binom{4}{2}$ sets of $13$ cards which contain exactly two Aces. Like before, the probability that we fall in this case is
$$a_2=\frac{\binom{48}{11}\cdot\binom{4}{2}}{\binom{52}{13}-\binom{48}{13}}=\frac{2223}{7249}\simeq 30.67\%$$
Now, things get trickier. The position of the pairs of aces is a subset of size $2$ on $S=\{1,2,\dots,13\}$, and we are interested in the minimimum of this subset. Let $X$ denote this random variable.
There are $\binom{13}2$ $2$-subsets of $S$, and only $12$ of them contain the number $1$, which is a guaranteed minimum. Therefore
$$\mathbb{P}(X=1)=\frac{12}{\binom{13}2}$$
Similarly, there are $11$ $2$-subsets of $S$ whose minimum is $2$.
More generally, for each $k\in\{1,2,\dots,12\}$, $\binom{13-k}1$ of the $2$-subsets of $S$ have minimum $k$, and we find that
$$\mathbb{P}(X=k)=\frac{\binom{13-k}1}{\binom{13}2}.$$
As a sanity check, notice that they add up to $1$. The expected sum for this case is hence:
$$s_2=\sum_{k=1}^{12}\left(\frac{15}2\cdot (k-1)+1\right) \cdot \mathbb{P}(X=k)=\frac{57}2$$
$\qquad$Number of Aces in cards drawn: $3$
Now we've got most of the work done. We have that
$$a_3=\frac{\binom{48}{10}\cdot\binom{4}{3}}{\binom{52}{13}-\binom{48}{13}}=\frac{39}{659}\simeq 5.92\%$$
For this case, let $Y$ be the random variable which denotes the minimum of a uniformly sampled $3$-subset of $S$. Notice that there are $\binom{13}{3}$ $3$-subsets of $S$.
We will have that for each $k\in\{1,2,\dots,11\}$, $\binom{13-k}2$ of the $3$-subsets of $S$ have minimum $k$. Hence:
$$\mathbb{P}(Y=k)=\frac{\binom{13-k}2}{\binom{13}3}$$
Finally, the expected sum for this case is
$$s_3=\sum_{k=1}^{11}\left(\frac{15}2\cdot (k-1)+1\right) \cdot \mathbb{P}(Y=k)=\frac{79}4$$
$\qquad$Number of Aces in cards drawn: $4$
For this final case we have
$$a_4=\frac{\binom{48}{9}\cdot\binom{4}{4}}{\binom{52}{13}-\binom{48}{13}}=\frac{5}{1318}\simeq 0.38\%$$
and expected sum
$$s_4=\sum_{k=1}^{10}\left(\frac{15}2\cdot (k-1)+1\right) \cdot \frac{\binom{13-k}3}{\binom{13}4}=\frac{29}2$$
Let's put it all together. Supposing the game ends on a given round, the expected sum for that round will be $($and you can check that the $a_i$ add up to $1)$
$$w=\sum_{i=1}^4a_is_i=\frac{282424}{7249}\simeq38.96$$
Finally, the expected sum for the game will be given by
$$\sum_{n=1}^\infty\, \underbrace{\mathbb{P}(\text{Game ends on round $n$})}_{(1-p)^{n-1}\cdot p} \cdot \underbrace{\mathbb{E}(\text{Value of sum of cards of a game ending on round $n$})}_{(n-1)\,l+w}\\ =\sum_{n=1}^\infty\,(1-p)^{n-1}\cdot p \cdot \Big((n-1)\,l+w\Big)=(w-l)+\frac{l}p $$
This last step is standard manipulation of series and term-by-term differentiation, but I can further explain if it's not clear. Therefore, the final answer is
$$\frac{2363461}{28996} \simeq 81.51$$
Best Answer
Here is a (perhaps) more elementary method. Let $X$ be the amount of numbers you need to add until the sum exceeds $1$. Then (by linearity of expectation):
$$ \mathbb{E}[X] = 1 + \sum_{k \geq 1} \Pr[X > k] $$
Now $X > k$ if the sum of the first $k$ numbers $x_1,\ldots,x_k$ is smaller than $1$. This is exactly equal to the volume of the $k$-dimensional set:
$$ \left\{(x_1,\ldots,x_k) : \sum_{i=1}^k x_i \leq 1, \, x_1,\ldots,x_k \geq 0\right\}$$
This is known as the $k$-dimensional simplex. When $k = 1$, we get a line segment of length $1$. When $k = 2$, we get a right isosceles triangle with sides of length $1$, so the area is $1/2$. When $k=3$, we get a triangular pyramid (tetrahedron) with unit sides, so the volume is $1/6$. In general, the volume is $1/k!$, and so
$$ \mathbb{E}[X] = 1 + \sum_{k \geq 1} \frac{1}{k!} = e. $$