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

Jump to navigation Jump to search

## 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\ge \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)\gt 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?