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:
“Lap me in soft Lydian airs,
Married to immortal verse,
Such as the meeting soul may pierce
In notes with many a winding bout
Of linked sweetness long drawn out,
With wanton heed and giddy cunning,
The melting voice through mazes running,
Untwisting all the chains that tie
The hidden soul of harmony;”
—John Milton (1608–1674)