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

## Problem 1

A **proper -coloring** of a graph is a mapping such that for any edge we have .

Consider the following Markov chain for proper -colorings of a graph whose **maximum degree** is :

**Markov Chain for Graph Coloring**- Start with a proper -coloring of . At each step:

- Pick a vertex and a color uniformly at random.
- Change the color of to if the resulting coloring is proper; do nothing if otherwise.

Show that the Markov chain is:

- ergodic (i.e., aperiodic);
- irreducible if ;
- with uniform stationary distribution.

## Problem 2

Let be an undirected connected graph with known maximum degree . You want to design random walks over the vertices in such that at each step only adjacent vertices are allowed to walk to (i.e., the transition matrix is defined on and only if ). You are allowed to design the transition matrix for your random walk to achieve certain stationary distributions.

- Suppose that 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 over , design a time-reversible lazy random walk which is ergodic and always converges to the stationary distribution .
- (bonus question) Try to give sufficient conditions in terms of and for the rapid mixing of the above two random walks.

## Problem 3

Let be a connected undirected simple graph (no self-loops and parallel edges) defined on vertices. Let be the expansion ratio of . is NOT necessarily regular. For any , let be the degree of vertex .

- What is the largest possible value for ? Construct a graph with this expansion ratio and explain why it is the largest.
- What is the smallest possible value for ? Construct a graph with this expansion ratio and explain why it is the smallest.
- Run a lazy random walk on . What is the stationary distribution? Starting from an arbitrary vertex in an arbitrary unknown , 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 and .
- Suppose that the maximum degree of is known but the graph is not necessarily regular. Design a random walk on with uniform stationary distribution. How long should you run the random walk to be within -close to the uniform distribution in the worst case?