Derandomization

Derandomization converts a randomized construction or algorithm into a deterministic one while preserving its desired guarantee. The method of conditional probabilities does this by maintaining a computable conditional expectation until all choices are fixed.

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.

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.

Let $G=(V,E)$ be a finite undirected simple graph, with $n=|V|$ vertices and $m=|E|$ edges. A cut of a graph assigns each vertex a label zero or one; an edge crosses precisely when its endpoints have different labels. Its size is the number of crossing edges. A maximum cut maximizes that size.

For the analysis, assign independent fair bits $X_v$ to the vertices. For each edge $uv$, the indicator random variable $I_{uv}=1_{\{X_u\ne X_v\}}$ has expected value $1/2$: exactly two of the four equally likely endpoint assignments cross. Thus linearity of expectation gives the random cut lower bound:Linearity of expectation does not require the indicator random variables to be independent. What matters here is the stipulated distribution of the endpoint bits.

For any partial assignment $P$, let $f(P)$ count edges whose two endpoints are already fixed on opposite sides, and let $u(P)$ count edges with at least one unassigned endpoint. Under the remaining independent fair bits,An edge with fixed equal labels contributes zero; fixed unequal labels contribute one. If one endpoint is unassigned, its fair bit disagrees with the fixed label with probability $1/2$. If both endpoints are unassigned, their independent fair bits disagree with probability $1/2$ as well. Count each unresolved edge once, even when both endpoints are unassigned.

Process vertices in a fixed order. Evaluate the conditional expectation cut formula after setting the next label to zero and after setting it to one; retain the larger value, choosing zero on ties. The conditional expectation choice invariant ensures the final cut of a graph has size at least $m/2$. This is a deterministic approximation algorithm for maximum cut.^[ref]

Consider the following original five-vertex simple graph, where $AB$ denotes the undirected edge $\{A,B\}$:Its seven edges give initial expected value $q(\varnothing )=7/2=3.5$. Use vertex order $A,B,C,D,E$ and choose zero whenever the two child conditional expectations tie.

The complete decision ledger is below. A prefix lists fixed labels in vertex order; all later labels remain hypothetically independent fair bits. Each candidate entry is the conditional expectation of the final cut of a graph, including the contribution of unresolved edges.

For example, after $A=0,B=1$, edge $AB$ is fixed crossing and the other six edges are unresolved, giving $1+6/2=4$. Setting $C=0$ fixes $BC$ crossing and $AC$ noncrossing, leaving four unresolved edges: $2+4/2=4$. Setting $C=1$ instead fixes $AC$ crossing and $BC$ noncrossing, giving the same conditional expectation.

The final labels are $(0,1,0,0,1)$, so the two sides are $\{A,C,D\}$ and $\{B,E\}$. The five crossing edges are $AB,BC,DE,EA,BD$; $AC,CD$ do not cross. This exceeds $m/2=3.5$, and hence also the rounded-up guarantee of four edges.

It is not a maximum cut. Labels $(0,1,1,0,1)$ cross all edges except $BC$, giving six. Seven are impossible because the triangle in a graph $ABC$ cannot have all three edges crossing a two-sided cut of a graph. An independent enumeration of all $2^5=32$ complete label assignments gives the following distribution, counting an assignment and its label-swapped counterpart separately:

The weighted sum is $112$, so the average is $112/32=3.5$, agreeing with linearity of expectation. Choosing $C=0$ in the earlier tie discards the remaining size-six completion while preserving the average of four. The method protects an expected value guarantee; it need not preserve the best possible completion.

Directly scanning all $m$ edges to evaluate each child of each of $n$ choices takes $O(nm+n)$ elementary operations, in Big O notation. There is a faster implementation. When assigning vertex $v$, let $d_0$ and $d_1$ count its already assigned graph neighbours labelled zero and one. Contributions from edges not incident to $v$ are unchanged, and contributions from edges to unassigned graph neighbours stay $1/2$ for either choice. ThereforeChoose zero if $d_1\ge d_0$, otherwise one: put $v$ on the side with fewer already assigned graph neighbours. With adjacency lists, scanning each vertex's list once costs $O(n+m)$ operations overall and uses $O(n+m)$ storage including the graph. These bounds count operations on labels and counters that fit in machine words of $O(\log (n+m+2))$ bits. Multiplying the conditional expectation cut formula by two also permits exact integer comparisons without rounding.

If $\mathrm{OPT}$ is the size of a maximum cut, then $\mathrm{OPT}\le m$. The constructed cut of a graph thus has size at least $m/2\ge \mathrm{OPT}/2$, an approximation ratio of $1/2$ in the maximization convention. The five-versus-six example illustrates the gap between this guarantee and exact optimization.

For a general randomized algorithm, the averaging proof alone does not establish efficient derandomization. One needs a polynomial number of commitments, an efficient way to find a suitable child at each step, and manageable representations and evaluation costs for the relevant conditional expectations. Those evaluations can themselves be hard. Enumerating all completions verifies this small example, but would take exponentially many assignments as $n$ grows. The polynomial-time algorithm here comes from the local conditional expectation cut formula, not from that enumeration.