# 随机算法 (Spring 2014)/Problem Set 4

## Problem 1

A proper ${\displaystyle q}$-coloring of a graph ${\displaystyle G(V,E)}$ is a mapping ${\displaystyle f:V\to [q]}$ such that for any edge ${\displaystyle uv\in E}$ we have ${\displaystyle f(u)\neq f(v)}$.

Consider the following Markov chain for proper ${\displaystyle q}$-colorings of a graph ${\displaystyle G(V,E)}$ whose maximum degree is ${\displaystyle \Delta }$:

 Markov Chain for Graph Coloring Start with a proper ${\displaystyle q}$-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. ergodic (i.e., aperiodic);
2. irreducible if ${\displaystyle q\geq \Delta +2}$;
3. with uniform stationary distribution.

## Problem 2

Let ${\displaystyle G(V,E)}$ be an undirected connected graph with known maximum degree ${\displaystyle \Delta }$. You want to design random walks over the vertices in ${\displaystyle V}$ such that at each step only adjacent vertices are allowed to walk to (i.e., the transition matrix ${\displaystyle P}$ is defined on ${\displaystyle V\times V}$ and ${\displaystyle P(u,v)>0}$ only if ${\displaystyle uv\in E}$). You are allowed to design the transition matrix ${\displaystyle P}$ for your random walk to achieve certain stationary distributions.

• Suppose that ${\displaystyle G}$ is not necessarily regular (every vertex has the same degree). Design a time-reversible lazy random walk which is ergodic and always converges to uniform stationary distribution.
• Given an arbitrary distribution ${\displaystyle \pi }$ over ${\displaystyle V}$, design a time-reversible lazy random walk which is ergodic and always converges to the stationary distribution ${\displaystyle \pi }$.
• (bonus question) Try to give sufficient conditions in terms of ${\displaystyle G}$ and ${\displaystyle \pi }$ for the rapid mixing of the above two random walks.

## Problem 3

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?