What is the expectation value of this random variable? 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.

 A: 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}.$$
A: 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.
