Finding probability of random variable less than mean

Question

Very stuck on this problem and I could use a hint.

Consider a vector of independent random variables $X = (X_1, . . . , X_n)$, where $X_i = ±1$ with probability $\frac{1}{2}$, and a function $f (X)$ with $µ = E[f (X)]$. Even though there is some vector value $x$ with $f (x) \leq µ$, sometimes it is not easy to find such x. The following fact may help. Suppose that there is an efficient algorithm that for all possible $j \leq n$ and for all possible values of $x_1, . . . , x_j = ±1$, computes the conditional expected value $g_j(x_1, . . . , x_j) = E[ f (X) | X_1 = x_1, . . . , X_j = x_j ]$.

For example, it computes $g_3(1, −1, −1) = E[ f (X) | X_1 = 1, X_2 = −1, X_3 = −1].$ Show that then there is also a polynomial algorithm that computes $x$ such that $f (x) \leq \mu$.

Answer 1

The greedy algorithm will do:

1. First, compute $g_1(1)$ and $g_1(-1)$ and let $x_1$ be whichever of these gives the smaller value.
2. Second, compute $g_2(x_1, 1)$ and $g_2(x_2, -1)$ and let $x_2$ be whichever of these gives the smaller value.
3. Repeat with $x_3, x_4, \dots$ until you have picked all coordinates of $x$.

This is guaranteed to work, because $\frac12 g_1(1) + \frac12g_1(-1) = \mu$, so we can pick $x_1$ so that $g_1(x_1) \le \mu$. In general, $$\frac12 g_k(x_1, \dots, x_{k-1}, 1) + \frac12 g_k(x_1, \dots, x_{k-1}, -1) = g_{k-1}(x_1, \dots, x_{k-1})$$ so we can pick some value $x_k$ such that $g_k(x_1, \dots, x_k) \le g_{k-1}(x_1, \dots, x_{k-1})$.

Therefore, if we always pick the next value $x_k$ greedily, we have $$g_n(x_1, \dots, x_n) \le g_{n-1}(x_1, \dots, x_{n-1}) \le \dots \le g_1(x_1) \le \mu.$$ But the final value $g_n(x_1, \dots, x_n)$ is just $f(x)$, so we've found a vectors $x$ with $f(x) \le \mu$, as desired.