概率论 (Summer 2013)/Problem Set 5: Difference between revisions
Jump to navigation
Jump to search
imported>Zhangchihao |
imported>Zhangchihao |
||
| 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>. | ||
Revision as of 09:45, 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].