The Markov Property
A stochastic process (“a mathematical object usually defined as a collection of random variables”) is said to have the Markov Property if, conditional on the present value, the future is independent on the past.
Let’s firstly introduce some notation: let S be a countable set called the state space and let X = (Xt: t ≥ 0) be a sequence of random variables taking values in S.
Then, the sequence X is called a Markov Chain if it satisfies the Markov Property:
for all t ≥ 0 and all x0, x1, …, xt ϵ S.
Notation is simplified in the case where the Markov chain is homogeneous. This is when for all i, j ϵ S, the conditional probability P(Xt+1 = j | Xt = i) does not depend on the value of t.
- Branching Process: The branching process is a simple model of the growth of a population; each member of the nth generation has a number of offspring that is independent of the past; Xn = size of the nth generation.
- Random Walk: A particle performs a random walk on the line: let Z1, Z2, …, be independent with P(Zi = 1) = p and P(Zi = -1) = 1-p, then Xn =
Z1 + … + Zn; at each epoch of time, it jumps a random distance that is independent of the previous jumps.
- Poisson Process: the Poisson process satisfies a Markov property in which time is a continuous variable rather than a discrete variable, and thus the Poisson process is an example of a continuous-time Markov chain; the Markov property still holds as arrivals after time t are independent of arrivals before this time.
For simplification (and as this is only an intro to Markov chains) we’ll assume that the Markov chains are homogeneous.
Two quantities that are needed in order to calculate the probabilities in a chain are the:
- transition matrix: P = (pi,j: i,j ϵ S) given by pi,j = P(X1 = j | X0 = i);
- initial distribution: λ = (λi : i ϵ S) given by λi = P(X0 = i).
As we have assumed homogeneity we have that
pi,j = P(Xn+1 = j | Xn = i) for n ≥ 0.
These quantities are characterised in the following way:
a) The vector λ is a distribution in that λi ≥ 0 for i ϵ S and the sum of λi over i = 1.
b) The matrix P = (pi,j) is a stochastic matrix in that pi,j ≥ 0 for i, j ϵ S and the sum of pi,j over j = 1 for i ϵ S (i.e. that P row sums to 1)
a) As λi is a probability, it is clearly non-negative. Additionally, the sum of λi over i = the sum of P(X0 = i) over i = 1.
b) Since pi,j is a probability, it is non-negative. Finally, the sum of pi,j over j = the sum of P(Xn+1 = j | Xn = i) over j = P(Xn+1 ϵ S | Xn = i) = 1.
Hope you enjoyed this brief introduction to a Markov Chain!