Stochastic Processes
Part 2
Arrival Process (Pure Birth Process) 2
It is a counting process {N(t), t ∈ [0,∞)}, where N(t) denotes the number of arrivals (births)
occurred in time t, i.e., in [0, t] with N(0) = 0 and average rate of arrival λ > 0, and which
satisfies the following three assumptions:
1) The probability that an arrival occurs between time t and time t + Δt is equal to λΔt + o(Δt).
That is, Pr {one arrival occurs between t and t + Δt } = λΔt + o(Δt), where λ is a constant
independent of N(t), Δt is an incremental element, and o(Δt) denotes a quantity that
becomes negligible when compared to Δt as Δt → 0.
2) Pr { more than one arrival between t and t + Δt } = o(Δt), i.e., almost negligible.
3) The numbers of arrivals in non-overlapping intervals are statistically independent;
that is, the process has independent increments.
Arrival Process (Pure Birth Process) 3
State Transition Diagram of Pure Birth Process
• The circles represents the state of the process, i.e., the number of arrivals in time t.
• The directed arcs represents the transitions between the states which occur with rate λ.
• A birth process takes values in the whole numbers and can only increase by one
(a "birth") or remain unchanged.
Arrival Process (Pure Birth Process) 4
A pure birth process {N(t), t ∈ [0,∞)} is same as a Poisson process, PP(λ).
This means :
• The random variable N(t) denoting number of arrivals in time t follows
Poisson distribution with parameter λt, i.e., P(λt).
• Equivalently, it can be said that the time between successive arrivals/births,
i.e., the interarrival time follows an exponential distribution with parameter
λ, i.e., exp(λ).
Next, we are going to derive the above mentioned results.
Arrival Process (Pure Birth Process) 5
Given a pure birth process {N(t), t ∈ [0,∞)} with average birth rate λ, and which
satisfies the following assumptions :
1. N(0) = 0.
2. Pr { one arrival occurs between t and t + Δt } = λΔt + o(Δt).
3. Pr { more than one arrival between t and t + Δt } = o(Δt).
4. Numbers of arrivals in non-overlapping intervals are statistically independent.
To prove: N(t) follows P(λt), i.e., P{N(t) = n } denoted by pn(t) for all n ≥ 0 is given by
Arrival Process (Pure Birth Process) 6
Proof: We wish to calculate pn(t), the probability of n arrivals in a time interval of
length t, n being an integer ≥ 0.
We will do this by first developing / constructing differential–difference equations
for the arrival process.
For this consider the following state transition diagram of pure birth process:
We construct two equations, one for n = 0, and a general equation for all n ≥ 1.
Arrival Process (Pure Birth Process) 7
• We define pn(t) = Pr{ There are n customers in the system at time t} which is also
same as the Pr{n arrivals took place in time t}.
• We begin by constructing equation for pn(t + Δt).
0 Time scale, t t t + Δt
• The time interval [0, t + Δt] is divided into two non-overlapping intervals, i.e.,
[0, t] and [t, t+Δt].
• We now consider the arrivals occurring in the two intervals and construct the
equations.
8
9
10
11
Arrival Process (Pure Birth Process) 12
Thus, if we consider the random variable defined as the number of
arrivals to a queueing system by time t, this random variable has
the Poisson distribution given by
for all n ≥ 0 with a mean of λt arrivals, or a mean arrival rate
(arrivals per unit time) of λ.
Arrival Process (Pure Birth Process) 13
We now show that :
If the arrival process is Poisson, an associated random variable
defined as the time between successive arrivals (interarrival
time) follows the exponential distribution.
Let T be the random variable “time between successive arrivals”;
then
14
• Thus, T has the exponential distribution with mean 1/λ.
• We would intuitively expect the mean time between arrivals to be 1/λ if the mean
arrival rate is λ.
• It can also be shown that if the interarrival times are independent and have the
same exponential distribution, then the arrival rate follows the Poisson
distribution, P(λ).
Departure Process (Pure Death Process) 15
It is a counting process {N(t), t ∈ [0,∞)}, where N(t) denotes the number of departures
(deaths) occurred in time t, i.e., in [0, t] with N(0) = 0 and average rate of departure
µ> 0, and which satisfies the following three assumptions:
1) Pr { one departure occurs between t and t + Δt } = µΔt + o(Δt), where µ is a constant
independent of N(t), Δt is an incremental element, and o(Δt) denotes a quantity
that becomes negligible when compared to Δt as Δt → 0.
2) Pr { more than one departure between t and t + Δt } = o(Δt), i.e., negligible.
3) The numbers of departures in non-overlapping intervals are statistically
independent; that is, the process has independent increments.
Departure Process (Pure Death Process) 16
A pure death process {N(t), t ∈ [0,∞)} is same as a truncated Poisson process, PP(µ).
This means :
• The random variable N(t) denoting number of departures in time t follows a
truncated Poisson distribution with parameter µt, i.e., P(µt).
• Equivalently, it can be said that the time between successive departures,
i.e., the service time / inter-departure time follows an exponential
distribution with parameter µ, i.e., exp(µ).
Next, we are going to derive the above mentioned results.
Departure Process (Pure Death Process) 17
Given a pure death process {N(t), t ∈ [0,∞)} with average death rate µ, and which
satisfies the following assumptions :
1. At time t=0, there are, say, N customers in the system.
2. Pr { one departure occurs between t and t + Δt } = µ Δt + o(Δt).
3. Pr { more than one departure between t and t + Δt } = o(Δt).
4. Numbers of departures in non-overlapping intervals are statistically
independent.
To prove:
N(t) follows P(µt), i.e., P{N(t) = n } denoted by pn(t) for all n ≥ 0 is given by a
truncated Poisson p.m.f.
Departure Process (Pure Death Process) 18
Proof:
• We wish to calculate the probability of n departures in a time interval of
length t, n being an integer ≥ 0.
• For this we define pn(t) = Pr { There are n customers in the system at time t }.
• Therefore, Pr { n departures took place in time t } = Pr {There are (N – n)
customers in the system at time t }.
• We will do this by first developing / constructing differential–difference
equations for the departure process.
Departure Process (Pure Death Process) 19
State Transition Diagram of Pure Death Process
We construct three differential equations,
one for n = 0, one for n = N, and a general equation for all n, 1 ≤ n < N.
Departure Process (Pure Death Process) 20
• We define pn(t) : Pr { There are n customers in the system at time t} which is also
same as the Pr {(N – n) departures took place in time t}.
• We begin by constructing equation for pn(t + Δt).
• The time interval [0, t + Δt] is divided into two non-overlapping intervals, i.e.,
[0, t] and [t, t+Δt].
• We now consider the arrivals occurring in the two intervals and construct the
equations.
21
22
23
24
25
26
General Birth-Death Process (BDP) 27
• A birth–death process is a specific type of continuous-time Markov chain.
• It consists of a set of states {0,1,2,…}, typically denoting the “population”
of some system.
• State transitions occur as unit jumps up or down from the current state.
• When the system is in state n ≥ 0, the time until the next arrival / birth is
an exponential random variable with parameter λn.
• That is, the rate of next arrival into the system when there are n in the
system is λn.
• At an arrival, the system moves from state n to state n+1.
General Birth-Death Process (BDP) 28
• When the system is in state n ≥ 1, the time until the next departure/death is
an exponential random variable with parameter μn.
• That is, the rate of next departure from the system when there are n in the
system is µn.
• At a departure, the system moves from state n to state n−1.
State transition diagram (birth-death process)
General Birth-Death Process (BDP) 29
• As the inter-arrival times are exponential, arrivals follow Poisson(λn).
• As the inter-departure times are also exponential, departures follow Poisson(μn).
• We can make the following probability statements for a transition during (t, t+Δt]:
• P(one birth) = λn Δt + o(t),
• P(no birth) = 1 − λn Δt + o(t),
• P(more than one birth) = o(t),
• P(one death) = μn Δt + o(t),
• P(no death) = 1 − μn Δt + o(t),
• P(more than one death) = o(t).
• In other words, only one event can take place at one point of time, and
• Non-overlapping intervals are statistically independent.
General Birth-Death Process (BDP) 30
• Based on these assumptions, we can derive the steady-state
probability distribution of the number of customers in the system
(also called as steady-state system-size probability distribution).
• Steady-state system-size probability distribution is denoted by
pn = Pr{N = n} = 𝐥𝐢𝐦 𝐏 𝐍 𝐭 = 𝐧 ; n = 0, 1, 2,…
𝐭→∞
• Therefore, pn ; n = 0, 1, 2,… represents the p.m.f of number of
customers in the system (i.e., p.m.f of random variable N).
General Birth-Death Process (BDP) 31
Objective :
• To derive steady-state system-size probability distribution, i.e., pn , n ≥ 0.
• For this, we first construct system of differential-difference equations,
and then solve the system in the long run, i.e., as t → ∞ .
• We construct two equations, one for n = 0 and one for all n > 0.
32
33
34
35
36
Concept of flow balance in steady-state
• In steady state, the rate of transitions out of a given state must
equal the rate of transitions into that state.
Consider equations (6) and (7)
Concept of flow balance in steady-state
• The left side of equation (7) is the rate of transitions out of state n, and
the right side is the rate of transitions into state n.
• Thus, the equation is simply balancing the rate of transitions into and out
of state n. Hence, these equations are called as Balance Equations.
General Birth-Death Process 39
Special cases of general BDP:
• A pure birth process is a BDP with µi = 0 for all i = 1, 2, 3, …
• A pure death process is a BDP with λi = 0 for all i = 0, 1, 2, 3, …
• A Poisson process is a BDP with
λi = λ for all i = 0, 1, 2, … and
µi = 0 for all i = 1, 2, …