= Method of conditional probabilities
{wiki}
= Method of conditional expectations
{synonym}
The method of conditional probabilities turns an <expected value> guarantee into a deterministic construction. For a maximization <objective function>, fix one choice at a time, always keeping the <conditional expectation> of the final value at least as large as before. Once every choice is fixed, that <conditional expectation> is the actual value. The useful ingredient is a way to evaluate the <conditional expectations> efficiently.
No actual random choices are needed during this construction. The <probability distribution> describes hypothetical completions used in the analysis; the algorithm compares their <conditional expectations> and commits deterministically. For <maximum cut>, this converts the <random cut lower bound> into a <cut of a graph> containing at least half the <edges>. A <maximum cut> can still be larger, as the <conditional expectations cut example> shows.
Back to article page
