Summary
Summary - Stochastic Modeling period 1 (X_400646)
- Course
- Institution
This summary includes all material of the first period that is needed for the midterm. The summary includes detailed examples on all topics.
[Show more]
Seller
Follow
havikjavanas
Content preview
Stochastic Modeling X 400646 period 1Havikja 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller havikjavanas. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $11.34. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
57727 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now