概率论 (Summer 2013)/Problem Set 5

Problem 2

Let [math]\displaystyle{ G(V,E) }[/math] be an undirected connected graph with maximum degree [math]\displaystyle{ \Delta }[/math].

• Design an efficient, time reversible, ergodic random walk on [math]\displaystyle{ G }[/math] whose stationary distribution is the uniform distribution.
• Let [math]\displaystyle{ \pi }[/math] be an arbitrary distribution on [math]\displaystyle{ V }[/math] such that [math]\displaystyle{ \pi(v)\gt 0 }[/math] for all [math]\displaystyle{ v\in V }[/math]. Design a time reversible, ergodic random walk on [math]\displaystyle{ G }[/math] whose stationary distribution is [math]\displaystyle{ \pi }[/math].

Problem 3

Consider the following random walk on [math]\displaystyle{ n }[/math]-dimensional hypercube: Assume we are now at the vertex [math]\displaystyle{ b_1b_2\dots b_n }[/math] where each [math]\displaystyle{ b_i\in\{0,1\} }[/math], then

• With probability [math]\displaystyle{ \frac{1}{n+1} }[/math], do nothing.
• Otherwise, with probability [math]\displaystyle{ \frac{1}{n+1} }[/math] for each coordinate [math]\displaystyle{ i }[/math], flip [math]\displaystyle{ b_i }[/math].

Prove by coupling that the mixing time of this markov chain is [math]\displaystyle{ O(n\ln n) }[/math]