3.3.2.3 Queuing application
A system (for instance a processor) processes jobs (such as computations) in synchronized manner. A waiting room (buffer) allows to store jobs before they are processed. The instants of synchronization are numbered 
and 
denotes the number of jobs in the system just after time 
.
Between time 
and time 
, a random number 
of new jobs arrive, and up to a random number 
of the 
jobs already there can be processed, so that
In a simple special case, there is an integer 
s.t. 
, and it is said that the queue has 
servers.
The r.v. 
are assumed to be i.i.d. and independent of 
, and then Theorem 1.2.3 yields that 
is a Markov chain on 
. We assume that
so that there is a closed irreducible class containing 
, and we consider the chain restricted to this class, which is irreducible. We further assume that 
and 
are integrable, and will see that then the behavior of 
depends on the joint law of 
essentially only through 
.
For 
, we have 
and hence, 
, and 
a.s., and 
, and thus 
by dominated convergence (Theorem A.3.5). We deduce a number of facts from this observation.
- If
, then there exists 
s.t. if 
then 
. Then, the Foster criterion (Theorem 3.3.6) with 
and 
yields that the chain is positive recurrent, and 
. - If
, then the Tweedie criterion (Theorem 3.3.4) with 
and 
yields that the chain cannot be positive recurrent. - If
and 
and 
are square integrable, then the Lamperti criterion (Theorem 3.3.3) with 
and 
yields that the chain is transient. If only 
is square integrable, then if 
is large enough then
and the chain
with arrival and potential departures given by 
is transient, and as 
then 
is transient. - If
and 
, then Theorem 3.3.5 with 
and 
yields that the chain is recurrent, and hence null recurrent.
3.3.2.4 Necessity of jump amplitude control
In Theorems 3.3.3 and 3.3.4, the hypotheses 
are quite natural, but the hypotheses 
controlling the jump amplitudes cannot be suppressed (but can be weakened).
We will see this on an example. Consider the queuing system with
Then, 
is s.t. 
and 
for 
and is a random walk on 
reflected at 
. For 
and 
with 
and 
, it holds that 
and 
and, for 
,
so that hypothesis 
of Theorem 3.3.4 is satisfied, and if 
, then
so that hypothesis 
of Theorem 3.3.3 is satisfied.
Nevertheless, 
and we have seen that 
is positive recurrent for 
, null recurrent for 
, and transient for 
.
The hypothesis in Theorem 3.3.5 and hypothesis 
in Theorem 3.3.6 are also quite natural. The latter is enough to obtain the bound 
for 
, but an assumption such as hypothesis 
must be made to conclude to positive recurrence. For instance, let 
be a Markov chain with matrix 
s.t.
For 
and 
, it holds that 
for 
, and hypothesis 
of Theorem 3.3.6 holds, but the chain is null recurrent as
3.3.3 Time reversal, reversibility, and adjoint chain
3.3.3.1 Time reversal in equilibrium
Let 
be a Markov chain, 
an integer, and 
for 
. Then,
and 
corresponds to a time-inhomogeneous Markov chain with transition matrices given by
This chain is homogeneous if and only if 
is an invariant law, that is, if and only the chain is at equilibrium.
3.3.3.2 Doubly stationary Markov chain
Let 
be a transition matrix with an invariant law 
. Let 
have law 
, let 
and 
be Markov chains of matrices 
and 
, which are independent conditional on 
, and let 
. Then, 
is a stationary Markov chain in time 
with transition matrix 
, called the doubly stationary Markov chain of matrix 
, which can be imagined to be “started” at 
.
3.3.3.3 Reversible measures
The equality 
holds if and only if 
solves the local balance equations (3.2.5).
Then, the chain and its matrix are said to be reversible (in equilibrium), and 
to be a reversible law for 
. The equations (3.2.5) are also called the reversibility equations and their nonnegative and nonzero solutions the reversible measures.
In equilibrium, the probabilistic evolution of a reversible chain is the same in direct or reverse time, which is natural for many statistical mechanics models such as the Ehrenfest Urn.
3.3.3.4 Adjoint chain, superinvariant measures, and superharmonic functions
We gather some simple facts in the following lemma.
This allows to understand the relations between Theorems 3.2.3 and 3.3.1. Let 
be an irreducible recurrent transition matrix on 
and 
an arbitrary canonical invariant law.
If 
is a superinvariant measure for 
, then the function 
is nonnegative and superharmonic for 
, which is irreducible recurrent, and Theorem 3.3.1 yields that 
is constant, that is, Theorem 3.2.3.
Conversely, if 
nonnegative and superharmonic for 
, then 
is a superharmonic measure for 
, and Theorem 3.2.3 yields that 
is constant, that is, the “only if” part of Theorem 3.3.1.
The following result can be useful in the (rare) cases in which a matrix is not reversible, but its time reversal in equilibrium can be guessed.
3.3.4 Birth-and-death chains
A Markov chain on 
(or on an interval of 
) s.t.
is called a birth-and-death chain. All other terms of 
are then zero, this matrix is determined by the Birth-and-death probabilities
which satisfy 
, and its graph is given by
Several of the examples we have examined are birth-and-death chains: Nearest-neighbor random walks on 
, Nearest-neighbor random walks reflected at 
on 
, gambler's ruin, and macroscopic description for the Ehrenfest Urn on 
.
The chain is irreducible on 
if and only if
Birth-and-death on 
or 
Similarly, 
is a closed irreducible class if and only if
and 
is a closed irreducible class if and only if
In these cases, the restriction of the chain is considered. It can be interpreted as describing the evolution of a population that can only increase or decrease by one individual at each step, according to whether there has been a birth or a death of an individual, hence the terminology.
We now give several helpful results, among which a generalization of the gambler's ruin law.
If the birth-and-death chain is irreducible on 
for a finite 
, then it is always positive recurrent, and the invariant law 
is obtained by replacing 
by 
in the formula.
Exercises
Several exercises of Chapter 1 involve irreducibility and invariant laws.
3.1 Generating functions and potential matrix Let 
be a Markov chain on 
with matrix 
. For 
and 
in 
, consider the power series, for 
,
- (a) Prove that
converges for 
and 
for 
and that
- (b) Prove that
for 
. Prove that, 
denoting the identity matrix,
- (c) Prove that
and that if 
and 
, then 
. - (d) We are going to apply these results to the nearest-neighbor random walk on
, with matrix given by 
and 
. We recall that 
.
Compute
for 
and 
. Compute 
and then 
. When is this random walk recurrent?
3.2 Symmetric random Walks with independent coordinates Let 
be the transition matrix of the symmetric random walk on 
, given by 
. Use the Potential matrix criterion to prove that 
and 
are recurrent and 
is transient.
3.3 Lemma 3.1.3, alternate proofs Let 
be a Markov chain on 
with matrix 
, and 
in 
be s.t. 
is recurrent and 
.
- (a) Prove that
. Deduce from this that 
and thus that 
. Prove that 
is recurrent, for instance using the Potential matrix criterion. Deduce from all this that 
. - (b) Prove that
. Prove that 
. Prove that 
. Prove that 
. Conclude that 
is recurrent and then that 
. - (c) Prove that
and, for 
,
Deduce from this that
and then that 
. Conclude that 
.
3.4 Decomposition Find the transient class and the recurrent classes for the Markov chains with graph (every arrow corresponding to a positive transition probability) and matrices given by
3.5 Genetic models, see Exercise 1.8 Decompose each state space into its transient class and its recurrent classes. Prove without computations that the population will eventually be composed of individuals having all the same allele, a phenomenon called “allele fixation.”
3.6 Balance equations on a subset Let 
be a transition matrix on 
. Prove that for any subset 
of 
an invariant measure 
satisfies the balance equation
3.7 See Lemma 3.1.1 Let 
be a Markov chain on 
having an invariant law 
. Prove that 
. Deduce from this that 
or 
.
3.8 Induced chain, see Exercise 2.3 Let 
be an irreducible transition matrix.
- (a) Prove that the induced transition matrix
is recurrent if and only if 
is recurrent. - (b) If
is an invariant measure for 
, find an invariant measure 
for 
. If 
is an invariant measure for 
, find an invariant measure 
for 
. - (c) Prove that if
is positive recurrent, then 
is positive recurrent. - (d) Let
and 
. Let 
on 
given by 
and 
and 
for 
, and 
. Compute 
, prove that 
is positive recurrent and that 
is null recurrent.
3.9 Difficult advance Let 
be the Markov chain on 
with matrix given by 
for 
and 
for 
, with 
and 
.
- (a) Prove that
is irreducible. Are there any reversible measures? - (b) Find the invariant measures. Is there uniqueness for these?
- (c) Prove that the chain is recurrent positive if and only if
, and compute then the invariant law. What is the value of 
for 
? - (d) Let
and 
and 
, 
. Prove that the 
are stopping times which are finite, a.s. Prove that 
is a Markov chain on 
and give its transition matrix 
. - (e) Let
be the induced chain constituted of the successive distinct states visited by 
. We admit it is a Markov chain, see Exercise 2.3. Give its transition matrix 
. - (f) Use known results to prove that
is null recurrent if 
and transient if 
. Deduce from this that the same property for 
and for 
.
3.10 Queue with 
servers, 1 The evolution of a queue with 
servers is given by a birth-and-death chain on 
s.t. 
and 
for 
, with 
and 
. Let 
.
- (a) Is this chain irreducible?
- (b) Prove that there is a unique invariant measure, and compute it in terms of
and 
. - (c) Prove that the chain is positive recurrent if and only if
. - (d) Prove that the chain is null recurrent if
and transient if 
, first using results on birth-and-death chains, and then using Lyapunov functions. - (e) We now considered the generalized case in which
, so that 
. Prove that there is an invariant law 
, compute it explicitly, and prove that the chain is positive recurrent. Compute 
.
3.11 ALOHA The ALOHA protocol was established in 1970 in order to manage a star-shaped wireless network, linking a large number of computers through a central hub on two frequencies, one for sending and the other for receiving.
A signal regularly emitted by the hub allows to synchronize emissions by cutting time into timeslots of same duration, sufficient for sending a certain quantity of bits called a packet. If a single computer tries to emit during a timeslot, it is successful and the packet is retransmitted by the hub to all computers. If two or more computers attempt transmission in a timeslot, then the packets interfere and the attempt is unsuccessful; this event is called a collision. The only information available to the computers is whether there has been at least one collision or not. When there is a collision, the computers attempt to retransmit after a random duration. For a simple Markovian analysis, we assume that this happens with probability 
in each subsequent timeslot, so that the duration is geometric.
Let 
be the initial number of packets awaiting retransmission, 
be i.i.d., where 
is the number of new transmission attempts in timeslot 
, and 
be i.i.d., where 
with probability 
if the 
-th packet awaiting retransmission after timeslot 
undergoes a retransmission attempt in timeslot 
, or else 
. All these r.v. are independent. We assume that
- (a) Prove that the number of packets awaiting retransmission after timeslot
is given by
and that
is an irreducible Markov chain on 
. - (b) If
, use the Lamperti criterion (Theorem 3.3.3) to prove that this chain is transient for every 
. - (c) Conclude to the same result when
.
3.12 Queuing by sessions Time is discrete, 
jobs arrive at time 
in i.i.d. manner, and 
and 
. Session 
is devoted to servicing exclusively and exhaustively the 
jobs that were waiting at its start, and has an integer-valued random duration 
, which conditional on 
is integrable, independent of the rest, and has law not depending on 
.
- (a) Prove that
is a Markov chain on 
. - (b) Prove that
belongs to a closed irreducible class and that all states outside this class are transient. - (c) We consider the restriction of the chain to this closed irreducible class. Prove that if
then the chain is positive recurrent. - (d) Prove that if
, then 
is positive recurrent. Prove that 
satisfies hypothesis 
of the Lamperti criterion for 
and 
. Does it satisfy hypothesis 
of the Lamperti criterion or of the Tweedie criterion?
3.13 Big jumps Let 
be a Markov chain on 
with matrix 
with only nonzero terms 
and 
.
- (a) Prove that this chain is irreducible.
- (b) Prove that if
, then the chain is positive recurrent and that there exists 
and a finite subset 
of 
s.t. 
. - (c) Prove that if
, then the chain is transient.
3.14 Quick return Let 
be a Markov chain on 
with matrix 
. Assume that there exists a nonempty subset 
of 
and 
and 
s.t. if 
, then 
and 
. (We may assume that 
vanishes on 
.) Let 
.
- (a) Prove that
for 
and 
. Deduce from this that 
for 
and 
. - (b) Prove that
and that 
for 
and 
. - (c) Let
, and 
be i.i.d., the power series 
have convergence radius 
, and 
. Consider 
independent of 
and (queue with 
servers)
Prove that there exists
and 
s.t. 
. Find a finite subset 
of 
and a function 
satisfying the above. - (d) Let
be a nonempty subset of 
s.t. 
. Find 
and 
satisfying the above. For which renewal processes does this hold for 
?
3.15 Adjoints Let 
be the transition matrix of the nearest-neighbor random walk on 
, given by 
and 
. Give the adjoint transition matrix with respect to 
and the adjoint transition matrix with respect to the uniform measure.
3.16 Labouchère system, see Exercises 1.4 and 2.10 Let 
be the random walk on 
with matrix 
given by 
and 
.
- (a) Are there any reversible measures?
- (b) Prove that if
, then an invariant measure must be of the form 
for 
, and if 
of the form 
. - (c) By considering the behaviors for
and 
, prove that if 
, then the invariant measures are of the form 
with 
and 
not both zero and that if 
, then the unique invariant measure is uniform. Deduce from this that if 
, then this random walk is transient. - (d) Let
be the random walk reflected at 
on 
, with matrix 
given by 
and 
for 
, and 
. Write the global balance equations. Prove that if 
, then the unique invariant measure is 
, and if 
, then the unique invariant measure is uniform. - (e) Prove that
is positive recurrent if and only if 
, and compute the invariant law 
if it exists. Compute 
. - (f) Use a Lyapunov function technique to prove that
is positive recurrent if 
, null recurrent if 
, and transient if 
.
3.17 Random walk on a graph A discrete set 
is furnished with a (nonoriented) graph structure as follows. The elements of 
are the nodes of the graph, and the elements of 
are the links of the graph. The neighborhood of 
is given by 
, and the degree of 
is given by its number of neighbors 
. It is assumed that 
for every 
. The random walk on the graph 
is defined as the Markov chain 
on 
s.t. if 
, then 
is chosen uniformly in 
.
- (a) Give an explicit expression for the transition matrix
of 
. Give a simple condition for it to be irreducible. - (b) Describe the symmetric nearest-neighbor random walk on
and the microscopic representation of the Ehrenfest Urn as random walks on graphs. - (c) Assume that
is irreducible. Find a reversible measure for this chain. Give a simple necessary and sufficient condition for the chain to be positive recurrent and then give an expression for the invariant law 
. - (d) Let
and
Find two (nonproportional) invariant measures for the random walk. Prove that the random walk is transient.
3.18 Caricature of TCP In a caricature of the transmission control protocol (TCP), which manages the window sizes for data transmission in the Internet, any packet is independently received with probability 
, and the consecutive distinct window sizes (in packets) 
for 
constitute a Markov chain on 
, with matrix 
with nonzero terms 
and 
.
- (a) Prove that this Markov chain is irreducible. Prove that there exists a unique invariant law
, by using a Lyapunov function technique. - (b) Write the global balance equations satisfied by the invariant law
. - (c) Prove that, for
,
- (d) Deduce from this, for
, that 
and then that 
. - (e) Prove that
. - (f) Let
and 
. Prove that 
is nondecreasing, 
, and 
.