A Markov chain is a series of random variables, known as states, that satisfy the Markov property: the probability of the current state only depends on the state that preceded it. In other words, past and future states are stochastically independent. The “time” can be discrete, continuous or more generally, a totally ordered set.
Christopher DeFiglia
Example of Markov Chains
Imagine a mouse in a cage with two cells 1 and 2 containing fresh and stinky cheese. The mouse is in cell 1 at time n, then at time n + 1 it is either still in 1 or has moved to 2. Statistical observation shows that the mouse moves from cell 1 to cell 2 with probability α = 0.05 regardless of where it was at an earlier time. Similarly, it moves from 2 to 1 with probability β = 0.99. This can be represented by a transition diagram and/or a transition probability matrix.
A special kind of Markov chain is known as a random walk. This is a chain that presents spatial homogeneity in addition to time-homogeneous transition probabilities. In other words, at every state, the next step is an outgoing edge chosen according to an arbitrary distribution.
A simple random walk is symmetric if the moving “object” has the same probability for each of its neighbors.
The following is a simulation of a random walk using absorbing barriersbetween –10 and 10. As explained previously, if the walk reaches any of these states, it will stay there. This example uses the same transition distribution as before. This time, however, let’s start all walks at 0.
The following graph represents a random walk in which the initial distribution is asymmetric. Notice that even a slight change in probability drastically changes the general tendency of the trajectories.
If a transition probability depends on the current position, the random walk is called reluctant. This is represented in the following graph. The closer we get to 0 or 10, the probability that any of these numbers are going to be reached decreases, thus we say the random walk is reluctant to end.
