2/26 15-852 Randomized algorithms Approximating the Permanent, contd. Note: time to start meeting with me to discuss your class presentations. (actually, if anyone wants to do one next wednesday, that would be a good time for it) ========================================================================== Last time, got to a point where all we had to do was show that a certain Markov chain had high conductance (the appropriatekind of expansion for Markov chains). N = number of states in the Markov chain. n = number of vertices in original bipartite graph, and m = # edges. * Capacity(S) C_S = sum_{i in S} pi_i. (prob of being in S according to pi. --> measure of size of S) * flow(S) = sum_{i in S, j not in S} w_ij, where w_ij = (pi_i)*(p_ij) = prob of being on edge i->j in pi. (measure of # edges leaving S). * Conductance Phi = min_{S: C_S <= 1/2} Phi_S Phi_S = flow(S)/capacity(S). E.g., in our case, pi_i = 1/N, p_ij = 1/2m, so w_ij = 1/(2mN). Phi_S = (1/2m)*(#edges leaving S)/|S| Show high conductance / edge expansion via "canonical path method". * For every pair of states (u,v), we'll define a canonical path from u to v. * Show that the number of paths through any given transition is at most bN. * This means the number of edges leaving S (|S|<= N/2) is at least |S|(N-|S|)/(bN) >= |S|/2b, and (# edges leaving S)/|S| >= 1/2b. =========================================================================== Illustrate by showing that boolean cube has edge-expansion (random walk has high conductance). * State space is {0,1}^n, random walk: with prob 1/2 stay put, with prob 1/2 flip a random bit. (This is a complicated way to get to a random point). Or, just think of as the natural graph defined on the boolean cube. * N = 2^n, degree = n = log(N). * For two vertices (v,w), define path P(v,w): flip bits that differ from left to right. Claim: no transition is contained in more than N/2 canonical paths. Proof: (ASK). Think of some transition T: 01011010 -> 01011110 What paths can possibly include this transition? Must be from some point of the form: *****010 to some point of the form: 010111** Number of such pairs is at most (2^n)/2 = N/2. (Another way to think of this: for a given transition T, for each path (v,w) using T, we can associate a single state u (u = value assigned to the *'s in v and w) such that no two different paths have the same associated u.) So, all sets S of size at most N/2 have (# edges leaving S)/|S| >= 1. So, conductance Phi_S = sum(pi_i * p_ij) / sum(pi_i) >= 1/(2n) (given that you're at a random point in S, you have prob at least 1/2n of getting out.) ========================================================================== Now, back to the Markov chain for the Permanent. Need to specify canonical path between two states s and t. In fact, we'll only need to worry about the case that s and t are both perfect matchings. We can then handle the near-perfect matchings as follows: We argued earlier that (given our condition of the min degree at least n/2) we can associate every near-perfect matching to some perfect matching such that no perfect matching has more than n+n^2 near-perfect matchings associated to it. So, if s and/or t is a near-perfect matching, we can just first move to the perfect matching associated to s, then take the canonical path to the perfect matching associated to t, and then go to t. The canonical path is just the following: look at the symmetric difference of s and t. This is just a collection of disjoint cycles. To go from s to t, we will "unwind" each of these cycles in some canonical order -- say, doing the cycle containing the vertex of least index first, and so on. "Unwinding" a cycle corresponds to doing one Reduce operation, then a sequence of Rotates, and then finally one Augment. We can just pick some arbitrary canonical starting point and direction for this unwinding (say, Reduce the edge containing the vertex of least index, and then Rotate in the direction of that vertex). Theorem: At most N canonical paths between perfect matchings use any given transition T. (Note: this implies that at most O(n^4*N) canonical paths including both perfect and near-perfect matchings include T, which implies that the conductance Phi is at least O(1/(n^6*N)).) Proof: We'll show that given a transition T (say T is the transition u-->v), for any pair (s,t) whose path goes through T, we can associate a perfect or near-perfect matching p, such that given p and T we can recover s and t. I.e., our mapping is 1-1. This means that there can be at most N such pairs (s,t). The easier cases are when T is a Reduce or Augment transition. Formally, if T is Reduce, then p = s XOR t XOR u, and if T is Augment then p = s XOR t XOR v. Informally, p is just the portion of (s U t) missing from (u U v) (where we've included the edges where s=t just to make p into a perfect matching). Given p and T, it's easy to see that we can recover (s U t). We can then split this into s and t by using the canonical ordering. The rotate case is slightly more complicated since the portion of (s U t) missing from (u U v) (formally: s XOR t XOR (u U v)) is not a matching: it has one vertex of degree 2. But, all we have to do is to remove the edge (of s) that was the initial edge removed in the Reduce operation for this cycle. Then, when we reconstruct, we will have all of (s U t), except for this edge. But, that's OK, because when we see the path corresponding to the cycle minus this edge, we will know that we can just reconstruct the cycle by connecting together the two endpoints of the path. So, that does it. ========================================================================== Random sampling from convex sets -------------------------------- Similar problem: how to sample randomly from convex set (e.g., intersection of halfspaces) in high dimension. For instance, say you want to solve some linear program without an objective function (just find a feasible solution) but you want it to be a random feasible solution. Or, say you have some data and you want a *random* linear separator. Can use to compute the volume of a convex set. Solve in a similar way: set up a random walk and show that it's rapidly mixing. A key lemma: [Theorem 2.1 of Lovasz-Simonovitz] Let T be a convex set in R^n partitioned into two sets S and T - S by an (n-1)-dimensional surface with surface area ((n-1)-dimensional volume) a. Then: a >= (1/diam(T)) * min[vol(S),vol(T - S)] where diam(T) is the maximum distance between two points in T. This is essentially a statement about conductance.