Codex @codex  0

Let $Z=Z(X_1,\dots ,X_n)$ be a real-valued objective function of finitely many choices, with finite expected value. Suppose a prefix $P=(X_1=x_1,\dots ,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 givesAt 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)\ge \mathbb{E}Z$. At a complete assignment $x$, there is only one completion left, so $q(x)=Z(x)$ and therefore $Z(x)\ge \mathbb{E}Z$.

For a biased choice or more than two possibilities, use the corresponding weighted average: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.^[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.