随机算法 (Spring 2013)/Problem Set 4

Problem 1

Consider the Markov chain of graph coloring

Markov Chain for Graph Coloring

Start with a proper coloring of $G(V,E)$. At each step: Pick a vertex $v\in V$ and a color $c\in [q]$ uniformly at random. Change the color of $v$ to $c$ if the resulting coloring is proper; do nothing if otherwise.

Show that the Markov chain is:

1. aperiodic;
2. irreducible if $q\ge \mathrm{\Delta }+2$;
3. with uniform stationary distribution.

Problem 2

Consider the following random walk on hypercube:

Yet another random Walk on Hypercube

At each step, for the current state $x\in \{0,1{\}}^n$: pick an $i\in \{0,1,2,\dots ,n\}$ uniformly at random; flip $x_i$ (let $x_i=1-x_i$) if $i\ne 0$.

• Show that the random walk is ergodic.
• Give the stationary distribution of the random walk.
• Analyze the mixing time of the random walk by coupling.

Hint.1: Construct a coupling rule such that the Hamming distance between two states never increases.

Hint.2: When constructing the coupling, consider a cyclic permutation of disagreeing positions.

Problem 3

Consider the following random walk over all subsets $S\in (\genfrac{}{}{0ex}{}{[n]}{k})$ for some $k\le \frac{n}{2}$:

Random walk over $k$-subsets

At each step, for the current state $S\in (\genfrac{}{}{0ex}{}{[n]}{k})$: with probability $p$, do nothing; else pick an $x\in S$ and a $y\in [n]\setminus S$ independently and uniformly at random, and change the current set to be $S\setminus \{x\}\cup \{y\}$.

You are allowed to choose a self-loop probability $p$ for your convenience.

• Show that the random walk is ergodic
• Give the stationary distribution of the random walk.
• Prove that the mixing time is $O(k\log k)$ by coupling.

Hint.1: Considering a coupling $(S,T)$, the $[n]$ is partitioned into $S\cap T,S\setminus T,T\setminus S,\overline{S\cup T}$. Design a coupling rule to adopt different cases (regarding where $x$ and $y$ belong) so that the difference between two states never increases.

Hint.2: Use a cyclic permutation (with some desirable property) of elements in $S\mathrm{△}T$ which is the symmetric difference between $S$ and $T$.

Problem 4

Let $G(V,E)$ be a connected undirected simple graph (no self-loops and parallel edges) defined on $n$ vertices. Let $\varphi (G)$ be the expansion ratio of $G$. $G$ is NOT necessarily regular. For any $v\in V$, let $d_v$ be the degree of vertex $v$.

• What is the largest possible value for $\varphi (G)$? Construct a graph $G$ with this expansion ratio and explain why it is the largest.
• What is the smallest possible value for $\varphi (G)$? Construct a graph $G$ with this expansion ratio and explain why it is the smallest.
• Run a lazy random walk on $G$. What is the stationary distribution? Starting from an arbitrary vertex in an arbitrary unknown $G$, how long in the worst case should you run the random walk to guarantee the distribution of the current position is within a total variation distance of $ϵ$ from the stationary distribution? Give an upper bound of the time in terms of $n$ and $ϵ$.
• Suppose that the maximum degree of $G$ is known but the graph is not necessarily regular. Design a random walk with uniform stationary distribution. How long should you run the random walk to be within $ϵ$-close to the uniform distribution in the worst case?