# 随机算法 (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 ${\displaystyle G(V,E)}$. At each step: Pick a vertex ${\displaystyle v\in V}$ and a color ${\displaystyle c\in [q]}$ uniformly at random. Change the color of ${\displaystyle v}$ to ${\displaystyle c}$ if the resulting coloring is proper; do nothing if otherwise.

Show that the Markov chain is:

1. aperiodic;
2. irreducible if ${\displaystyle q\geq \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 ${\displaystyle x\in \{0,1\}^{n}}$: pick an ${\displaystyle i\in \{0,1,2,\ldots ,n\}}$ uniformly at random; flip ${\displaystyle x_{i}}$ (let ${\displaystyle x_{i}=1-x_{i}}$) if ${\displaystyle i\neq 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, and decreases much faster than the naive coupling which forces the two chains to use the same ${\displaystyle i}$.

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

## Problem 3

Consider the following random walk over all subsets ${\displaystyle S\in {[n] \choose k}}$ for some ${\displaystyle k\leq {\frac {n}{2}}}$:

 Random walk over ${\displaystyle k}$-subsets At each step, for the current state ${\displaystyle S\in {[n] \choose k}}$: with probability ${\displaystyle p}$, do nothing; else pick an ${\displaystyle x\in S}$ and a ${\displaystyle y\in [n]\setminus S}$ independently and uniformly at random, and change the current set to be ${\displaystyle S\setminus \{x\}\cup \{y\}}$.

You are allowed to choose a self-loop probability ${\displaystyle 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 ${\displaystyle O(k\log k)}$ by coupling.

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

Hint.2: Use a cyclic permutation (with some desirable property) of elements in the symmetric difference ${\displaystyle S\oplus T}$ to achieve the above goal.

## Problem 4

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

• What is the largest possible value for ${\displaystyle \phi (G)}$? Construct a graph ${\displaystyle G}$ with this expansion ratio and explain why it is the largest.
• What is the smallest possible value for ${\displaystyle \phi (G)}$? Construct a graph ${\displaystyle G}$ with this expansion ratio and explain why it is the smallest.
• Run a lazy random walk on ${\displaystyle G}$. What is the stationary distribution? Starting from an arbitrary vertex in an arbitrary unknown ${\displaystyle 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 ${\displaystyle \epsilon }$ from the stationary distribution? Give an upper bound of the time in terms of ${\displaystyle n}$ and ${\displaystyle \epsilon }$.
• Suppose that the maximum degree of ${\displaystyle G}$ is known but the graph is not necessarily regular. Design a random walk on ${\displaystyle G}$ with uniform stationary distribution. How long should you run the random walk to be within ${\displaystyle \epsilon }$-close to the uniform distribution in the worst case?