What is the expectation value of this random variable?

Question

Let s be a positive integer. Do the following:

• Step 1: choose a random natural number $s_1 \in \{0, \ldots,s\}$ (uniformly distributed)
• If $s_1 = 0$, stop.
• Otherwise, step 2: choose a random number $s_2 \in \{0, \ldots, s_1\}$
• Continue until you get 0.
• Let $Y$ be the number of steps you have to make until you choose 0.

What is the expectation of $Y$?

My idea: Well, let $Y_{k}$ be the number you chose in step $k$. It is $ E[Y] = \sum_{k=1}^{\infty} k \cdot P(Y=k)$ and we get

• $P(Y=1) = \frac{1}{s+1}$
• $P(Y=2) = P(Y_{2} = 0 \mid Y_{1}>0)$ etc., but I‘m stuck here. This is actually a sum over all possible values of $Y_{1}$, but it seems to complicated.

Answer 1

I do not know how to solve this completely, but I think that the following is a step in the right direction: Let $E_s$ denote the expected number of steps when we start with $s$. Then $E_0 = 0$ (trivial) and $E_1 = 2$ (geometric distribution with parameter $1/2$). Furthermore, $E_s = 1 + \frac{1}{1+s} \cdot \sum_{i=0}^s E_i$. This is because you need one iteration, and after that your next number is one between $0$ and $s$, each with a probability of $\frac 1{1+s}$.

To give a rough estimate for $E_s$: With a probability of $1/2$, the value is halved in an iteration, which yields $E_s = O(\log s)$.

If you define $T_s = \sum_{i=0}^s E_i$, then we get the recursion $T_s = \frac{i+1}i \cdot (1 + T_{s-1})$, which might be easier solvable.

Answer 2

This is going to be long and use a ton of ideas from probabilities. It may not be the most effective way to solve it, but it should work ! If there are concepts or results here that you are not familiar with, feel free to ask and I will edit this post.

What you have here is a typical situation of a Markov Chain. Let $X_k$ be the number you have after $k$ steps of your processus (if you reach $0$ before, then $X_k$ stays equal to $0$). To determine $X_{k+1}$, you only have to know the value of $X_k$. More specifically, for $i,j\in \{ 0,\cdots,s\}$, we have $$P(X_{k+1} = i | X_k = j ) = \left\{ \begin{array}{ccc}\frac{1}{j+1} &\text{if } i \leq j \\ 0 &\text{if } i>j\end{array}\right.$$ Thus we get the transition matrix $$A = \begin{pmatrix}1&\frac{1}{2}&\frac{1}{3}&\cdots &\frac{1}{s+1} \\ 0&\frac{1}{2}&\frac{1}{3}&\cdots &\frac{1}{s+1} \\ 0&0&\frac{1}{3}&\cdots &\frac{1}{s+1} \\ \vdots&\vdots&\ddots&\cdots &\vdots \\ 0&0&0&\cdots &\frac{1}{s+1} \\\end{pmatrix}.$$

Using the law of total probability and noting $U_k = \begin{pmatrix}P(X_k=0) \\P(X_k=1) \\\vdots\\ P(X_k=s) \end{pmatrix}$, we get $$U_{k+1} = A \times U_k$$ and therefore $$U_k = A^k U_0 = A^k \times \begin{pmatrix}0 \\0 \\\vdots\\ 0 \\1 \end{pmatrix}.$$

$\rhd$ Now, note that $E[Y] = \sum\limits_{k=1}^{+\infty} P(Y \geq k)$. This comes from the fact that $$\begin{array}{lll} \sum\limits_{k=1}^{+\infty} P(Y \geq k)&=& \sum\limits_{k=1}^{+\infty} \sum\limits_{i = k}^{+\infty} P(Y=i) \\ &=&\sum\limits_{i = 1}^{+\infty} \sum\limits_{k=1}^{i} P(Y=i) \\ &=&\sum\limits_{i = 1}^{+\infty} i P(Y=i) \\ &=&E[Y] \end{array}$$ As $(Y \geq k)$ is the event $(X_{k-1} >0)$, we get $$\begin{array}{lll} E[Y] &=& \sum\limits_{k=1}^{+\infty} P(X_{k-1}>0) \\ &=& \sum\limits_{k=0}^{+\infty} P(X_{k}>0) \\ &=& \sum\limits_{k=0}^{+\infty} \sum\limits_{j=1}^s P(X_{k}=j)\\ &=& \sum\limits_{j=1}^s \sum\limits_{k=0}^{+\infty} P(X_k=j)\end{array}$$ Noting $(e_0,e_1,\cdots,e_s)$ the canonical basis of $\mathbb{R}^{s+1}$ and $\langle.,.\rangle$ the canonical innet product, we have $$P(X_k=j) = \langle e_j , U_k \rangle = \langle e_j , A^k e_s \rangle$$ therefore

$$E[Y] = \sum\limits_{j=1}^s \sum\limits_{k=0}^{+\infty} \langle e_j , A^k e_s \rangle.$$ $\rhd$ Now, ideally, we would like to write $$E[Y] = \sum\limits_{j=1}^s \langle e_j , \sum\limits_{k=0}^{+\infty} A^k e_s \rangle = \sum\limits_{j=1}^s \langle e_j , (I_{s+1}-A)^{-1} e_s \rangle.$$ However, this can't be done as $I_{s+1}-A$ is not invertible because of the first coefficient of $A$. But in our sum, the first vector $e_0$ does not come up. Thus we limit ourselves to what happens on the coordinates $1,2,...,s$. Write $$A = \begin{pmatrix} 1 & *&\cdots&* \\ 0&&& \\ \vdots &&N& \\ 0&&&\end{pmatrix}$$ Then $A^k =\begin{pmatrix} 1 & *&\cdots&* \\ 0&&& \\ \vdots &&N^k& \\ 0&&&\end{pmatrix}$ and, for $j \geq 1$, $\langle e_j , A^k e_s \rangle = \langle e'_{j} , N^k e_{s}' \rangle$ where $(e_1',\dots,e_s')$ is the canonical basis of $\mathbb{R}^s$.

Now we get $$E[Y] = \sum\limits_{j=1}^s \sum\limits_{k=0}^{+\infty} \langle e'_j , N^k e_s' \rangle=\sum\limits_{j=1}^s \langle e_j' , \sum\limits_{k=0}^{+\infty} N^k e_s' \rangle = \sum\limits_{j=1}^s \langle e_j , (I_{s}-N)^{-1} e_s \rangle.$$

Now, as $I_{s}-N$ is triangular, we can compute somewhat directly the matrix $(I_{s}-N)^{-1}$, and if I didn't make any mistake it is $$(I_{s}-N)^{-1} = \begin{pmatrix} 2 &1&1&\cdots&1&1 \\ 0&\frac{2}{3} &\frac{1}{2}&\cdots&\frac{1}{2}&\frac{1}{2} \\ 0&0&0&\frac{s-1}{s-2} & \frac{1}{s-2}& \frac{1}{s-2}\\ 0&0&0&0&\frac{s}{s-1} & \frac{1}{s-1}\\ 0&0&0&\cdots&0&\frac{s+1}{s} \\ \end{pmatrix}$$ Given our formula for $E[Y]$, $E[Y]$ is the sum of all of the last column of this, hence :

$$E[Y] = \sum\limits_{i=1}^{s-1} \frac{1}{i} \quad + \dfrac{s+1}{s} = 1+\sum\limits_{i=1}^{s} \frac{1}{i}.$$