Stochastic Modeling X 400646 period 1
Havikja van As
October 18, 2023
Contents
1 Introduction DTMC 2
2 Transient distribution, Hitting time and probabilities 4
3 Communicating classes 7
4 Long-term behaviour 9
4.1 Existence of . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5 Costs 13
6 Exponential distribution 15
6.1 Memorylessness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.2 Total probability law . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.3 Competing exponentials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7 The Poisson Process 17
7.1 Definition 1 via Exponential inter-arrivals . . . . . . . . . . . . . . . . . . . . . . . . . . 17
7.2 Definition 2 via Poisson increments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
7.3 The Poisson Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
7.3.1 Merging and splitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
7.4 Merging and splitting for Poisson Process . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1
,1 Introduction DTMC
A Discreet Time Markov Chain (DTMC) on a countable state space S that is time-homogeneous.
• is a sequence of random variables {Xn , n = 0, 1, 2, . . . } with values in S,
– n is referred to as time
– Xn is referred to as the state at time n, Xn ∈ S
• which has the Markov property: for all n = 0, 1, 2, . . . , for all i, j, i1 , . . . , in−1 ∈ S,
P (Xn+1 = j|X0 = i0 , X1 = i1 , . . . , Xn−1 in−1 ,Xn = i) = P (Xn+1 = j|Xn = i)
i.e. the history does not influence the future (only the present can influence the future).
• and lastly whose one-step transition probabilities are the same at all times n, P (Xn+1 = j|Xn =
i) =: pij
– P := (pij , i, j ∈ S) is the transition matrix
– a transition diagram depicts the pij ’s on S
Example - machine reliability
Formulate a DTMC of the following situation. A machine can be up(1) or down(0),
• if up today then up tomorrow with a probability of 0.98
• if down today then up tomorrow with a probability of 0.97
Xn := state of the machine on day n
S = {0, 1}
P (X1 = 1|X0 = 1) = P (Up tomorrow given up today) = 0.98
P (X1 = 0|X0 = 1) = P (Down tomorrow given up today) = 1 − 0.98 = 0.02
P (X1 = 1|X0 = 0) = P (Up tomorrow given down today) = 0.97
P (X1 = 0|X0 = 0) = P (Down tomorrow given down today) = 1 − 0.97 = 0.03
The transition diagram:
0.97
0.03 0 1 0.98
0.02
The transition matrix
0.03 0.02
P =
0.97 0.98
The Markov property holds since it is implicitly given, that only the present influences the
transition probabilities.
Time-homogeneity holds since the value of n does not influence the transition probabilities.
2
,Example - Harry’s diner
Harry has dinner at either restaurant A or B. His choice depends on the previous two evenings:
• After . . . AA in A wp 0.2
• After . . . BA in A wp 0.4
• After . . . AB in B wp 0.5
• After . . . BB in B wp 0.3
Xn := The restaurant at evening n,
S = {A, B}
Time-homogeneity holds since the value of n does not influence the transition probabilities.
However, the Markov property does not hold because the history influences the future. We
solve this by formulating a new variable:
Yn := {Xn−1 , Xn } and S = {AA, AB, BA, BB}
Now the Markov property does apply since: P (Yn+1 = j|Y0 , Y1 , . . . , Yn ) = P (Yn+1 = j|Yn )
0.2 AA BB 0.3
0.5
0.8 0.7
0.4
0.6
AB BA
0.5
3
, 2 Transient distribution, Hitting time and probabilities
The probability to visit a sequence of states:
P (Xn = in , Xn−1 = in−1 , . . . , X1 = i1 ) = pin−2 in−1 pi1 i2 . . . pin−2 in−1 pin−1 in
Proof.
P (Xn = in , Xn−1 = in−1 , . . . , X1 = i1 ) =P (Xn = in |Xn−1 = in−1 , . . . , X2 = i2 , X1 = i1 , X0 = i0 )∗
P (Xn−1 = in−1 |Xn−2 = in−1 , . . . , X2 = i2 , X1 = i1 , X0 = i0 ) ∗ · · · ∗
P (X2 = i2 |X1 = i1 , X0 = i0 ) ∗ P (X1 = i1 |X0 = i0 )
= P (Xn = in |Xn−1 = in−1 ) ∗ P (Xn−1 = in−1 |Xn−2 = in−2 ) ∗ · · · ∗
P (X2 = i2 |X1 = i1 ) ∗ P (X1 = i1 |X0 = i0 )
= pin−2 in−1 pi1 i2 . . . pin−2 in−1 pin−1 in
n-step transition probabilities:
(n)
pij := P (Xn = j|X0 = i)
Time-homogeneity also applies for n-step transition probabilities, thus:
(n)
P (Xm+n = j|Xm = i) = pij , same for all m.
(n)
Theorem 2.1. The matrix (pij : i, j ∈ S) of n-step transition probabilities is equal to (P n )ij .
The transient distribution at time n is the distribution of Xn , with the following notation:
(n)
πj := P (Xn = j),
(n)
π (n) := rowvector(πj : j ∈ S)
The distribution of π (0) is called the initial distribution of the Markov chain.
Theorem 2.2. The transient distribution at time n is give by π (n) = π (0) P n
Example - machine reliability
• if the machine is up today, what is the probability that it will be up three days from now?
(3)
P (X3 = 1|X0 = 1) = p11 = 0.979798
• if today the machine is up with probability 0.3, what are the chances it will be up on day 3
from now and what is the probability it will be down on day 3 from now?
π (0) = (0.7; 0.3)
π (3) = (P (X3 = 0), P (X3 = 1))
= π (0) P 3
= (0.7 ∗ 0.020203 + 0.3 ∗ 0.020202; 0.7 ∗ 0.979797 + 0.3 ∗ 0.979798)
= (0.0202027; 0.9797973)
4
Havikja van As
October 18, 2023
Contents
1 Introduction DTMC 2
2 Transient distribution, Hitting time and probabilities 4
3 Communicating classes 7
4 Long-term behaviour 9
4.1 Existence of . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5 Costs 13
6 Exponential distribution 15
6.1 Memorylessness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.2 Total probability law . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.3 Competing exponentials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7 The Poisson Process 17
7.1 Definition 1 via Exponential inter-arrivals . . . . . . . . . . . . . . . . . . . . . . . . . . 17
7.2 Definition 2 via Poisson increments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
7.3 The Poisson Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
7.3.1 Merging and splitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
7.4 Merging and splitting for Poisson Process . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1
,1 Introduction DTMC
A Discreet Time Markov Chain (DTMC) on a countable state space S that is time-homogeneous.
• is a sequence of random variables {Xn , n = 0, 1, 2, . . . } with values in S,
– n is referred to as time
– Xn is referred to as the state at time n, Xn ∈ S
• which has the Markov property: for all n = 0, 1, 2, . . . , for all i, j, i1 , . . . , in−1 ∈ S,
P (Xn+1 = j|X0 = i0 , X1 = i1 , . . . , Xn−1 in−1 ,Xn = i) = P (Xn+1 = j|Xn = i)
i.e. the history does not influence the future (only the present can influence the future).
• and lastly whose one-step transition probabilities are the same at all times n, P (Xn+1 = j|Xn =
i) =: pij
– P := (pij , i, j ∈ S) is the transition matrix
– a transition diagram depicts the pij ’s on S
Example - machine reliability
Formulate a DTMC of the following situation. A machine can be up(1) or down(0),
• if up today then up tomorrow with a probability of 0.98
• if down today then up tomorrow with a probability of 0.97
Xn := state of the machine on day n
S = {0, 1}
P (X1 = 1|X0 = 1) = P (Up tomorrow given up today) = 0.98
P (X1 = 0|X0 = 1) = P (Down tomorrow given up today) = 1 − 0.98 = 0.02
P (X1 = 1|X0 = 0) = P (Up tomorrow given down today) = 0.97
P (X1 = 0|X0 = 0) = P (Down tomorrow given down today) = 1 − 0.97 = 0.03
The transition diagram:
0.97
0.03 0 1 0.98
0.02
The transition matrix
0.03 0.02
P =
0.97 0.98
The Markov property holds since it is implicitly given, that only the present influences the
transition probabilities.
Time-homogeneity holds since the value of n does not influence the transition probabilities.
2
,Example - Harry’s diner
Harry has dinner at either restaurant A or B. His choice depends on the previous two evenings:
• After . . . AA in A wp 0.2
• After . . . BA in A wp 0.4
• After . . . AB in B wp 0.5
• After . . . BB in B wp 0.3
Xn := The restaurant at evening n,
S = {A, B}
Time-homogeneity holds since the value of n does not influence the transition probabilities.
However, the Markov property does not hold because the history influences the future. We
solve this by formulating a new variable:
Yn := {Xn−1 , Xn } and S = {AA, AB, BA, BB}
Now the Markov property does apply since: P (Yn+1 = j|Y0 , Y1 , . . . , Yn ) = P (Yn+1 = j|Yn )
0.2 AA BB 0.3
0.5
0.8 0.7
0.4
0.6
AB BA
0.5
3
, 2 Transient distribution, Hitting time and probabilities
The probability to visit a sequence of states:
P (Xn = in , Xn−1 = in−1 , . . . , X1 = i1 ) = pin−2 in−1 pi1 i2 . . . pin−2 in−1 pin−1 in
Proof.
P (Xn = in , Xn−1 = in−1 , . . . , X1 = i1 ) =P (Xn = in |Xn−1 = in−1 , . . . , X2 = i2 , X1 = i1 , X0 = i0 )∗
P (Xn−1 = in−1 |Xn−2 = in−1 , . . . , X2 = i2 , X1 = i1 , X0 = i0 ) ∗ · · · ∗
P (X2 = i2 |X1 = i1 , X0 = i0 ) ∗ P (X1 = i1 |X0 = i0 )
= P (Xn = in |Xn−1 = in−1 ) ∗ P (Xn−1 = in−1 |Xn−2 = in−2 ) ∗ · · · ∗
P (X2 = i2 |X1 = i1 ) ∗ P (X1 = i1 |X0 = i0 )
= pin−2 in−1 pi1 i2 . . . pin−2 in−1 pin−1 in
n-step transition probabilities:
(n)
pij := P (Xn = j|X0 = i)
Time-homogeneity also applies for n-step transition probabilities, thus:
(n)
P (Xm+n = j|Xm = i) = pij , same for all m.
(n)
Theorem 2.1. The matrix (pij : i, j ∈ S) of n-step transition probabilities is equal to (P n )ij .
The transient distribution at time n is the distribution of Xn , with the following notation:
(n)
πj := P (Xn = j),
(n)
π (n) := rowvector(πj : j ∈ S)
The distribution of π (0) is called the initial distribution of the Markov chain.
Theorem 2.2. The transient distribution at time n is give by π (n) = π (0) P n
Example - machine reliability
• if the machine is up today, what is the probability that it will be up three days from now?
(3)
P (X3 = 1|X0 = 1) = p11 = 0.979798
• if today the machine is up with probability 0.3, what are the chances it will be up on day 3
from now and what is the probability it will be down on day 3 from now?
π (0) = (0.7; 0.3)
π (3) = (P (X3 = 0), P (X3 = 1))
= π (0) P 3
= (0.7 ∗ 0.020203 + 0.3 ∗ 0.020202; 0.7 ∗ 0.979797 + 0.3 ∗ 0.979798)
= (0.0202027; 0.9797973)
4
