Count to sample

Hey all!

This week’s post is about an interesting relation between counting and sampling, motivated from an enlightening paper [MD02] by Prof. Martin Dyer. More specifically, the paper introduces dynamic programming as a technique to aid in approximate counting and uniform sampling using a dart throwing approach, however, this blog post is only about the example presented in the beginning of the paper where Prof. Dyer uses the count of the solutions to the 0-1 knapsack problem to sample from the set of these solutions uniformly at random in expected polynomial time (in the number of variables). You are encouraged to read [WK16] to learn more about the knapsack problem. I hope you like this post 🙂

So, the problem at hand is to be able to produce a solution to a given 0-1 knapsack problem which has been sampled uniformly at random from the set of all such solutions. Why would one require to do so? Well, among the many applications of the ability to sample uniformly at random from combinatorial sets, the one I encounter the most is in computer simulations and producing approximations. It is well known that the general knapsack problem is hard to solve, so counting the number of solutions will only be harder, let alone the problem of sampling one of these solutions. Hence, if we can approximate the count using some efficient technique, (almost) uniform sampling will become readily available. How?

Well, to answer this question, let’s first formalize the problem a little bit. The 0-1 knapsack problem can be written as the inequality \sum_{j=1}^n a_j x_j \leq b for x_i \in \{0,1\} for all i. Here, we assume that 0 \leq a_1 \leq \dots \leq a_n \leq b are all integers. Note that any single linear inequality in 0-1 variables with rational coefficients can be written in this form [MD02, WL75]. Denote by S the set of all solutions to this inequation. Then, the problem at hand is to sample uniformly at random from S. So, back to the question. What if we don’t know |S|?

One way of sampling from S without any knowledge of its size is to exploit the fact that we can efficiently check if a given assignment of 0’s and 1’s to our variables satisfies the inequality above, i.e. whether a given 0-1 assignment is in S or not. This is crucial for obvious reasons, most important of which is that we will rely on this capability to accept only those assignments that lie in S and reject others in a technique popularly known as rejection sampling. Start with randomly producing a 0-1 assignment of the variables and accept it if it satisfies the inequality and repeat otherwise. Simple, but not always efficient. Why?

Suppose S is very small, say O(1). Then, the probability of acceptance in one iteration when we have n variables is O(1/2^n), which is o(1). Hence, in expectation, exponentially many rejections will happen before the first assignment is sampled, making the algorithm extremely slow. Can we do better? Well, let’s try Prof. Dyer’s approach.

The main idea behind the technique I am now going to talk about is eliminating the rejections above and directly sampling a solution to the problem. Since each solution must be sampled with probability 1/|S|, it will be good to know |S|. Let us say we do. Now, fix a variable, say x_3. What is the probability that x_3 = 0 in a satisfying assignment to the problem? Well, since we are sampling uniformly at random from S, this probability is equal to the ratio of the number of solutions in which x_3 = 0 to |S|. Hence, it will be good to know the number of solutions in which x_3 = 0 after which the problem becomes trivial. So, how to compute this number?

[Enter dynamic programming.]

Let F(r,s) be the number of solutions to inequality \sum_{j=1}^r a_j x_j \leq s, where a_j‘s and x_j‘s are the same as above. Clearly, we can write F(1,s) = 1 if s < a_1 and 2 otherwise. Also, observe that |S| = F(n,b). To recursively compute F(r,s), note that if we set x_r = 0, then we have the inequality \sum_{j=1}^{r-1} a_j x_j \leq s, whose number of solutions is F(r-1,s). However, if we set x_r = 1, then we have the inequality \sum_{j=1}^{r-1} a_j x_j \leq s-a_r, whose number of solutions is F(r-1,s-a_r). Thus, we can write F(r,s) = F(r-1,s) + F(r-1,s-a_r) and solve the dynamic program recursively in O(nb) time.

We are not quite done yet. We still do not know the number of solutions in which x_3 = 0. At least not directly. However, this is where the genius in [MD02] shines. We sample an assignment from S as follows. With probability F(n-1,b)/F(n,b), set x_n = 0 and with probability F(n-1,b-a_n)/F(n,b), set x_n = 1. Once we have this done, use the dynamic program above to recursively set the values of the other variables until we are done. The claim here is that the resulting assignment is a valid solution to the inequality and is sampled uniformly at random from S. How? Here is why.

To see why the resulting assignment is in S is easy. Once we assign the value to a variable, the dynamic program lets us sample the value of the next variable (or the previous one, whichever way you see it) based on the number of solutions in which the next (previous) variable is assigned a particular value. In other words, say we just assigned the value to x_4. Then, if x_3 = 1 is not a valid solution, the dynamic program will take care of it by itself.

To see why the resulting assignment is uniformly random, let us compute the probability p that a solution \{ x_1 = v_1, \dots, x_n = v_n \} is produced for some v_i \in \{0,1\} such that \sum_{j=1}^n a_j v_j \leq b. We can write p = Pr \{  x_n = v_n \mid x_1 = v_1, \dots, x_{n-1} = v_{n-1} \} Pr \{x_1 = v_1, \dots, x_{n-1} = v_{n-1} \}. Since the assignment to x_n is independent of other variables, we can write this as p = \frac{F(n-1,b-a_n)v_n + F(n-1,b)(1-v_n)}{F(n,b)}Pr \{x_1 = v_1, \dots, x_{n-1} = v_{n-1} \}. Now, we can expand Pr \{x_1 = v_1, \dots, x_{n-1} = v_{n-1} \} similarly as Pr \{x_{n-1} = v_{n-1} \mid x_1 = v_1, \dots, x_{n-2} = v_{n-2} \} Pr \{x_1 = v_1, \dots, x_{n-2} = v_{n-2} \}. Again, the assignment of x_{n-1} is independent of all others and hence, Pr \{ x_{n-1} = v_{n-1} \} = \frac{F(n-2,b)(1-v_{n-1}) + F(n-2,b-a_{n-1})v_{n-1}}{F(n,b)} + \frac{F(n-2,b-a_n)(1-v_{n-1}) + F(n-2,b-a_n-a_{n-1})v_{n-1}}{F(n,b)}. Keep going on like this to obtain that the probability p = 1/F(n,b), which is what we wanted to prove.

Hence, we just saw a technique using counting and dynamic programming that allows us to sample exactly from a set of objects which would be difficult to sample from in general. This technique can be extended to many other combinatorial problems, however, the dynamic program to count may not be straight forward. However, it should now be clear that if exact counts are replaced by approximate counts (through some technique), then uniform sampling becomes almost uniform sampling. An important application of this is approximate counting of the number of perfect matchings in a given graph and then sampling (almost) uniformly at random one of these matchings.

The reverse direction is, however, pretty straight forward. If we knew how to sample, we can count easily. However, an exact count may not be possible using this approach, but we can count to a precision that is arbitrarily close to the exact count by using a technique similar to rejection sampling.

I hope this post was helpful in understanding this fascinating connection between sampling and counting of combinatorial objects. It is a huge area of research and lots of interesting applications have been explored. I am trying to learn more in this area and hope to come up with more fascinating examples in the future posts. Until then, ciao!

References

[MD02] Dyer, Martin. “Approximate counting by dynamic programming.” In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pp. 693-699. ACM, 2003.

[WK16] https://en.wikipedia.org/wiki/Knapsack_problem

[WL75] Wolsey, Laurence A. “Faces for a linear inequality in 0–1 variables.” Mathematical Programming 8.1 (1975): 165-178.

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s