概率论 (Summer 2013)/Problem Set 5

Problem 1

Let [math]\displaystyle{ G(V,E) }[/math] be an undirected connected graph with [math]\displaystyle{ V=\{v_1,\dots,v_n\} }[/math] and [math]\displaystyle{ |E|=m }[/math]. Consider the following random process on [math]\displaystyle{ G }[/math]: In the beginning, every vertex in [math]\displaystyle{ V }[/math] is colored either black or white. Then for each step, we do the following for every vertex simultaneously:

• with probability [math]\displaystyle{ \frac{1}{2} }[/math] do nothing,
• otherwise, choose an incident vertex uniformly at random and change own color to the color of that vertex.

Eventually, all vertices are monochromatic and the process terminates. We use [math]\displaystyle{ X_t\in\{white,black\}^V }[/math] to denote the color of each vertex at step [math]\displaystyle{ t }[/math].

1. Let the random variable [math]\displaystyle{ Y_t }[/math] denote the sum of the degrees of all the white vertices at time [math]\displaystyle{ t }[/math]. Show that [math]\displaystyle{ Y_t }[/math] is a martingale with respect to [math]\displaystyle{ \{X_t\} }[/math].
2. Use the optional stopping theorem to compute the probability that the process terminates in the all-white configuration, as a function of the initial configuration.
3. (Bonus) Use the optional stopping theorem again to show that the expected duration of the process is at most [math]\displaystyle{ O(m^2) }[/math] steps.

Problem 2

Let [math]\displaystyle{ G(V,E) }[/math] be an undirected connected graph with maximum degree [math]\displaystyle{ \Delta }[/math].

• Design an efficient, time reversible, ergodic random walk on [math]\displaystyle{ G }[/math] whose stationary distribution is the uniform distribution.
• Let [math]\displaystyle{ \pi }[/math] be an arbitrary distribution on [math]\displaystyle{ V }[/math] such that [math]\displaystyle{ \pi(v)\gt 0 }[/math] for all [math]\displaystyle{ v\in V }[/math]. Design a time reversible, ergodic random walk on [math]\displaystyle{ G }[/math] whose stationary distribution is [math]\displaystyle{ \pi }[/math].

Problem 3

Consider the following random walk on [math]\displaystyle{ n }[/math]-dimensional hypercube: Assume we are now at the vertex [math]\displaystyle{ b_1b_2\dots b_n }[/math] where each [math]\displaystyle{ b_i\in\{0,1\} }[/math], then

• With probability [math]\displaystyle{ \frac{1}{n+1} }[/math], do nothing.
• Otherwise, with probability [math]\displaystyle{ \frac{1}{n+1} }[/math] for each coordinate [math]\displaystyle{ i }[/math], flip [math]\displaystyle{ b_i }[/math].

Prove by coupling that the mixing time of this markov chain is [math]\displaystyle{ O(n\ln n) }[/math]

Problem 4

Recall the markov chain we used in class to sample proper colorings: Let [math]\displaystyle{ G(V,E) }[/math] be an undirected graph with maximum degree [math]\displaystyle{ \Delta }[/math], [math]\displaystyle{ q\ge\delta+2 }[/math] is the number of colors. Assume we are currently given a proper coloring, then

• Pick a vertex [math]\displaystyle{ v\in V }[/math] uniformly at random and a color [math]\displaystyle{ c\in\{1,2,\dots,q\} }[/math] uniformly at random.
• Recolor [math]\displaystyle{ v }[/math] with [math]\displaystyle{ c }[/math] if this yields a proper coloring, else do nothing.

1. Prove that the markov chain is irreducible, aperiodic, time reversible and the stationary distribution is the uniform distribution.
2. Suppose [math]\displaystyle{ q\le\Delta+1 }[/math], show that the markov chain is no longer always irreducible.

Problem 5

Let [math]\displaystyle{ n,k\gt 0 }[/math] be two numbers and [math]\displaystyle{ k\le\frac{n}{2} }[/math]. Let [math]\displaystyle{ \Omega=\binom{[n]}{k} }[/math], i.e., the family all subsets of [math]\displaystyle{ \{1,\dots,n\} }[/math] of cardinality [math]\displaystyle{ k }[/math] and choose a number [math]\displaystyle{ p\in[0,1) }[/math]. We run a markov chain on [math]\displaystyle{ \Omega }[/math] in the following way: Assume you are now at some [math]\displaystyle{ S\in\Omega }[/math],

• With probability p, do nothing.
• Otherwise, pick [math]\displaystyle{ a\in S }[/math] uniformly at random and pick [math]\displaystyle{ b\in\{1,2,\dots,n\}-S }[/math] uniformly at random. Move to [math]\displaystyle{ S-\{a\}+\{b\} }[/math]

1. Show that this Markov chain is ergodic with uniform stationary distribution. You can choose arbitrary [math]\displaystyle{ p\in[0,1) }[/math] to ease your analysis.
2. Using coupling to show that the mixing time is asymptotically [math]\displaystyle{ O(n\log k) }[/math] or less.