概率论 (Summer 2013)/Problem Set 5: Difference between revisions
Jump to navigation
Jump to search
imported>Zhangchihao |
imported>Zhangchihao |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
== Problem 1 == | == Problem 1 == | ||
== Problem 2 == | == Problem 2 == | ||
Let <math>G(V,E)</math> be an undirected connected graph with maximum degree <math>\Delta</math> | Let <math>G(V,E)</math> be an undirected connected graph with maximum degree <math>\Delta</math>. | ||
* Design an efficient, time reversible, ergodic random walk on <math>G</math> whose stationary distribution is uniform distribution. | * Design an efficient, time reversible, ergodic random walk on <math>G</math> whose stationary distribution is the uniform distribution. | ||
* Let <math>\pi</math> be an arbitrary distribution on <math>V</math> such that <math>\pi(v)>0</math> for all <math>v\in V</math>. Design a time reversible, ergodic random walk on <math>G</math> whose stationary distribution is <math>\pi</math>. | * Let <math>\pi</math> be an arbitrary distribution on <math>V</math> such that <math>\pi(v)>0</math> for all <math>v\in V</math>. Design a time reversible, ergodic random walk on <math>G</math> whose stationary distribution is <math>\pi</math>. | ||
== Problem 3 == | == Problem 3 == | ||
Consider the following random walk on <math>n</math>-dimensional hypercube: Assume we are now at the vertex <math>b_1b_2\dots b_n</math> where each <math>b_i\in\{0,1\}</math>, then | |||
* With probability <math>\frac{1}{n+1}</math>, do nothing. | |||
* Otherwise, with probability <math>\frac{1}{n+1}</math> for each coordinate <math>i</math>, flip <math>b_i</math>. | |||
Prove by coupling that the mixing time of this markov chain is <math>O(n\ln n)</math> | |||
== Problem 4 == | == Problem 4 == | ||
== Problem 5 == | == Problem 5 == | ||
Revision as of 09:54, 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]