概率论 (Summer 2013)/Problem Set 5: Difference between revisions
imported>Zhangchihao |
imported>Zhangchihao |
||
Line 13: | Line 13: | ||
== Problem 4 == | == Problem 4 == | ||
Recall the markov chain we used in class to sample proper colorings: Let <math>G(V,E)</math> be an undirected graph with maximum degree <math>\Delta</math>, <math>q\ge\delta+2</math> is the number of colors. Assume we are currently given a proper coloring, then | |||
* Pick a vertex <math>v\in V</math> uniformly at random and a color <math>c\in\{1,2,\dots,q\}</math> uniformly at random. | |||
* Recolor <math>v</math> with <math>c</math> if this yields a proper coloring, else do nothing. | |||
# Prove that this markov chain is irreducible, aperiodic, time reversible and the stationary distribution is the uniform distribution. | |||
# Suppose <math>q\le\Delta+1</math>, show that this markov chain is no long always irreducible. | |||
== Problem 5 == | == Problem 5 == |
Revision as of 10:48, 1 August 2013
Problem 1
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]
Problem 4
Recall the markov chain we used in class to sample proper colorings: Let [math]\displaystyle{ G(V,E) }[/math] be an undirected graph with maximum degree [math]\displaystyle{ \Delta }[/math], [math]\displaystyle{ q\ge\delta+2 }[/math] is the number of colors. Assume we are currently given a proper coloring, then
- Pick a vertex [math]\displaystyle{ v\in V }[/math] uniformly at random and a color [math]\displaystyle{ c\in\{1,2,\dots,q\} }[/math] uniformly at random.
- Recolor [math]\displaystyle{ v }[/math] with [math]\displaystyle{ c }[/math] if this yields a proper coloring, else do nothing.
- Prove that this markov chain is irreducible, aperiodic, time reversible and the stationary distribution is the uniform distribution.
- Suppose [math]\displaystyle{ q\le\Delta+1 }[/math], show that this markov chain is no long always irreducible.