method of conditional probabilities (Max Cut)

The method of conditional probabilities converts a probabilistic existence proof into a deterministic algorithm.

The method of conditional probabilities is a systematic method for converting non-constructive probabilistic existence proofs into efficient deterministic algorithms that explicitly construct the desired object.



Description

Raghavan (1988) gives this description of the method:

We first show the existence of a provably good approximate solution using the probabilistic method [1]. [We then] show that the probabilistic existence proof can be converted, in a very precise sense, into a deterministic approximation algorithm. To this end we use an interesting “method of conditional probabilities”…We apply our method to integer programs arising in packing, routing, and maximum multicommodity flow… [2]

(Raghavan is discussing the method in the context of randomized rounding, but it works with the probabilistic method in general.)

To derive a constructive algorithm from a random experiment, one first casts the random experiment as a series of “small” random choices, then modifies the random process, replacing each small random choice by a deterministic choice, chosen so as to keep the current conditional probability of failure (given the choices made so far) below 1.

\includegraphics[type=pdf,ext=.pdf,read=.pdf,width=5.5in]{shared/graphics/method_of_conditional_probabilities_2}

Trivial example: flipping three coins

Here is a toy example to illustrate the principle.

Lemma.

It is possible to flip three coins so that the number of tails is at least 2.

Proof.

If the three coins are flipped randomly, the expected number of tails is 1.5. Thus, there must be some outcome (way of flipping the coins) so that the number of tails is at least 1.5. Since the number of tails is an integer, in such an outcome there are at least 2 tails.

 
 

In this example the random experiment consists of flipping three fair coins. The experiment is illustrated by the rooted tree in the diagram. There are eight outcomes, each corresponding to a leaf in the tree. A trial of the random experiment corresponds to taking a random walk from the root (the top node in the tree, where no coins have been flipped) to a leaf. The successful outcomes are those in which at least two coins came up tails. The interior nodes in the tree correspond to partially determined outcomes, where only 0, 1, or 2 of the coins have been flipped so far.

To apply the method of conditional probabilities, one focuses on the conditional probability of failure, given the choices so far as the experiment proceeds step by step.

In the diagram, each node is labeled with this conditional probability. (For example, if only the first coin has been flipped, and it comes up tails, that corresponds to the second child of the root. Conditioned on that partial state, the probability of failure is 0.25.)

We replace the random root-to-leaf walk by a deterministic walk to a leaf labeled 0.

General description

In general, it is always possible to replace each random step by a deterministic step to maintain the invariant that the conditional probability of failure, given the current state, is less than 1. The invariant holds initially (at the root), because the original proof showed that the (unconditioned) probability of failure is less than 1. At any interior node whose probability of failure is less than 1, because the probability at that node is a weighted average of the probabilities at the children, there is at least one child to choose that also has probability of failure less than 1. By maintaining the invariant until the end (when the walk arrives at a leaf), the outcome reached must be successful.

In practice, there are various ways to make each choice to keep the conditional probability of failure below 1. Often, the exact conditional probability of failure is hard to compute. Instead one keeps an upper bound on the conditional probability of failure below 1, which suffices. Or, it may suffice to keep the conditional expectation of some other quantity above or below a certain threshold. (See the discussion of pessimistic estimators.)

Example: derandomizing the Max-Cut existence proof

Here is how the method of conditional probabilities works for the Max-Cut example in the note on the probabilistic method. That proof shows that for a randomly chosen cut, the number of edges in the graph G=(V,E) that are cut is |E|/2 in expectation. Thus, the probability of cutting fewer than |E|/2 edges is less than 1.

Let random variable Q be the number of edges cut. The algorithm will emulate the random experiment, coloring the vertices one by one. To keep the conditional probability of failure (Q \lt |E|/2) below 1, the algorithm will keep the conditional expectation of Q at or above |E|/2. To do this, it will simply color each vertex to keep the conditional expectation of Q from decreasing. (Here, the “conditional expectation” refers to the expectation if the remaining vertices were to be colored randomly, even though the algorithm will end up coloring them deterministically.)

So what is the conditional expectation of Q? Suppose the first t vertices have been colored. Let S_ t denote the state (first t vertex colors). Each edge that already has both endpoints colored differently will definitely be cut; let c(S_ t) denote the number of these edges. Each edge that already has both endpoints colored the same will definitely not be cut. Each other edge has at least one undetermined endpoint and has a 1/2 chance of being cut; let u(S_ t) denote the number of these edges. Thus, the conditional expectation of Q given S_ t, that is, E[Q \, |\, S_ t], is c(S_ t)+u(S_ t)/2 — the number of edges cut so far plus half the undetermined edges.

To color the t+1st vertex, say v, the algorithm computes the conditional expectation (\textrm{E}[Q \, |\, S_{t+1}] = c(S_{t+1})+u(S_{t+1})/2) that would result from coloring v red and compares that to the conditional expectation that would result from coloring v blue. One of these two choices will give a conditional expectation at least as large as the current one \textrm{E}[Q \, |\, S_ t]. (This is because the current conditional expectation is the average of the two possible next conditional expectations.) The algorithm colors v whichever way maximizes \textrm{E}[Q \, |\, S_{t+1}], guaranteeing that \textrm{E}[Q \, |\, S_{t+1}] \ge \textrm{E}[Q\, |\, S_ t].

More concretely, this algorithm reduces to the following: Consider the vertices in any order. When considering a vertex v, color it red if among its colored neighbors, more are blue then red. Otherwise color it blue.

Since the algorithm maintains the invariant \textrm{E}[Q \, |\, S_{t+1}] \ge |E|/2, it maintains the invariant that the conditional probability of failure is less than 1. Thus, it is guaranteed to succeed (cut at least half the edges).