Markov Chains
The probability of going from state i to state j in n time steps is
and the single-step transition is
For a time-homogeneous Markov chain:
and
The n-step transition probabilities satisfy the Chapman–Kolmogorov equation, that for any k such that 0 < k < n,
where S is the state space of the Markov chain.
The marginal distribution Pr(Xn = x) is the distribution over states at time n. The initial distribution is Pr(X0 = x). The evolution of the process through one time step is described by
Note: The superscript (n) is an index and not an exponent.
Read more about this topic: Markov Chain
Famous quotes containing the word chains:
“Let the saints be joyful in glory: let them sing aloud upon their beds. Let the high praises of God be in their mouth, and a two-edged sword in their hand; to execute vengeance upon the heathen, and punishments upon the people; to bind their kings with chains and their nobles with fetters of iron; to execute upon them the judgment written.”
—Bible: Hebrew Psalms 149:5-9.