7 Days0Site 7 Days0
30 Days0Site 30 Days0
Total0Site Total0

Markov Chain Note

Date: 2024/05/29
Last Updated: 2024-08-16T15:42:43.994Z
Categories: Probability
Tags: Probability, Markov Chain
Read Time: 8 minutes

Contents

Stochastic Process

A stochastic process is a collection of random variables XtX_t indexed by time tt.

Markov Property

A stochastic process {Xt}\{X_t\} has the Markov property if for any n0n \geq 0, any t0<t1<<tnt_0 < t_1 < \cdots < t_n, and any BBB \in \mathcal{B}, we have

P(Xtn+1BXt0,Xt1,,Xtn)=P(Xtn+1BXtn).P(X_{t_{n+1}} \in B | X_{t_0}, X_{t_1}, \ldots, X_{t_n}) = P(X_{t_{n+1}} \in B | X_{t_n}).

Markov Chain

A Markov chain is a stochastic process with the Markov property.

Transition Probability

The transition probability at time nn of a Markov chain is defined as

Pij=P(Xn+1=jXn=i).P_{ij} = P(X_{n+1} = j | X_n = i).

Transition Probability Matrix

The transition probability matrix at time nn of a Markov chain is a matrix P=(Pij)P = (P_{ij}) where PijP_{ij} is the transition probability from state ii to state jj.

n-Step Transition Probability

The n-step transition probability from time mm to n+mn+m of a Markov chain is defined as

Pij(n)=P(Xn+m=jXm=i).P_{ij}^{(n)} = P(X_{n+m} = j | X_m = i).

Time-Homogeneous Markov Chain

A Markov chain is time-homogeneous if the transition probabilities are independent of time.

In this note, we focus on time-homogeneous Markov chains.

Chapman-Kolmogorov Equation

The Chapman-Kolmogorov equation states that for a time-homogeneous Markov chain, the (n+m)-step(n+m)\text{-step} transition probability is given by

Pij(n+m)=kPik(n)Pkj(m).P_{ij}^{(n+m)} = \sum_{k} P_{ik}^{(n)} P_{kj}^{(m)}.

Hitting Probability

The hitting probability of a state jj starting from state ii is defined as

fij=P(state j is hit starting from state i)f_{ij} = P(\text{state } j \text{ is hit starting from state } i)

By intuition, the hitting probability could be calculated by

fij=n=1P(state j is first hit at time nX0=i).f_{ij} = \sum_{n=1}^{\infty} P(\text{state } j \text{ is first hit at time } n | X_0 = i).

Thus, we have the following definition.

First-Visit(Hitting) Probability

The first-visit probability of a state jj starting from state ii is defined as

fij(n)=P(state j is first hit at time nX0=i).f_{ij}^{(n)} = P(\text{state } j \text{ is first hit at time } n | X_0 = i).

Convergence of First-Visit Probability

The first-visit probability will always converge to 00 as nn goes to infinity.

Proof:

If this is not the case, then the sum of hitting probabilities will be greater than 11, which is a contradiction.

Hitting Time for a Given Path

The hitting time of a state jj to state ii for a given path i0,i1,i_0, i_1, \ldots is defined as

Tji=min{n1:Xn=iX0=j}T_{j}^i = \min\{n \geq 1: X_n = i | X_0 = j\}

Sometimes we use TiT^i if it is clear that the starting state is jj.

Mean Hitting Time (Mean First-Visit Time)

The average hitting time of a state jj to state ii is defined as

βji=E[TjiX0=j].\beta_{j}^i = E[T_{j}^i | X_0 = j].

Communication

We say that the state ii communicates with state jj if

Pij(n)>0 for some n0P_{ij}^{(n)} > 0 \text{ for some } n \geq 0

and is denoted by iji \rightarrow j.

Inter-Communication

Two states ii and jj are said to inter-communicate if iji \rightarrow j and jij \rightarrow i.

Irreducible Class of States

A set of states CC is said to be an irreducible class of states if any state in CC communicates with any other state in CC.

Closed Class of States

A set of states CC is said to be a closed class of states if any state in CC communicates only with other states in CC.

Absorbing State

A state ii is said to be an absorbing state if itself forms a closed class of states.

Recurrence

Recurrent and Transient State

A state ii is said to be recurrent if the hitting probability

fii=1.f_{ii} = 1.

A state ii is said to be transient if it is not recurrent.

Recurrent and Transient Class

A class of states CC is said to be recurrent if any state in CC is recurrent.

A class of states CC is said to be transient if any state in CC is transient.

Two Important Theorems

  1. A state ii is recurrent if and only if
n=1Pii(n)=.\sum_{n=1}^{\infty} P_{ii}^{(n)} = \infty.

Proof:

We define the following generating function:

f(s)=n=1fii(n)snf(s) = \sum_{n=1}^{\infty} f_{ii}^{(n)} s^n

Then, the probability of hitting state ii at time nn for the k-th time is the coefficient of sns^n in the expansion of f(s)kf(s)^k.

Thus, we the transition probability:

Pii(n)=k=1nP(hitting i at time n for the k-th time)P_{ii}^{(n)} = \sum_{k=1}^{n} P(\text{hitting }i\text{ at time }n\text{ for the }k\text{-th time})

which should equal to the coefficient of sns^n in the expansion of k=1nfk(s)\sum_{k=1}^{n}f^k(s).

As the coefficient of sis^i for i<ki<k in f(s)kf(s)^k is 0, we have

Pii(n)=coefficient of sn in k=1nfk(s)=coefficient of sn in fn+1(s)+coefficient of sn in k=1nfk(s)=coefficient of sn in k=1n+1fk(s)(by repeating similar steps)=coefficient of sn in k=1fk(s)\begin{align} P_{ii}^{(n)} &= \text{coefficient of }s^n\text{ in }\sum_{k=1}^{n} f^k(s) \\ &= \text{coefficient of }s^n\text{ in }f^{n+1}(s) + \text{coefficient of }s^n\text{ in }\sum_{k=1}^{n} f^k(s) \\ &= \text{coefficient of }s^n\text{ in }\sum_{k=1}^{n+1} f^k(s) \text{(by repeating similar steps)} \\ &= \text{coefficient of }s^n\text{ in }\sum_{k=1}^{\infty} f^k(s) \end{align}

Thus, we have

n=1Pii(n)=n=1fk(1)\sum_{n=1}^{\infty} P_{ii}^{(n)} = \sum_{n=1}^{\infty} f^k(1)

If ii is recurrent, then f(1)=1f(1) = 1 the previous sum diverges.

If ii is transient, then f(1)<1f(1) < 1 and the previous sum is a sum of a geometric series, which converges.

  1. If ii is transient, then for all jj
Pji(n)0 as n.P_{ji}^{(n)} \rightarrow 0 \text{ as } n \rightarrow \infty.

Proof:

If the condition does not satisfy, we assume that a=limnPji(n)a=\lim_{n\rightarrow\infty}P_{ji}^{(n)}, and as ii is transient, let α=fii<1\alpha = f_{ii}<1. We choose ϵ\epsilon, such that a(1α)3+α>ϵ>0\frac{a(1-\alpha)}{3+\alpha} > \epsilon >0. Then there exist NN such that for all nNn\ge N, aϵ<Pji(n)<a+ϵa-\epsilon<P_{ji}^{(n)}<a+\epsilon, and fji(n)<ϵf_{ji}^{(n)} < \epsilon and k=1nfii(n)>αϵ\sum_{k=1}^{n}f_{ii}^{(n)} > \alpha-\epsilon

For n>2N+1n>2N+1, we have

Pji(n)=fji(n)+k=1n1Pjikfiinkϵ+k=1n1Pjikfiinkϵ+ϵ+k=Nn1Pjikfiink2ϵ+k=Nn1(a+ϵ)fiink=2ϵ+(a+ϵ)k=Nn1fiink2ϵ+(a+ϵ)α<aϵ\begin{align} P_{ji}^{(n)} &= f_{ji}^{(n)} + \sum_{k=1}^{n-1}P_{ji}^{k}f_{ii}^{n-k} \\ &\le \epsilon+\sum_{k=1}^{n-1}P_{ji}^{k}f_{ii}^{n-k} \\ &\le \epsilon+\epsilon+\sum_{k=N}^{n-1}P_{ji}^{k}f_{ii}^{n-k} \\ &\le 2\epsilon+\sum_{k=N}^{n-1}(a+\epsilon)f_{ii}^{n-k} \\ &= 2\epsilon+(a+\epsilon)\sum_{k=N}^{n-1}f_{ii}^{n-k} \\ &\le 2\epsilon + (a+\epsilon)\alpha \\ &< a-\epsilon \end{align}

which contradicts the assumption.

Finite State Space Must have Recurrent State

If the state space is finite, then there must be at least one recurrent state.

Proof:

If all state are transient, then by the second theorem in previous section, we have Pji(n)0P_{ji}^{(n)} \rightarrow 0 as nn \rightarrow \infty for all ii and jj, thus iSPji(n)\sum_{i\in S} P_{ji}^{(n)} tends to 0 as nn goes to infinity.

However, iSPji(n)\sum_{i\in S} P_{ji}^{(n)} is constantly 1 as it is the sum of the transition probability of state jj to all other states, which is a contradiction.

Intercommunication and Recurrence

If two states intercommunicate, then they are either both recurrent or both transient.

Proof:

Given two states ii and jj that intercommunicate.

Suppose ii is recurrent, then

n=1Pii(n)=\sum_{n=1}^{\infty} P_{ii}^{(n)} = \infty

As ii and jj intercommunicate, there either exists nn such that Pij(n)>0P_{ij}^{(n)} > 0, and mm such that Pji(m)>0P_{ji}^{(m)} > 0,

Then we have

Pjj(n+k+m)Pij(n)Pjj(k)Pji(m)P_{jj}^{(n+k+m)} \ge P_{ij}^{(n)}P_{jj}^{(k)}P_{ji}^{(m)}

Thus,

α=1Pjj(α)α=n+m+1Pjj(α)α=1Pij(n)Pjj(α)Pji(m)=Pij(n)Pji(m)α=1Pjj(α)\begin{align} \sum_{\alpha=1}^{\infty} P_{jj}^{(\alpha)} &\ge \sum_{\alpha=n+m+1}^{\infty} P_{jj}^{(\alpha)} \\ &\ge \sum_{\alpha=1}^{\infty} P_{ij}^{(n)}P_{jj}^{(\alpha)}P_{ji}^{(m)} \\ &= P_{ij}^{(n)}P_{ji}^{(m)}\sum_{\alpha=1}^{\infty} P_{jj}^{(\alpha)} \end{align}

which is infinite as the sum of Pjj(α)P_{jj}^{(\alpha)} is infinite.

Then, jj is recurrent.

Number of Visits to a State for a Given Path

The number of visits to a state jj for a given path i0,i1,i_0, i_1, \ldots is defined as

Nj=n=1I(Xn=j).N_j = \sum_{n=1}^{\infty} I(X_n = j).

Number of Visits at Infinity

P(Nj=)=1 if j is recurrentP(Nj=)=0 if j is transient\begin{align} P(N_j = \infty) = 1 &\text{ if } j \text{ is recurrent} \\ P(N_j = \infty) = 0 &\text{ if } j \text{ is transient} \end{align}

Decomposition of State Space

The state space can be decomposed into a set of Irreducible Closed Recurrent classes and a set of Transient classes.

Proof:

Given state space II, as the InterCommunicate relation is an equivalence relation, we have a partition of II into Inter Communicate classes. Let the classes be Iα,αAI_{\alpha}, \alpha \in A.

As all states in an InnerCommunicate class have the same Recurrence, let

B={αAIα is Transient}\begin{equation} B = \{\alpha \in A | I_{\alpha} \text{ is Transient}\} \end{equation}

Let C=ABC = A - B. Then, for all αC\alpha \in C, IαI_{\alpha} is Recurrent.

We then prove that IαI_{\alpha} is Closed for all αC\alpha \in C., which finished the proof of this theorem.

If IαI_{\alpha} is not closed, then there exists iIαi \in I_{\alpha} and jIαj \notin I_{\alpha}, and nNn \in \mathbb{N} such that Pij(n)>0P_{ij}^{(n)} > 0.

Also, as iIαi \in I_{\alpha}, ii is Recurrent, and thus

fii=1\begin{equation} f_{ii} = 1 \end{equation}

Also, in this case, jj can not Communicate with ii, as if it does, jj will be in IαI_{\alpha}, which means

fji=0\begin{equation} f_{ji} = 0 \end{equation}

Then we have

1=fii=kIPik(n)fki=Pij(n)fji+kI,kjPik(n)fki=kI,kjPik(n)fkikI,kjPik(n)=1Pij(n)<1\begin{align*} 1 &= f_{ii} \\ &= \sum_{k\in I} P_{ik}^{(n)} f_{ki} \\ &= P_{ij}^{(n)}*f_{ji} + \sum_{k\in I, k\neq j} P_{ik}^{(n)} f_{ki} \\ &= \sum_{k\in I, k\neq j} P_{ik}^{(n)} f_{ki} \\ &\le \sum_{k\in I, k\neq j} P_{ik}^{(n)} \\ &= 1- P_{ij}^{(n)} \\ &< 1 \end{align*}

This is a contradiction. Thus, IαI_{\alpha} is closed.

Mean Recurrence Time

The mean recurrence time of a state ii is defined as

μi=E[TiiX0=i]=n=1nfii(n).\mu_i = E[T_i^i | X_0 = i] = \sum_{n=1}^{\infty} n f_{ii}^{(n)}.

Mean Recurrence Time for a Transient State

The mean recurrence time for a transient state is infinite.

Positive and Null Recurrent State

A state ii is said to be positive recurrent if the mean recurrence time:

μi<.\mu_i < \infty.

A state ii is said to be null recurrent if the mean recurrence time:

μi=.\mu_i = \infty.

Identification of Positive and Null Recurrent State

A null recurrent state has similar properties to a transient state:

A recurrent state is null recurrent if and only if

limnPii(n)=0\lim_{n\rightarrow \infty}P_{ii}^{(n)} = 0

State in the Same Irreducible Class have the Same Recurrence (Positive or Null)

If two states are in the same irreducible class, then they are either both positive recurrent or both null recurrent.

Finite State Space Must have Positive Recurrent State

If the state space is finite, then there must be at least one positive recurrent state.

Periodicity

Period of a State

The period of a state ii is defined as

di=gcd{n1:Pii(n)>0}d_i = \gcd\{n \geq 1: P_{ii}^{(n)} > 0\}

If did_{i} is 11, then the state is said to be aperiodic.

where gcd\gcd is the greatest common divisor.

Period of a Class

All states in the same irreducible class have the same period.

Stationary Distribution

Stationary Distribution

A distribution π=(π1,π2,)\pi = (\pi_1, \pi_2, \ldots) is said to be a stationary distribution of a Markov chain if

π=πP\pi = \pi P

where PP is the transition probability matrix.

Existence and Uniqueness of Stationary Distribution

If a Markov chain is irreducible and positive recurrent, then it has a unique stationary distribution.

And the stationary distribution is given by

πi=1μi\pi_i = \frac{1}{\mu_i}

where μi\mu_i is the mean recurrence time of state ii.

Ergodic Markov Chain

A Markov chain is said to be ergodic if it is irreducible, positive recurrent and aperiodic.

Limiting Distribution

Given an ergodic Markov chain, and any vector π(0)\pi^{(0)},

The limit:

limnπ(0)Pn=π\lim_{n\rightarrow \infty} \pi^{(0)} P^n = \pi

where π\pi is the stationary distribution.

Discrete Renewal Process

Define a sequence of independent distributed random variables {Xn}\{X_n\} with positive integer state space.

Define a stochastic process {Tn}\{T_n\} as

Tn=Tn1+XnT_n = T_{n-1} + X_n

where T0=0T_0 = 0.

Then, {Tn}\{T_n\} is a discrete renewal process.

Other Ways to Define Discrete Renewal Process

This first definition is defined by the inter-arrival time. We can directly define the process by the renewal time TnT_n, which are not independent.

We can also define the process by assign each time nn a renewal probability unu_n, which is the probability that the process is renewed at time nn.

Or we can define the process by the number of renewal NnN_n, which is the number of renewals in the time interval [0,n][0, n].

Mean of Number of Renewals

If we are given the renewal probability unu_n, then the mean of the number of renewals in the time interval [0,n][0, n] is

E[Nn]=k=1nuk.E[N_n] = \sum_{k=1}^{n} u_k.

Renewal Process and Markov Chain

If we are given a Markov chain with state space S={1,2,}S = \{1, 2, \ldots\}, and we set Y0=1Y_0 = 1, and we said the process is renewed whenever it hits state 11, then the process is a discrete renewal process.

And the renewal probability is given by

un=P(the process is renewed at time n)=P(Yn=1Y0=1)=P11(n)u_n = P(\text{the process is renewed at time } n) = P(Y_n = 1|Y_0=1) = P_{11}^{(n)}

Inter-renewal Distribution of Discrete Renewal Process Defined by Markov Chain

The inter-renewal distribution of the discrete renewal process defined by a Markov chain is given by

fk=P(the precess first reach 1 at kY0=1)=f11(k)f_k = P(\text{the precess first reach }1\text{ at } k | Y_0 = 1) = f_{11}^{(k)}

which is the first renewal probability.

The Limit Renewal Theorem of Ergodic Markov Chain

Given an ergodic Markov chain with state space S={1,2,}S = \{1, 2, \ldots\}, and we set Y0=1Y_0 = 1, and we said the process is renewed whenever it hits state 11, and we set the number of renewals in the time interval [0,n][0, n] as NnN_n, then

limnE[Nn]n=1E[T1]\lim_{n\rightarrow \infty} \frac{E[N_n]}{n} = \frac{1}{E[T_1]}

where E[T1]E[T_1] is the mean recurrence time of state 11.

Branching Process

Offspring Distribution

An offspring distribution is a probability distribution of the number of offspring of each individual.

Discrete Branching Process

A discrete branching process with offspring distribution ZZ is a stochastic process {Xn}\{X_n\} defined as

Xn=i=1Xn1ZX_n = \sum_{i=1}^{X_{n-1}} Z

And XnX_n is called the size of the nth generation.

The Probability Generating Function of Discrete Branching Process

The probability generating function of a discrete branching process is defined as

F(s)=E[sZ]F(s) = E[s^{Z}]

where ZZ is the offspring distribution.

Mean Generation Size

If we are starting from X0=1X_{0} = 1, then the mean generation size of the nth generation is given by

E[Xn]=E[Z]nE[X_n] = E[Z]^n

where E[Z]E[Z] is the mean of the offspring distribution.

Total Progeny

The total progeny of the branching process is defined as the total number of individuals that ever exist in the process.

T=n=0XnT = \sum_{n=0}^{\infty} X_n

Probability Generating Function of Total Progeny

Let G(s)G(s) be the probability generating function of the total progeny TT, then

G(s)=sF(G(s))G(s) = sF(G(s))

Extinction

We say that the branching process is extinct if Xn=0X_n = 0 for some nn.

Probability of Extinction

The probability of extinction is given by the ever visit probability of state 00 starting from state 11.

γ=f10=P(extinction)=n=1f10(n)\gamma = f_{10} = P(\text{extinction}) = \sum_{n=1}^{\infty} f_{10}^{(n)}
Calculation of Probability of Extinction

The probability of extinction is the least non-negative solution of the equation

s=F(s)s = F(s)

Random Walk

Simple Random Walk

A simple random walk is a stochastic process {Xn}\{X_n\} defined as

Xn=Xn1+YnX_n = X_{n-1} + Y_n

where YnY_n is a sequence of independent and identically distributed random variables.

In this note, we only focusing on YY to be a Bernoulli random variable with

P(Y=1)=p,P(Y=1)=1pP(Y = 1) = p, P(Y = -1) = 1 - p

Symmetric Random Walk

If p=0.5p = 0.5, then the random walk is said to be symmetric.

Number of Possible Path

The number of possible paths of a simple random walk from (0,i)(0,i) to (n,j)(n,j) is denoted as Nn(i,j)N_n(i,j).

Crossing Condition

Let the number Nnm(i,j)N_{n}^{m}(i,j) denote the number of possible paths of a simple random walk from (0,i)(0,i) to (n,j)(n,j) that is at (k,m)(k,m) for some kk.