Probability and Computing, Oxford 2018-19
Lectures

Randomised algorithms make random choices. How can this help? The simple reason is that for a well-designed randomised algorithm, it is highly improbable that the algorithm will make all the wrong choices during its execution.

The advantages of randomised algorithms are:

simplicity

randomised algorithms are usually simpler than their deterministic counterparts

efficiency

they are faster, use less memory, or less communication than the best known deterministic algorithm

dealing with incomplete information

randomised algorithms are better in adversarial situations

Although there is a general consensus that randomised algorithms have many advantages over their deterministic counterparts, it is mainly based on evidence rather than rigorous analysis. In fact, there are very few provable cases in which randomised algorithms perform better than deterministic ones. These include the following:

• we will see an example (string equality) in which randomised algorithms have provably better communication complexity than deterministic algorithms
  • for the similar problem of equality of multivariate polynomials, we know good randomised algorithms but no polynomial-time deterministic algorithm
• randomised algorithms provide provably better guarantees in online algorithms and learning

We have no rigorous proof that randomised algorithms are actually better than deterministic ones. This may be either because they are not really better or because we don’t have the mathematical sophistication to prove it. This is one of the outstanding open problems in computational complexity.

A randomised algorithm \(A(x,r)\) is a deterministic algorithm with two inputs. Informally, we say that \(A(x,r)\) computes a function \(f(x)\), when for a random $r\,$: \(A(x,r)=f(x)\) with significant probability.

We view this as a randomised algorithm because when we provide the algorithm with a random \(r\), it will accept with probability at least \(1/2\), when \(x\in L\), and probability \(1\), when \(x\not\in L\).

• Note the asymmetry between positive and negative instances. When an RP algorithm accepts, we are certain that \(x\in L\); when it rejects, we know that it is correct with probability at least \(1/2\).
• The class co-RP is the class with the same definition with RP, but with inverse roles of “accept” and “reject”. For example, the string equality problem is in co-RP, and the string inequality problem in RP.
• The bound \(1/2\) on the probability is arbitrary; any constant in \((0,1)\) defines the same class.
• The class NP has very similar definition. The only difference is that when \(x\in L\), the algorithm accepts not for at least half of the \(r\)’s but with at least a single \(r\).
• Similarly for the class P, the only difference is that when \(x\in L\), the algorithm accepts for all \(r\).

This shows

For RP algorithms, if we want higher probability of success, we run the algorithm \(k\) times, so that the algorithm succeeds for \(x\in L\) with probability at least \(1-2^{-k}\).

Besides RP, there are other randomised complexity classes. The class ZPP (Zero-error Probabilistic Polynomial time) is the intersection of RP and its complement co-RP. Note that a language in ZPP admits an RP and a co-RP algorithm. We can repeatedly run both of them until we get an answer for which we are certain. The classes RP and ZPP correspond to the following types of algorithms

Monte Carlo algorithm (RP)

it runs in polynomial time and has probability of success at least \(1/2\) when \(x\in L\), and its is always correct when \(x\not\in L\).

Las Vegas algorithm (ZPP)

it runs in expected polynomial time and it always gives the correct answer.

Arguably, if we leave aside quantum computation, the class that captures feasible computation is the BPP class:

• Again the constant \(3/4\) is arbitrary; any constant in \((1/2, 1)\) defines the same class.
• By repeating the algorithm many times and taking the majority, we can bring the probability of getting the correct answer very close to 1.

We don’t know much about the relation between the various classes. Clearly \(RP\subseteq BPP\), because if we run an RP algorithm twice, the probability of success is at least \(3/4\), for every input. One major open problem is whether \(BPP\subseteq NP\).

We want to hire a secretary by interviewing \(n\) candidates. The problem is that we have to hire a candidate on the spot without seeing future candidates. Assuming that the candidates arrive in random order and that we can only compare the candidates that we have already seen, what is the strategy to maximise the probability to hire the best candidate?

More precisely, suppose that we see one-by-one the elements of a fixed set of \(n\) distinct numbers. Knowing only that the numbers have been permuted randomly, we have to stop at some point and pick the current number. What is the strategy that maximises the probability to pick the minimum number?

We will study the strategies that are based on a threshold \(t\): we simply interview the first \(t\) candidates but we don’t hire them. For the rest of the candidates, we hire the first candidate who is the best so far (if any).

Let \(\pi\) be a permutation denoting the ranks of the candidates. Let \(W_i^t\) denote the event that the best candidate among the first \(i\) candidates appears in the first \(t\) positions. Since the permutation is random \(\P(W_i^t)=t/i\), for \(i\geq t\).

The probability that we succeed on step \(i\), for \(i>t\), is \(\P(\pi_i=1 \wedge W_{i-1}^t)\). Since the events \(\pi_i=1 \wedge W_{i-1}^t\) are mutually exclusive, we can write the probability of success as

This achieves its maximum value \(1/e\), when \(t=n/e\).

It is not very complicated to show that there is an optimal strategy which is a threshold strategy⁴. Thus

Let \(X_1,\ldots,X_n\) be nonnegative independent random variables drawn from distributions \(F_1,\ldots,F_n\). We know the distributions but not the actual values. We see one-by-one the values \(X_1,\ldots,X_n\) and at some point we select one without knowing the future values. This is our reward. What is the optimal strategy to optimise the expected reward?

It is easy to see that we can find the optimal strategy by backwards induction. If we have reached the last value, we definitely select \(X_n\). For the previous step, we select \(X_{n-1}\) when \(X_{i-1}\geq \E[X_n]\), and so on. The following theorem says that we can get half of the optimal reward with a threshold value.

The above theorem is tight as the following example shows: Fix some \(\epsilon>0\) and consider \(X_1=\epsilon\) (with probability 1), \(X_2=1\) with probability \(\epsilon\), and \(X_2=0\) with probability \(1-\epsilon\). Then no strategy (threshold or not) can achieve a reward more than \(\epsilon\), while the optimal strategy has expected reward \(2\epsilon-\epsilon^2\) and the ratio tends to \(1/2\) as \(\epsilon\) tends to 0.

Note that linearity of expectations does not require independence of the random variables!

Derandomisation is the process of taking a randomised algorithm and transform it into an equivalent deterministic one without increasing substantially its complexity. Is there a generic way to do this? We don’t know, and in fact, we have randomised algorithms that we don’t believe that can be directly transformed into deterministic ones (for example, the algorithm of verifying identity of multivariate polynomials). But we do have some techniques that work for many randomised algorithms. The simpler such technique is the method of conditional expectations. Other more sophisticated methods of derandomisation are based on reducing the number of required randomness and then try all possible choices.

Recall that random variables \(X_1,\ldots,X_n\) are independent if \[\P(X_1=a_1 \cap \cdots \cap X_n=a_n) = \P(X_1=a_1) \cdots \P(X_n=a_n)\] for all \(a_1,\ldots,a_n\).

Quicksort is a simple and practical algorithm for sorting large sequences. The algorithm works as follows: it selects as pivot an element \(v\) of the sequence and then partitions the sequence into two parts: part \(L\) that contains the elements that are smaller than the pivot element and part \(R\) that contains the elements that are larger than the pivot element. It then sorts recursively \(L\) and \(R\) and puts everything together: sorted \(L\), \(v\), sorted \(R\).

Randomised Quicksort selects the pivot elements independently and uniformly at random. We want to compute the expected number of comparisons of this algorithm.

Another application of the linearity of expectations is a proof of Jensen’s inequality, a very general lemma and an important tool in probability theory.

The theory of convex functions of one or more variables plays an important part in many fields and in particular in algorithms. A function is called convex if for every \(x\), \(y\), and \(\lambda\in[0,1]\): \(f(\lambda x+(1-\lambda) y)\leq \lambda f(x)+(1-\lambda) f(y)\).

Jensen’s inequality holds for every convex function \(f\), but for simplicity we will prove it only for differentiable \(f\). For differentiable functions, the definition of convexity is equivalent to: for every \(x\) and \(y\), \(f(y)\geq f(x)+f'(x)(y-x)\).

With this, Jensen’s inequality is a trivial application of the linearity of expectations:

An immediate application of Jensen’s inequality is that for every random variable \(X\): \(\E[X^2]\geq (\E[X])^2\).

We have seen that in many cases we can easily compute exactly or approximately the expectation of random variables. For example, we have computed the expected value of the number of comparisons of Randomised Quicksort to be \(2n\ln n+O(n)\). But this is not very informative about the behaviour of the algorithm. For example, it may be that the running time of the algorithm is either approximately \(n\) or approximately \(n^2\), but never close to the expected running time. It would be much more informative if we new the distribution of the number of comparisons of the algorithm. Concentration bounds–also known as tail bounds–go a long way towards providing this kind of information: they tell us that some random variable takes values close to its expectation with high probability. We will see a few concentration bounds in this course, such as Markov’s and Chebyshev’s inequality and Chernoff’s bound. All these provide inequalities for probabilities.

One of most useful concentration bounds is Chernoff’s bound for binomial random variables and more generally for sums of \(0-1\) independent random variables.

The next corollary gives slightly weaker bounds that are simpler to apply. They can be derived directly from the theorem using the following inequalities for \(0<\delta<1\), which can be established by elementary calculus techniques:

We throw \(n\) balls into \(n\) bins and we are interested in the maximum load.

First let’s consider a fixed bin, say bin \(1\). Its expected load is 1. Since the balls are thrown independently, we can use the Chernoff bounds. Here we have the sum of \(n\) 0-1 independent random variables, each with probability \(1/n\). In other words, the number of balls into bin \(1\) is \(Y_1\sim B(n,1/n)\). Chernoff bound gives (with \(\mu=\E[Y_1]=1\))

If we select \(\delta=\Theta(\ln n/\ln\ln n)\), the right-hand side is at most \(1/n^2\). Specifically for \(1+\delta=3\ln n/\ln\ln n\), the right-hand side is at most \(1/n^2\).

By the union bound, the probability that every bin has load at most \(1+\delta\) is at most \(n(1/n^2)=1/n\).

To bound the expected maximum load, we provide an upper bound for the following two cases:

• with probability at least \(1-1/n\), the maximum load is at most \(3\ln n/\ln\ln n\)
• with probability at most \(1/n\), the maximum load is at most \(n\)

Therefore the expected maximum load is at most \((1-1/n)\cdot 3\ln n/\ln\ln n+1/n \cdot n\leq 1+3\ln n/\ln\ln n\).

This is an upper bound on the expected maximum load and it is tight. One can derive the opposite direction using the second moment method, but this is beyond today’s lecture. The following theorem is offered without proof.

In fact, we know of very precise bounds, that we will also not prove here. The expected maximum load is \(\ln n/\ln\ln n (1+o(1))\).

We consider here an application of Chernoff bounds to computational complexity. Recall the definition of the complexity class BPP.

Fix a problem that admits a randomised BPP algorithm \(A(x,r)\) with running time \(p(n)\). We will consider only inputs of length \(n\). Imagine a very large table with rows the \(2^n\) possible inputs \(x\) of size \(n\), columns the \(2^{p(n)}\) random strings \(r\), and 0-1 entries indicating whether the algorithm is correct for the given input and random string. The fact that this is a BPP algorithm is equivalent of saying that for every row of the table, the fraction of \(1\)’s is at least \(3/4\). Note that this immediately implies that there exists a column whose fraction of \(1\)’s is at least \(3/4\). Now if we run the algorithm three times and take the majority of answers, the probability of success increases to \(27/32\). This means that there exist 3 columns in the table such that for a fraction of \(27/32\) of the rows the majority in the three columns is 1. By running the algorithm many times, we can make the probability of success more than \(1-2^{-n}\), which implies that there are \(k\) columns such that for every row the majority is 1.

If we knew these \(k\) columns, we could use them to get the correct answer for every input. Reinterpreting this, we can say that we can derandomise the algorithm by running the algorithm with these particular \(k\) random strings and taking the majority.

We now show that \(k\) does not have to be very large. What is the probability of failure when we run the algorithm \(k\) times? Since we take the majority, it is equal to \(\P(X\leq k/2)\), where \(X\) is a binomial variable \(X\sim B(k,3/4)\). To apply a Chernoff bound, we compute \(E[X]=\mu=3k/4\), \(k/2=(1-\delta)\mu\) where \(\delta=1/3\).

We want this to be less than \(2^{-n}\), which shows that \(k=O(n)\). So, we have shown that

When we fix the random string to be \(r_n^{*}\), algorithm \(A'\) becomes a deterministic algorithm, but it works only for inputs \(x\) of length \(n\). This is an example of non-uniform computational complexity: for each input size we have a different algorithm. Non-uniform computation is not in general equivalent to uniform computational complexity. In particular, computing the strings \(r_n^{*}\), may be a substantially more difficult problem.

Similar considerations apply to RP, as well as to other computational models. In particular, the same reasoning shows that we don’t need to consider randomised circuits. Circuits is a typical non-uniform computational model: we need a different circuit for every input size. With a similar reasoning as with BPP, we get

Given that a language with running time \(O(p(n))\) has circuits of size \(O(p(n)^2)\), we get

If we replace the last condition by \(\E[Z_{n+1} \,|\, X_0,\ldots, X_n] \leq Z_n\), we get a supermartingale. The inverse condition gives a submartingale.

For example, in gambler’s fortune (equivalent to the random walk on the line), the first time that the gambler wins an amount \(k\) is a stopping time, but the first time that the gambler attains the maximum winnings during the first \(n\) games is not a stopping time.

The variable \(X_t\) represents the state of the Markov chain at time \(t\), and the matrix \(Q\) encodes the state-to-state transition probabilities. The characteristic property of a Markov chain is that the distribution of \(X_t\) depends only on \(X_{t-1}\). Note also that in the above definition the conditional probability \(\P(X_{t+1} =j \mid X_t=i)\) is independent of the time \(t\).

The \(t\)-step transition probabilities are given by the power matrix \({Q}^t\), that is,

for all \(s,t \in \mathbb{N}\). Thus we have

In particular, a Markov chain is completely determined by the distribution of \(X_0\) and the transition matrix \({Q}\).

A Markov chain can equivalently be represented as a weighted directed graph whose vertices are the states of the chain and in which there is an edge \((i,j)\) of weight \(Q_{i,j}\) whenever \(Q_{i,j} > 0\). We define the weight of a path to be the product of the weights of the edges along the path, i.e., the probability to take the path. Then the sum of the weights of all length-\(k\) paths \(i\) to \(j\) is \({Q}^k_{i,j}\).

The term random walk usually refers to the random process in which a particle moves on a graph, selecting the next node uniformly at random from the adjacent nodes. It is the special case of a Markov chain when for every state \(i\) all non-zero probabilities \(Q_{i,j}\) for \(j\neq i\) are equal and \(Q_{i,i}=0\). A lazy random walk is similar but with \(Q_{i,i}=1/2\).

The 2-SAT problem is the special case of the satisfiability problem: given a 2-CNF formula, either find a satisfying assignment or determine that no such assignment exists. It is known that 2-SAT is solvable in polynomial time, in fact linear time. Here we give a very simple polynomial-time randomised algorithm for 2-CNF formulas whose analysis is based on a random walk.

The 2-SAT algorithm has one-sided errors—if the input \(\varphi\) is not satisfiable then the algorithm certainly returns “unsatisfiable”, however if \(\varphi\) is satisfiable then the algorithm might not find a satisfying assignment. Below we analyse the probability that the algorithm gives the correct answer.

Consider a run of the 2-SAT algorithm in case the input \(\varphi\) is satisfiable. Let \(S\) be a particular assignment that satisfies \(\varphi\). We will bound the probability that the algorithm finds \(S\). If \(\varphi\) is not satisfied by an assignment \(A\) there must be an unsatisfied clause \(C\). The crucial observation is that one or both literals of \(C\) must then have different truth values under \(A\) and \(S\). Thus if we flip a random literal in \(C\) then the probability that we increase the agreement between \(A\) and \(S\) is either \(1/2\) or \(1\). Writing \(A_t\) for the assignment after \(t\) iterations of the main loop and \(X_t\) for the number of variables in which \(A_t\) agrees with \(S\), we have

If we replace the inequalities with equalities then \(X=X_0,X_1,\ldots\) becomes a Markov chain on the state space \(\{0,1,\ldots,n\}\). This chain describes the movement of a particle on a line: it is an example of a one-dimensional random walk with one reflecting and one absorbing barrier (elsewhere called gambler’s ruin against the sheriff).

The expected time until \(X_t=n\) is an upper bound on the expected number of steps for the 2-SAT algorithm to find \(S\). In turn this is an upper bound for the algorithm to find some satisfying assignment.

Let \(h_j\) be the expected time for \(X\) to first reach \(n\) starting at \(j\). Then we have

This is a linear system of equations in \(n+1\) unknowns. One way to solve the equations is to first find a relationship between \(h_j\) and \(h_{j+1}\) for \(0 \leq j < n\). Here it is not difficult to deduce that \(h_j=h_{j+1}+2j+1\). Combining this with the boundary condition \(h_n=0\) we get that \(h_j =n^2-j^2\). We conclude that \(h_j \leq n^2\) for all \(j\).

Let \(T\) denote the number of steps for the 2-SAT algorithm to find assignment \(S\) starting from some arbitrary assignment. By Markov’s inequality we have

Here we extend the randomised algorithm for 2-SAT to handle 3-SAT—the satisfiability problem for 3-CNF formulas. We find that the expected running time is no longer polynomial in the number of variables \(n\). This is not surprising since 3-SAT is NP-complete. The algorithm we describe has expected running time that is exponential in \(n\) but is nevertheless significantly better than the running time \(O(2^n)\) arising from exhaustive search.

Let us first consider what happens if we try to directly apply the 2-SAT algorithm to the 3-SAT problem mutatis mutandis. Suppose that a given 3-CNF formula \(\varphi\) has a satisfying assignment \(S\). Let \(A_t\) be the assignment after \(t\) steps and let \(X_t\) denote the number of propositional variables in which \(A_t\) agrees with \(S\). Following the same reasoning as in the 2-SAT case we have that

As with the 2-SAT algorithm, we can turn the process \(X\) into a Markov chain by changing the above inequalities into equalities, and the expected time for the resulting chain to reach state \(n\) is an upper bound for the expected time of the algorithm to find a satisfying valuation.

Again we have a one-dimensional random walk. But notice that in this case the particle is twice as likely to move away from state \(n\) as it is to move toward state \(n\). This greatly affects the expected time to reach the state \(n\). Let us write \(h_j\) for the expected number of steps to reach \(n\) when starting from state \(j\). Then we have the following system of equations:

Again this is a linear system in \(n+1\) unknowns, and we solve by first seeking a relationship between \(h_j\) and \(h_{j+1}\). Here we get that

The above bound shows that the expected number of flips to find \(S\) is at most \(O(2^n)\). This bound is useless since we can find \(S\) in \(2^n\) steps by exhaustive search. However we can significantly improve the performance of this procedure by incorporating random restarts into our search. A random truth assignment leads to a binomial distribution over the states of the Markov chain \(X\) centred around the state \(n/2\). Since the Markov chain has a tendency to move towards state \(0\), after running it for a little while we are better off restarting with a random distribution than continuing to flip literals. After a random restart, by Chernoff bounds, the current assignment differs from \(S\) is approximately \(n/2\) positions with high probability.

The algorithm below tries to find a satisfying assignment in \(N=O((4/3)^n \sqrt{n})\) phases, where each phase starts with a random restart and consists of \(3n\) literal flips. The exact constant \(N\) will be determined by the analysis below.

In this section we state a constructive existence theorem for stationary distributions, we give conditions under which the stationary distribution is unique and under which the distribution of \(X_t\) converges to the stationary distribution as \(t \rightarrow \infty\). First we need some preliminary notions.

In general \(h_{i,j}\) may be infinite. Certainly \(h_{i,j}=\infty\) if \(j\) is not reachable from \(i\) in the underlying graph, or, more generally, if \(i\) can reach a state \(k\) from which \(j\) is no longer reachable. Let us therefore restrict attention to Markov chains whose underlying graph consists of a single strongly connected component. We call such chains irreducible.

We can still have \(h_{i,j}=\infty\) in an irreducible chain. For example, it is not difficult to define an infinite-state irreducible Markov chain such that starting from state \(i\) the probability to reach \(j\) is less than one. The following example shows that we can even have \(h_{i,j}=\infty\) when the probability to reach \(j\) from \(i\) is one.

Consider the Markov chain with set of states \(\{1,2,3,\ldots\}\) and transition matrix \(Q\), where \(Q_{i,i+1}=i/(i+1)\) and \(Q_{i,1}=1/(i+1)\). Starting at state \(1\), the probability not to have returned to state \(1\) within \(t\) steps is

Thus we return to state \(1\) almost surely, but the expected return time is

However our focus is on finite Markov chains, and in a finite irreducible Markov chain the mean hitting time between any pair of states is always finite.

The next result states that a finite irreducible Markov chain has a unique stationary distribution. Note that irreducibility is necessary for uniqueness: for example, if \(P\) is the identity matrix then every distribution is stationary.

One interpretation of this theorem is that the stationary distribution represents a time average. On average the chain visits state \(j\) every \(h_{j,j}\) steps, and thus spends proportion of time \(\pi_j = 1/h_{j,j}\) in state \(j\). We might expect that the stationary distribution is also a space average, that is, that the distribution of \(X_t\) converges to \(\pi\) as \(t\) tends to infinity. However in general this need not be true. For example, if the transition matrix is \(Q = \left(\begin{array}{cc} 0 & 1 \\1 & 0 \end{array}\right)\), then the stationary distribution is \((1/2, 1/2)\), but the chain does not converge to this distribution from the starting distribution \((1,0)\). Each state is visited every other time step, which leads us to the notion of periodicity.

A Markov chain is irreducible and aperiodic if and only if there exists some power of the transition matrix \(Q\) with all entries strictly positive.

A Markov chain with transition matrix \(Q\) and stationary distribution \(\pi\) is called time-reversible if it satisfies the condition

for every state \(i\) and \(j\).

Time-reversibility is common and therefore the following theorem provides an easy way to compute the stationary distribution of many useful Markov chains. It’s proof is a direct application of the first Fundamental Theorem of Markov Chains.

Let \(G=(V,E)\) be a finite, undirected and connected graph. The degree of a vertex \(v \in V\) is the number \(d(v)\) of edges incident to \(v\). A random walk on \(G\) is a Markov chain modelling a particle that moves along the edges of \(G\) and which is equally likely to take any outgoing edge at a given vertex. Formally a random walk on \(G\) has set of states is \(V\) and for each edge \(\{u,v\} \in E\) the probability to transition from \(u\) to \(v\) is \(1/d(u)\).

Clearly if a connected graph with at least two nodes is bipartite, the period of every state is \(2\). Conversely, if the graph is not bipartite it must contain an odd simple cycle. Then, by connectivity, every node \(v\) is in an odd (not-necessarily simple) cycle. Since \(v\) trivially belongs to a 2-cycle, because every edge creates a 2-cycle, \(v\) has period 1.

The cover time of a random walk on a graph \(G\) is the maximum over all vertices \(v\) of the expected time for a walk starting at \(v\) to visit all other vertices.

We can use the bound on the cover time of random walks to design an impressively simple space-efficient algorithm for the fundamental problem of \(s-t\) connectivity. In this problem we are given an undirected graph with \(n\) nodes, not necessarily connected. We are also given two nodes \(s\) and \(t\) and we want to find out whether \(s\) and \(t\) are connected.

Note that there are no false positives in the algorithm above. If there is a path between \(s\) and \(t\) then the expected time for the random walk to go from \(s\) to \(t\) is at most the cover time \(4 V E \leq 2n^3\). By Markov’s inequality the algorithm outputs a path from \(s\) to \(t\) with probability at least \(1/2\).

The above algorithm only needs to store a constant number of vertex-addresses at any one time. It follows that we can decide reachability in undirected graphs in \(O(\log n)\) space using randomisation. Reingold showed the remarkable result that there is a deterministic algorithm that decides reachability in space \(O(\log n)\).

The term Monte Carlo method refers to algorithms that estimate a value based on sampling and simulation. Given an instance \(I\) of a function problem, let \(f(I)\in\mathbb{N}\) denote the desired output. For example, \(I\) could be a graph and \(f(I)\) the number of independent sets in \(I\).

We can generalise the above to get

A randomized approximation scheme for such a problem is a randomized algorithm that takes as input an instance \(I\) and an error tolerance \(\epsilon\) and outputs a value \(X\) such that

That is, the relative error is greater than \(\epsilon\) with probability at most \(1/3\). By repeating the experiment we can make the probability less than any constant.

Note that we allow an FPRAS to have running time polynomial in \(1/\epsilon\), which is in turn exponential in the length of the bit-wise representation of \(\epsilon\). The reason for not requiring time polynomial in \(\log 1/\epsilon\) is that for many NP-hard problems this is not possible, unless \(P=NP\).

Let \(\varphi \equiv C_1 \vee \cdots \vee C_t\) be a propositional formula in \textbf{disjunctive normal form (DNF)} over the set of variables \(x_1,\ldots,x_n\). For example,

The DNF counting problem asks to compute the number \(\#\varphi\) of truth assignments that satisfy \(\varphi\).

Since \(\overline \varphi\) is satisfiable if and only if \(\#\varphi<2^n\), the problem is NP-hard¹³. However we will see an FPRAS for the DNF counting problem. In fact we will consider a more general problem called the union-of-sets problem.

For a wide class of computational problems one can use an FPAUS for sampling solutions of the problem to develop an FPRAS for counting solutions of the problem. We illustrate this in the case of counting independent sets. It should be clear from this how to apply the technique to other problems of interest.

Consider a sample space \(\Omega\). Assume we have an edge relation \(E \subseteq \Omega \times \Omega\). We generate random samples from \(\Omega\) by taking something like a weighted random walk on \(\Omega\) using edges \(E\). We first consider the uniform distribution.

We prove a more general result that shows how to obtain an arbitrary distribution \(\pi\).

Observe that to apply this result one needs only to know the ratios \(\pi_x/\pi_y\) for any edge \((x,y)\in E\). Of course, if \((\Omega,E)\) is connected then these values determine \(\pi\), but in applications of interest it is typically infeasible to recover an explicit representation of \(\pi\) because \(\Omega\) is too large. Consider the following example:

As a running example, consider a Markov chain based on card shuffling. The set of states is the set of \(52!\) permutations of a deck of playing cards. From a given state the transition function picks a card uniformly at random and moves it to the top of the deck. Thus there are \(52\) transitions from each state, each with probability \(1/52\). It is clear that the the resulting chain is irreducible and aperiodic with the uniform distribution as its stationary distribution. In particular, the state distribution converges to the uniform distribution from any initial state. The main question is how quickly the chain converges to the stationary distribution, that is, how many shuffles are required for the distribution to be close to uniform. To address this question we have first to give a formal definition of the distance between two distributions.

The factor of \(1/2\) ensures that the variation distance is between \(0\) and \(1\). We have also the following characterisation in terms of the maximum difference in the probability of an event under the two distributions:

To illustrate the usefulness of the lemma, suppose we shuffle a deck of cards leaving the bottom card—say the ace of spades—unchanged. Let the resulting distribution on permutations of the set of cards be \(p_1\). Let \(p_2\) be the uniform distribution. Then we have \(||p_1-p_2|| \geq 51/52\) since if \(A\) is the event that the bottom card is the ace of spades, then \(p_1(A)=1\) and \(p_2(A)=1/52\).

Using the notion of variation distance, we formalise sampling as a computational problem. For simplicity we consider only uniform distributions. A sampling problem comprises a set of input instances \(I\) such that there is a sample space \(\Omega_I\) associated with each instance. For example, the instances could be graphs, with \(\Omega_I\) the set of colourings of a graph \(I\). The goal is to approximately sample from the uniform distribution \(U_I\) on \(\Omega_I\). A randomised sampling algorithm for the problem is required to input an instance \(I\) and parameter \(\epsilon\) and output a value in \(\Omega_I\) according to a distribution \(D_I\) such that \(||D_I - U_I|| \leq \epsilon\). This is exactly the definition of a fully polynomial almost uniform sampler (FPAUS), when the algorithm runs in polynomial time in \(I\) and \(\ln (1/\epsilon)\).

Let \(\{ M_t : t \in \mathbb{N}\}\) be a Markov chain with state space \(S\) and stationary distribution \(\pi\). We denote by \(p^t_x\) the state distribution at time \(t\) given that the chain starts in state \(x\). We define

to be the maximum variation distance between \(p^t_x\) and \(\pi\). Given \(\epsilon > 0\), the mixing time,

is the first time that the state distribution comes within variation distance \(\epsilon\) of the stationary distribution. It turns out¹⁴ that \(\Delta(t)\) is monotone decreasing, so that \(||p^t_x-\pi|| \leq \epsilon\) for all \(t \geq \tau(\epsilon)\).

We use the following notion to obtain bounds on the mixing time.

That is, a coupling is a Markov chain structure on the product such that the projection of the transition matrix on each component agrees with the transition matrix of the original chain.

One obvious coupling is to consider two copies of \(M_t\) operating independently in parallel having started from two different states \(x\) and \(y\), that is, define

However this example is of limited use for our purposes. Rather, motivated by the following lemma, we seek couplings in which the two copies of \(M_t\) make identical moves when they are in the same state, i.e., when the two copies come together they stay together.

• Algorithmic version of Lovász Local Lemma:
  • Mitzenmacher and Upfal, 2nd edition, 6.10 in second edition only
  • Ronitt Rubinfeld’s lecture
  • Terence Tao’s blog

An interactive proof for a language \(L\) is a protocol run by a verifier \(V\) and a prover \(P\). The question is whether the prover, who has unlimited computational power, can help the verifier, who has usually polynomial-time power, to decide whether \(x\in L\). For example, for Satisfiability, the prover needs only to provide a satisfying truth assignment. But for Unsatisfiability, no such certificate exists, unless NP=co-NP. But we will see that with randomisation and interaction, there is an interactive proof for Unsatisfiability.

• when \(x\in L\), we assume that there exists a honest prover, who can help the verifier (with probability \(2/3\)); when \(x\not\in L\), we assume that even if the prover is malicious, the verifier will not be fooled (with probability \(2/3\)).
• the total running time of the verifier must be polynomial; this means that the number of rounds is bounded by a polynomial
• the probabilities \(1/3-2/3\) are arbitrary; it turns out if we replace \(2/3\) with \(1\), we still get the same class.
• NP is a subset of IP; only the prover transmits
• randomisation is essential, otherwise the prover could precompute everything and send all the answers together

That IP is in PSPACE is the easy part: given an input \(x\), it is sufficient to be able to traverse the tree of all possible interactions, which can be done with polynomial space. The converse is a clever application of verifying polynomial identities. We will show the weaker result that #3SAT \(\in\) IP, where #3SAT is the counting version of 3SAT and asks for the number of satisfying truth assignments. More precisely, we will show that given a 3CNF formula \(\varphi\) and an integer \(k\), there is an interactive proof to verify that the number of satisfying truth assignments of \(\varphi\) is \(k\). We will also briefly discuss how to generalise the proof to PSPACE.

The proof of IP=PSPACE extends the above protocol to quantified Boolean formulas, that is, Boolean formulas with “exists” and “for all” quantifiers. The Satisfiability problem for these formulas is PSPACE-complete. There is a similar arithmetisation of such formulas: \(\exists x_i\) maps to \(\sum_{x_i=0}^1\) and \(\forall x_i\) maps to \(\prod_{x_i=0}^1\). Essentially, the only additionally difficulty in generalising the above protocol is to transform an arbitrary quantified Boolean formula to a special form so that the computations can be performed efficiently.

• Michel Goemans’ notes (Sections 4-6) http://www-math.mit.edu/~goemans/notes-online.ps