Ref: “Discrete-Time Markov Chains and Monte Carlo Methods” by Jem Corcoran. Link to the Course: Link.

ROUGH NOTES (!)
Updated: 3/2/26

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

For example, ${ X _0, X _1, X _2 \ldots . }$

For now, we will consider discrete time and discrete random variables.

The random variables in a stochastic process ${ \lbrace X _n \rbrace _{n = 0} ^{\infty} }$ take values from a common state space ${ S . }$

Eg: [The Markov Property by example]

We want only the most recent piece of given information to matter.

For example, we want

\[{ \mathbb{P}(X _4 = 5 \vert X _3 = 2, X _2 = -1, X _1 = 3, X _0= 1) }\]

to be equal to

\[{ \mathbb{P}(X _4 = 5 \vert X _3 = 2) . }\]

Def: Let ${ S }$ be a discrete state space. The discrete-time stochastic process ${ \lbrace X _n \rbrace _{n = 0} ^{\infty} }$ on ${ S }$ is a Markov chain if

\[{ {\begin{aligned} &\, \mathbb{P}(X _{n + 1} = j \vert X _n = i, X _{n - 1} = i _{n - 1}, \ldots, X _0 = i _0) \\ = &\, \mathbb{P}(X _{n + 1} = j \vert X _{n} = i ) \end{aligned}} }\]

for all ${ n = 0, 1, 2 , \ldots }$ and for all ${ i _0, \ldots, i _{n - 1}, i , j \in S }$ whenever these conditional probabilities are defined.

Eg: Two green balls and four white balls are put into two buckets in such a way that each bucket contains ${ 3 }$ balls.

Call the buckets ${ I }$ and ${ II . }$

At each time step, we randomly select one ball from each bucket and interchange them.

Let

\[{ X _n = \text{ \# green balls in bucket I after the nth exchange. } }\]

Is ${ \lbrace X _n \rbrace }$ a Markov chain?

${ S = \lbrace 0, 1 , 2 \rbrace . }$

For example

\[{ \mathbb{P}(\underbrace{X _4 = 1} _{\text{next timestep}} \vert \underbrace{X _3 = 1} _{\text{current time}}, \underbrace{X _2 = 2, X _1 = 1, X _0 = 0} _{\text{past history}} ) }\]

is equal to

\[{ \mathbb{P}(\underbrace{X _4 = 1} _{\text{next timestep}} \vert \underbrace{X _3 = 1} _{\text{current time}}) . }\]

Hence ${ \lbrace X _n \rbrace }$ is a Markov chain.

Eg: For a Markov chain

\[{ {\begin{aligned} &\, \mathbb{P}(X _4 = 2 \vert X _2 = 5 , X _0 = 0) \\ = &\, \mathbb{P}(X _4 = 2 \vert X _2 = 5 ) . \end{aligned}} }\]

That is, only the most recent piece of given information matters.

Pf: Note that

\[{ {\begin{aligned} &\, \mathbb{P}(X _4 = 2 \vert X _2 = 5 , X _0 = 0) \\ = &\, \sum _{i \in S} \mathbb{P}(X _4 = 2, X _3 = i \vert X _2 = 5, X _0 = 0) \\ = &\, \sum _{i \in S} \sum _{j \in S} \mathbb{P}(\underbrace{X _4 = 2} _{A} , \underbrace{X _3 = i, X _1 = j} _{B} \vert X _2 = 5, X _0 = 0) \\ = &\, \sum _{i \in S} \sum _{j \in S} \mathbb{P}(X _4 = 2 \vert X _3 = i, X _2 = 5, X _1 = j, X _0 = 0) \mathbb{P}( X _3 = i, X _1 = j\vert X _2 = 5, X _0 = 0) \\ = &\, \sum _{i \in S} \sum _{j \in S} \mathbb{P}(X _4 = 2 \vert X _3 = i) \mathbb{P}( X _3 = i, X _1 = j\vert X _2 = 5, X _0 = 0) \\ = &\, \sum _{i \in S} \mathbb{P}(X _4 = 2 \vert X _3 = i) \mathbb{P}(X _3 = i \vert X _2 = 5, X _0 = 0) . \end{aligned}} }\]

Note that

\[{ {\begin{aligned} &\, \mathbb{P}(X _4 = 2 \vert X _2 = 5 ) \\ = &\, \sum _{i \in S} \sum _{j \in S} \sum _{k \in S} \mathbb{P}(\underbrace{X _4 = 2} _{A}, \underbrace{X _3 = i, X _1 = j, X _0 = k} _{B} \vert X _2 = 5) \\ = &\, \sum _{i \in S} \sum _{j \in S} \sum _{k \in S} \mathbb{P}(X _4 = 2 \vert X _3 = i, X _2 = 5, X _1 = j, X _0 = k ) \mathbb{P}(X _3 = i, X _1 = j, X _0 = k \vert X _2 = 5) \\ = &\, \sum _{i \in S} \sum _{j \in S} \sum _{k \in S} \mathbb{P}(X _4 = 2 \vert X _3 = i) \mathbb{P}(X _3 = i, X _1 = j, X _0 = k \vert X _2 = 5) \\ = &\, \sum _{i \in S} \mathbb{P}(X _4 = 2 \vert X _3 = i) \mathbb{P}(X _3 = i \vert X _2 = 5) . \end{aligned}} }\]

Hence it suffices to show

\[{ \text{To show: } \quad \mathbb{P}(X _3 = i \vert X _2 = 5, X _0 = 0) = \mathbb{P}(X _3 = i \vert X _2 = 5) . }\]

Note that

\[{ {\begin{aligned} &\, \mathbb{P}(X _3 = i \vert X _2 = 5, X _0 = 0) \\ = &\, \sum _{j \in S} \mathbb{P}(\underbrace{X _3 = i} _{A}, \underbrace{X _1 = j} _{B} \vert X _2 = 5, X _0 = 0) \\ = &\, \sum _{j \in S} \mathbb{P}(X _3 = i \vert X _2 = 5, X _1 = j, X _0 = 0) \mathbb{P}(X _1 = j \vert X _2 = 5, X _0 = 0) \\ = &\, \mathbb{P}(X _3 = i \vert X _2 = 5) \sum _{j \in S} \mathbb{P}(X _1 = j \vert X _2 = 5, X _0 = 0) \\ = &\, \mathbb{P}(X _3 = i \vert X _2 = 5) \end{aligned}} }\]

as needed.

Eg: Consider a Markov chain ${ \lbrace X _n \rbrace . }$

Are ${ X _2 }$ and ${ X _4 }$ conditionally independent given ${ X _3 }$?

That is, do we have

\[{ {\begin{aligned} &\, \mathbb{P}(X _2 = x _2 , X _4 = x _4 \vert X _3 = x _3 ) \\ \overset{?}{=} &\, \mathbb{P}(X _2 = x _2 \vert X _3 = x _3) \mathbb{P}(X _4 = x _4 \vert X _3 = x _3) \end{aligned}} }\]

Note that

\[{ {\begin{aligned} &\, \mathbb{P}(\underbrace{X _2 = x _2} _{B} , \underbrace{X _4 = x _4} _{A} \vert X _3 = x _3 ) \\ = &\, \mathbb{P}(X _4 = x _4 \vert X _3 = x _3, X _2 = x _2) \mathbb{P}(X _2 = x _2 \vert X _3 = x _3) \\ = &\, \mathbb{P}(X _4 = x _4 \vert X _3 = x _3) \mathbb{P}(X _2 = x _2 \vert X _3 = x _3) \end{aligned}} }\]

as needed.