Nested Expected Values

Question

Assume we have random variables $X_1,\dots,X_N$ i.i.d. $\mathcal{U}\,(0,1)$ distributed and now define $Y_i$ as $$Y_i = f(Y_{i-1},X_i)\qquad \text{and}\qquad Y_0 \text{ arbitrary constant}$$ for some function $f:\mathbb R^2 \to \mathbb R$, i.e. we have a stochastic process where the next step depends on the last and some independent new part ($X_i$).

Now I am interested in $\mathbb E \, Y_N$ and suppose I follow an appealingly simple approach: Compute inductively $$ y_0=Y_0\quad,\quad y_i = f(y_{i-1},\mathbb E X_i) = f(y_{i-1},0.5)$$

Under what assumptions does $\mathbb E\,Y_N = y_N$ hold?

Motivation:

The above problem is an abstraction of the analysis of a random search optimization algorithm. Assume a bijective function $g:S\to\{1,\dots,|S|\}$, which we'd like to maximize and a current iterate $x_i$. One step of the algorithm consists of choosing a random point $x_{i+1}\in S$ and accepting it if $g(x_{i+1}) > g(x_i)$.

We are interested in the expected function value $g(x_N)$ reached after $N$ improving steps when starting in the worst point (for simplicity, we do not count points with lower function value). For $N \ll |S|$, this leads to the above abstract problem with $$f(y,x) = (|S|-y)x+y\;.$$

Answer 1

You are very fortunate in your choice of $f(y,x)$. Normally, substituting the mean values into the function will not work, but in your case $f$ is linear in $y$ with $x$ held fixed and vice versa. In this case, your procedure gives you the correct value of $\mathbb{E}(Y_i)$.

By linearity of expectation and independence of $X_i$ and $Y_{i-1}$ we get \begin{eqnarray*}\mathbb{E}(Y_i)&=&\mathbb{E}[(|S|-Y_{i-1})X_i+Y_{i-1}]\cr &=&\mathbb{E}[(|S|-Y_{i-1})X_i]+\mathbb{E}[Y_{i-1}]\cr &=&\mathbb{E}[(|S|-Y_{i-1})]\mathbb{E}[X_i]+\mathbb{E}[Y_{i-1}]\cr &=&(|S|-y_{i-1})\ {0.5}+y_{i-1}\cr &=& f(y_{i-1},0.5). \end{eqnarray*}