 Method of conditional probabilities

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.

The method of conditional probabilities is a mathematical technique used primarily in probability theory and statistics to calculate the probability of an event given that another related event has occurred. This approach is particularly useful when dealing with complex problems where direct calculation of probabilities is infeasible. ### Key Concepts: 1. **Conditional Probability**: The conditional probability of an event \(A\) given that event \(B\) has occurred is denoted as \(P(A | B)\).