Invited talk

for

Workshop celebrating Tony Pakes’ 60th

Birthday

by Phil Pollett

The University of Queensland

ERGODICITY AND

RECURRENCE

Pakes, A.G. (1969) Some conditions for ergodicity and recurrence of Markov chains. Operat. Res. 17, 1058–1061.

Let (X_{n}, n = 0, 1, …) be an irreducible aperiodic Markov chain taking values in the nonnegative integers and let

γ_{i} = E(X_{n+1} − X_{n}|X_{n} = i).

Then, γ_{i} ≤ 0 for all i sufficiently large is enough to guarantee recurrence, while |γ_{i}| < ∞ and lim sup _{i→∞} γ_{i} < 0 is sufficient for ergodicity.

This result has been used by many authors in a variety of contexts, for example, in the control of random access broadcast channels: slotted Aloha and CSMA/CD (Carrier sense multiple access with collision detect) protocol.

The Aloha Scheme

The following description is based on (Kelly, 1985)^{∗}.

Several stations use the same channel (assume infinitely many stations). Packets arrive for transmission as a Poisson stream with rate ν (< 1). Time is broken down into “slots” (0, 1], (1, 2], . . .. Let Y_{t} be the number of packets to arrive in the slot (t − 1, t] (E(Y_{t}) = ν). Their transmission will first be attempted in the next slot (t, t + 1]. Let Z_{t} represent the output of the channel at time t:

Z_{t} = \begin{cases}0 & if 0 transmissions attempted \\ 1 & if 1 transmission attempted \\ ∗ & if > 1 transmissions attempted \end{cases}

∗Kelly, F.P. (1985) Stochastic models of computer communication systems. J. Royal Stat. Soc., Ser. B 47, 379–395 (with discussion, 415–428).

If Z_{t} = ∗, a “collision” has occurred, and retransmission will be attempted in later slots, independently in each slot with probability f until successful. Thus, the transmission delay (measured in slots) has a geometric distribution with parameter 1 − f.

The backlog (N_{t}) is a Markov chain with

N_{t+1} = N_{t} + Y_{t} − I[Z_{t} = 1].

Thus,

γ_{n} := E(N_{t+1} − N_{t}|N_{t} = n)
= ν − Pr(Z_{t} = 1|N_{t} = n)

and

Pr(Z_{t} = 1|N_{t} = n) = e^{−ν}nf(1 − f)^{n−1} + νe^{−ν}(1 − f)^{n}.

We deduce that γ_{n} > 0 for all n sufficiently large. Indeed the chain is transient (Kleinrock (1983), Fayolle, Gelenbe and Labetoulle (1977), Rosenkrantz and Towsley (1983)).

State-dependent Retransmission

Now suppose that the retransmission probability is allowed to depend on the backlog: f = f_{n} when N_{t} = n. Then, Pr(Z_{t} = 1|N_{t} = n) is maximized by

f_{n} = \frac{1 − ν}{n − ν},

and, with this choice,

γ_{n} := E(N_{t+1} − N_{t}|N_{t} = n, f = f_{n})

= ν − e^{−ν} (\frac{n − 1}{n − ν} )^{n−1} .

Thus, |γ_{n}| < ∞ and γ_{n} → ν − e^{−1}. Thus, (N_{t}) is ergodic, that is, the backlog is eventually cleared, if ν < e^{−1} ≃ 0.368.

But, users of the channel do not know the backlog, and thus cannot determine the optimal retransmission probability.

Towards a Better Control Scheme

It would be better to choose the retransmission probability f_{t} = f(Z_{1}, Z_{2}, …, Z_{t−1}) based on the observed channel output. Several schemes have been suggested by Mikhailov (1979) and Hajek and van Loon (1982). For example, suppose each station maintains a counter S_{t}, updated as follows: S_{0} = 1 and

S_{t+1} = max {1, S_{t} + aI[Z_{t} = 0] + bI[Z_{t} = 1] + cI[Z_{t} = ∗]},

where a, b and c are to be specified. For example, (a, b, c) = (−1, 0, 1) is an obvious choice. Suppose that f_{t} = 1/S_{t}. Then, (N_{t}, S_{t}) is a Markov chain. We would like S_{t} to “track” the backlog, at least when N_{t} is large. Consider the drift in (S_{t}):

ϕ_{n,s} := E(S_{t+1} − S_{t}|N_{t} = n, S_{t} = s)

= (a − c) (1 − \frac{1}{s} )^{n} + (b − c)\frac{n}{s} (1 − \frac{1}{s} )^{n} + c.

Let n → ∞ with κ = n/s held fixed. Then,

ϕ_{n,s} → (a − c)e^{−κ} + (b − c)κe^{−κ}.

The choice (a, b, c) = ((2 − e)α, 0, α), where α > 0, makes the drift in (S_{t}) negative if κ < 1 and positive if κ > 1. Thus, if the backlog were held steady at a large value, then the counter would approach that value. Also,

γ_{n,s} := E(N_{t+1} − N_{t}|N_{t} = n, S_{t} = s)

= ν − \frac{n}{s} (1 − \frac{1}{s} )^{n−1} → ν − κe^{−κ}.

Mikhailov (1979) showed that the choice (a, b, c) = (2 − e, 0, 1) ensures that (N_{t}, S_{t}) is ergodic whenever ν < e^{−1}.

Question. For an irreducible aperiodic Markov chain (N_{t}, S_{t}), can one infer anything about its ergodicity and recurrence from the marginal drifts?

THE BIRTH-DEATH AND

CATASTROPHE PROCESS

Pakes, A.G. (1987) Limit theorems for the population size of a birth and death process allowing catastrophes. J. Math. Biol. 25, 307–325.

An appropriate model for populations that are subject to crashes (dramatic losses can occur in animal populations due to disease, food shortages, significant changes in climate).

Such populations can exhibit quasi-stationary behaviour: they may survive for long periods before extinction occurs and can settle down to an apparently stationary regime. This behaviour can be modelled using a limiting conditional (or quasi-stationary) distribution.

The Model

It is a continuous-time Markov chain (X(t), t ≥ 0), where X(t) represents the population size at time t, with transition rates (q_{jk}, j, k ≥ 0) given by

q_{j,j+1} = jρa,  j ≥ 0,
q_{j,j} = −jρ,  j ≥ 0,
q_{j,j−i} = jρb_{i},  j ≥ 2, 1 ≤ i < j,
q_{j,0} = jρ_{∑i≥j} b_{i},  j ≥ 1,

with the other transition rates equal to 0. Here, ρ > 0, a > 0 and b_{i} > 0 for at least one i in C = {1, 2, … }, and, a + ∑_{i≥1} b_{i} = 1.

Interpretation. For j ≠ k, q_{jk} is the instantaneous rate at which the population size changes from j to k, ρ is the per capita rate of change and, given a change occurs, a is the probability that this results in a birth and b_{i} is the probability that this results in a catastrophe of size i (corresponding to the death or emigration of i individuals).

Some Properties

The state space. Clearly 0 is an absorbing state (corresponding to population extinction) and C is an irreducible class.

Extinction probabilities. If α_{i} is the probability of extinction starting with i individuals, then α_{i} = 1 for all i ∈ C if and only if D (the expected increment size), given by

D := a −_{∑i≥1} ib_{i} = 1 −_{∑i≥1} (i + 1)b_{i},

is less than 0 (the subcritical case) or equal to 0 (the critical case).

In the supercritical case (D > 0), the extinction probabilities can be expressed in terms of the probability generating function

f(s) = a +_{∑i≥1} b_{i}s^{i+1} , |s| < 1.

We find that

∑i≥1 α_{i}s^{i} = s/(1 − s) − Ds/b(s),

where b(s) = f(s) − s.

Limiting Conditional Distributions

In order to describe the long-term behaviour of the process, we use two types of limiting conditional distribution (LCD), called Type I and Type II, corresponding to the limits:

lim_{t→∞} Pr(X(t) = j|X(0) = i, X(t) > 0,

X(t + r) = 0 for some r > 0),

lim_{t→∞} lim_{s→∞} Pr(X(t) = j|X(0) = i, X(t + s) > 0,

X(t + s + r) = 0 for some r > 0),

where i, j ∈ C. Thus, we seek the limiting probability that the population size is j, given that extinction has not occurred, or (in the second case) will not occur in the distant future, but that eventually it will occur; we have conditioned on eventual extinction to deal with the supercritical case, where this event has probability less than 1.

The Existence of Limiting Conditional Distributions^{∗}

Consider the two eigenvector equations

\begin{matrix}_{∑i∈C} m_{i}q_{ij} = −μm_{j}, j ∈ C, \\ _{∑j∈C} q_{ij}x_{j} = −μx_{i}, i ∈ C, \end{matrix}

where μ ≥ 0 and C is the irreducible class.

In order that both types of LCD exist, it is necessary that these equations have strictly positive solutions for some μ > 0, these being the positive left and right eigenvectors of Q_{C} (the transition-rate matrix restricted to C) corresponding to a strictly negative eigenvalue −μ.

Let λ be the maximum value of μ for which positive eigenvectors exist (λ is known to be finite), and denote the corresponding eigenvectors by m = (m_{j}, j ∈ C) and x = (x_{j}, j ∈ C).

∗PKP technology

The Existence of Limiting Conditional Distributions

Proposition.^{∗} Suppose that Q is regular.

(i) If ∑ m_{k}x_{k} converges, and either ∑ m_{k} converges or {x_{k}} is bounded, then the Type II LCD exists and defines a proper probability distribution π^{(2)} = (π_{j}^{(2)} , j ∈ C) over C, given by

π_{j}^{(2)} = \frac{m_{j}x_{j}}{∑ m_{k}x_{k}}, j ∈ C.

(All unmarked sums are over k in C.) (ii) If in addition ∑ m_{k}α_{k} converges, then the

Type I LCD exists and defines a proper probability distribution π^{(1)} = (π_{j}^{(1)} , j ∈ C) over C, given by

π_{j}^{(1)} = \frac{m_{j}α_{j}}{∑ m_{k}α_{k}}, j ∈ C.

∗Pollett, P. (1988) Reversibility, invariance and μinvariance. Adv. Appl. Probab. 20, 600–621.

Try to use PKP Technology

We need the fact that b(s) = 0 has a unique solution σ on [0, 1], and that σ = 1 or 0 < σ < 1 according as D ≥ 0 or D < 0.

Setting x_{0} = m_{0} = 0, the eigenvector equations can be written (for j ∈ C) as

(j − 1)ρam_{j−1} + ∞ ; ∑ ; k=j+1 kρb_{k−j}m_{k} = (jρ − μ)m_{j},

jρax_{j+1} + j ; ∑ ; k=0 jρb_{j−k}x_{k} = (jρ − μ)x_{j}.

What is the maximum value of μ for which a positive solution exists? If x = (x_{j}, j ∈ C) is any solution to the second, then its generating function X(s) = ∑ x_{j}s^{j} satisfies

X(s) = \frac{s}{b(s)} exp (−μB(s)), s < σ,

where, for s < σ, B(s) = ρ^{−1} ∫_{0}^{s} dy/b(y).

Using this approach, we cannot really avoid the question: when is X(s) a power series with non-negative coefficients? The function C(s) = (μ/ρ) ∑(x_{j}/j)s^{j} satisfies

C(s) = 1 − exp (−μB(s)).

So, equivalently, we ask: when does C(s) have non-negative coefficients?

This is answered in the following paper (assuming, as we have here, that B(s) is a power series with non-negative coefficients):

Pakes, A.G. (1997) On the recognition and structure of probability generating functions. In (Eds. K.B. Athreya and P. Jagers) Classical and Modern Branching Processes, IMA Vols. Math. Appl. 84, Springer, New York, pp. 263– 284.

Lemon. The maximum value of μ for which a positive right eigenvector exists is λ = −ρb′(σ−). When μ = λ, the left eigenvector is given by m_{j} = σ^{j}, j ∈ C.

The Subcritical Case

We have D := −b′(1−) < 0 and σ < 1. Since m_{j} = σ^{j}, j ∈ C, we have also ∑ m_{k} < ∞ and ∑ m_{k}x_{k} = X(σ−) < ∞. The combination of technologies thus yields: Theorem. In the subcritical case both types of LCD exist. The Type I LCD is given by

π_{j}^{(1)} = (1 − σ)σ^{j−1},

and the Type II LCD has pgf

Π^{(2)} (s) = X(σs)/X(σ−),

where

X(s) = \frac{s}{b(s)} exp (−λB(s)), s < σ,

and, for s < σ, B(s) = ρ^{−1} ∫_{0}^{s} dy/b(y). This result is contained in Theorems 5.1 and 6.2 of Pakes (1987).

The Supercritical Case

We have D > 0 and σ = 1, and the absorption probabilities have generating function

∑i≥1 α_{i}s^{i} = s/(1 − s) − Ds/b(s).

Since m_{j} = 1, j ∈ C, we have ∑ m_{k}α_{k} = ∑ α_{k} and ∑ m_{k}x_{k} = X(1−). When do these series converge?

Condition (A). The catastrophe-size distribution has finite second moment, that is, f′′(1−) < ∞ (equivalently b′′(1−) < ∞).

Condition (B). The function b can be written

b(s) = D(1 − s) + (1 − s)^{2}L((1 − s)^{−1}),

where L is slowly varying, that is, L(xt) ∼ L(x) for large t.

Theorem. In the supercritical case, the Type I LCD exists under (A), and is given by π_{j}^{(1)} = α_{j}/ ∑ α_{k}. If in addition (B) holds, then the Type II LCD exists and has pgf Π^{(2)} (s) = X(s)/X(1−).

This first part (Type I LCD) is contained in:

Pakes, A.G. and Pollett, P.K. (1989) The supercritical birth, death and catastrophe process: limit theorems on the set of extinction. Stochastic Process. Appl. 32, 161–170.

The second part (Type II LCD) is contained in Theorem 6.2 of Pakes (1987).

Other papers important to my work:

Pakes, A.G. (1971) A branching process with a state dependent immigration component. Adv. Appl. Probab. 3, 301–314.

Pakes, A.G. (1975) On the tails of waiting-time distributions. J. Appl. Probab. 12, 555–564.

Pakes, A.G. (1992) Divergence rates for explosive birth processes. Stochastic Process. Appl. 41, 91–99.

Pakes, A.G. (1993) Explosive Markov branching processes: entrance laws and limiting behaviour. Adv. Appl. Probab. 25, 737–756.

Pakes, A.G. (1993) Absorbing Markov and branching processes with instantaneous resurrection. Stochastic Process. Appl. 48, 85–106.

Pakes, A.G. (1995) Quasi-stationary laws for Markov processes: examples of an always proximate absorbing state. Adv. Appl. Probab. 27, 120–145.