A Markov chain is a mathematical system that experiences transitions from one state to another according to certain probabilistic rules. The defining characteristic of a Markov chain is that no matter how the process arrived at its present state, the possible future states are fixed. In other words, the probability of transitioning to any particular state is dependent solely on the current state and time elapsed. The state space, or set of all possible states, can be anything: letters, numbers, weather conditions, baseball scores, or stock performances.
Markov chains may be modeled by finite state machines, and random walks provide a prolific example of their usefulness in mathematics. They arise broadly in statistical and information-theoretical contexts and are widely employed in economics, game theory, queueing (communication) theory, genetics, and finance. While it is possible to discuss Markov chains with any size of state space, the initial theory and most applications are focused on cases with a finite (or countably infinite) number of states.
Many uses of Markov chains require proficiency with common matrix methods.
A Markov chain is a stochastic process, but it differs from a general stochastic process in that a Markov chain must be "memory-less." That is, (the probability of) future actions are not dependent upon the steps that led up to the present state. This is called the Markov property. While the theory of Markov chains is important precisely because so many "everyday" processes satisfy the Markov property, there are many common examples of stochastic properties that do not satisfy the Markov property.
A common probability question asks what the probability of getting a certain color ball is when selecting uniformly at random from a bag of multi-colored balls. It could also ask what the probability of the next ball is, and so on. In such a way, a stochastic process begins to exist with color for the random variable, and it does not satisfy the Markov property. Depending upon which balls are removed, the probability of getting a certain color ball later may be drastically different.
A variant of the same question asks once again for ball color, but it allows replacement each time a ball is drawn. Once again, this creates a stochastic process with color for the random variable. This process, however, does satisfy the Markov property. Can you figure out why?
In probability theory, the most immediate example is that of a time-homogeneous Markov chain, in which the probability of any state transition is independent of time. Such a process may be visualized with a labeled directed graph, for which the sum of the labels of any vertex's outgoing edges is 1.
A (time-homogeneous) Markov chain built on states A and B is depicted in the diagram below. What is the probability that a process beginning on A will be on B after 2 moves?
In order to move from A to B, the process must either stay on A the first move, then move to B the second move; or move to B the first move, then stay on B the second move. According to the diagram, the probability of that is
Alternatively, the probability that the process will be on A after 2 moves is . Since there are only two states in the chain, the process must be on B if it is not on A, and therefore the probability that the process will be on B after 2 moves is
The Markov Property.
For any positive integer and possible states of the random variables,
In other words, knowledge of the previous state is all that is necessary to determine the probability distribution of the current state. This definition is broader than the one explored above, as it allows for non-stationary transition probabilities and therefore time-inhomogeneous Markov chains; that is, as time goes on (steps increase), the probability of moving from one state to another may change.
A transition matrix for Markov chain at time is a matrix containing information on the probability of transitioning between states. In particular, given an ordering of a matrix's rows and columns by the state space , the element of the matrix is given by
This means each row of the matrix is a probability vector, and the sum of its entries is .
Transition matrices have the property that the product of subsequent ones describes a transition along the time interval spanned by the transition matrices. That is to say, has in its position the probability that given that . And, in general, the position of is the probability .
Prove that, for any natural number and states , the matrix entry .
Denote . By matrix multiplication,
The final equality follows from conditional probability.
The -step transition matrix is and, by the above, satisfies
For the time-independent Markov chain described by the picture below, what is its 2-step transition matrix?
Note the transition matrix is
It follows that the -step transition matrix is
A Markov chain has first state A and second state B, and its transition probabilities for all time are given by the following graph:
What is its transition matrix?
Note: The transition matrix is oriented such that the row represents the set of probabilities of transitioning from state to another state.
Once people arrive in Thailand, they want to enjoy the sun and beaches on 2 popular islands in the south: Samui Island & Phangan Island.
From survey data, when on the mainland, 70% of tourists plan to go to Samui Island, 20% to Phangan Island, and only 10% remain on shore the next day.
When on Samui Island, 40% continue to stay on Samui, 50% plan to go to Phangan Island, and only 10% return to mainland the next day.
Finally, when on Phangan Island, 30% prolong their stay here, 30% divert to Samui Island, and 40% go back to mainland the next day.
Starting from the mainland, what is the probability (in percentage) that the travelers will be on the mainland at the end of a 3-day trip?
A variety of descriptions of either a specific state in a Markov chain or the entire Markov chain allow for better understanding of the Markov chain's behavior. Let be the transition matrix of Markov chain .
- A state has period if any chain starting at and returning to state with positive probability must take a number of steps divisible by . If , then the state is known as aperiodic, and if , the state is known as periodic. If all states are aperiodic, then the Markov chain is known as aperiodic.
- A Markov chain is known as irreducible if there exists a chain of steps between any two states that has positive probability.
- An absorbing state is a state for which . Absorbing states are crucial for the discussion of absorbing Markov chains.
- A state is known as recurrent or transient depending upon whether or not the Markov chain will eventually return to it. A recurrent state is known as positive recurrent if it is expected to return within a finite number of steps, and null recurrent otherwise.
- A state is known as ergodic if it is positive recurrent and aperiodic. A Markov chain is ergodic if all its states are.
Irreducibility and periodicity both concern the locations a Markov chain could be at some later point in time, given where it started. Stationary distributions deal with the likelihood of a process being in a certain state at an unknown point of time. For Markov chains with a finite number of states, each of which is positive recurrent, an aperiodic Markov chain is the same as an irreducible Markov chain.
The graphs of two time-homogeneous Markov chains are shown below.
Determine facts about their periodicity and reducibility.