Motivation
A proof that a good object exists need not construct it directly. One can define a random experiment, show that its expected quality is high, and conclude that at least one outcome is good. The method of conditional expectations goes further: it can choose the random decisions one at a time while preserving a lower bound on the expected final quality. We develop both steps for maximum cut, keeping the probability argument separate from the algorithmic work needed to compute its conditional values.
Definitions
Definition 6.6.1
(Cut, cut weight and the half-approximation guarantee)
Let be a finite undirected graph with no loops and nonnegative real edge weights . A cut is a partition ; an edge crosses it when its endpoints lie in different parts. Its weight is the sum of the weights of its crossing edges. Let and let be the maximum cut weight. A randomized algorithm has an expected approximation ratio at least here if its expected cut weight is at least on every such input. The expectation is over the algorithm's random choices for a fixed graph; it does not promise that every run achieves that value.
Theorem/proposition
Theorem 6.6.2
(Random-cut expectation)
Put every vertex independently into either part with probability . The expected cut weight is , and at least one cut has weight at least .
Theorem 6.6.3
(Conditional-expectation construction)
There is a deterministic algorithm which, by fixing vertex sides one at a time while never decreasing the conditional expected final cut weight, outputs a cut of weight at least .
Proof sketch or proof idea
Proof
(Linearity of expectation over edge indicators)
For each edge , define to be 1 when are on different sides and 0 otherwise. Their independent fair choices give . The cut weight is , so linearity of expectation gives
Linearity does not require the edge indicators to be jointly independent. In a triangle, the number of crossing edges is always even, so all three indicators cannot equal 1; yet each equals 1 with probability . Thus their joint probability of all being 1 is 0 rather than . Sharing a vertex alone does not prove dependence: distinct pairs of edge indicators are independent in this fair-bit experiment on a simple graph. Independence is used to compute the crossing probability of each individual edge. Since the finite set of possible cuts has average weight , at least one cut has weight at least its average. If every cut had lower weight, their average would also be lower.
Proof
(Conditional expectations never decrease)
For the deterministic construction, suppose some vertices have fixed sides and the others remain independent fair choices. Let be the current conditional expectation. For an unfixed vertex , let and be the expectations conditional on assigning it to each side. The law of total expectation gives . At least one of is at least ; choose such a side and continue. Once all vertices are fixed, the conditional expectation equals the actual cut weight. Since it never decreased, that weight is at least the initial .
The conditional value is easy to calculate. A fully assigned edge contributes its full weight if it crosses and zero otherwise. An edge with at least one unfixed endpoint crosses with conditional probability and contributes half its weight. This uses independence of the remaining fair assignments. Therefore and can be calculated by scanning the incident edges, giving a polynomial-time algorithm. With suitable bookkeeping each edge needs only constant processing as its endpoints are fixed.
Proof X-ray
Why the invariant never drops
The proof maintains one invariant: given the sides fixed so far, the conditional expectation of the final cut weight is at least . It holds at the start, because nothing is fixed and . The one non-routine step is that is the average of and . The next vertex's fair choice is independent of the sides already fixed and takes each side with probability , so the larger of the two values cannot lie below their average. This is the averaging argument of the existence proof applied one decision at a time, and it is what turns existence into a procedure.
At the end nothing random remains, so is the weight of the output cut. The invariant itself needs no assumption on the weights; nonnegativity enters only when is compared with . The procedure also needs and to be computable, which the preceding proof supplies.
Worked examples
Worked example 6.6.4
(A triangle)
For a triangle with unit weights, and the expected random cut weight is . Any cut putting one vertex on one side and two on the other crosses two edges. Thus a cut of weight 2 exists, above the average. The all-on-one-side outcome has weight zero, showing that a single random run need not reach the expectation.
Worked example 6.6.5
(Choose a side conditionally)
Suppose vertex has already been assigned to , and the remaining vertices of a unit-weight triangle are unassigned. Assigning to makes contribute zero, while and each contribute , giving conditional expectation 1. Assigning to makes contribute 1 and the other two edges contribute each, giving 2. Choose . No matter which side receives , the final cut weight is 2.
Worked example 6.6.6
(Unequal weights)
For a three-vertex path with edge weights 2 and 6, and the expected weight of a random cut is 4. Put the middle vertex on one side and both endpoints on the other to cut both edges, obtaining 8. Nonnegative weights ensure , which connects the guarantee to .
Common mistakes
Common mistake
(An average is not a guarantee for each run)
An expectation is an average, not a per-run guarantee. The triangle's zero-weight outcome is a counterexample to claiming that every random cut weighs at least . Also, a high average alone gives existence but does not automatically give an efficient deterministic search. The construction above relies on computing the conditional expectations efficiently.
Counterexample mode
Negative weights break the half-approximation guarantee
A tempting claim is that the random cut has expected weight at least whatever the weights. Take one edge of weight between two vertices. Then , and the random cut has expected weight , as linearity predicts. But putting both vertices on the same side cuts nothing, so and : the claim fails.
The step that breaks is , which needs nonnegative weights; here . The calculation still holds for arbitrary real weights, but its approximation meaning must be reconsidered.
Summary
Random choices give an average, and an average gives an existence statement. Conditional expectations make this proof constructive when the next conditional values can be computed efficiently. The edge indicators need not be independent of each other, but independent fair vertex choices are used to obtain each crossing probability.
The approximation statement and its limits
Every cut uses a subset of the edges. When weights are nonnegative its weight is at most , so . Consequently both the expected random-cut weight and the deterministic construction satisfy
This is a lower bound relative to an optimum we may not know how to compute efficiently. The proof does not claim that ; an odd cycle cannot have every edge cross a cut. If , all weights are zero and every cut has weight zero, so the inequality still holds without dividing by zero. Writing a ratio of two numerical weights in that case would be undefined; the inequality formulation avoids that issue.
On one edge of weight 1, the random cut has expected weight and the optimum is 1. Thus the analysis of this particular random experiment is sharp. The deterministic conditional-expectation method makes the endpoints opposite and obtains the optimum on this instance, but that does not prove it always finds an optimum on every graph.
Concept lensAlgebraic
Cut weight with signs
Encode the sides by signs . An edge crosses exactly when , so its indicator is and
For independent fair signs, , which gives again. Maximizing the cut means making the signed sum as negative as possible. For one edge of weight this gives , equal to for opposite signs.
A probability guarantee can be extracted for a weaker threshold. Suppose and write for the uncut weight. Since weights are nonnegative, and . Markov's inequality gives
Therefore . This bound is weaker than a promise of a half-optimal cut in each run, but it is a genuine per-run probability statement. It also relies on nonnegative weights and . Repeated independent runs can raise the probability of seeing at least one cut above ; that amplification needs independent random choices between runs.
An explicit conditional update
When assigning an unassigned vertex , consider an incident edge of weight whose other endpoint is already assigned. Before the choice, its conditional contribution is . Assigning to the opposite side changes that contribution to , while assigning it to the same side changes it to zero. An edge from to an unassigned vertex contributes under either choice, because that other endpoint remains fair. Edges not incident to are unchanged. Hence the better side is the one that cuts at least half the total weight of edges from to already assigned vertices.
For example, if previously assigned neighbors of on have total incident weight 7 and those on have total 4, placing in immediately cuts weight 7 from these edges; placing it in cuts weight 4. The former choice preserves or increases conditional expectation. The comparison concerns only already fixed neighbors; future edges are not ignored, but their conditional contributions are equal under the two choices.
This update also proves the running-time claim constructively. Process vertices in a fixed order. For each edge, when its second endpoint is processed, inspect the already assigned first endpoint and add the edge weight to the appropriate side total. Each adjacency entry is visited a constant number of times in a conventional adjacency-list representation. In a real-arithmetic operation model, the number of graph and arithmetic operations is . For rational weights encoded as bits, bit complexity also depends on their representation and the cost of arithmetic.
A different use of the same averaging argument
Suppose a finite set of candidate solutions has real scores. If their average is , at least one score is at least and at least one is at most . No probability model beyond choosing a uniformly random candidate is needed. For weighted distributions the same conclusion holds among outcomes of positive probability, because the expectation is a convex combination of their scores. If the average equals the maximum, every positive-probability outcome has that maximum; otherwise some strictly smaller score would lower the average.
The theorem does not say how many outcomes are good. For example, one outcome with score 100 and 99 outcomes with score zero has average 1, even though only one outcome reaches or exceeds the average. Nor does an existence proof ensure a useful probability of sampling a good object. A separate concentration or sampling argument is needed for a high-probability algorithmic guarantee.
Exercises
Quick check
(A graph has four edges of weights . What is the expected weight of the random cut?)
Add the weights and halve.
Solution · Answer
The total weight is 8, so the expected cut weight is 4. The graph's arrangement does not change this calculation, provided every edge joins distinct vertices.
Quick check
(A partially assigned graph has conditional expectations 7 if the next vertex goes to and 9 if it goes to . What is the current conditional expectation and which choice preserves it?)
Average the two conditional values.
Solution · Answer
The current expectation is . Choose , whose conditional value is 9. Choosing would reduce the conditional expectation at this step, although it might still happen to lead to a good final cut.
Quick check
(A unit-weight path has three edges. State the random-cut expectation and exhibit a cut attaining the optimum.)
Try alternating the sides along the path.
Solution · Answer
The expectation is . Alternating the sides along the four vertices cuts all three edges, giving weight 3. Since no cut can use more than all three edges, this is optimal.
Quick check
(A vertex has already assigned neighbors with incident weights 2 and 5 on , and weights 4 and 1 on . Which choice keeps the conditional expectation from decreasing?)
Compare the total weight of the assigned neighbors on each side.
Solution · Answer
The total weights are 7 on and 5 on . Assign the vertex to , which cuts the 7 units toward . Before the assignment these edges contributed in expectation; afterwards they contribute 7. Contributions from edges to unassigned neighbors stay unchanged at half their weights.
Quick check
(Does the conditional-expectation proof require the two choices for the next vertex to yield different values?)
What does the law of total expectation say when the two values are equal?
Solution · Answer
No. If , both equal their average and either choice preserves the invariant. Ties can be broken by a fixed convention, such as always choosing . An isolated vertex is a simple example: its side changes no edge contribution, so both choices have equal conditional value. A deterministic tie rule ensures that the resulting algorithm is fully specified, even though different tie rules may produce different cuts.