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:
“He that has his chains knocked off, and the prison doors set open to him, is perfectly at liberty, because he may either go or stay, as he best likes; though his preference be determined to stay, by the darkness of the night, or illness of the weather, or want of other lodging. He ceases not to be free, though the desire of some convenience to be had there absolutely determines his preference, and makes him stay in his prison.”
—John Locke (1632–1704)