Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

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

share|improve this answer
    
“$f$ linear in $x$ and $y$” is a useful sufficient condition, thanks. Is it also necessary? –  Sebastian Nov 11 '11 at 16:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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