I have the following problem in my probability course. I am asked to compute the expected value of a random variable $X$ defined as follows:
Let $n \in \mathbb{N}$. In the first step a number $Y_1$ is randomly (uniformly distributed) chosen among $\{0, \ldots, n\}$. In the second step a number $Y_2$ is randomly chosen among $\{0, \ldots, Y_1\}$. This procedure is continued until the $0$ is drawn. Let $X$ be the number of steps necessary for this.
The solution to this exercise is given as:
Let $X_n$ be the number of steps necessary, when $\{0, \ldots, n\}$ is the first set. Let $n \geq 2$. If the first draw is $k \neq 0$, then the number of remaining steps has the same distribution as $X_k$ and thus
$$ \text{E}(X_n) = 1 + \sum_{k = 1}^n \text{E}(X_k) \cdot \mathbb{P}(Y_1 = k) ~~.$$
After that, some more derivation follows until an explicit formula for $X_n$ is derived. However, the stuff after the formular is clear.
My question is: How is this formula derived?
The formula would be true if
$$ X_n = 1 + \sum_{k = 1}^n X_k \mathbb{P}(Y_1 = k)$$
And, in fact, this was one explanation that was given on the blackboard, when this problem came up in a discussion.
However, since $\mathbb{P}(Y_1 = k) = \frac{1}{n+1}$, the right hand side may not even be an integer, while the left hand side is.
$X_n$, from the word problem, is presumably defined on $\Omega := \{0, \ldots, n\}^{\mathbb{N}}$ - I would not know what else would be a suitable space. But then for some $\omega \in \Omega$ we had
$$ X_n(\omega) = 1 + \sum_{k = 1}^n X_k(\omega) \mathbb{P}(Y_1 = k) ~~.$$
How would $X_k(\omega)$ even be defined for some $k < n$?