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?


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\;.$$


1 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*}

  • $\begingroup$ “$f$ linear in $x$ and $y$” is a useful sufficient condition, thanks. Is it also necessary? $\endgroup$
    – Sebastian
    Nov 11, 2011 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.