AMS 309: STOCHASTIC PROCESSES I
LECTURE NOTES
Table of Contents
Chapter One ................................................................................................................................................................................ 3
Probability Generating Functions ...................................................................................................................................... 3
1.1 Introduction................................................................................................................................................................... 3
1.2 Generating Functions................................................................................................................................................. 3
1.3 Mean and Variance of a Random Variable in Terms of the PGF and its Derivatives. ...................... 4
1.4 Methods of Obtaining the Coefficients of the Generating Function A(S) ............................................. 4
1.5.1 PGF of a Sum of Random Number of Independent and Identically Distributed Variables ... 7
1.5.2 The Mean Value and Variance of 𝐙𝐍 .......................................................................................................... 7
Chapter Two ............................................................................................................................................................................. 10
Discrete Branching Process................................................................................................................................................ 10
2.1 Introduction................................................................................................................................................................. 10
2.2 The PGF of the nth Generation............................................................................................................................. 10
2.3 The Mean and Variance of the Size of the nth Generation ....................................................................... 11
Chapter Three .......................................................................................................................................................................... 17
Markov Chains ......................................................................................................................................................................... 17
3.1 Introduction................................................................................................................................................................. 17
3.2 Higher Order Transition Probabilities ............................................................................................................. 18
3.2.1 Higher Order Absolute Probabilities ........................................................................................................ 19
3.3 Classification of the States of a Markov Chain ............................................................................................... 20
3.3.1 Persistent and Transient States .................................................................................................................. 20
3.3.2 Irreducible Closed Sets ................................................................................................................................... 21
3.3.3 Irreducible Markov Chain.............................................................................................................................. 22
3.4 Stationary (or Invariant) Distributions ........................................................................................................... 23
Chapter Four ............................................................................................................................................................................ 29
Absorbing Markov Chains and Random Walk Models ............................................................................................. 29
4.1 Absorbing Markov Chain........................................................................................................................................ 29
, 2
4.2 Higher orders of P .................................................................................................................................................... 29
4.3 Application and Interpretation of the Fundamental Matrix (𝐍 = It − 𝐐 − 𝟏) ............................... 30
4.4 Interpretation of 𝐁 = 𝐍𝐑 .................................................................................................................................... 31
4.5 Random Walk and Ruin Problem ....................................................................................................................... 33
4.2.1 Gambler`s Ruin Problem ................................................................................................................................ 34
Chapter Five ............................................................................................................................................................................. 39
Birth and Death Processes .................................................................................................................................................. 39
5.1 Introduction................................................................................................................................................................. 39
5.3 Special Cases of Birth and Death Processes ................................................................................................... 40
5.3.1 The Pure Birth Process ................................................................................................................................... 40
5.3.2 Simple Birth and Death Process ................................................................................................................. 47
5.4 Waiting Line and Servicing Problems: Servicing Problem where there are Infinitely Many
Channels Available ........................................................................................................................................................... 50
References
1. An Introduction to Probability Theory and its Applications by William Feller
2. Elements of Stochastic Processes by Norman and J. Bailey
, 3
Chapter One
Probability Generating Functions
1.1 Introduction
A mathematical model which specifies complete probability distribution of the number of
individuals in a given system at each point of time is a stochastic model.
The whole process, determined by the probability distribution as a function of time is
called a stochastic process (or probability process).
The simplest processes occur at discrete time intervals (branching processes and Markov
chains). Birth-and–death processes occur at continuous time.
The random variables involved in all cases are discrete and take positive integer values.
If we are dealing with processes involving large populations, it may be appropriate to use a
deterministic model instead of a stochastic model. Deterministic models do not involve any
probability distribution.
1.2 Generating Functions
Definition
Let 𝑎0 , 𝑎1 , 𝑎2 , . . , to be a sequence of real numbers.
If A(s) = 𝑎0 + 𝑎1 𝑠 + 𝑎2 𝑠 2 + . . = ∑∞
𝑛=0 𝑎𝑛 𝑠
𝑛
converges, then A(s) is a generating
function of the sequence {𝑎n }.
Probability Generating Function (pgf)
Definition
Let X to be an integral valued random variable and p𝑥 = Pr(X = 𝑥) , 𝑥 = 0, 1, 2, . . ∞.
The function G(s) = ∑ p𝑥 s 𝑥 is called the probability generating function (pgf) of the
probability distribution {p𝑥 }.
The pgf converges for at least |s|≤1. If we let s = 1, we get, G(1) = ∑ p𝑥 = 1
Alternatively, we see that G(s) = ∑ p𝑥 sx = ∑ Pr(X = 𝑥) s 𝑥 = E(s X )
Therefore 𝐆(𝐬) = 𝐄(𝐬𝐗 )
Uses of the pgf
The probability generating function once obtained can be used to;
(i) Obtain the mean and variance of the probability distribution.
(ii) Determine the probabilities for some or all the values of X.
(iii) Identify the actual probability distribution.
, 4
1.3 Mean and Variance of a Random Variable in Terms of the PGF and its Derivatives.
G′ (s) = ∑∞
𝑥=1 𝑥p𝑥 s
𝑥−1
= ∑∞
i=0 𝑥p𝑥 s
𝑥−1
If we let s = 1, we get, G′ (1) = ∑ 𝑥p𝑥 = E(X).
Therefore 𝐄(𝐗) = 𝐆′ (𝟏) = 𝛍
Also G′′ (s) = ∑∞𝑥=2 𝑥 (𝑥 − 1)p𝑥 s
𝑥−2
By letting s = 1, we get,
G′′ (1) = ∑∞ ∞ ∞ 2 ∞
𝑥=2 𝑥(𝑥 − 1)p𝑥 = ∑𝑥=0 𝑥(𝑥 − 1)p𝑥 = ∑𝑥=0 𝑥 p𝑥 − ∑𝑥= 𝑥 p𝑥
= E(X 2 ) − E(X) = (σ2 + μ2 ) − μ where σ2 = Var(X).
Therefore, 𝛔𝟐 = 𝐆′′ (𝟏) + 𝐆′ (𝟏) − {𝐆′ (𝟏)}𝟐
Example 1.1
𝜆𝑥
Find the pgf of the Poisson distribution; f(𝑥) = p𝑥 = e−λ ; 𝑥 = 0, 1, 2, . . .
x!
Use the pgf to find the mean and the variance of the distribution.
Solution
λ𝑥
G(S) = E(s X ) = e−λ ∑∞ x
𝑥=0 s 𝑥!
(Sλ)x
= e−λ ∑∞
𝑥=0 𝑥!
Sλ Sλ 2 Sλ 3
= e−λ [1 + + ( ) + ( ) + . . ] = e−λ [eSλ ]
1 2! 3!
λ(S−1)
G(S) = e is the pgf.
′ (s)
G = λe [e ] and G′′ (s) = λ2 e−λ [eSλ ]
−λ Sλ
E(X) = G′ (1) = λ and σ2 = G′′ (1) + G′ (1) − {G′ (1)}2 = λ2 + λ − λ2 = λ.
The mean and variance are both equal to λ.
1.4 Methods of Obtaining the Coefficients of the Generating Function A(S)
For a pgf, p𝑥 = Pr(X = 𝑥) = Coeff. of s 𝑥 and also ∑ p𝑥 = 1
(a) Power series expansion of A(S)
A(s) = 𝑎0 + 𝑎1 𝑠 + 𝑎2 𝑠 2 + 𝑎3 𝑠 3 + . .
𝑎n = coeff. of sn
(b) Differentiation of A(S)
A(0) = 𝑎0
LECTURE NOTES
Table of Contents
Chapter One ................................................................................................................................................................................ 3
Probability Generating Functions ...................................................................................................................................... 3
1.1 Introduction................................................................................................................................................................... 3
1.2 Generating Functions................................................................................................................................................. 3
1.3 Mean and Variance of a Random Variable in Terms of the PGF and its Derivatives. ...................... 4
1.4 Methods of Obtaining the Coefficients of the Generating Function A(S) ............................................. 4
1.5.1 PGF of a Sum of Random Number of Independent and Identically Distributed Variables ... 7
1.5.2 The Mean Value and Variance of 𝐙𝐍 .......................................................................................................... 7
Chapter Two ............................................................................................................................................................................. 10
Discrete Branching Process................................................................................................................................................ 10
2.1 Introduction................................................................................................................................................................. 10
2.2 The PGF of the nth Generation............................................................................................................................. 10
2.3 The Mean and Variance of the Size of the nth Generation ....................................................................... 11
Chapter Three .......................................................................................................................................................................... 17
Markov Chains ......................................................................................................................................................................... 17
3.1 Introduction................................................................................................................................................................. 17
3.2 Higher Order Transition Probabilities ............................................................................................................. 18
3.2.1 Higher Order Absolute Probabilities ........................................................................................................ 19
3.3 Classification of the States of a Markov Chain ............................................................................................... 20
3.3.1 Persistent and Transient States .................................................................................................................. 20
3.3.2 Irreducible Closed Sets ................................................................................................................................... 21
3.3.3 Irreducible Markov Chain.............................................................................................................................. 22
3.4 Stationary (or Invariant) Distributions ........................................................................................................... 23
Chapter Four ............................................................................................................................................................................ 29
Absorbing Markov Chains and Random Walk Models ............................................................................................. 29
4.1 Absorbing Markov Chain........................................................................................................................................ 29
, 2
4.2 Higher orders of P .................................................................................................................................................... 29
4.3 Application and Interpretation of the Fundamental Matrix (𝐍 = It − 𝐐 − 𝟏) ............................... 30
4.4 Interpretation of 𝐁 = 𝐍𝐑 .................................................................................................................................... 31
4.5 Random Walk and Ruin Problem ....................................................................................................................... 33
4.2.1 Gambler`s Ruin Problem ................................................................................................................................ 34
Chapter Five ............................................................................................................................................................................. 39
Birth and Death Processes .................................................................................................................................................. 39
5.1 Introduction................................................................................................................................................................. 39
5.3 Special Cases of Birth and Death Processes ................................................................................................... 40
5.3.1 The Pure Birth Process ................................................................................................................................... 40
5.3.2 Simple Birth and Death Process ................................................................................................................. 47
5.4 Waiting Line and Servicing Problems: Servicing Problem where there are Infinitely Many
Channels Available ........................................................................................................................................................... 50
References
1. An Introduction to Probability Theory and its Applications by William Feller
2. Elements of Stochastic Processes by Norman and J. Bailey
, 3
Chapter One
Probability Generating Functions
1.1 Introduction
A mathematical model which specifies complete probability distribution of the number of
individuals in a given system at each point of time is a stochastic model.
The whole process, determined by the probability distribution as a function of time is
called a stochastic process (or probability process).
The simplest processes occur at discrete time intervals (branching processes and Markov
chains). Birth-and–death processes occur at continuous time.
The random variables involved in all cases are discrete and take positive integer values.
If we are dealing with processes involving large populations, it may be appropriate to use a
deterministic model instead of a stochastic model. Deterministic models do not involve any
probability distribution.
1.2 Generating Functions
Definition
Let 𝑎0 , 𝑎1 , 𝑎2 , . . , to be a sequence of real numbers.
If A(s) = 𝑎0 + 𝑎1 𝑠 + 𝑎2 𝑠 2 + . . = ∑∞
𝑛=0 𝑎𝑛 𝑠
𝑛
converges, then A(s) is a generating
function of the sequence {𝑎n }.
Probability Generating Function (pgf)
Definition
Let X to be an integral valued random variable and p𝑥 = Pr(X = 𝑥) , 𝑥 = 0, 1, 2, . . ∞.
The function G(s) = ∑ p𝑥 s 𝑥 is called the probability generating function (pgf) of the
probability distribution {p𝑥 }.
The pgf converges for at least |s|≤1. If we let s = 1, we get, G(1) = ∑ p𝑥 = 1
Alternatively, we see that G(s) = ∑ p𝑥 sx = ∑ Pr(X = 𝑥) s 𝑥 = E(s X )
Therefore 𝐆(𝐬) = 𝐄(𝐬𝐗 )
Uses of the pgf
The probability generating function once obtained can be used to;
(i) Obtain the mean and variance of the probability distribution.
(ii) Determine the probabilities for some or all the values of X.
(iii) Identify the actual probability distribution.
, 4
1.3 Mean and Variance of a Random Variable in Terms of the PGF and its Derivatives.
G′ (s) = ∑∞
𝑥=1 𝑥p𝑥 s
𝑥−1
= ∑∞
i=0 𝑥p𝑥 s
𝑥−1
If we let s = 1, we get, G′ (1) = ∑ 𝑥p𝑥 = E(X).
Therefore 𝐄(𝐗) = 𝐆′ (𝟏) = 𝛍
Also G′′ (s) = ∑∞𝑥=2 𝑥 (𝑥 − 1)p𝑥 s
𝑥−2
By letting s = 1, we get,
G′′ (1) = ∑∞ ∞ ∞ 2 ∞
𝑥=2 𝑥(𝑥 − 1)p𝑥 = ∑𝑥=0 𝑥(𝑥 − 1)p𝑥 = ∑𝑥=0 𝑥 p𝑥 − ∑𝑥= 𝑥 p𝑥
= E(X 2 ) − E(X) = (σ2 + μ2 ) − μ where σ2 = Var(X).
Therefore, 𝛔𝟐 = 𝐆′′ (𝟏) + 𝐆′ (𝟏) − {𝐆′ (𝟏)}𝟐
Example 1.1
𝜆𝑥
Find the pgf of the Poisson distribution; f(𝑥) = p𝑥 = e−λ ; 𝑥 = 0, 1, 2, . . .
x!
Use the pgf to find the mean and the variance of the distribution.
Solution
λ𝑥
G(S) = E(s X ) = e−λ ∑∞ x
𝑥=0 s 𝑥!
(Sλ)x
= e−λ ∑∞
𝑥=0 𝑥!
Sλ Sλ 2 Sλ 3
= e−λ [1 + + ( ) + ( ) + . . ] = e−λ [eSλ ]
1 2! 3!
λ(S−1)
G(S) = e is the pgf.
′ (s)
G = λe [e ] and G′′ (s) = λ2 e−λ [eSλ ]
−λ Sλ
E(X) = G′ (1) = λ and σ2 = G′′ (1) + G′ (1) − {G′ (1)}2 = λ2 + λ − λ2 = λ.
The mean and variance are both equal to λ.
1.4 Methods of Obtaining the Coefficients of the Generating Function A(S)
For a pgf, p𝑥 = Pr(X = 𝑥) = Coeff. of s 𝑥 and also ∑ p𝑥 = 1
(a) Power series expansion of A(S)
A(s) = 𝑎0 + 𝑎1 𝑠 + 𝑎2 𝑠 2 + 𝑎3 𝑠 3 + . .
𝑎n = coeff. of sn
(b) Differentiation of A(S)
A(0) = 𝑎0
