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

## Contents

## Problem 1

Consider the Markov chain of graph coloring

**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:

- aperiodic;
- irreducible if ;
- 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 :

- pick an uniformly at random;
- flip (let ) if .

- 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 .

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

## Problem 3

Consider the following random walk over all subsets for some :

**Random walk over -subsets**- At each step, for the current state :

- with probability , do nothing;
- else pick an and a independently and uniformly at random, and change the current set to be .

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

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

Hint.1: Considering a coupling , the is partitioned into . Design a coupling rule to adopt different cases (regarding which parts the random and 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 to achieve the above goal.

## Problem 4

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?