A Markov chain is a stochastic process—it’s a sequence of events in which the probability of each event depends only on the the previous event. Wikipedia gives a good summary and includes a 3-state example—the behaviour of a hypothetical stock market.
Here the three states are labelled A, B and C, and the process proceeds in even steps of a few seconds each. At every step one of the states is selected as the current state and highlighted in green.
The probability of selecting A B or C as the next state depends only on the current state. For example, if the current state is A, there is a 0.9 probability (a 90% chance) that the next state will also be A, there is a 0.075 probability (a 7.5% chance) that the next state will be B and a 0.025 probability (a 2.5% chance) that the next state will be C.
These are called the transition probabilities of the Markov chain. They are usually presented as the entries in a transition matrix—
| A | B | C | |
| A | |||
| B | |||
| C | |||
The diagonal entries of this transition matrix can be used to calculate the mean rest times—the average number of steps the process remains in a particular state before moving to another state. If pii is the ith diagonal entry, 1⁄(1 -pii) is the average number of steps the process remains in the ith state each time it arrives there. In this case the mean rest times are—
| A | B | C | |
Successive powers of the transition matrix represent successively longer-term probabilites. For example, the comprises the transition probablities after —
| A | B | C | |
| A | |||
| B | |||
| C | |||
The transition probabilities eventually settle down to be the same in every row of the matrix power.
(In fact this is true for any process that can be classified as a finite regular Markov chain
.)
In this case every row becomes—
| A | B | C | |
This means the state will eventually be A about of the time, B about of the time and C about of the time. These are called the steady state probabilities of the Markov chain—
| A | B | C | |
These figures have been rounded to the nearest percent. More precise figures would be misleading because the variances are likely to be relatively large.
The mean first passage times of any finite regular Markov chain can be also calculated, but this does take some slightly more complicated matrix algebra. In this case the result is—
| A | B | C | |
| A | |||
| B | |||
| C | |||
For example, if the current state is A it will take an average of steps before the process next arrives at B and an average of steps before the process next arrives at C. The diagonal entries in this matrix are the mean return times. For example, if th current state is A it will take an average of steps before the process is next at A (including a count of 1 if it’s there at the next step). Again the figures have been rounded because more decimal places would be misleading when the variances are likely to be large.
