Big Red Bits

Bounded Degree Spanning Tree and an Uncrossing Lemma

November 17th, 2009 renatoppl No comments

I’ve been reading about the Bounded Degree Spanning Tree problem and I thought of writing some of what I am learning here. It illustrates a beautiful techique called Iterated Rounding and uses the combinatorial idea of uncrossing. I’ll try to give a high-level idea of the argument and give references on the details. The first result of this kind was given by Goemans (although there were previous results with weaker guarantees) by Goemans in Minimum Bounded Degree Spanning Trees, but the result based on iterated rounding and a subsequent improvement are due to Singh and Lau in a serie of papers. A main reference is Approximating minimum bounded degree spanning trees to within one of optimal.

The problem of bounded degree spanning tree is as follows: consider a graph ${G = (V,E)}$ with edge weights and we for some nodes ${W \subseteq V}$ a degree bound ${b_v, v \in W}$ . We want to find, among the spanning trees for which the degree of ${v}$ is ${\leq b_v}$ the one with minimum cost. It is clearly a hard problem, since taking all weights equal to ${1}$ and ${b_v = 2}$ for all nodes is the Hamiltonian Path problem, which is NP-complete. We will get a different kind of approximation. Let OPT be the optimal solution: we will show an algorithm that gives a spanning tree of cost ${\leq OPT}$ such that each node ${v}$ has degree ${\leq b_v + 2}$ (this can be improved to ${b_v + 1}$ with a more sofisticated algorithm, also based on Iterated Rounding).

As always, the first step to design an approximation algorithm is to relax it to an LP. We consider the following LP:

$\displaystyle \left. \begin{aligned} & \min \sum_{e\in E} c_e x_e \text{ s.t. } \\ & \qquad \left. \begin{aligned} & \sum_{e \in E} x_e = \vert V \vert - 1 \\ & \sum_{e \in E(S)} x_e \leq \vert S \vert - 1 & \forall S \subseteq V, \vert S \vert \geq 2 \\ & \sum_{e \in \delta(v)} x_e \leq b_v & \forall v \in W\\ & x_e \geq 0 & \forall e \in E \end{aligned} \right. \end{aligned} \right.$

The first constraint expresses that in a spanning tree, there are at most ${\vert V \vert - 1}$ edges, the second prevent the formation of cycles and the third guarantees the degree bounds. For ${W = \emptyset}$ we have the standard Minimal Spanning Tree problem and for this problem the polytope is integral. With the degree bounds, we lose this nice property. We can solve this LP using the Ellipsoid Method. The separation oracle for the ${\sum_{e \in E(S)} x_e \leq \vert S \vert - 1}$ is done by a flow computation.

Iterated Rounding

Now, let’s go ahead and solve the LP. It would be great if we had an integral solution: we would be done. It is unfortunately not the case, but we can still hope it is almost integral in some sense: for example, some edges are integral and we can take them to the final solution and recurse the algorithm on a smaller graph. This is not far from truth and that’s the main idea of the iterated rounding. We will show that the support of the optimal solution ${E(x) = \{e \in E; x_e > 0\}}$ has some nice structure. Consider the following lemma:

Lemma 1 For any basic solution ${x}$ of the LP, either there is ${v}$ with just one incident edge in the support ${E(x)}$ or there is one ${v \in W}$ such that that at most ${3}$ edges are incident to it.

If we can prove this lemma, we can solve the problem in the following way: we begin with an empty tree: then we solve the LP and look at the support ${E(x)}$ . There are two possibilities according to the lemma:

If there is one node ${v}$ with just one edge ${e = (u,v)}$ incident to it in the support, we add it to the tree, remove ${v}$ from ${V}$ , decrease ${b_u}$ , make ${E = E(x)}$ (the trick is to remove in each iteration edges from ${E}$ that are not in the support. Clearly, removing those edges doesn’t hurt the objective value) and run the algorithm again. Notice that the LP called in the recursion has value less or equal then the actual LP ${- c_e}$ . So if by induction we get a spanning tree respecting the new degree bounds plus two and value less or equal than the new LP value, we can just add ${e}$ and we have a solution with value less or equal than the one of the original LP respecting the degree bounds plus two.
Otherwise, there is one node ${v \in W}$ that has degree ${3}$ in the support. So, we just remove that degree bound on that vertex (i.e. remove ${v}$ from ${W}$ ), make ${E = E(x)}$ (again,eliminate the edges not in the support) and run the algorithm again. Clearly, if one node is still in ${W}$ , it has ${b_v \geq 1}$ , since there are only three edges in the support, there will be for the rest of the computation, just three edges incident to it, so there will be at most three edges more incident to it. So it will exceed its original ${b_v}$ by at most ${2}$ .

The algorithm eventually stops, since in each iteration we have less edges or less nodes in ${W}$ and the solution is as desired. The main effort is therefore to prove the lemma. But before, let’s look at the lemma: it is of the following kind: “any basic solution of the LP has some nice properties, which envolve having a not too big (at least in some point) support”. So, it involves proving that the support is not too large. That is our next task as we are trying to prove the lemma. And we will be done with:

Theorem 2 The algorithm described above produces a spanning tree of cost ${\leq Z^*}$ (the LP values and therefore ${\leq OPT}$ )in which each node ${v \in W}$ has degree ${\leq b_v + 2}$ .

Bounding the size of the support

We would like now to prove some result like the Lemma above: that in the solution of the LP we have either one ${v}$ with degree ${1}$ in ${E(x)}$ or we have a node in ${W}$ with degree ${\leq 3}$ . First, we suppose the opposite, that ${(V,E(x))}$ has all the nodes with degree ${\geq 2}$ and all the nodes in ${W}$ have degree ${\geq 4}$ . This implies that we have a large number of edges in the support. From the degrees, we know that:

$\displaystyle \vert E(x) \vert \geq \frac{1}{2} \left( 2( \vert V \vert - \vert W \vert ) + 4 \vert W \vert \right) = \vert V \vert + \vert W \vert$

We want to prove that the support ${\vert E(x) \vert}$ of the LP can’t be too large. The first question is: how to estimate the size of the support of a basic solution. The constraints look like that:

bst_fig1

A basic solution can be represented by picking ${\vert E \vert}$ rows of the matrix and making them tight. So, if we have a general ${Ax \leq b}$ LP, we pick some submatrix ${A'}$ of ${A}$ which is ${n \times n}$ and the basic solution is just ${x = A'^{-1} b'}$ . The lines of matrix ${A'}$ can be of three types: they can be ${\chi_S}$ , which are corresponding to ${\sum_{e \in E(S)} x_e \leq \vert S \vert - 1}$ , ${\chi_v}$ that correspond to ${\sum_{e \in \delta(v)} x_e \leq b_v}$ or ${\delta_e}$ corresponding to ${x_e \geq 0}$ . There are ${\vert E \vert}$ vectors in total. The size of the support ${E(x)}$ is smaller or equal the number of rows of the form ${\chi_S, \chi_v}$ in the basic solution. Therefore the idea to bound the size of the support is to prove that “all basic solutions can be represented by a small number of rows in the form ${\chi_S, \chi_v}$ . And this is done using the following:

Lemma 3 Assuming ${E = E(x)}$ , for any basic solution ${x}$ , there is ${Z \subseteq W}$ and a family ${\mathcal{S}}$ of sets such that:

The restrictions correspondent to ${S \in \mathcal{S}}$ and ${v \in Z}$ are tight for ${x}$

${\{ \chi_S; S \in \mathcal{S} \} \cup \{ \chi_v; v \in Z \}}$ is an independent set

${\vert \mathcal{S} \vert + \vert Z \vert = \vert E(x) \vert}$

${\mathcal{S}}$ is a laminar family

The first 3 items are straightfoward properties of basic solutions. The fourth one, means that for two sets ${S_1, S_2 \in \mathcal{S}}$ , one of three things happen: ${S_1 \subseteq S_2}$ , ${S_2 \subseteq S_1}$ or ${S_1 \cap S_2 = \emptyset}$ . Now, we based on the previous lemma and in the following result that can be easily proved by induction, we will prove Lemma 1.

Lemma 4 If ${\mathcal{S}}$ is a laminar family over the set ${V}$ where each set ${S \in \mathcal{S}}$ contains at least ${2}$ elements, then ${\vert \mathcal{S} \vert \leq \vert V \vert - 1}$ .

Now, the proof of Lemma 1 is easy. Let’s do it and then we come back to prove Lemma 3. Simply see that ${\vert E(x) \vert = \vert \mathcal{S} \vert + \vert Z \vert \leq \vert V \vert - 1 + \vert W \vert}$ what contradicts ${\vert E(x) \vert \geq \vert V \vert + \vert W \vert}$ .

Uncrossing argument

And now we arrive in the technical heart of the proof, which is proving Lemma 3. This says that given any basic solution, given any feasible solution, we can write it as a “structured” basic solution. We start with any basic feasible solution. This already satifies (1)-(3), then we need to change that solution to satisfy condition (4) as well. We need to get rid crossing elements, i.e., ${S,T \in \mathcal{S}}$ in the form:

bst_fig2

We do that by the means of the:

Lemma 5 (Uncrossing Lemma) If ${S}$ and ${T}$ are intersecting and tight (tight in the sense that their respective constraint is tight), then ${S \cup T}$ and ${S \cap T}$ are also tight and:

$\displaystyle \chi_{S \cap T} + \chi_{S \cup T} = \chi_S + \chi_T$

Which corresponds to that picture:

bst_fig3

Proof: First, we note that ${x(E(S))}$ is a supermodular function, i.e.:

$\displaystyle x(E(S)) + x(E(T)) \leq x(E(S \cap T)) + x(E(S \cup T))$

We can see that by case analysis. Every edge appearing in the left side appears in the right side with at least the same multiplicity. Notice also that it holds with strict inequality iff there are edges from ${S\setminus T}$ to ${T \setminus S}$ . Now, we have:

$\displaystyle \begin{aligned} (\vert S \vert - 1) + (\vert T \vert - 1) & = (\vert S \cap T \vert - 1) + (\vert S \cup T \vert - 1) \geq \\ & \geq x(E(S \cap T)) + x(E(S \cup T)) \geq \\ & \geq x(E(S)) + x(E(T)) = (\vert S \vert - 1) + (\vert T \vert - 1) \end{aligned}$

where the first relation is trivial, the second is by feasibility, the third is by supermodularity and the lastone is by tightness. So, all hold with equality and therefore ${S \cap T}$ and ${S \cup T}$ are tight. We also proved that:

$\displaystyle x(E(S \cap T)) + x(E(S \cup T)) = x(E(S)) + x(E(T))$

so there can be no edge from ${S\setminus T}$ to ${T \setminus S}$ in ${E(x)}$ and therefore, thinking just of edges in ${E(x)}$ we have:

$\displaystyle \chi_{S \cap T} + \chi_{S \cup T} = \chi_S + \chi_T$

$\Box$

Uncrossing arguments are found everywhere in combinatorics. Now, we show how the Uncrossing Lemma can be used to prove Lemma 1:

Proof: Let ${x}$ be any basic solution. It can be represented by a pair ${(Y, \mathcal{C})}$ where ${Y \subseteq W}$ and ${\mathcal{C}}$ is a family of sets. We will show that the same basic solution can be represented by ${(Y, \mathcal{L})}$ where ${\mathcal{L}}$ is a laminar family and has the same size of ${\mathcal{C}}$ .

Let ${\mathcal{S}}$ be all sets that are tight under ${x}$ and ${\mathcal{L}}$ a maximal laminar family of tights sets in ${\mathcal{S}}$ , such that ${\{\chi_S; S \in \mathcal{L} \} \cup \{\chi_v; v \in Z \}}$ are independent. I claim that ${\vert \mathcal{L} \vert = dim(span(\mathcal{S}))}$ .

In fact, suppose ${\vert \mathcal{L} \vert < dim(span(\mathcal{S}))}$ , then there are sets of ${\mathcal{S}}$ we could add to ${\mathcal{L}}$ without violating independence – the problem is that those sets would cross some set. Pick such ${S \in \mathcal{S}}$ intersecting fewer possible sets in ${\mathcal{L}}$ . The set ${S}$ intersects some ${T \in \mathcal{L}}$ . Since both are tight we can use the Uncrossing Lemma and we get:

$\displaystyle \chi_{S \cap T} + \chi_{S \cup T} = \chi_S + \chi_T$

since ${\chi_S \notin span(\mathcal{L})}$ , we can’t have simultaneously ${\chi_{S \cap T}}$ and ${\chi_{S \cup T}}$ in ${span(\mathcal{L})}$ . Let’s consider two cases:

${\chi_{S \cap T} \notin span(\mathcal{L})}$ , then ${S \cap T \in span(\mathcal{S})}$ is in ${span(\mathcal{S}) \setminus span(\mathcal{L})}$ and intersects fewer sets of ${\mathcal{L}}$ than ${S}$ , since all sets that intersect ${S \cap T}$ in ${\mathcal{L}}$ must intersect ${S}$ as well (since no set can cross ${T}$ ).
${\chi_{S \cup T} \notin span(\mathcal{L})}$ , then ${S \cup T \in span(\mathcal{S})}$ is in ${span(\mathcal{S}) \setminus span(\mathcal{L})}$ and intersects fewer sets of ${\mathcal{L}}$ than ${S}$ , since all sets that intersect ${S \cup T}$ in ${\mathcal{L}}$ must intersect ${S}$ .

In either case we have a contradiction, so we proved that ${\vert \mathcal{L} \vert = dim(span(\mathcal{S}))}$ . So we can generate all the space of tight sets with a laminar family. $\Box$

And this finishes the proof. Let’s go over all that we’ve done: we started with an LP and we wanted to prove that the support of each solution was not too large. We wanted that because we wanted to prove that there was one node with degree one in the support or a node in ${W}$ with small ( ${\leq 3}$ ) degree. To prove that the degree of the support is small, we show that any basic solution has a representation in terms of a laminar family. Then we use the fact that laminar families can’t be very large families of sets. For that, we use the celebrated Uncrossing Lemma.

Note: Most of this is based on my notes on David Williamson’s Approximation Algorithms class. I spent some time thinking about this algorithm and therefore I decided o post it here.

Categories: theory Tags: approximation algorithms, combinatorics, iterated rounding, linear algebra, linear programming, uncrossing

Looking at probability distributions

November 12th, 2009 renatoppl No comments

I’ve been taking two classes in probability this semester and in those I saw the proofs of a lot of interesting theorems which I knew about previously but I have never seen the proof, as the Central Limit Theorem, the Laws of Large Numbers and so on… Also, some theory which is looks somewhat ugly in the undergrad courses becomes very clear with the proper formal treatment. Today I was thinking what was the main take-home message that a computer scientist could take from those classes and. at ;east for me, this message is the various ways of looking to probability distributions. I’ve heard about moments, Laplace transform, Fourier transform and other tools like that, but I never realized before their true power. Probably still today, most of their true power is hidden from me, but I am starting to look at them in a different way. Let me try to go over a few examples of different ways we can look at probability distributions and show cases where they are interesting.

Most of ways of looking at probability distributions are associated with multiplicative system: a multiplicative system ${Q}$ is a set of real-valued functions with the property that if ${f_1, f_2 \in Q}$ then ${f_1 \dot f_2 \in Q}$ . Those kinds of sets are powerful because of the Multiplicative Systems Theorem:

Theorem 1 (Multiplicative Systems Theorem) If ${Q}$ is a multiplicative system, ${H}$ is a linear space containing ${1}$ (the constant function ${1}$ ) and is closed under bounded convergence, then ${Q \subseteq H}$ implies that ${H}$ contains all bounded ${\sigma(Q)}$ -measurable functions.

The theorem might look a bit cryptic if you are not familiar with the definitions, but it boils down to the following translation:

Theorem 2 (Translation of the Multiplicative Systems Theorem) If ${Q}$ is “general” multiplicative system, ${X}$ and ${Y}$ are random variable such that ${\mathop{\mathbb E}{f(X)} = \mathop{\mathbb E}{f(Y)}}$ for all ${f \in Q}$ then ${X}$ and ${Y}$ have the same distribution.

where general excludes some troublesome cases like ${Q = \{1\}}$ or all constant functions, for example. In technical terms, we wanted ${\sigma(Q) = \sigma\{f^{-1}((-\infty,a]); a\in {\mathbb R}, f \in Q \}}$ to be the Borel ${\sigma}$ -algebra. But let’s not worry about those technical details and just look at the translated version. We now, discuss several kinds of multiplicative systems:

The most common description of the a random variable is by the cummulative distribution function ${F(u) = P\{X \leq u\}}$ . This is associated with ${Q = \{ 1_{(-\infty,u]}(x); u \in {\mathbb R} \}}$ notice that simply ${F(u) = \mathop{\mathbb E}{1_{(-\infty,u]}}}$ .
We can characterize a random variable by its moments: the variable ${X}$ is characterized by the set ${M_n = \int_{\mathbb R} x^n \mu_X(dx)}$ . Given the moemnts ${M_1, M_2, \hdots}$ , the variable is totally characterized, i.e., if two variables have the same moments, then they have the same distribution by the Multiplicative Systems Theorem. This description is associated with the system ${Q = \{x^n; n = 1, 2, \hdots\}}$
Moment Generating Function: If ${X}$ is a variable that assumes only integer values, we can describe the it as ${p_0, p_1, p_2, \hdots}$ , where ${p_n = P\{ X = n \}}$ . An interesting way of representing those probabilities is as the moment generating function ${\psi_X(z) = \mathop{\mathbb E}{z^X} = \sum_{n=0}^\infty p_n z^n}$ . This is associated with the multiplicative system ${Q = \{z^x, 0 \leq z < 1\}}$ .Now suppose we are given two discrete independent variables ${X}$ and ${Y}$ . What do we know about ${X+Y}$ . It is easy to know its expectation, its variance, … but what about more complicated things? What is the distribution of ${X+Y}$ ? Moment generating functions answer this question very easily, since:
$\displaystyle \psi_{X+Y} (z) = \mathop{\mathbb E} [z^{X+Y}] = \mathop{\mathbb E} [z^{X}] \cdot \mathop{\mathbb E}[z^{Y}] = \psi_X(z) \cdot \psi_Y(z)$

If we know moment generating functions, we can calculate expectation very easily, since ${\mathop{\mathbb E}[X] = \psi'_X(1)}$ . For example, suppose we have a process like that: there is one bacteria in time ${t = 0}$ . In each timestep, either this bacteria dies (with probability ${p_0}$ ), continues alive without reproducing (with probability ${p_1}$ or has ${k}$ offsprings (with probability ${p_{1+k}}$ ). In that case ${\sum_0^\infty p_n = 1}$ . Each time, the same happens, independently with each of the bacteria alive in that moment. The question is, what is the expected number of bacteria in time ${t}$ ?

It looks like a complicated problem with just elementary tools, but it is a simple problem if we have moment generating functions. Just let ${X_{ti}}$ be the variable associated with the ${i^{th}}$ bacteria of time ${t}$ . It is zero if it dies, ${1}$ if it stays the same and ${k+1}$ if it has ${k}$ offsprings. Let also ${N_t}$ be the number of bacteria in time ${t}$ . We want to know ${\mathop{\mathbb E} N_t}$ . First, see that:

$\displaystyle N_t = \sum_{i=1}^{N_{t-1}} X_{ti}$

Now, let’s write that in terms of moment generating functions:

$\displaystyle \psi_{N_t}(z) = \mathop{\mathbb E}{z^{X_{t1} + \hdots + X_{tN_t}}} = \sum_{k=0}^\infty P\{N_{t-1} = k\} \cdot \mathop{\mathbb E}[z^{X_{t1} + \hdots + X_{tN_t}} \vert N_t = k]$

which is just:

$\displaystyle \psi_{N_t}(z) = \sum_{k=0}^\infty P\{N_{t-1} = k\} \cdot \mathop{\mathbb E}[z^{X_{t1} + \hdots + X_{tk}}] = \sum_{k=0}^\infty P\{N_{t-1} = k \} \cdot \psi_X (z)^k$

since the variables are all independent and identically distributed. Now, notice that:

$\displaystyle \psi_{N_{t-1}}(z) = \sum_{k=0}^\infty P\{N_{t-1} = k\} \cdot z^k$

by the definition of moment generating function, so we effectively proved that:

$\displaystyle \psi_{N_{t}}(z) = \psi_{N_{t-1}}(\psi_X(z)) = \psi_X \psi_X \hdots \psi_X(z)$

We proved that ${\psi_{N_{t}}(z)}$ is just ${\psi(z)}$ iterated ${t}$ times. Now, calculating the expectation is easy, using the fact that ${\psi_X(1) = 1}$ and ${\psi'_X(1) = \mathop{\mathbb E} X}$ . Just see that: ${\mathop{\mathbb E} N_t = \psi_{N_{t}}'(1) = \psi_{N_{t-1}}'(\psi_X(1)) \cdot \psi'_X(1) = \psi_{N_{t-1}}'(1) \cdot \mathop{\mathbb E} X }$ . Then, clearly ${\mathop{\mathbb E} N_t = (\mathop{\mathbb E} X)^t}$ . Using similar technique we can prove a lot more things about this process, just by analyzing the behavior of the moment generating function.
Laplace Tranform: Now, moving to continuous variables, if ${X}$ is a continuous non-negative variable we can define its Laplace tranform as: ${\phi_X(u) = \mathop{\mathbb E} [e^{u X}] = \int_0^\infty e^{ux} \mu_X(dx)}$ , where ${\mu_X(dx)}$ stands for the distribution of ${X}$ , for example, ${\rho_X(x) dx}$ . This is associated with the multiplicative system ${Q = \{e^{ux}; u \geq 0\}}$ . Again, by the Multiplicative Systems Theorem, if ${\phi_X = \phi_Y}$ , then the two variables have the same distribution. The Laplace tranform has the same nice properties as the Moment Generating Function, for example, ${\phi_{X+Y}(u) = \mathop{\mathbb E}[e^{(X+Y)u}] = \mathop{\mathbb E}[e^{Xu}] \cdot \mathop{\mathbb E}[e^{Yu}] = \phi_X(u) \cdot \phi_Y(u)}$ .And it allows us to do similar tricks than the one I just showed for Moment Generating Functions. One common trick that is used, for example, in the proof of Chernoff bounds is, given independent non-negative random variables:
$\displaystyle P\left\{\sum_i X_i > u\right\} = P\left\{e^{\sum_i X_i} > e^u\right\} \leq \frac{\mathop{\mathbb E}[e^{\sum_i X_i} ]}{e^u} = \frac{\prod_i \mathop{\mathbb E}[e^{X_i} ]}{e^u}$

where we also used Markov Inequality: ${\mathop{\mathbb E}[X] \geq \beta P\{X \geq \beta\}}$ . Passing to the Laplace transform is the main ingredient in the Chernoff bound and it allows us to sort of “decouple” the random variables in the sum. There are several other cases where the Laplace transform proves itsself very useful and turns things that looked very complicated when we saw in undergrad courses into simple and clear things. One clear example of that is the motivation for the Poisson random variable:

If ${T_i}$ are independend exponentially distributed random variables with mean ${\lambda}$ , then ${\rho_{T_i}(t) = \lambda e^{- \lambda t}}$ . An elementary calculation shows that its laplace transform is ${\phi_{T_i}(u) = \frac{\lambda}{\lambda+u}}$ . Let ${S_n = T-0 + T_1 + T_2 + \hdots + T_n}$ , i.e., the time of the ${(n+1)^{th}}$ arrival. We want to know what is the distribution of ${S_n}$ . How to do that?

$\displaystyle \phi_{S_n}(u) = \mathop{\mathbb E}[e^{u(T_0 + \hdots + T_n)}] = \phi_T(u)^{n+1} = \left( \frac{\lambda}{\lambda+u} \right)^{n+1}$

Now, we need to find ${\rho_{S_n}}$ such that ${\int_0^\infty \rho_{S_n}(t) e^{iu} dt = \left( \frac{\lambda}{\lambda+u} \right)^{n+1}}$ . Now it is just a matter of solving this equation and we get: ${\rho_{S_n}(t) = \frac{\lambda (\lambda t)^n}{n!} e^{-\lambda t}}$ . Now, the Poisson varible ${N_t}$ measures the number of arrivals in ${[0,t]}$ and therefore:

$\displaystyle \begin{aligned} P\{N_t = n\} & = P\{S_{n-1} < t < S_n\} = P\{S_n > t\} - P\{S_{n-1} \geq t\} \\ & = \int_t^\infty \rho_{S_n}(t) dt - \int_t^\infty \rho_{S_{n-1}}(t) dt = \frac{(\lambda t)^n}{n!} e^{-\lambda t} \end{aligned}$
Characteristic Function or Fourier Tranform: Taking ${Q = \{e^{i\lambda x}; x \in \mathbb{C}\}}$ we get the Fourier Transform: ${f_X(\lambda) = \mathop{\mathbb E} e^{i \lambda x}}$ which also has some of the nice properties of the previous ones and some additional ones. The characteristic functions were the main actors in the development of all the probability techniques that lead to the main result of 19th century Probability Theory: the Central Limit Theorem. We know that moment generating functions and Laplace transforms completely characterize the distributions, but it is not clear how to recover a distribution once we have a transform. For Fourier Transform there is a cleas and simple way of doing that by means of the Inversion Formula:
$\displaystyle \rho_X(x) = \frac{1}{2 \pi} \int_{\mathbb R} e^{-i \lambda x} f_X(\lambda) d\lambda$

One fact that always puzzled me was: why is the normal distribution ${\rho_N (x) = \frac{1}{\sqrt{2 \pi}} e^{-x^2/2} }$ so important? What does it have in special to be the limiting distribution in the Central Limit Theorem, i.e., if ${X_1, X_2, \hdots, X_n}$ is a sequence of independent random variables, ${S_n = \sum_1^n X_i - \sum_1^n \mathop{\mathbb E} X_i}$ then ${S_n / \sqrt{var S_n} \rightarrow N(0,1)}$ under some natural conditions on the variables. The reason the normal is so special is because it is a “fixed point” for the Fourier Transform. We can see that ${f_N(\lambda) = e^{-\lambda_2/2}}$ . And there we have something special about it that makes me believe the Central Limit Theorem.

————————-

This blog post was based on lectures by Professor Dynkin at Cornell.

Categories: theory Tags: mathematics, probability

Random Spanning Trees

November 3rd, 2009 renatoppl No comments

BigRedBits is again pleased to have Igor Gorodezky as a guest blogger directly from UCLA. I leave you with his excelent post on the Wilson’s algorithm.

——————————————

Igor again, with another mathematical dispatch from UCLA, where I’m spending the semester eating and breathing combinatorics as part of the 2009 program on combinatorics and its applications at IPAM. In the course of some reading related to a problem with which I’ve been occupying myself, I ran across a neat algorithmic result – Wilson’s algorithm for uniformly generating spanning trees of a graph. With Renato’s kind permission, let me once again make myself at home here at Big Red Bits and tell you all about this little gem.

The problem is straightforward, and I’ve essentially already stated it: given an undirected, connected graph ${G}$ , we want an algorithm that outputs uniformly random spanning trees of ${G}$ . In the early ’90s, Aldous and Broder independently discovered an algorithm for accomplishing this task. This algorithm generates a tree ${T}$ by, roughly speaking, performing a random walk on ${G}$ and adding the edge ${(u,v)}$ to ${T}$ every time that the walk steps from ${u}$ to ${v}$ and ${v}$ is a vertex that has not been seen before.

Wilson’s algorithm (D. B. Wilson, “Generating random spanning trees more quickly than the cover time,” STOC ’96) takes a slightly different approach. Let us fix a root vertex ${r}$ . Wilson’s algorithm can be stated as a loop-erased random walk on ${G}$ as follows.

Algorithm 1 (Loop-erased random walk) Maintain a tree ${T}$ , initialized to consist of ${r}$ alone. While there remains a vertex ${v}$ not in ${T}$ : perform a random walk starting at ${v}$ , erasing loops as they are created, until the walk encounters a vertex in ${T}$ , then add to ${T}$ the cycle-erased simple path from ${v}$ to ${T}$ .

We observe that the algorithm halts with probability 1 (its expected running time is actually polynomial, but let’s not concern ourselves with these issues here), and outputs a random directed spanning tree oriented towards ${r}$ . It is a minor miracle that this tree is in fact sampled uniformly from the set of all such trees. Let us note that this offers a solution to the original problem, as sampling ${r}$ randomly and then running the algorithm will produce a uniformly generated spanning tree of ${G}$ .

It remains, then, to prove that the algorithm produces uniform spanning trees rooted at ${r}$ (by which we mean directed spanning trees oriented towards ${r}$ ). To this we dedicate the remainder of this post.

1. A “different” algorithm

Wilson’s proof is delightfully sneaky: we begin by stating and analyzing a seemingly different algorithm, the cycle-popping algorithm. We will prove that this algorithm has the desired properties, and then argue that it is equivalent to the loop-erased random walk (henceforth LERW).

The cycle-popping algorithm works as follows. Given ${G}$ and ${r}$ , associate with each non-root vertex ${v}$ an infinite stack of neighbors. More formally, to each ${v \neq r}$ we associate

$\displaystyle \mathcal S_v = [u_{0}, u_{1}, \dots ]$

where each ${u_{i}}$ is uniformly (and independently) sampled from the set of neighbors of ${v}$ . Note that each stack is not a random walk, just a list of neighbors. We refer to the left-most element above as the top of ${\mathcal S_v}$ , and by popping the stack ${\mathcal S_v}$ we mean removing this top vertex from ${\mathcal S_v}$ .

Define the stack graph ${G_{\mathcal S}}$ to be the directed graph on ${V}$ that has an edge from ${v}$ to ${u}$ if ${u}$ is at the top of the stack ${\mathcal S_v}$ . Clearly, if ${G}$ has ${n}$ vertices then ${G_{\mathcal S}}$ is an oriented subgraph of ${G}$ with ${n-1}$ edges. The following lemma follows immediately.

Lemma 1 Either ${G_{\mathcal S}}$ is a directed spanning tree oriented towards ${r}$ or it contains a directed cycle.

If there is a directed cycle ${C}$ in ${G_{\mathcal S}}$ we may pop it by popping ${\mathcal S_v}$ for every ${v \in C}$ . This eliminates ${C}$ , but of course might create other directed cycles. Without resolving this tension quite yet, let us go ahead and formally state the cycle-popping algorithm.

Algorithm 2 (Cycle-popping algorithm) Create a stack ${\mathcal S_v}$ for every ${v \neq r}$ . While ${G_{\mathcal S}}$ contains any directed cycles, pop a cycle from the stacks. If this process ever terminates, output ${G_{\mathcal S}}$ .

Note that by the lemma, if the algorithm ever terminates then its output is a spanning tree rooted at ${r}$ . We claim that the algorithm terminates with probability 1, and moreover generates spanning trees rooted at ${r}$ uniformly.

To this end, some more definitions: let us say that given a stack ${\mathcal S_v}$ , the vertex ${u_i}$ is at level ${i}$ . The level of a vertex in a stack is static, and is defined when the stack is created. That is, the level of ${u_i}$ does not change even if ${u_i}$ advances to the top of the stack as a result of the stack getting popped.

We regard the sequence of stack graphs produced by the algorithm as leveled stack graphs: each non-root vertex ${v}$ is assigned the level of its stack. Observe that the level of ${v}$ in ${G_{\mathcal S}}$ is the number of times that ${\mathcal S_v}$ has been popped. In the same way, we regard cycles encountered by the algorithm as leveled cycles, and we can regard the tree produced by the algorithm (if indeed one is produced) as a leveled tree.

The analysis of the algorithm relies on the following key lemma (Theorem 4 in Wilson’s paper), which tells us that the order in which the algorithm pops cycles is irrelevant.

Lemma 2 For a given set of stacks, either the cycle-popping algorithm never terminates, or there exists a unique leveled spanning tree ${T}$ rooted at ${r}$ such that the algorithm outputs ${T}$ irrespective of the order in which cycles are popped.

Proof: Fix a set of stacks ${\{ \mathcal S_v \}_{v \neq r}}$ . Consider a leveled cycle ${C}$ that is pop-able, i.e.~there exist leveled cycles ${C_1, C_2, \dots, C_k=C}$ that can be popped in sequence. We claim that if the algorithm pops any cycle not equal to ${C}$ , then there still must exist a series of cycles that ends in ${C}$ and that can be popped in sequence. In other words, if ${C}$ is pop-able then it remains pop-able, no matter which cycles are popped, until ${C}$ itself is actually popped.

Let ${C'}$ be a cycle popped by the algorithm. If ${C'=C_1}$ then the claim is clearly true. Also, if ${C'}$ shares no vertices with ${C_1, \dots, C_k}$ , then the claim is true again. So assume otherwise, and let ${C_i}$ be the first in the series ${C_1, \dots, C_k}$ to share a vertex with ${C'}$ . Let us show that ${C'=C_i}$ by contradiction.

If ${C_i \neq C'}$ , then ${C_i}$ and ${C'}$ must share a vertex ${w}$ that has different successors in ${C'}$ and ${C_i}$ . But by definition of ${C_i}$ , none of the ${C_1, \dots, C_{i-1}}$ contain ${w}$ , and this implies that ${w}$ has the same level in ${C'}$ and ${C_i}$ . Therefore its successor in both cycles is the same, a contradiction. This proves ${C_i=C'}$ .

Moreover, the argument above proves that ${C_i}$ and ${C'}$ are equal as leveled cycles (i.e.~every vertex has the same level in both cycles). Hence

$\displaystyle C'=C_i, C_1, C_2, \dots, C_{i-1}, C_{i+1}, \dots, C_k=C$

is a series of cycles that can be popped in sequence, which proves the original claim about ${C}$ .

We conclude that given a set of stacks, either there is an infinite number of pop-able cycles, in which case there will always be an infinite number and the algorithm will never terminate, or there is a finite number of such cycles. In the latter case, every one of these cycles is eventually popped, and the algorithm produces a spanning tree ${T}$ rooted at ${r}$ . The level of each non-root vertex in ${T}$ is given by (one plus) the number of popped cycles that contained ${v}$ . $\Box$

Wilson summarizes the cycle-popping algorithm thusly: “[T]he stacks uniquely define a tree together with a partially ordered set of cycles layered on top of it. The algorithm peels off these cycles to find the tree.”

Theorem 3 The cycle-popping algorithm terminates with probability 1, and the tree that it outputs is a uniformly sampled spanning tree rooted at ${r}$ .

Proof: The first claim is easy: ${G}$ has a spanning tree, therefore it has a directed spanning tree oriented towards ${r}$ . The stacks generated in the first step of the algorithm will contain such a tree, and hence the algorithm will terminate, with probability 1.

Now, consider a spanning tree ${T}$ rooted at ${r}$ . We’ll abuse notation and let ${T}$ be the event that ${T}$ is produced by the algorithm. Similarly, given a collection of leveled cycles ${\mathcal C}$ , we will write ${\mathcal C}$ for the event that ${\mathcal C}$ is the set of leveled cycles popped by the algorithm before it terminates. Finally, let ${\mathcal C \wedge T}$ be the event that the algorithm popped the leveled cycles in ${\mathcal C}$ and terminated, with the resulting leveled tree being equal to ${T}$ .

By the independence of the stack entries, we have ${\Pr[\mathcal C \wedge T] = \Pr[\mathcal C] \cdot p}$ , where ${p}$ is the probability that the algorithm’s output is a leveled version of ${T}$ , a quantity which a moment’s reflection will reveal is independent of ${T}$ . Now,

$\displaystyle \Pr[T] = \sum_{\mathcal C} \Pr[\mathcal C \wedge T] = p \sum_{\mathcal C} \Pr[\mathcal C]$

which, as desired, is independent of ${T}$ . $\Box$

2. Conclusion

We have shown that the cycle-popping algorithm generates spanning trees rooted at ${r}$ uniformly. It remains to observe that the LERW algorithm is nothing more than an implementation of the cycle-popping algorithm! Instead of initially generating the (infinitely long) stacks and then looking for cycles to pop, the LERW generates stack elements as necessary via random walk (computer scientists might recognize this as the Principle of Deferred Decisions). If the LERW encounters a loop, then it has found a cycle in the stack graph ${G_{\mathcal S}}$ induced by the stacks that the LERW has been generating. Erasing the loop is equivalent to popping this cycle. We conclude that the LERW algorithm generates spanning trees rooted at ${r}$ uniformly.

Categories: theory Tags: combinatorics, probability, theory

Newer Entries Older Entries

Archive

Bounded Degree Spanning Tree and an Uncrossing Lemma

Looking at probability distributions

Random Spanning Trees

Recent Posts

Archives

Categories

Comics

Systems Links

Theory Links

Meta