# 随机算法 (Fall 2011)/Problem set 4

## Problem 1

Let ${\displaystyle p}$ and ${\displaystyle q}$ be two probability distributions over ${\displaystyle \Omega }$. Give an explicit construction of a coupling ${\displaystyle \mu }$ of ${\displaystyle p}$ and ${\displaystyle q}$ such that

${\displaystyle \Pr _{(X,Y)\sim \mu }[X\neq Y]=\|p-q\|_{TV}}$.

## Problem 2

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 3

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.

## Problem 4

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(n\log k)}$.