Randomized Algorithms (Spring 2010)/Markov chains and random walks: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
Line 7: | Line 7: | ||
{|border="1" | {|border="1" | ||
|'''Theorem (Basic limit theorem)''' | |'''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 | :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> | ::<math> | ||
\lim_{n\rightarrow\infty}\pi_n(i)=\pi(i) | \lim_{n\rightarrow\infty}\pi_n(i)=\pi(i) |
Revision as of 13:53, 22 April 2010
Markov Chains
The Markov property and transition matrices
Stationary distributions
Theorem (Basic limit theorem)
|