Markov Chain and Queuing System

Zijing Hu

October 15, 2022

Contents

1 Discrete-Time Markov Chain (DTMC) 1

2 Continuous-Time Markov Chain (CTMC) 11

3 Poisson Process 14

4 Queuing System 15

*This note is based on ECEN 755: Stochastic Systems by Dr. P. R. Kumar, TAMU.

1 Discrete-Time Markov Chain (DTMC)

Definition 1.1. A discrete-time Markov chain on a countable set, S, is a stochastic process satis-

fying the Markov property

P r (x(t) = i

|x(t − 1) = i

t−1

, . . . , x(0) = i

)

=P r (x(t) = i

|x(t − 1) = i

t−1

)

for any i

, . . . , i

∈ S and n ∈ N.

Consider only time-homogeneous Markov chains in which the transition probabilities are

time-invariant (Note that P

= I):

= p

(t) = P r (x(t + 1) = j|x(t) = i)

For a discrete time and time-homogeneous Markov chain on S we thus have that

P r(x(t) = i

, . . . , x(0) = i

) = p

t−1

· · · · · p

· π(i

)

where we use the notation

π(i

) = P r(x(0) = i

)

for the initial distribution of π

π(0). We also have π

π(t + k) = π

π(t)P

. Any probability vector

π(t) = (π

(t))

i∈S

and two-dimensional array of probabilities P = (p

)

i,j∈S

with

j∈S

= 1 for all

i ∈ S deﬁnes the distribution of a time-homogeneous Markov chain on S through the identity.

Definition 1.2. If π

π = π

πP, we say π

π is a steady state distribution for the Markov Chain.

Definition 1.3. For a Markov chain with state space S, consider a pair of states (i, j). We say that

j is reachable from i, denoted by i → j, if there exists an integer n ≥ 0 such that P

> 0.

Definition 1.4. If j is reachable from i, and i is reachable from j, then the states i and j are said

to communicate, denoted by i ←→ j.

The relation deﬁned by communication satisﬁes the following conditions:

1. All states communicate with themselves: P

= 1 > 0.

2. Symmetry: If i ←→ j, then j ←→ i.

3. Transitivity: If i ←→ k and k ←→ j, then i ←→ j.

Proposition 1.5. For each Markov chain, there exists a unique decomposition of the state space S

into a sequence of disjoint subsets C

, C

, ...,

S =

∞

[

i=1

in which each subset has the property that all states within it communicate. Each such subset is called

a communication class of the Markov chain.

Example 1.6. Here’s an example of DTMC:

D E

G H I

There are six communication classes: C

= {A, B, C}, C

= {D, E}, C

= {F }, C

= {G},

= {H}, and C

= {I, J, K, L, M }. Thus, we can draw the hierarchy of these communication

classes,

in which C

, C

, and C

are called transient communication class and C

, C

, and C

are called closed

communication class.

Definition 1.7. A communication class C s is said to be closed if there is no i ∈ C and j ∈ C

such

that i → j. Otherwise, it is said to be transient.

Theorem 1.8. If T = set of all transient states, then P r(x(t) ∈ T |x(0) ∈ T ) ≤ cr

, where 0 < r < 1.

Lemma 1.9. Suppose i −→ j and let N

= {t : p

(t) > 0}. N

i is closed under addition.

Theorem 1.10. If a set of non-negative integers is closed under addition then it contains all but a

ﬁnite numbers of multiples of its gcd (greatest common divisor).

Deﬁne N

= {t : (p

(t) > 0} and d

= gcd of N

. Then N

contains kd

expect for a ﬁnite

number of k

⋆

s. Note that d

is called the period of the communication class and period is a class

property.

Lemma 1.11. i −→ j ⇒ d

= d

Proof. Suppose i

−→ j

−→ i. Then n + m ∈ N

. With Theorem 1.10, we have i

−→ j

−−→ j

−→ i.

Then n + m ∈ N

and i

−→ j

(k+1)d

−−−−−→ j

−→ i. Then n + m ∈ N

for some ks. This implies d

Similarly, we have d

, which shows d

= d

Definition 1.12. (1) A Markov chain is irreducible if all states communicate with each other; (2)

A communication class is aperiodic if its period = 1; (3) A Markov chain is called regular if it is

irreducible and aperiodic.

Example 1.13. Aperiodic communication classes.

Let T be the set of all transient states and C

represent all closed communication classes. We can

write the structure of P

for general Markov chain as:

... C













× 0 · · · 0 0 C

0 ×

× · · · 0 0 C

0 0 · · · ×

× 0 C

× ×

× · · · ×

× ×

× T

If t goes to inﬁnite, the matrix becomes:

... C













× 0 · · · 0 0 C

0 ×

× · · · 0 0 C

0 0 · · · ×

× 0 C

× ×

× · · · ×

× 0 T

Theorem 1.14. Let P be a regular Markov chain. Then we have

(1) lim

n→∞

= A = [α

⊤

,α

⊤

, . . . ,α

⊤

]

⊤

(2) PA = AP, α

αP = α

(3) α

α is the unique invariant probability vector.

(4) For any π

π(0), we have lim

t→∞

π(t) → α

Proof. Taking any x, we can show that the diﬀerence between the max (M) and the min (m) elements

of lim

n→∞

→ 0. Suppose for all elements of P, we have P

≥ β > 0. Then,

t+1

≤ (1 − β)M

+ βm

t+1

≥ βM

+ (1 − β)m

⇒M

− m

≤ (1 − 2β)

− m

which proves (1). Using Proof by contradiction can prove (2) and (3).

Definition 1.15. Deﬁne a sequence {x

(1) Suppose that lim

n→∞

= x. We say the sequence {x

} converges to x.

(2) Suppose that lim

n→∞

i=1

= x. Then the sequence {x

} is “Ces`aro-Summable to x.”

(3) Take any γ ∈ (0, 1), deﬁne

i=0





n−i

(1 − γ)

Suppose that lim

n→∞

= x. Then the sequence {x

} is “Euler-Summable to x.”

Facts

If {x

} converges to x, then it is Ces`aro-Summable and Euler-Summable to x.

If {x

} is Ces`aro-Summable and Euler-Summable to x, then the two sums must be the same.

(Kemeny, J. G., Snell, J. L. Finite Markov Chains, Princeton, 1960, pp. 12)

Theorem 1.16. Let P be a irreducible Markov chain with d > 1. Then we have

(1) {P

} is Euler-Summable for all γ ∈ (0, 1)

(2) {P

} is Ces`aro-Summable

Proof. (1)

i=0





n−i

(1 − γ)

= [γI + (1 − γ)P]

which is a stochastic matrix of a regular Markov chain and converges to A when n goes to inﬁnity.

we also have

α [γI + (1 − γ)P] = α ⇒ α

αP = α

(2) We can show that

lim

n→∞

d−1

i=0

nd+i

→ B ⇒ lim

m→∞

i=0

m + 1

→ B

Now we show an example with d = 3. Then P can be written as

0 ×

× 0 C

0 0 ×

× C

× 0 0 C

and we also have

0 0 ×

× C

× 0 0 C

0 ×

× 0 C

, P

× 0 0 C

0 ×

× 0 C

0 0 ×

× C

0 0 C

0 R

0 C

0 0 R

where R

are stochastic matrices of regular Markov chains. Then we have

lim

n→∞

= lim

n→∞

0 0 C

0 R

0 C

0 0 R

→

0 0 C

0 A

0 C

0 0 A

Thus,

lim

n→∞

+ P

nd+1

+ P

nd+2

→ B

Definition 1.17. (Sample path behavior of Markov chain) we deﬁne the jumping time as

= 0, T

t+1

= min{t > T

, x(t) = x(T

)}

and holding time as

= T

i+1

− T

− 1.

Deﬁne the jump chain as

= x(T

)

x(t)

= 1 τ

= 3

Theorem 1.18. (1) {x

} is a Markov chain with transformation probability P, where

= 0, p

1 − p

(2) Given x

, τ

is geometrically distributed:

P r



= l|x

= i



= p

(1 − p

)

(3) Given x

, τ

and x

n+1

are independent with each other.

Proof.

P r



k+1

= j and τ

= l|x

= i



= p

· p

1 − p

· p

(1 − p

)

= P r



k+1

= j|x

= i



P r



= l|x

= i



Geometric distribution

A random variable z is said to be geometrically distributed with the parameter q ∈ (0, 1) if

p(z > t) = q

(1 − q). We also have p(z ≥ t) =

∞

t=T

(1 − q) = q

and p(z ≥ s + t|z ≥ s) = q

. We

say z is memoryless.

Finite and countable inﬁnite state Markov chain

• Same: “→”, “←→”, and hierarchy of communicating classes.

• Diﬀerent: there may be no closed communicating class; even if there is closed communicating

class, it may not have invariant distribution vector.

A warm-up example

Suppose that f (t) =

where α > 0. Then we have

+∞

f(t) dt =

+∞

dt =

(

α−1

if α > 1

+∞ otherwise

We also have

+∞

n=2

+∞

f(t) dt <

+∞

n=1

which suggests that

+∞

n=1

(

< ∞ if α > 1

= +∞ otherwise

Now let τ

= min{t ≥ 1 : x(t) = i} and M

= E[τ

|x(0) = i]. We can show that M

could be either

ﬁnite or inﬁnite:

• Suppose that ˜p

= 1/n

and

+∞

n=1

˜p

= c. Let p

= ˜p

/c be the probability of returning to

state i in n steps after starting from state i. Then we have

+∞

n=1

+∞

n=1

= +∞

• Suppose that ˜p

= 1/n

and

+∞

n=1

˜p

= d. Let p

= ˜p

/d. Then we have

+∞

n=1

+∞

n=1

< +∞

Definition 1.19. We say state i is (1) transient if P r(τ < +∞|x(0) = i) < 1; (2) null recurrent

if P r(τ < +∞|x(0) = i) = 1 and M

= +∞; (3) positive recurrent if P r(τ < +∞|x(0) = i) < 1

and and M

< +∞.

1 2 3 4 5

...

1 1 1 1 1

Here is an example of recurrent state. Deﬁne p

= P r(x(t + 1) = i|x(t) = 1) where i = 2, 3, ....

Thus, the mean return time M

+∞

n=2

. State 1 is null recurrent if M

= +∞ or positive

recurrent if M

< +∞.

Definition 1.20. Deﬁne the probability that the ﬁrst passage time from state i to state j is equal

to n as

(n) = P r



x(1) = j, x(2) = j, . . . , x(n − 1) = j, x(n) = j|x(0) = i



State i is transient if and only if

+∞

n=1

(n) < 1 or P r(τ

< +∞|x(0) = i) < 1.

State i is recurrent if and only if

+∞

n=1

(n) = 1 or P r(τ

< +∞|x(0) = i) = 1.

Note that p

(0) = δ

but f

(0) = 0 for all i and j. We can compute p

(n) and f

(n) for n > 0

as follows:

(n) = δ

m=0

(m)p

(n − m)

(n) = p

(n) − δ

−

n−1

m=0

(m)p

(n − m)

Definition 1.21. The (one-sided or unilateral) Z-transform is deﬁned as

X(z) = Z{x(n)} =

+∞

n=0

x(n) · z

Theorem 1.22. Let P

(z) and F

(z) be the Z-transforms of p

(n) and f

(n), respectively. We have

(z) =

1 − F

(z)

Proof.

(z) =p

(0) +

+∞

n=1

m=1

(m)p

(n − m)

=1 +

+∞

m=0

+∞

n=m

(m)p

(n − m)z

given that f

(0) = 0

=1 +

+∞

m=0

+∞

n=m

(m) · z

]

(n − m) · z

(n−m)

=1 +

+∞

m=0

(m) · z

+∞

n=0

(n) · z

let n ←− n − m

=1 + P

(z)F

(z)

When can you interchange limit and integral/summation? Below rules hold for both

integral and summation.

Example 1.23. Let f

(x) = 1 for any x ∈ [n − 1, n]. Otherwise f

(x) = 0. Then we have

+∞

(x) dx = 1, ∀n =⇒ lim

n→+∞

+∞

(x) dx = 1

lim

n→+∞

(x) = 0, ∀x =⇒

+∞



lim

n→+∞

(x) dx



= 0

Lemma 1.24. (Fatou’s Lemma) Suppose that f

(x) ≥ 0, ∀x and lim

n→∞

= f(x). Then we have

lim

n→∞

(x) dx ≥

f(x) dx

Theorem 1.25. (Monotone Convergence Theorem) If f

n−1

(x) ≥ f

(x), ∀x (f

(x) is monotonically

increasing in n) and lim

n→+∞

(x) = f(x), then

lim

x→+∞

(x) dx =

f(x) dx

Theorem 1.26. (Dominated Convergence Theorem) Suppose that |f

(x)| ≤ g(x), ∀n, x and

g(x) dx <

+∞, then

lim

x→+∞

(x) dx =

lim

n→+∞

(x) dx

Lemma 1.27. State i is transient ⇐⇒

+∞

n=1

(n) < +∞.

Proof. Use Theorem 1.22 and Theorem 1.25.

lim

z→1

+∞

n=0

(n)z

= lim

z→1

1 −

+∞

n=0

(n)z

+∞

n=0

(n) lim

z→1

1 −

+∞

n=0

(n) lim

z→1

+∞

n=0

(n) =

1 −

+∞

n=0

(n)

Thus, we have

+∞

n=0

(n) < +∞ ⇐⇒

+∞

n=0

(n) < 1 ⇐⇒ State i is transient

Lemma 1.28. State i is recurrent ⇐⇒

+∞

n=0

(n) = +∞

Proof. Let E

= 1 if x(n) = i. Otherwise E

= 0. Then

+∞

n=0

= E [# of returns to i]

Using Theorem 1.25 we have

+∞

n=0

+∞

n=0

E [E

] =

+∞

n=0

(n)

Lemma 1.29. Recurrence is a class property: if i ←→ j and i is recurrent, then j is recurrent.

Proof. Suppose i ←→ j and j is recurrent. Then we have

(n) ≥ p

(k)p

(n − k − l)p

(l)

+∞

n=0

(n) ≥ p

(k)

+∞

n=0

(n − k − l)p

(l) = +∞

Theorem 1.30. A special case of Blackwell’s Renewal Theorem (aperiodic Markov chain)

lim

n→+∞

(n) =

+∞

n=0

(n)

Lemma 1.31. For regular Markov chain, we have

lim

n→+∞

(n) =

+∞

n=0

(n)

Lemma 1.32. Positive recurrence is a class property.

Proof. Suppose that j is a positive recurrent state. Using Lemma 1.29 we know that i is recurrent.

We can ﬁnd p

(k) > 0 for some k and p

(l) > 0 for some l. Then we have

(n) ≥ p

(k)p

(n − k − l)p

(l)

= lim

n→+∞

(n) ≥ p

(k)



lim

n→+∞

(n − k − l)



(l) =

(k)p

(l) > 0

Theorem 1.33. For a regular, positive recurrent Markov chain, let lim

n→+∞

(n) = π

where π

> 0.

Then π

= 1, and these results are unique.

Proof. Step 1. Given that p

(n + 1) =

(n)p

, we take limits of both left and right sides and

use Fatou’s Lemma (Lemma 1.24):

= lim

n→+∞

(n + 1) = lim

n→+∞

(n)p

≥

lim

n→+∞

(n)p

Step 2.

≥

(2)

=⇒ π

≥

(2) ≥ · · · ≥

(n) ≥ . . .

Suppose that π

(n) for some n. Then it leads to contradiction

(n) =

=⇒ π

(n), ∀n

Step 3.

lim

n→+∞

(n) = π

=⇒

= 1

Definition 1.34. Let V (t) be a stochastic process and F

= {V (0), V (1), . . . , V (t)}. E|V (t)| < +∞.

• Martingale: E[V (t + 1)|F

] = V (t).

• Supermartingale: E[V (t + 1)|F

] ≤ V (t).

• Submartingale: E[V (t + 1)|F

] ≥ V (t).

Theorem 1.35. Supermartingale Convergence Theorem. Suppose V (t) ≥ 0 is a supermartingale

lim

t→+∞

V (t) = Random

Theorem 1.36. Submartingale Convergence Theorem. Suppose (1) V (t) ≥ 0 is a submartingale

and (2) lim sup E|V (t)| < +∞

lim

t→+∞

V (t) = Random

E|V (t)| < +∞

Theorem 1.37. L2-Super/sub/martingale Convergence Theorem. Suppose (1) V (t) ≥ 0 is a

super/sub/martingale and (2) E[V

(t)] ≤ C, ∀t

lim

t→+∞

V (t) = Random

E[V (t)] → E[V ], E|V (t) − V | → 0

Lemma 1.38. Borel–Cantelli Lemma. Suppose that E(t) represents some event and we have

+∞

t=0

P [E(t)] < +∞

Then E(t) happens only ﬁnitely many times with probability 1.

Compare it with Markov chain. Suppose x(t) = 0, P [x(t) = i|x(0) = i] = p

(t) and

+∞

t=0

(t) <

+∞. Then x(t) = i holds only for ﬁnitely many t.

Definition 1.39. A Lyapunov function for an autonomous dynamical system ˙y = g(y),where

g : R

→ R

, with an equilibrium point at y = 0 is a scalar function V : R

→ R that is continuous,

has continuous ﬁrst derivatives, is strictly positive for y = 0, and for which the time derivative

V = ∇V · g is non positive.

Example 1.40. Consider Lyapunov function

V (x

(t), x

(t)) =

(t) + x

(t))

(a) Suppose that an autonomous dynamical system is deﬁned as follows

(t)

= x

(t),

(t)

= −x

(t),

We have

= x

(t)

+ x

(t)

= 0

Hence x

(t) + x

(t) = x

(0) + x

(0).

(b) Suppose that an autonomous dynamical system is deﬁned as follows

(t)

= x

(t) − x

(t)(x

(t) + x

(t))

(t)

= −x

(t) − x

(t)(x

(t) + x

(t))

We have

V = −(x

+ x

) = −4V

. Hence

= −

4 dt =⇒ V (t) =

V (0)

+ 4t

V (t) → 0 as t → +∞

Definition 1.41. Let F denote the history information with respect to t. τ is a stopping point of

the event {τ ≤ t} is known at time t

Theorem 1.42. Suppose {V

} is a martingale with respect to {F

}. Let τ be a stopping point of {F

Then {V

min(τ,t)

} is a martingale.

Lemma 1.43. Suppose V (·) is a Lyapunov function and

E [V (x(t + 1))|x(t)] ≤ V (x(t)) − 1(x(t) = 0)

Let τ

is the ﬁrst time hit state 0 when starting from state i. Then

E[τ

] ≤ V (i)

Proof. Suppose that x(0) = i. We have

E [E [V (x(t + 1))|x(t)]] ≤ E [V (x(t)) − 1(x(t) = 0)]

E[1(x(t) = 0)] ≤ E[V (x(t))] − E [V (x(t + 1))]

E[τ

] =

t=0

E[1(x(t) = 0)] ≤ V (x(0)) − E [V (x(t + 1))] ≤ V (x(0)) = V (i)

Lemma 1.44. Deﬁne V (·) as in Lemma 1.43. Suppose

V (i) < +∞. Then the Markov chain is

positive recurrent.

Proof.

E[τ

] = p

i=0

E[τ

] ≤ p

i=0

V (i) < +∞

Theorem 1.45. (Foster’s Theorem) Let X = (X

)

n∈Z

be a DTMC on countable, irreducible state-

space X . If L : X → R

is a function with EL (X

) < ∞ and such that for some K > k ≥ 0 and

some ϵ > 0, X (k) = {x ∈ X : L(x) ≤ k} is ﬁnite, and

E [L (X

) | X

n−1

] < K, if L (X

n−1

) ≤ k

E [L (X

) − L (X

n−1

) | X

n−1

] < −ϵ, if L (X

n−1

) > k

then X is positive recurrent.

2 Continuous-Time Markov Chain (CTMC)

Definition 2.1. Continuous time Markov chain satisfying the Markov property

P r(x(t) = j|x(u) for u ≤ s) = P r(x(t) = j|x(s))

Hence

P r(x(t) = j|x(s) = i) = p

(t, s)

For time-homogeneous cases, we have

(t, s) = p

(t − s)

Theorem 2.2. Chapman–Kolmogorov equation:

(t, s) =

(t, u)p

(u, s) ∀u ∈ (s, t)

For time-homogeneous cases, we have P(s + t) = P(s)P(t) (semigroup property) where P(t) = [p

(t)]

Definition 2.3. The inﬁnitesimal generator of CTMC is deﬁned as the one-sided derivative

Q = lim

t→0

P(t) − P(0)

= lim

t→0

P(t) − I

Q is a real matrix independent of t.

Properties of Q (suppose that i = j):

= lim

t→0

(t) − 1

≤ 0

= lim

t→0

(t) − 0

≥ 0

The row sum of Q = lim

t→0

(t) − 1

= 0

Using Chapman–Kolmogorov equation, we have

P(s + t) = P

′

(s)P(t) =

dP(s + t)

d(s + t)

P(s + t) = P

′

(s + t)

s = 0 =⇒ P

′

(t) = QP(t) (Forward diﬀerential equation)

t = 0 =⇒ P

′

(s) = P(s)Q (Backward diﬀerential equation)

The solution of the above equations is

P(t) = e

= I + tQ +

+ . . .

Combined with the initial state, we have

π(t) = π

π(0)P(t)

′

(t) = π

π(0)P(t)Q = π

π(t)Q

Interpretation of π

′

(t) = π

π(t)Q: for j = i and samll t, we have (1) q

≈ p

(t)/t =⇒ rate of

probability ﬂow into j from i and (2) −q

=⇒ total rate of probability ﬂow out of i. Thus,

′

(t) = π

(t)q

j=i

(t)q

= π

(t)



total rate of ﬂow out of i



j=i

(t)



rate of ﬂow from j into i



Definition 2.4. π

π(t) is a stead state if π

′

(t) = 0 ⇔ π

π(t)Q = 0.

DTMC and CTMC

• Same: “←→”, closed communicating class, transient

• Diﬀerent: aperiodic

Note that for any CTMC we can sample {t, 2t, . . . kt, . . . } to get a DTMC:

P(kt) = P(t)P(t) · · · = P

(t)

Definition 2.5. Let x(0) = i. The leave time T

′

and return time T are deﬁned as

′

= min{t ≥ 0, x(t) = i}

T = min{t ≥ T

′

, x(t) = i}

Note that the deﬁnition of return time in terms of CTMC is diﬀerent from DTMC because one

has to ﬁrst leave the state before returning.

x(t)

Definition 2.6. We say state i is (1) transient if P r(T < +∞|x(0) = i) < 1; (2) null recurrent

if P r(T < +∞|x(0) = i) = 1 and E(T ) = +∞; (3) positive recurrent if P r(T < +∞|x(0) = i) < 1

and and E(T ) < +∞.

Sample Path Behavior of CTMC

Assume that the sample paths (1) have only isolated jumps (next jump is meaningful) and (2) are

right continuous.

Definition 2.7. The jump time is deﬁned as

= min{t > T

n−1

: x(t) = x(T

n−1

)}

The holding time is deﬁned as

= T

n+1

− T

Theorem 2.8. Sample Markov chain right after jump time: x(T

) (x(T

n+1

) = x(T

)). We have

1. {x(T

) : n ≥ 0} is a DTMC

2. τ

is exponential distributed: P r(z ≤ t) = 1 − e

−λt

and E[τ

] = −1/q

(suppose that x(T

) = i)

3. τ

and x(T

n+1

) are independent given x(T

)

Proof. We can sample from the Markov chain every h seconds. Denote the sampled sequence as x(kh)

where k = 0, 1, 2, . . . . Denote the sampled time points right after jumps as {x

h,J

}. As h → 0

, we

have (x

h,J

, x

h,J

, x

h,J

, . . . ) → (x(T

), x(T

), . . . ). Then, as h → 0

we have

h,J

(h)

1 − p

(h)

h ·

(h)−0

k=j

(h)−0

+ o(h)

k=j

[hq

+ o(h)]

−→

k=j

Suppose that x(T

) = i. Given that P(t) = e

, we have τ

∼ exp(−q

), which is a Markov chain.

Definition 2.9. Fraction of time spent on state i. Let τ

(i)

and T

(i)

denote the sampled holding

time and jump time for state i, respectively. Then,

= lim

t→+∞

1(x(s) = i) ds = lim

K→+∞

k=1

(i)

k=1

(i)

k+1

− T

(i)

)

= −

where

= E

(i)

k+1

− T

(i)

= −

Note that for positive recurrent Markov chain we have M

< +∞ and π

πQ = 0; for null recurrent

Markov chain we have M

= +∞. What does π

πQ = 0 mean?

0 =





i=j





+ π

i=j

− π

i=j

So the inﬂux and outﬂux of rates for j are equal.

3 Poisson Process

0 1 2 3 4 5

...

λ λ λ λ λ λ

Consider a CTMC with the inﬁnitesimal generator

Q =







−λ λ

. . . . . .







Suppose that N(0) = 0 (N(t) and x(t) are equivalent but in Poisson process we prefer to use N(t)).

Given π

′

(t) = π

π(t)Q, we have

dπ

(t)

= π

(t)q

= −λπ

(t)

dπ

(t)

= π

(t)q

+ π

(t)q

= λπ

(t) − λπ

(t)

......

dπ

(t)

= π

n−1

(t)q

n−1,n

+ π

(t)q

n,n

= λπ

n−1

(t) − λπ

(t)

Now we solve the above equations with π

π(0) = (1, 0, 0, . . . ):

(t) =

(λt)

−λt

π(t) =



−λt

, λte

−λt

, . . . ,

(λt)

−λt

, . . .



Another way to solve π

π(t) is to use z-transform Π(z, t) =

+∞

n=0

(t),

∂Π(z, t)

∂t

= −λπ

(t) + λ

+∞

n≥1

[π

n−1

(t) − π

(t)] = (zλ − λ)Π(z, t)

=⇒ Π(z, t) = e

(zλ−λ)t

= e

−λt

+ zλte

−λt

+ · · · + z

(λt)

−λt

+ . . .

Now we have

P r(N(t) − N (s) = k) = P r(N (t − s) = k) = e

−λ(t−s)

[λ(t − s)]

Theorem 3.1. Superposition of a Poisson process. If {N

(t) : t ≥ 0} and {N

(t) : t ≥ 0} are

two independent Poisson processes with respective rates λ

and λ

. Then, {N

(t) + N

(t) : t ≥ 0}

is a Poisson process with rate λ

+ λ

. The Poisson process {N

(t) + N

(t) : t ≥ 0} is called the

superposition of {N

(t) : t ≥ 0} and {N

(t) : t ≥ 0}

Theorem 3.2. Decomposition of a Poisson process. Consider a Poisson process {N (t) : t ≥ 0}

with rate λ. Suppose that each time an event occurs it is classiﬁed as either a type I or a type II event.

Suppose further that each event is classiﬁed as type I event with probability p and as type II event with

probability 1−p. Let N

(t) denote respectively the number of type I events occurring in [0, t]. Let N

(t)

denote respectively the number of type II events occurring in [0, t]. Note that N(t) = N

(t) + N

(t).

Then, {N

(t) : t ≥ 0} and {N

(t) : t ≥ 0} are independent Poisson processes with respective rates

= λp and λ

= λ(1 − p).

4 Queuing System

0 1 2 3 4

...

Definition 4.1. In a birth-death process, let x(t) denote the population, λ

the birth rate, and µ

the death rate. λ

and µ

can vary with time. Then, we have

Q =







−λ

−µ

−(λ

+ µ

) λ

−µ

−(λ

+ µ

) λ

. . . . . .







How to solve π

π, the steady state probability distribution? One way is to ﬁx π

and solve π

recurrently. But there’s a simpler way. Recall that in steady cases, the probability ﬂows between two

sets constituting a partition of the state space are in balance. We have µ

i+1

= λ

and hence

= π

n−1

i=0

i+1

∀n ≥ 1

Given that

+∞

i=0

= 1, we have

1 +

+∞

n=1



n−1

i=0

i+1



n−1

i=0

i+1

1 +

+∞

n=1



n−1

i=0

i+1



The CTMC is positive recurrent if and only if

+∞

n=1



n−1

i=0

i+1



< +∞.

Definition 4.2. M/M/1 queue represents the queue length in a system having a single server (the

“1”), where arrivals are determined by a Poisson process P oiss(λ) (the ﬁrst “M”) and job service

times have an exponential distribution exp(µ) (the second “M”).

According to the Birth-Death Process, we have π

= ρ

, where ρ = λ/µ is the utilization of

service. To ensure the system has a steady state, ρ < 1.

ρ =

mean service time

mean arrival time

We also have

+∞

= 1 − ρ = Pr(the service is idle)

ρ = Pr(the service is busy)

Let L denote the mean number of customers/items. Then,

L =

+∞

i=0

iπ

+∞

i=0

iρ

(1 − ρ) = ρ(1 − ρ)

dρ

+∞

i=1

1 − ρ

Theorem 4.3. Little’s Theorem. Let W denote mean delay. Then L = λW .

Proof. Suppose that

α(t) = # of arrivals in [0, t] minutes

δ(t) = # of departures in [0, t] minutes

A(t) =

(α(t) − δ(t)) dt = customer/item minutes

Then, when t goes to inﬁnity, we have

L =

A(t)

α(t)

= λW

The Little’s Theorem can be applied to model either waiting for service or mean of total time

spent. Denote the time to wait for service as W

and the mean of total time spent as W . We have

= W −

. Therefore, L

= λW

1−ρ

− ρ, where L

is the mean of total number of customers

in the queue (but not receiving service yet).

Example 4.4. M/M/c Queue.

0 1 2 3

...

c+1

...

2µ 3µ 4µ

cµ

cµ cµ

λ λ λ λ λ

λ λ

The system has steady state if and only if ρ < c. We also have

if i ≤ c

i−c

if i > c

Example 4.5. M/M/∞ Queue. In this system, we have W =

and L =

0 1 2 3

...

c+1

...

2µ 3µ 4µ

cµ

(c + 1)µ (c + 2)µ

λ λ λ λ λ

λ λ

Example 4.6. M/M/c/c Queue (Erlang Model of a Telephone Exchange). The last c rep-

resents the capacity of the system.

0 1 2 3

...

2µ 3µ 4µ

cµ

λ λ λ λ λ

Let λ,

, and c be the arrival rate, mean length of phone call, and number of lens, respectively.

Then the probability that the system is busy, π

, is

Given that

+∞

i=0

= 1, we have

+∞

i=0

, π

/c!

i=0

/i!

is called Erlang B formula or Erlang loss formula.

Arriving Customer’s Viewpoint

Let π

(n) = P r(the n-th arriving customer sees i customers when he arrives) and π

= lim

n→+∞

(n).

Example 4.7. Birth-death process. Let N(t) be the number of customers in the system at time t.

Assume there is a steady state.

= P r(N(t) = i|arriving in (t, t + h))

P r(arriving in (t, t + h))P r(N(t) = i)

+∞

j=0

P r(arriving in (t, t + h))P r(N(t) = j)

hπ

+∞

j=0

hπ

+∞

j=0

If λ

= λ, we have π

= π

Theorem 4.8. PASTA property (Poisson arrivals see time averages). If a Markov chain

has only unit jumps and steady state exists, then, asymptotically, arriving customers’ viewpoint is

equivalent to departing customers’ viewpoint.

Example 4.9. M/G/1. “G” refers to any general distribution, B(t), of the time of service time.

Let

= the number of customers in the system just after n-th service completed.

= the number of customers who arrive between the n-th and (n + 1)-th completed service.

Then X

n+1

= X

n+1

−1 if X

≥ 1. Otherwise, X

n+1

= A

n+1

. This is called embedded Markov

chain.

= P r(A = a) =

+∞

(λt)

−λt

dB(t)

Then we have

P =







+ k

. . .







We can rewrite the formula as X

n+1

= X

+ A

n+1

− 1(X

≥ 0). Let n → +∞ and assume the steady

state exists. We have

E[X] = E[X] + E[A] − E[1(X

≥ 0)] ⇒ E[A] = E[1(X

≥ 0)]

E[X

] = E[X

] + E[A

] + E[1(X

≥ 0)

] + 2E[XA] − 2E[X] − 2E[A 1(X

≥ 0)]

= E[X

] + E[A

] + E[A] + 2E[X]E[A] − 2E[X] − 2E[A

]

Given that

E[X] = L

E[A] =

+∞

λt dB(t) =

= ρ

E[A

] =

+∞

dB(t) = ρ

+ ρ + λ

V ar

we have the Pollaczek–Khinchine formula:

L = ρ +

+ λ

V ar

2(1 − ρ)

This shows that it is the variance of service time causes delay. If the service time is deterministic,

then we get the least delay

L = ρ

2(1 − ρ)

Example 4.10. G/M/1. “G” refers to any general distribution A(t) of the time between two arrivals.

Let

= the number of customers in the system just prior to the n-th arrival.

= the number of customers who are served in the n-th inter arrival time.

Then X

n+1

= X

+ 1 − B

= P r(B = m) =

+∞

(µt)

−µt

dA(t)

Then we have

P =







+∞

k=2

+∞

k=3

+∞

k=4

. . . . . . . . . . . . . . . . . .







Example 4.11. G/G/1 (G

′

′′

/1). Let

= waiting time for service to begin for the n-th customer.

= service time for the n-th customer. S

∼ G

′

= inter arrival time between the n-th and (n + 1)-th customer. T

∼ G

′′

Then W

n+1

= max{0, W

+ S

− T

} (Lindley equation) and we have

P r(W

n+1

≤ t) = F

n+1

(t) = P r(W

+ S

− T

≤ t)

F =

−∞

F (t − x) dU(x)

where U(x) = P r(S

− T

≤ x). The Wiener–Hopf method can be used to solve this expression.