Expected length of a sequence

1k Views Asked by At

The following problem has kept me pondering for a while now and since I can't get through, I'm posting it here.

Say that you can draw a number $x_i$ uniformly from the set $\mathcal{X} \sim \{0,0,1,2,3,4,5,6\}$. The sum of those numbers we call $X$. We stop drawing numbers when $X$ is at least $5$, the amount of numbers drawn we will call $N$. I would write the stopping condition as:

$$X = \sum_{i=0}^{N}x_i \geq 5 $$

What is the expected value of numbers we need to draw, $E[N]$?

I'll attempt some visualisations based on empirical outcomes.

2

There are 2 best solutions below

1
On

It is possible to solve a more general problem. We are looking for $$N(t)=\min \left\{ n : \sum_{i=1}^n x_i >t\right\}.$$ Now set $$m(t)=\mathbb{E}[N(t)]$$ We can condition on $x_1$ to obtain $$m(t)=\cases{ 1 & if $\quad x_1\ge t$\cr m(t-x_1) & if $\quad x_1<t$\cr}$$ We know also that $$\begin{align}m(t)=\mathbb{E}[\mathbb{E}[N(t)|x_1]]&=\sum_{i=0}^{t-1} m(t-i)\mathbb{P}(x_1=i)+\sum_{i=t}^6\mathbb{P}(x_1=i)\\ &=p\sum_{j=1}^{t} m(j)+(6-t)p\end{align}$$ Where, for brevity and because $x_i$ is uniform, we have written $p$ for $\mathbb{P}(x_1=i)$ Assume we know the expressions for all $m(j)$ with $j=1,...,k$, then $$\begin{align}m(k+1)&=p\sum_{j=1}^{k+1} m(j)+(6-k-1)p\\ &= pm(k+1)+p\sum_{j=1}^{k} m(j)+(6-k-1)p \\ &\Rightarrow m(k+1)=\frac{p}{1-p}\sum_{j=1}^{k} m(j)+(6-k-1)\frac{p}{1-p}\end{align}$$ We can calculate $m(1)$ from the recursion, namely $$m(1)=p m(1)+5p\Rightarrow m(1)=\frac{5p}{1-p}$$ Now $$m(2)=\frac{p}{1-p}\frac{5p}{1-p}+(6-1-1)\frac{p}{1-p}=5\left(\frac{p}{1-p}\right)^2+4\frac{p}{1-p}$$ $$m(3)=5\left(\frac{p}{1-p}\right)^3+9\left(\frac{p}{1-p}\right)^2+3\frac{p}{1-p}$$ $$m(4)=5\left(\frac{p}{1-p}\right)^4+14\left(\frac{p}{1-p}\right)^3+12\left(\frac{p}{1-p}\right)^2+2\left(\frac{p}{1-p}\right)$$ And finally $$m(5)=5\left(\frac{p}{1-p}\right)^5+19\left(\frac{p}{1-p}\right)^4+26\left(\frac{p}{1-p}\right)^3+14\left(\frac{p}{1-p}\right)^2+\frac{p}{1-p}$$

0
On

Define the function $h(x)=\mathbb{E}_x(N)$ to be the expected number of steps needed, if we start with a sum of $x$. First step analysis gives

\begin{eqnarray*} h(4)&=&1+h(4)/4 \\ h(3)&=&1+h(3)/4+h(4)/8\\ h(2)&=&1+h(2)/4+h(3)/8+h(4)/8\\ h(1)&=&1+h(1)/4+h(2)/8+h(3)/8+h(4)/8\\ h(0)&=&1+h(0)/4+h(1)/8+h(2)/8+h(3)/8+h(4)/8. \end{eqnarray*}

Solving this system we get $E(N)=h(0)={2401\over 972}\approx 2.47.$