8 Random Processes: Continuous-time Markov Chains Flashcards
continuous-time Markov chains
In many applications time flows continuously and events (births, deaths, …) can happen at continuous random time t∈ [0, ∞)
(time increments are random, have a distribution)
consider finite/countable state space
X(t)∈ S = {0, 1, 2, . . . }
CTMC
CTMC memoryless
satisfy Markov’s property
Prob{X(tₙ₊₁) = iₙ₊₁ | X(t₀)= i₀,…,X(tₙ)=iₙ}
= Prob{X(tₙ₊₁)=iₙ₊₁|X(tₙ)=iₙ}
the probability of being in state iₙ₊₁ at tₙ₊₁ depends ONLY on being in state iₙ at tₙ
not on entire history
CTMC probability distribution
A CTMC
X(t) ∈ S = {0, 1, 2, . . . }
s characterized by its probability distribution
{p₀(t), p₁(t), ₂(t). . .}
where
pᵢ(t) = Prob{X(t) = i ∈ S}
(process at time t has value i)
and is the vector of probability
p(t) = (p₀(t), p₁(t), ₂(t). . .)^T
pᵢⱼ
Transition probability
pⱼᵢ(t,s)
gives the probability to move from state i at time s at state j at time t>s
pⱼᵢ(t,s)= pⱼᵢ(t-s) =Prob{X(t)=j|X(s)=i}
=Prob{X(t-s)=j|X(0)=i} with t>s
writing
pⱼᵢ(t,s)=pⱼᵢ(t-s)=p(∆t)
with ∆t=t-s >0
we assume time is homogenous
assume time is homogeneous meaning only time difference t-s>0 matters
the probability only dep on the time difference
stochastic transition matrix
As for DTMCs, the transition probability between state i at time s to state j at time t>s is specified by
the element pⱼᵢ(t,s)=pⱼᵢ(t-s)=pⱼᵢ(∆t) of the stochastic transition matrix
P(∆t)=(pⱼᵢ(∆t))
probability conservation
Σ_{k∈S} pₖⱼ(∆t)=1
each column of P(∆t) adds up to 1
Relation between transition probability and probability distribution is
product:
p(∆t)
= P(∆t) x p(0)
prob. vector after ∆t=
transition matrix prob. x vector at t = 0
if initial state X(0)= i ∈ S
then pₖ(0) =δₖ,ᵢ
thus p(0)=
(0)
….
(1)
(0) element i
…
(0)
p_{j∈S}(∆t) = Σ_{k∈S} pⱼₖ(∆t)δₖ,ᵢ
= pⱼᵢ(∆t)
δₖ,ᵢ =
δₖ,ᵢ =
{1 if i = k
{0 if i ̸= k
The Chapman-Kolmogorov equation for CTMCs in matrix form
P(s)P(t) = P(t + s)
All this is similar to what we have seen for discrete-time Markov chains
However, in CTMCs:
- Events can occur at random time that flows continuously (there is no fixed, discrete time increment)
=>Time between two events is randomly distributed
- CTMCs are now analyzed in terms of transition rates
8.2
transition rates
qⱼᵢ
are defined in terms of transition prob. as
qⱼᵢ= lim_{∆t→0} of
[pⱼᵢ(∆t)-pⱼᵢ(0)]/ ∆t
=
{lim_{∆t→0}pⱼᵢ(∆t)/∆t if i ̸= j
{lim_{∆t→0} (pⱼⱼ (∆t)−1)/∆t if i = j,
Since pⱼᵢ(∆t) ≥ 0 and ∆t > 0
⇒ qⱼᵢ ≥ 0 if i ̸= j
where pⱼᵢ(0)= δᵢ,ⱼ
P(0)= I identity matrix
means
pⱼᵢ(∆t) = δⱼ,ᵢ+ qⱼᵢ∆t + o(∆t)
h.o.t negligible/ inifinitesimally small, such that lim_{∆t→0} o(∆t)/∆t = 0
When ∆t → 0 (with o(∆t) negligible):
When ∆t → 0 (with o(∆t) negligible):
Since
(kronecker delta function used, taking sum over j)
Σ_{j∈S} pⱼᵢ
= 1
= 1 + ∆tΣ_{j∈S}qⱼᵢ
= 1 + ∆t[ Σ_{j∈S/i}qⱼᵢ + qⱼⱼ]
(here we demand [] sums to 0 for j not equal to i)
giving
qⱼᵢ = − Σ_{j∈S/i} qⱼᵢ
GENERATOR MATRIX
Q=
(qⱼᵢ)
whose columns add up to zero and
whose off-diagonal element is non-negative and is the rate of the transition
i to j
(qⱼᵢ)
Since P(0) = I, for a CTMC of range S={0,1,2…} , the generator matrix explicitly reads:
(qⱼᵢ)=Q=
lim_{∆t→0} [P(∆t) − I]/((∆t)
=
[ () q₀₁ q₀₂ ….]
[ q₁₀ ( .) q₁₂…]
[ q₂₀ q₂₁ (*..) …]
[… ]
s.t all ≥ 0
from state i=0 from state i=1…
to state
j=0
j=1
…
- = -Σ_{k∈S/0} qₖ₀
*.= -Σ_{k∈S/1} qₖ₁
*..= -Σ_{k∈S/1} qₖ₂
note: each element columns add to 0
except for diagonal all elements correspond to transition rates
gen matrix doesnt dep on delta t
The Chapman-Kolmogorov equation says
P(t + ∆t) = P(∆t)P(t)
pⱼᵢ(t + ∆t) = Σ_{k∈S} pⱼₖ(∆t)pₖᵢ(t)
= Σ_{k∈S} pₖᵢ(t)[δⱼₖ + qⱼₖ∆t + o(∆t)]
now [δⱼₖ ] is 0 or 1 dep on if j=k
REARRANGING
in the limit ∆t → 0
we obtain the master equation
lim_{∆t→0} of
pⱼᵢ(t + ∆t) - pⱼᵢ(t)/∆t
=
dpⱼᵢ(t)/dt
=
Σ_{k∈S} qⱼₖpₖᵢ(t)
matrix form, the master equation
formal sol
d/dt P(t) = Q P(t)
giving
P(t)=
exp(Qt)P(0)
= exp(Qt)
where P(0) =I
and we clearly have
P(t₁ + t₂) = P(t₁)P(t₂)
(exponential of a matrix (generally
is nonsymmetric and large)
which come from (diagonal?) elements
using
p(t + ∆t) = P(∆t)p(t)
as
[p(t + ∆t) − p(t)]/∆t =
[P(∆t) − I]p(t)/∆t
in the limit∆t → 0
obtain
MASTER EQUATION FOR THE PROBABILITY VECTOR
(d/dt) p(t) = Q p(t)
which gives the equation of motion of the probability vector
p(t) = exp(Qt)p(0)
solution
relationship between probability vector and transition matrix
when given IC….
often the initital distribution p(0) is known and the relationship between transition probabilities and probability distribution is simple.
For instance, if initially,
X(0) = k ∈ S
gives
pᵢ(0) = δᵢ,ₖ
and
pᵢₖ(t) = Prob {X(t) =i | X(0)=k}
=
Prob {X(t)=i)= pᵢ(t)
so given IC
we work out Q
depeneds on the model of the process
then use sol
continuous-time Markov chains with discrete state space
S={0,1,2,…}
states
continuous time t ∈ [0, ∞)
with randomly distributed time between events
when time is continuous the delta t is infinitely small and we have randomly distributed,
probability of each states given by master equation, giving the distribution of the probabilities
master equation
continuous-time MC
d/dt p(t) =Qp(t)
Q= (qⱼᵢ)
where qⱼᵢ≥0
is the rate of i −qⱼᵢ→ j for i ̸= j
each state of system
Q generator matrix, tranisiton rates, each col sums to 0
A Poisson process is
discrete state
continuous time
e.g. number of goals in a football game
a CTMC with and de {X(t) ∈ S : t ∈ [0, ∞)} S = {0, 1, 2, . . .}, λ > 0, ∆t → 0 defined by:
*At t = 0: X(0) = 0
* pᵢ₊₁(∆t) = Prob {X(t + ∆t) = i + 1|X(t) = i} = λ∆t + o(∆t)
(∆t so small we can only move +1,0 in ∆t)
- pᵢᵢ(∆t) = Prob {X(t + ∆t) = i|X(t) = i} = 1 − λ∆t + o(∆t)
*pⱼᵢ(∆t) = Prob {X(t + ∆t) = j ≥ i + 2|X(t) = i} = o(∆t) if j ≥ i + 2
* pⱼᵢ(∆t) = 0 if j < i
where o(∆t) is infinitesimally small s.t lim_{∆t→0} o(∆t)/∆t = 0
, i.e. that decrease to zero faster
than ∆t
In the Poisson process, there are only transitions into higher states (never down): summary
i −λ→ i + 1,
i −o(∆t)→ j > i + 1,
and i −prob. 0→ j < i
For the Poisson process , the transition prob. in is ∆t
pⱼₖ(∆t)
related to
qⱼₖ
pⱼₖ(∆t) = δⱼ,ₖ + qⱼₖ∆t + o(∆t)
when ∆t → 0
qⱼₖ= λ(δⱼ,ₖ₊₁ - δⱼ,ₖ)
Generator matrix Poisson process
Q= (qⱼₖ) =
[−λ 0 0 0 0 . . .]
[λ −λ 0 0 0 . . .]
[0 λ −λ 0 0 . . .]
[0 0 λ −λ 0 . . .]
[. … … …]
0 except in 2 cases
j=k+1
or
j=k
sum of columns is 0
guarantees probability conservation
Given IC X(0)=0
pᵢ(0)=
pᵢ(0)=δᵢ,₀ = pᵢ,₀(0) and
pᵢ(t)= pᵢ,₀(t)
master eq
d/dt p(t) =Qp(t)
with probability vector
p(t)= (p₀(t),p₁(t),…)^T
system of coupled linear ODES:
d/dt p₀(t)
master equation
d/dt p₀(t)= −λp₀(t)
with p₀(0)=1
giving
p₀(t)=exp(−λt)
(p₀)
(p₁)
(…)
=
[−λ 0 0 0 0 . . .]
[λ −λ 0 0 0 . . .]
[0 λ −λ 0 0 . . .]
[0 0 λ −λ 0 . . .]
[. … … …]
*
(p₀)
(p₁)
(…)
with pᵢ(0)=
{1 if i=0
{0 if i not equal to 0
uses the time derivative of each component
d/dt p₁(t)
system of coupled linear ODES:
master equation
d/dt p₁(t)
= λp₀ − λp₁ = −λp₁(t) + λexp(−λt)
with p₁(0) = 0
⇒
p₁(t) = λtexp(−λt)
so probability vanishes exponentially in time
d/dt p₂(t)
system of coupled linear ODES:
…
master equation
d/dt p₂(t)
= λp₁ −λp₂
= −λp₂(t) +λ²texp(−λt),
with p₂(0) = 0 ⇒
p₂(t) = ((λt)²/2)exp(−λt)
…
d/dt pᵢ(t)
= λ(pᵢ₋₁ − pᵢ)
= −λpᵢ(t) + λ(λt)ᶦ⁻¹/(i − 1)! exp(−λt)
with IC
pᵢ(0) = 0 for i > 0
⇒ pᵢ(t) = ((λt)ᶦ/i!) exp(−λt)
We recognize the Poisson distribution of parameter λt
mean E(X(t)]=Var(X(t))=λt
standard dev square root (λt)
as time goes on more pronounced deviation
probability to remain in state 0
This is an example of an important general results: in CTMCs, the time between 2 events is
vanishes exponentially in t
p_0(t)=exp(-λt)
Prob{{i = 0 → i = 1 at time > t} = exp(−λt)
Prob {i = 0 → i = 1 at time ≤ t}
= 1 − exp(−λt)
This is an example of an important general results: in CTMCs, the time between 2 events is exponentially
distributed
Stationary distribution
continuous time MC has unique SD
Under generic conditions the CTMC
{X(t) ∈ S : t ∈ [0, ∞)}
with state space
S={0,1,2,…}
has a unique stationary distribution
lim_{t→∞} p(t)= π
= (π₀,π₁,π₂,…)^T
with
Σ_{i∈S} πᵢ = 1
(probability conservation)
Stationarity
Qπ=0
P(t)π = π
Q= lim_{∆t→0} [P(∆t) - I]/∆t
identity matrix I
Hence the stationary distribution is the right eigenvector of the generator matrix Q with eigenvalue 0
In general:
At stationarity
P(t) π = π
with lim_[t→∞} p(t) = π
⇒** ⃗π** is also the right eigenvector of P with eigenvalue 1
birth and death processes
Often the number of individuals in an evolutionary process changes at most by in each small time
increment; these are called birth (+1) or death (-1) events.
The class of CTMCs with this property are called “birth-and-death” processes (BDPs)
time is continuous states are discrete
birth and death
rates
{X(t) ∈ S : t ∈ [0, ∞)} with state space S = {0, 1, 2, . . . }
birth: i → i + 1 at rate λᵢ
death: i → i − 1 at rate µᵢ
e.g start at 2 can move in delta t to 1 or 3
birth and death derive probability of transitions:
{X(t) ∈ S : t ∈ [0, ∞)} with state space S = {0, 1, 2, . . . }
birth: i → i + 1 at rate λᵢ
death: i → i − 1 at rate µᵢ
i → i + k in ∆t :
pᵢ₊ₖ ᵢ(∆t) = Prob {∆X(t) = k|X(t) = i} =
{λᵢ∆t + o(∆t) if k = 1 (birth in state i)
{µᵢ∆t + o(∆t) if k = −1(death state i)
{1 − (λi + µi)∆t + o(∆t) if k = 0 (no birth and no death)
{o(∆t) otherwise (negligible)
Probability of transition
i
Since there are no deaths in state 0 (no individuals), we have µ₀
µ₀ = 0
If the state space is
S = {0, 1, . . . , N − 1, N}
λₙ=
λₙ=0
since there cannot
be a birth with N− λₙ=0→ N + 1
here the population is said to not be able to exceed N. In this case
can only reach state N from N-1
at state N
either absorbing stays there
or cant go N+1 but can go right
matrix q_n_ will tell us
When the state space is bounded and
S = {0, 1, . . . , N − 1, N} =⇒
Generator matrix:
qⱼ₊ₖ ⱼ =
lim_{∆t→0}
[pⱼ₊ₖ ⱼ (∆t) − pⱼ₊ₖ ⱼ(0)]/∆t
=
{λⱼ if k = 1
{µⱼ if k = −1
{−(λⱼ + µⱼ) if k = 0
{0 otherwise
Boundaries:
We need to consider the case j+k=0 and j+k=N separately since we have
and µ_0 = 0 λ_N = 0
p₀ⱼ(∆t)=
pₙⱼ(∆t)=
p₀ⱼ(∆t)=
{µ₁∆t + o(∆t) if j = 1
{1 − λ₀∆t + o(∆t) if j = 0
{o(∆t) otherwise
pₙⱼ(∆t)=
{λₙ₋₁∆t + o(∆t) if j = N − 1
{1 − µₙ ∆t + o(∆t) if j = N
{o(∆t) otherwise.
p₀ⱼ(∆t)=
{µ₁∆t + o(∆t) if j = 1
{1 − λ₀∆t + o(∆t) if j = 0
{o(∆t) otherwise
pₙⱼ(∆t)=
{λₙ₋₁∆t + o(∆t) if j = N − 1
{1 − µₙ ∆t + o(∆t) if j = N
{o(∆t) otherwise.
giving q₀ⱼ=
q₀ⱼ=
lim_{∆t→0}
[p₀ⱼ (∆t) − p₀ⱼ (0)]/∆t =
{µ₁ if j = 1
{−λ₀ if j = 0
{0 otherwise.
qₙⱼ=
lim_{∆t→0}
[pₙⱼ (∆t) − pₙⱼ (0)]/∆t =
{λₙ₋₁ if j = N − 1
{−µₙ if j = N
{0 otherwise.
