= Conditional expectation choice invariant
{title2=$q_{i+1}\geq q_i$}
Let $Z=Z(X_1,\ldots,X_n)$ be a real-valued <objective function> of finitely many choices, with finite <expected value>. Suppose a prefix $P=(X_1=x_1,\ldots,X_i=x_i)$ has positive <probability>. Write $q(P)=\mathbb E[Z\mid P]$. If the next choice is a fair <bit>, the <law of total expectation> gives
$$
q(P)=\frac{q(P,0)+q(P,1)}2.
$$
At least one child is at least this average. Choose a child with the larger value, using a fixed rule for ties. The resulting <loop invariant> is $q(P)\geq\mathbb E Z$. At a complete assignment $x$, there is only one completion left, so $q(x)=Z(x)$ and therefore $Z(x)\geq\mathbb E Z$.
For a biased choice or more than two possibilities, use the corresponding weighted average:
$$
q(P)=\sum_{a:\,p_a>0}p_aq(P,a),\qquad p_a=\mathbb P(X_{i+1}=a\mid P).
$$
Some positive-<probability> child is at least the weighted average. For minimization, choose a child at most the current <conditional expectation> and reverse the invariant. The averaging identity is the same in both directions.<Discrete Probability by Jeff Erickson>[Jeff Erickson, Discrete Probability, §1.2.2, printed pp. 6–7: conditional expectation decomposition and linearity; authorship stated on the author's Algorithms notes page]{ref}
The word "probabilities" in the method's name also covers an <indicator random variable> for an undesirable outcome: keeping its <conditional expectation>, which is its <conditional probability>, strictly below one eventually forces that indicator to be zero. Optimizing an ordinary numerical <objective function> is the <method of conditional expectations> formulation used below.
Back to article page
