7 Random Processes: Discrete-time Markov Chains

Question 1

Evolutionary processes are random

Answer 1

We have looked @ where time is discrete (generations)
deterministic, maps and ODES
equations, given IC we could solve

but in reality chance is an important component of evolution

model using probabilistic tools
discrete vs continuous RVs
pmf
probability vector
probability density
cumulative functs
expected values
moments

Question 2

discrete RV X with binomial distribution
parameter p

distribution function

generating function

expectation

variance

Answer 2

fⱼˣ
≡ Prob(X = j) =
(n)
(j) pʲ(1-p)ⁿ⁻ʲ
=Bin(n,j)

j=0,…,n
e.g. urn containing fraction p black balls fraction 1-p white balls
X is RV corresponding to drawing X=j black balls in n attempts (returning the balls)

(as you vary p small average (peak of distribution towards left) (p large peak towards right)
when p=0.5 distribution peak at RV x=10 when n=20)

generating funct: pgf
Gₓ(z) ≡ E(zˣ) ≡ Σⱼ₌₀ⁿ zʲ fⱼˣ = · · ·
= [pz + 1 − p]ⁿ

average:
differentiating pgf then setting z=1

E(X) = G′ₓ(z = 1) = np(pz + 1 − p)ⁿ−¹
=np

variance:
var(X) ≡ E(X²) − (E(X))²
= G′′ₓ(1) + G′ₓ(1) − [G′(1)]²
= np(1 − p)

Question 3

stochastic process

Answer 3

A stochastic process is a collection of (discrete or continuous) random variables {Xₜ:t ∈ T}, where T is an index set and t ∈ T is here the discrete time index. The set of all
possible realizations (or range) of Xₜ
is S such that Xₜ ∈ S (see Sec. 7.5).

The sample sequence
{Xᵢ, . . . , Xⱼ} = {Xₜ ∈ S : t ∈ T˜
= [i, j] ⊂ T}

corresponds to the sample path
or stochastic realization of the process Xₜ on t ∈ T˜ = [i, j] which is a subset of T

Question 4

e.g. Xₜ~ position each minute an organism moving one step left or right with equal probability

Answer 4

infinite line
over a period of 100 minutes, organism moves for total of 1000 minutes
This is an example of
a symmetric one-dimensional random walk,

the state space is S = Z and T˜ =
{0, 1, 2, . . . , 100} ⊂ T = {0, 1, 2, . . . , 1000}.

Typical sample paths, or stochastic realizations,
of this process for t ∈ T˜ .
{X_i,..,X_j}={X_t in S s.t t in [i,j]}

We notice that while S = Z, all paths
are here within {−20, . . . , −2, −1, 0, +1, +2, . . . , +20}.

There are relationships between the set of random variables {X_t}: they are not independent. The stochastic process X_t can be discrete or continuous in time and space, depending respectively on whether t is a discrete or continuous variable, and S is a discrete or continuous
set.

Question 5

random walk

Answer 5

An example of discrete-time stochastic process is the one-dimensional “random walk” in which, at each discrete time increment ∆t random walker can take one discrete step to the right with prob. q or one step to left with prob. 1-q. The random walk is symmetric when q=1/2, and asymmetric otherwise.

position wrt origin
∆x
S= {. . . , −1, 0, 1, . . . }

Question 6

position of random walker
probabilities

Answer 6

Position of the RWer is characterized by probability vector

p(t) = (. . . , p₋₁(t), p₀(t), p₁(t), . . .)ᵀ

where pⱼ(t) gives the probability for RWer to be @ position k after time t steps

t=0,1,…
and
Σ_{j∈S} pⱼ(t)=1
(probability conservation)

Question 7

probability distribution

Answer 7

is the RW probability distribution
{p_{j∈S} (t)}

Question 8

Discrete-time Markov chains (DTMC)

Answer 8

we want to know how the probability vector p(t) =
p_{i∈S} (t))

with
p_i∈S (t))=Prob {Xt = i ∈ S}

of X_t vary in time

Question 9

Markov property

Answer 9

Markov process is s.t
Markov property, the process is
is “Markovian”, it is a “Markov process” (here a DTMC) and there is a systematic way to find p(t)

Consider DTMC and hence time is discrete

X_t has the Markov property if
Prob{Xₜ = iₜ|X₀ = i₀, . . . , Xₜ₋₁ = iₜ₋₁}
= Prob{Xₜ = iₜ|Xₜ₋₁ = iₜ₋₁}
iₖ ∈ S and k ∈ {0, 1, 2, . . . , t}

MEMORYLESS

Question 10

MEMORYLESS

Answer 10

The Markov property therefore means that the value of Xₜ depends only of Xₜ₋₁ , its value at time t-1

=> a Markov process is often said to be memoryless

Question 11

E.g DTMC

one step transition probability

Answer 11

1D random walk; each move is independent from the previous and the position at t depends on where the RWer is at t-1.

one step transition probability

pᵢⱼ(t)

Question 12

one step transition probability

pᵢⱼ(t)

Answer 12

one step transition probability

pᵢⱼ(t)

the probability for X=i at time t+1 given that X=j at the previous time step t

when time is homogeneous
pᵢⱼ

Question 13

one step transition matrix

Answer 13

one step transition matrix
P=(pᵢⱼ)
[p₁₁ p₁₂ p₁₃…]
[p₂₁ p₂₂ p₂₃…]
[p₃₁ p₃₂ p₃₃…]

all cols add to 1

with
pᵢᵢⱼ=1- sum_{i̸=j} pᵢⱼ

We assume that all are constant (time is homogeneous) and therefore , and we have
PROBABILITY CONSERVATION
sum_ i in S of pᵢⱼ=1
and pᵢⱼ≥ 0

Question 14

stochastic matrix

Answer 14

one step transition matrix

Since all columns add up to 1, is a “stochastic matrix”.
P²,P³,… are also stochastic matrices

stochastic matrices are that all have eigenvalues , and at least
one eigenvalue is equal to 1.

Question 15

l-step probability matrix

Answer 15

P⁽ˡ⁾
=Pˡ

gives the probability of transition from i to j in steps.

For DTMC, there is a simple relation between simple identity step probability matrices, or powers
of :Chapman-Kolmogorov equation (CKE):

Question 16

Chapman-Kolmogorov equation (CKE):

Answer 16

Pˡ= Pˡ⁻ˢPˢ
for any ℓ > s > 0

=> Evolution of probability of probability vector
p(t)
=(p₀,p₁,…,pₙ)^T
of DTMC

X_t in S={0,1,…,n}

is obtained from the one-transition matrix using the CKE
p(t+1)=Pp(t)
gives
p(t)= Pᵗp(0)

{pᵢ(t)}ᵢ₌₀ᶦ⁼ⁿ is the probability distribution of X_tin S={0,1,…,n}

(note: pⱼ(t+1)= Σᵢ Pᵢⱼ pᵢ(t)
sum of prob. that X_t=i multiplied by prob. of one step transition i to j

Question 17

Moments

Answer 17

From the probability distribution , or probability vector, we can obtain the moments of Xₜ

kth (“raw”) moment is the expected value of (Xₜ)ᵏ that is

E[( Xₜ)ᵏ] = Σ_{j∈S} jᵏ pⱼ(t)

Question 18

Stationary probability distribution

Answer 18

In the long run

lim_t→∞ pᵢ(t)= πᵢ

and is the stationary probability distribution of
Xₜ∈ S = {0, 1, . . . }
The probability distribution π is stationary when it does not change in time
Pπ= π

HENCE π
is a right eigenvector of the one-step transition matrix P with eigenvalue 1

(In finite space S , the fact
that is a stochastic matrix P
of finite size ensures that there
is at least one such eigenvector.
However there can be more
than one.)

Question 19

finite DTMC has a unique stat dist

Answer 19

A finite DTMC has unique stationary distribution π if X_t is irreducible (if it is always possible to reach any state from any other state) and aperiodic (if returns to any given state occur at irregular
intervals.)

Question 20

Example from Q1(c) of Example Sheet 4:

Answer 20

X_t ∈ {1, 2, 3}
is a DTMC with 1-step transition matrix

P=(pᵢⱼ)
= Xₜ=1 Xₜ=2 Xₜ=3
Xₜ₊₁=1[ 0.5 0.5 0]
Xₜ₊₁=2[0.25 0.5 0.5]
Xₜ₊₁=3[0.25 0 0.5]

Stationary distribution obtained by solving the eigenvalue problem

Pπ= π =
(π₁)
(π₂)
(π₃)

solving gives

(2/5)
(2/5)
(1/5)

Question 21

random walk

Answer 21

Random walk is broadly used to model movement in many biological applications, and in the continuum limits leads to the Brownian motion whose probability density obeys the diffusion equation.

In many applications, boundary conditions are important especially in the context of first-passage
problems.

Question 22

Symmetric random walk on the infinite line Z

X_t

Answer 22

A random walker (RWer), initially at the origin (at t=0), moves along the infinite line.

At each time-step the RWer moves one step to the right with probability 1/2 or one step to the left also with probability 1/2

X_t: DTMC giving the position of the RWer after t time-steps (i.e. t jumps)

Question 23

what is the probability that the RWer is at n∆x after k time steps?

Answer 23

We assume n and k of same parity and are interested in (both even/odd)

pₙ(k) = Prob{Xₖ= n∆x} = Probability{to be at n∆x after k time steps}

Question 24

After k time steps: RWer is certainly between

Answer 24

between −k∆x and k∆x
(all k left, all k right)
Xₖ∈[-k∆x, k∆x]

At each time step, the RWer has two choices (left/right jump, L/R)
=> after t=1 time step, 2 possible paths with respect to the origin: either L or R

=> after t=2 time steps, 2x2 possible paths: L or R and again L or R => 4 possible paths: LL, LR, RL, RR
(-2,0,0,2)
=> after t=k , 2ᵏ possible paths: L or R at each step=> number of possible paths after k steps is 2ᵏ

Question 25

the probability that the RWer is at n∆x after k time steps is

Answer 25

pₙ(k)=Prob(Xₖ= n∆x) = [#paths ending at n∆x after k jumps] / [total#of possible paths after k jumps] for all the different paths

Question 26

Say there are n+ jumps right and n- jumps to the left to reach n∆x in k steps

Answer 26

n₊+ n₋ =k total #moves n₊- n₋ =n position in unit of ∆x w.r.t. the origin n₊= {k+n}\2 and n₋= (k-n)/2

Question 27

combinatorics: How many ways to take n₊ right steps and n₋ left steps

Answer 27

k!\{n₊!n₋!} ways to take n₊ right steps and n₋ left steps with n₊ + n₋ =k

Question 28

paths ending at n∆x after k steps

Answer 28

n₊ + n₋ =k Since these k steps need to land to the position n∆x after k steps k!\{n₊!n₋!} = k!/ [[[k+n]/2]! [[k-n]/2]!

Question 29

pₙ(k)

Answer 29

pₙ(k) = [Nb of paths ending at n∆x after k jumps]/ [Total number of possible paths after k jumps] = [k!]/ [(k+n)/2]! [(k-n)/2]! * (1/2ᵏ) out of total possible paths

Question 30

stirling formula and taylor expansion for large k show that pₙ(k)

Answer 30

k! ≃ kᵏe⁻ᵏ√(2πk) pₙ(k) approx Gaussian distribution for large k pₙ(k)≈ Probability{to be at n∆x after k time steps} = square root(2/πk) * exp(-n²/(2k)) in the continuum limit ∆x → 0, ∆t → 0 with D= (∆x)²/∆t finite with x= n∆x and t=k∆t the random walk on Z becomes the Brownian motion on R and lim_{∆x→0,∆t→0} pₙ(k) =P(x,t) exp(-x²/(4Dt))/(√(4πDt)) where P(x,t) is the probability density of the 1D Brownian Motion (with the Brownian particle initially at x=0); as shown in Chapter 10 it obeys the 1D diffusion equation. (optional appendix notes)

Question 31

Brownian motion

Answer 31

Brownian motion on R and lim_{∆x→0,∆t→0} pₙ(k) =P(x,t) exp(-x²/(4Dt))/(√(4πDt)) where P(x,t) is the probability density of the 1D Brownian Motion (with the Brownian particle initially at x=0); as shown in Chapter 10 it obeys the 1D diffusion equation. Figures for: Samples paths of 1D random walk starting from the origin (t is in unit of time steps) evolving unrestricted on Z all start from origin but their own path Continuous sample paths of the symmetric 1D Brownian on starting from the origin

Question 32

7.3.2 The asymmetric 1D random walk with absorbing boundaries

Answer 32

In many applications, one-dimensional motion is restricted, e.g. particles move randomly within a finite domain that they cannot leave, e.g. a random walker of position is confined between 0 and N. In this case, the state space is and we need to specify what happens at the boundaries 0 and N=> specify the boundary conditions (BCs).

Question 33

absorbing boundaries at 0 and N

Answer 33

one the RWer reaches one of the ends, either X=0 or X=N, then it is "absorbed" there. It is stuck and cannot move from that location. In this sense the boundaries 0 and N are "absorbing". and absorbing boundary conditions p₀₀=pₙₙ=1 and p₁₀ =Pₙ-₁ₙ

Question 34

asymmetric RW transition probabilities

Answer 34

Asymmetric random walk: at each , the RWer moves ∆t 1 step to the left with prob q or one step to the right with probability p=1-q The random walk is symmetric only when q=1/2. transition probabilities pᵢⱼ=p if i=j+1 pᵢⱼ=q if i = j-1 pᵢⱼ=0 if i ̸= j ± 1 with i=1,..,N-1

Question 35

In general: Asymmetric RW

Answer 35

in finite Markov chains (with either discrete or continuous time), i.e. when N < ∞ with absorbing boundaries, absorption after a finite time (that may be large) is **guaranteed** The asymmetric RWer will eventually reach either state 0 or N, and at that point the dynamics cease and X=0 or X=N.

Question 36

what is the probability ϕₖ to be absorbed in state N if initially X₀=k∈S ?

Answer 36

ϕₖ = Prob{X_{t→∞} = N|X₀ = k ∈ S} =? so Probability of being absorbed at X = 0 is simply 1 − ϕₖ

Question 37

1st-step analysis:

Answer 37

at each time-step, the RWer moves to the right with prob p=1-q or to the left with prob q => Recursion relation ϕₖ for (2nd-order linear map, see Chapter 2): ϕₖ=p ϕₖ₊₁ + qϕₖ₋₁ Prob. to jump right k → k + 1 * Prob. of being absorbed at N from k + 1 + Prob. to jump left k → k − 1 * Prob. of being absorbed at N from k − 1 with absorbing BCS: ϕ₀=0 ϕₙ=1 Prob. of being absorbed at N if we start at X0 = 0 (absorbing) is zero

Question 38

with absorbing BCS: ϕ₀=0 ϕₙ=1

Answer 38

starting then stay forever so will be absorbed there

Question 39

Worked example (Example Sheet 4)

Answer 39

try Solution of the form ϕk = C1 + C2(q/p) k, where C1, C2 are constants, with BCs: ϕk = (q/p) k − 1 (q/p) N − 1 if q ̸= p and ϕk = k/N i hence when q>p... Absorption at N almost impossible if RWer is biased towards jumping to the left (q>p) starting away from the ends of a long "path" (N>>k>>1) lambda gives

Question 40

not discussed: Reflecting bcs

Answer 40

if p_00 = q and p_10 = p, and p_NN = p and p_{N−1}=q reaches one of its reflecting boundaries, the DTMC cannot move beyond it: it is “bounced” towards the other boundary with probability p or q, or stays put at the boundary with the complementary probabilities q and

Question 41

Extra MATH5567M topic: recurrent, transient & absorbing states

Answer 41

It is often useful to know if and when a stochastic process returns to a previous state => notions of recurrence and transience. In many applications, one is also interested in the mean time after which an absorbing state is reached. e.g. will it return to the origin? After how long?

Question 42

Extra MATH5567M topic: recurrent, transient & absorbing states: a discrete-time Markov chain

Answer 42

{Xₘ}ₘ₌₀ᵐ⁼∞ with Xₘ∈ S

Question 43

Extra MATH5567M topic: recurrent, transient & absorbing states TRANSIENT

Answer 43

A state is transient if the probability to return to state i is less than 1 (i.e. return is not certain). i ∈ S Formally: state i is transient if Σ_n≥1 Prob{Xₙ=i, Xₘ ̸= i, m = 1, 2, . . . , n − 1|X₀=i} <1 ≡first return probability to state i in n steps as the return to state i does not occur with a probability 1.

Question 44

Extra MATH5567M topic: recurrent, transient & absorbing states first return property

Answer 44

We are interested in the first time we return (perhaps 0 or many times) We want to find X_n s.t all previous steps are different to i if the sum over all n <1 the probability that return to state i is not guranteed/may may not hence it is transient

Question 45

A state is recurrent

Answer 45

i ∈ S is reccurent guaranteed/certain return Σ_n≥1 Prob{Xₙ=i, Xₘ ̸= i, m = 1, 2, . . . , n − 1|X₀=i} =1 return to state i is certain as it occurs with a probability 1. (doesn't say how long it would take)

Question 46

A state is recurrent if and only if

Answer 46

i ∈ S is recurent IFF Sum from n equals zero to infinity of pᵢᵢ⁽ⁿ⁾ equals infinity the n-step transition probability pᵢᵢ⁽ⁿ⁾ (to return to state i in n steps) is generally nonzero the sum over all possible number of steps diverges when i is recurrent if state is reccurent: for any n the property is non 0 however if transient the sum of (this probabiloty is different to first return probbility)

Question 47

Theorem 7.1: state is recurrent if and only if

Answer 47

Σₙ₌₀ ∞ pᵢᵢ⁽ⁿ⁾ = ∞ Similarly, state is transient if and only if i ∈ S Σₙ₌₀ ∞ pᵢᵢ⁽ⁿ⁾ < ∞ as non zro when we add we get divergence but if transient then whenever we add will be finite

Question 48

q5 ps4 Examples: - Symmetric one-dimensional random walk on :

Answer 48

definitely try this one all states are RECURRENT since Σₙ₌₀ ∞ pᵢᵢ⁽ⁿ⁾ = ∞ , see Q5 of Example sheet 4 diagram: Sample path of 1D random walk on starting from the origin. Z At later times, the randomwalkers returns to the origin=> the state i=0 and all the other states are recurrent.

Question 49

Note that pᵢᵢ⁽ⁿ⁾

Answer 49

Note that pᵢᵢ⁽ⁿ⁾ generally differs from the first-return probability to state i when n>1. This is because in the transition from i to i at the step n, given by , the first return to i may have occurred at any earlier step 1,2,..., n-1 ⇒ pᵢᵢ⁽ⁿ⁾ ≥ first return probability to i in n steps | {z }

Question 50

Symmetric one-dimensional random walk on Z

Answer 50

all states are RECURRENT since Σₙ₌₀ ∞ pᵢᵢ⁽ⁿ⁾ = ∞ convergent guaranteed

Question 51

Asymmetric one-dimensional random walk on Z

Answer 51

all states are TRANSIENT since Σₙ₌₀ ∞ pᵢᵢ⁽ⁿ⁾ < ∞

Question 52

Symmetric two-dimensional random walk on Z^2

Answer 52

: all states i∈Z² are RECURRENT Each sample paths of the 2D random walk on eventually covers the entire 2D space => return to any state is guaranteed => all states are recurrent

Question 53

Symmetric two-dimensional random walk on Z^3

Answer 53

all states i∈Z^3 are TRANSIENT Sample paths of the 3D random walk may not cross each other and do not cover entirely the 3D space=> return to any state is not guaranteed=> all states are transient

Question 54

In finite DTMC, all states are transient true or false?

Answer 54

In finite DTMC, not all states are transient false

Question 55

asymmetric 1D random walk on [0,N] with absorbing boundaries at 0 and N: recurrent? transient?

Answer 55

absorbing states 0 and N are recurrent since, by definition p₀₀=p₀₀⁽ⁿ⁾ = 1 = pₙₙ= pₙₙ⁽ⁿ⁾ Σₙ₌₀∞ p₀₀⁽ⁿ⁾ = ∞ and Σₙ₌₀∞ pₙₙ⁽ⁿ⁾= ∞

Question 56

asymmetric 1D random walk on [0,N] with absorbing boundaries at 0 and N: absorption?

Answer 56

We have seen that in the asymmetric 1D random walk with absorbing boundaries at 0 and N, absorption is guaranteed and we computed the probability ϕₖ = Prob{Xₜ→∞= N|X₀ = k ∈ S} that absorption occurs at X=N given X₀= k ∈ S (if i start at k probability i am absorbed at N) We used the fi ϕk rst-step analysis to obtain a recursion relation for ϕₖ

Question 57

What is the mean absorption time?

Answer 57

What is the mean time to reach either absorbing state 0 or N? Using the first-step analysis: move from k to k+1 with probability p=1-q move from k to k-1 with probability q 1 time-step elapses between each moves k → k ± 1 If τₖ is the mean absorption time in state k, and τₖ±₁ are mean absorption times in states k ± 1 () gives RECCURRENCE RELATION τₖ = p(τₖ₊₁ + 1) + q(τₖ₋₁ + 1) i'm at k, take step to right end up at k+1 etc 1 time step

Question 58

diagram mean absorption time

Answer 58

If q>1/2 (jumps to left more likely)=> mean abs. time is max close to N initial position of RWer vs mean absorption time (0,0) then skewed n shape to right (100,0) N=100 q=0.55 p=0.45 more likely Left than right tau_k when q>p then tau_k is max when value k is closer to n but not quite at n (not too close as otherwise right) p=q=0.5 would be n shape with N/2=k takes longest in the middle

Question 59

τₖ is the mean absorption time BCs?

Answer 59

RECCURRENCE RELATION gives.. τₖ = p(τₖ₊₁ + 1) + q(τₖ₋₁ + 1) = p + q + pτₖ₊₁ + qτₖ₋₁ = 1 + pτₖ₊₁ + qτₖ₋₁ => **inhomogeneous** linear 2nd-order map: pτₖ₊₁ + qτₖ₋₁ − τₖ = **−1**, with abs. BCs τ_0 = τ_N = 0 (absorption time is 0 if...)

Question 60

**inhomogeneous** linear 2nd-order map: pτₖ₊₁ + qτₖ₋₁ − τₖ = **−1**, with abs. BCs τ_0 = τ_N = 0 (absorption time is 0 if...) q2 ps4

Answer 60

if q ̸= p try solution: τₖ = C₁ + C₂k + C₃(q/p)ᵏ and use the BCs => τₖ = [1/(q-p)] [k - N ([1-(q/p)ᵏ]/[1-(q/p)ᴺ]] if q ̸= p τₖ = k(N − k) if q = p = 1/2