Markov Chains
Contents
[hide]Markov Chains
Loosely put a Markov Chain is a mathematical process involving transitions, governed by certain probabilistic rules, between different states. Markov chains are a special type of stochastic process that satisfy the Markov property, which states that the future state of the system depends only on its present state, and not on its history of past states. These types of systems appear frequently in math competitions, and are even more prevalent in various real-world applications.
Formulation
When a Markov chain "jumps" from one state to another, we call it a step. The number of steps a chain has undergone is conventionally denoted by a nonnegative index known as the time of the system. We use to denote all the possible states of the system, to denote the time index of the system, and to denote the state of the system at time . Notice that the state of the system at time is random, so is a random variable. Here, we assume that we are dealing with a discrete-time Markov chain, which is equivalent to assuming is an integer. To describe the probabilities for our process we need to calculate
for every and sequence of states . Conditional probability tells us that the above is equal to
Define
We typically use instead of to simplify our notation. In reality, is the initial probability distribution usually given by the context.
Since our process satisfies the Markov property, we know that
Now we make the additional assumption that depends only on , but not . This assumption is called time homogeneity, and it just means that the "transition" probability from one state to another is invariant with respect to time. As a result, we can write for some function that from now on we will call the transition probability.
Using our new notation, it's not hard to see:
Notice that used to be our first term, but now it's our last term. Although we could have preserved the original order by using instead of (as seen in some textbooks), we choose to use over to avoid complications with matrix calculations that may arise later on.
Now consider the problem of calculating the probability distribution of for a given time and initial probability transition . There are several ways to approach this problem, all essentially the same, but different in form.
Approach 1 (Pure Matrix Multiplication)
Our goal is to calculate for any given time and state . By using the law of total probability, or just intuition, it's easy to see:
People well-versed in matrix multiplication will notice that the above summand is just the th term of the matrix product , where is the initial probability distribution vector given by
and is the transition matrix given by
is a column vector, and we know from above that for any value of . Define , and
denotes the probability distribution of , and our results above can be rewritten as
~tsun26
Absorbing Markov Chains
Problems
This article is a stub. Help us out by expanding it.