Method of conditional probabilities

In mathematics and computer science, the method of conditional probabilities[1][2] is a systematic method for converting non-constructive probabilistic existence proofs into efficient deterministic algorithms that explicitly construct the desired object.

[3] Often, the probabilistic method is used to prove the existence of mathematical objects with some desired combinatorial properties.

Consequently, they are nonconstructive — they don't explicitly describe an efficient method for computing the desired objects.

The method of conditional probabilities converts such a proof, in a "very precise sense", into an efficient deterministic algorithm, one that is guaranteed to compute an object with the desired properties.

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.

The method of conditional probabilities replaces the random root-to-leaf walk in the random experiment by a deterministic root-to-leaf walk, where each step is chosen to inductively maintain the following invariant: In this way, it is guaranteed to arrive at a leaf with label 0, that is, a successful outcome.

The invariant holds initially (at the root), because the original proof showed that the (unconditioned) probability of failure is less than 1.

Since the invariant holds at the end, when the walk arrives at a leaf and all choices have been determined, the outcome reached in this way must be a successful one.

In a typical application of the method, the goal is to be able to implement the resulting deterministic process by a reasonably efficient algorithm (the word "efficient" usually means an algorithm that runs in polynomial time), even though typically the number of possible outcomes is huge (exponentially large).

For example, consider the task with coin flipping, but extended to n flips for large n. In the ideal case, given a partial state (a node in the tree), the conditional probability of failure (the label on the node) can be efficiently and exactly computed.

There are two standard and related techniques for dealing with this: Many probabilistic proofs work as follows: they implicitly define a random variable Q, show that (i) the expectation of Q is at most (or at least) some threshold value, and (ii) in any outcome where Q is at most (at least) this threshold, the outcome is a success.

In some cases, as a proxy for the exact conditional expectation of the quantity Q, one uses an appropriately tight bound called a pessimistic estimator.

Typically, a good pessimistic estimator can be computed by precisely deconstructing the logic of the original proof.

Let random variable Q be the number of vertices added to S. The proof shows that E[Q] ≥ |V|/(D+1).

This will ensure a successful outcome, that is, one in which the independent set S has size at least |V|/(D+1), realizing the bound in Turán's theorem.

If u does not have a neighbor in S, then u is added to S. By calculation, if u is chosen randomly from the remaining vertices, the expected increase in the pessimistic estimator is non-negative.

By the previous considerations, this keeps the pessimistic estimator from decreasing and guarantees a successful outcome.

For the method of conditional probabilities to work, it suffices if the algorithm keeps the pessimistic estimator from decreasing (or increasing, as appropriate).

With each step of either algorithm, the net increase in the pessimistic estimator is where N(t)(u) denotes the neighbors of u in the remaining graph (that is, in R(t)).

For the first algorithm, the net increase is non-negative because, by the choice of u, where d(u) is the degree of u in the original graph.

For the second algorithm, the net increase is non-negative because, by the choice of u, where d′(u) is the degree of u in the remaining graph.