Randomized Algorithms (Spring 2010)/Markov chains and random walks: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop m (Protected "Randomized Algorithms (Spring 2010)/Markov chains and random walks" ([edit=sysop] (indefinite) [move=sysop] (indefinite))) |
imported>WikiSysop |
||
Line 4: | Line 4: | ||
=== Stationary distributions === | === Stationary distributions === | ||
{|border="1" | |||
|Theorem (Basic limit theorem) | |||
:Let <math>X_0,X_1,\ldots,</math> be an irreducible, aperiodic Markov chain having a stationary distribution <math>\pi</math>. Let <math>X_0</math> have the distribution <math>\pi_0</math>, an arbitrary initial distribution. Then | |||
::<math> | |||
\lim_{n\rightarrow\infty}\pi_n(i)=\pi(i) | |||
</math> | |||
:for all states <math>i</math>. | |||
|} | |||
=== Coupling === | === Coupling === |
Revision as of 13:51, 22 April 2010
Markov Chains
The Markov property and transition matrices
Stationary distributions
Theorem (Basic limit theorem)
|