COUPLING AND POISSON APPROXIMATION

Svante Janson

Abstract. We give an overview of the Stein–Chen method for establishing Poisson approximations of various random variables. Couplings of certain variables are used to gives explicit bounds for the total variation distance between the distribution of a random variable and a Poisson variable. Some applications are given. In some cases, explicit couplings may be used to obtain good estimates; in other applications it suffices to show the existence of couplings with certain monotonicity properties.

1. The Stein–Chen method

Consider a random variable W that can be written as a sum ∑_{α∈Γ} I_{α} of 0–1 random variables, where Γ is a finite index set. The variables I_{α} may be dependent, but we will be interested in cases where the dependencies are rather weak and the individual probabilities P(I_{α} = 1) rather small. It is then reasonable to try to approximate the distribution of W by a Poisson distribution.

The Stein–Chen method is a powerful tool to justify such approximations by establishing an upper bound to the error, measured as the total variation distance between L(W) and the Poisson distribution Po(λ) with a suitably chosen mean λ. In many cases, this method can be fruitfully combined with coupling methods to yield simple upper bounds. Furthermore, the bounds often turn out to be of the right order of magnitude.

The method was originally formulated for normal approximation by Stein in 1970, but the basic idea applies also to other cases. The Poisson approximation version was worked out by Chen (1975). See also Stein (1986). The method has successfully been applied to a number of different problems by various authors. The coupling approach described here is developed in detail in Barbour, Holst and Janson (1992), to which we refer for proofs, further details, additional references, and many more applications.

The central idea in the Stein–Chen method is that for any λ > 0 and A ⊂ Z^{+} there exists a function g_{λ,A} on Z^{+} satisfying Stein’s equation

λg_{λ,A}(j + 1) − jg_{λ,A}(j) = I(j ∈ A) − Po(λ){A}, j ≥ 0.  (1)

Consequently, substituting W, taking expectations and interchanging the sides, we get

P(W ∈ A) − Po(λ){A} = E(λg_{λ,A}(W + 1) − W g_{λ,A}(W)).  (2)

The function g_{λ,A} can be given explicitly, but the method ignores the exact form of g_{λ,A} and uses only some simple estimates. In particular, we will here only use the estimate

|g_{λ,A}(j + 1) − g_{λ,A}(j)| ≤ 1 ∧ λ^{−1}, j ≥ 0, A ⊂ Z^{+}.  (3)

Typeset by AMS-TEX

Supported by the Göran Gustafsson Foundation for Research in Natural Sciences and Medicine.

(The proof is elementary but too long to be included here.) We define

G = {g : Z^{+} → R | |g(j + 1) − g(j)| ≤ 1, j ≥ 0}

and obtain by (2) and (3)

d_{T V} (L(W), Po(λ)) = sup_{A}(P(W ∈ A) − Po(λ){A})

= sup_{A} E(λg_{λ,A}(W + 1) − W g_{λ,A}(W))

≤ (1 ∧ λ^{−1}) sup_{g∈G} E(λg(W + 1) − W g(W)).  (4)

So far W could be any Z^{+}-valued random variable and λ any positive number (assuming that the expectations above are finite), but we will now use our assumption W = ∑_{α} I_{α}. Furthermore, we will for simplicity consider only the case

λ = E W = ∑_{α} p_{α},

where

p_{α} = E I_{α} = P(I_{α} = 1).

We then have

E(λg(W + 1) − W g(W)) = λ E g(W + 1) − ∑_{α} E(I_{α}g(W))
= ∑_{α} p_{α} E g(W + 1) − ∑_{α} p_{α} E(g(W) | I_{α} = 1).  (5)

We now introduce couplings. Assume that for each α we can construct a random variable W_{α}, on the same probability space as W, such that the distribution L(W_{α}) equals the conditional distribution L(W −I_{α} | I_{α} = 1). The right hand side of (5) can then be further developed as

∑_{α} p_{α} E(g(W + 1) − g(W_{α} + 1)) ≤ ∑_{α} p_{α} E |W − W_{α}|,  (6)

for any g ∈ G. Combining the estimates above, we arrive at our fundamental result.

Theorem 1. If W and W_{α} are as above, then

d_{T V} (L(W), Po(λ)) ≤ (1 ∧ λ^{−1}) ∑_{α} p_{α} E |W − W_{α}|.  (7)

In order to justify the Poisson approximation we therefore only have to find couplings (W, W_{α}) such that the the right hand side of (7) is small. Before proceeding to examples of such couplings, let us note that the natural way to construct W_{α} is to find variables J_{βα}, α, β ∈ Γ, such that for each α

L(J_{βα}, β ∈ Γ) = L(I_{β}, β ∈ Γ | I_{α} = 1),  (8)

and then set W_{α} = ∑_{β≠α} J_{βα}. Since W − W_{α} = I_{α} + ∑_{β≠α}(I_{β} − J_{βα}), we obtain the following corollary.

Theorem 2. With (J_{βα}) as above,

d_{T V} (L(W), Po(λ)) ≤ (1 ∧ λ^{−1})(∑_{α∈Γ} p_{α}^{2} + ∑_{α∈Γ} ∑_{β≠α} p_{α} E |I_{β} − J_{βα}|).

We will, somewhat informally, also speak of (J_{βα}) as a coupling in this case. For later use we note that

p_{α} E J_{βα} = P(I_{α} = 1) P(I_{β} = 1 | I_{α} = 1) = P(I_{α} = I_{β} = 1) = E(I_{α}I_{β}).  (9)

Remark. The method gives estimates for the total variation distance between a finite sum and a Poisson distribution; no asymptotics are involved. On the other hand, limit theorems yielding convergence in distribution often follow directly from these estimates. Indeed, suppose that the variables and the index set depend on a parameter n, indicated by a subscript, and that the estimate of d_{T V} (L(W_{n}), Po(λ_{n})) given by Theorem 1 or Theorem 2 tends to 0 as n → ∞. If λ_{n} → λ for some λ < ∞, then d_{T V} (L(W_{n}), Po(λ)) → 0

and thus W_{n} ⟶^{d} Po(λ). If λ_{n} → ∞, then Po(λ_{n}) is asymptotically normal and it follows easily that (W_{n} − E W_{n})/(E W_{n})^{1/2} ⟶^{d} N(0, 1), i.e., W_{n} is asymptotically normal. Note that the factor 1∧λ^{−1} in the estimates may be ignored in the first case, and more generally in any situation where E W is bounded and we are only interested in the order of the total variation distance; but the factor gives an important improvement when E W → ∞.

In the next three sections, we show how the general results Theorems 1 and 2 can be applied in some special situations.

2. Independent summands

The simplest application of the estimates above is to a sum of independent indicators I_{α}. We then simply take W_{α} = ∑_{β≠α} I_{β}, or equivalently, J_{βα} = I_{β}, β ≠ α, and obtain from Theorem 1 or 2 the following estimate, due to Barbour and Hall (1984).

Theorem 3. If W = ∑_{α∈Γ} I_{α}, where I_{α}, α ∈ Γ, are independent indicators, then

d_{T V} (L(W), Po(λ)) ≤ (1 ∧ λ^{−1}) ∑_{α∈Γ} p_{α}^{2}.  (10)

This estimate is of the right order. In fact, Barbour and Hall (1984) proved also the opposite inequality d_{T V} (L(W), Po(λ)) ≥ \frac{1}{32}(1∧λ^{−1}) ∑_{α∈Γ} p_{α}^{2}. (The constant \frac{1}{32} has later been improved to \frac{1}{14}.)

As a corollary to Theorem 3, we obtain the simpler bound

d_{T V} (L(W), Po(λ)) ≤ λ^{−1} ∑_{α∈Γ} p_{α}^{2} ≤ max_{α} p_{α},  (11)

but this estimate is inferior to (10) when a few p_{α} are much larger than the others. In the special case of identically distributed I_{α}, W has a binomial distribution and we obtain, for all n and p, the simple estimate

d_{T V} (Bi(n, p), Po(np)) ≤ p.

(This estimate is of the right order, provided, say, np ≥ 1.)

3. Dissociated summands

Suppose that for each α there is a subset Γ_{α} ⊂ Γ such that I_{α} is independent of (I_{β}, β ∉ Γ_{α}). We may then choose J_{βα} = I_{β} whenever β ∉ Γ_{α}, and construct J_{βα} for β ∈ Γ_{α} such that (8) holds. (This is always possible, at least if we enlarge the probability space.) For β ∈ Γ_{α} we may use the trivial estimate p_{α} E |I_{β} − J_{βα}| ≤ p_{α} E(I_{β} + J_{βα}) = p_{α}p_{β} + E I_{α}I_{β}. This means that we can ignore the details of the construction of J_{βα}; it is only the existence of a coupling that is important. We obtain from Theorem 2 the following result by Barbour and Eagleson (1984).

Theorem 4. If Γ_{α} are as above, then

d_{T V} (L(W), Po(λ)) ≤ (1 ∧ λ^{−1})(∑_{α∈Γ} p_{α}^{2} + ∑_{α∈Γ} ∑_{β∈Γ_{α}\{α}}(p_{α}p_{β} + E I_{α}I_{β})).

The standard situation where this theorem is applicable is when the family (I_{α}) is dissociated, meaning that the index set Γ is a collection {α} of sets α = {α_{1}, …, α_{k}} of cardinality k, for some k ≥ 2, and that two sets of random variables (I_{α}, α ∈ A) and (I_{α}, α ∈ B) are independent whenever (⋃_{α∈A} α) ∩ (⋃_{α∈B} α) = ∅; we may thus apply Theorem 4 with Γ_{α} = {β : α ∩ β ≠ ∅}.

The most common case of dissociated variables is that in which I_{α} = ϕ_{α}(Y_{α_{1}}, …, Y_{α_{k}}), where the ϕ_{α} are symmetric 0–1 valued functions and the Y_{i} are independent random elements of some space Y. A typical example is when Y_{1}, …, Y_{n} are independent elements of some separable metric space and W is the number of pairs (Y_{i}, Y_{j}) with distance less than some fixed number (here k = 2 and Γ is the set of all pairs {i, j}, 1 ≤ i ≤ j ≤ n).

4. Monotone couplings

The estimate in Theorem 2 can be significantly simplified if there exists a coupling that is monotone in the following sense.

Definition. The indicator random variables (I_{α}, α ∈ Γ) are said to be positively related if for each α there exist random variables (J_{βα}, β ∈ Γ) such that (8) holds and J_{βα} ≥ I_{β} whenever α ≠ β. The variables are negatively related if there exist such J_{βα} with J_{βα} ≤ I_{β} whenever α ≠ β.

Remark. If the indicators are positively (negatively) related, then they are necessarily positively (negatively) correlated, but the converse does not hold. Correlation is only a pairwise property, whereas being positively or negatively related depends on the whole joint distribution.

If the variables (I_{α}) are positively related, then, using (9), we have for β ≠ α,

p_{α} E |I_{β} − J_{βα}| = p_{α} E(J_{βα} − I_{β}) = E I_{α}I_{β} − p_{α}p_{β} = Cov(I_{α}, I_{β})

and thus

∑_{α} ∑_{β≠α} p_{α} E |I_{β} − J_{βα}| = ∑_{α} ∑_{β} Cov(I_{α}, I_{β}) − ∑_{α} Var(I_{α})

= Var(∑_{α} I_{α}) − ∑_{α}(p_{α} − p_{α}^{2}) = Var W − λ + ∑_{α} p_{α}^{2}.

For negatively related variables we obtain the same result with opposite sign. Theorem 2 now yields:

Theorem 5. If the variables I_{α} are positively related, then

d_{T V} (L(W), Po(λ)) ≤ (1 ∧ λ^{−1})(Var W − λ + 2 ∑_{α} p_{α}^{2}).

Theorem 6. If the variables I_{α} are negatively related, then

d_{T V} (L(W), Po(λ)) ≤ (1 ∧ λ^{−1})(λ − Var W).

These results are very attractive indeed, since the mean and variance coincide for a Poisson distribution so that it is reasonable to require that | Var W −E W | is small as a first condition for Poisson approximation in some application. (Of course, counter examples can be constructed, but they do rarely occur in natural examples.) The theorems say that, in fact, this condition is sufficient when there exists a monotone coupling, provided that in the positively related case also (1 ∧ λ^{−1}) ∑_{α} p_{α}^{2} is small (a condition needed even in the independent case). Moreover, in the negatively related case, it may be shown that the estimate in Theorem 6 is off by at most logarithmic factors, and thus it is also necessary for good Poisson approximation that | Var W − E W | is small. Hence, for a sequence W_{n} of sums of negatively related variables such that E W_{n} → λ, we have W_{n} ⟶^{d} Po(λ) if and only if also Var W_{n} → λ. (Similar results hold for sums of positively related variables under additional conditions.)

Note that the estimates in Theorems 5 and 6 involve only first and second moments of the variables I_{α}, which makes them easy to compute in most applications. The couplings J_{βα} do not appear in the estimates, it is only the existence of a monotone coupling that matters.

The question of existence of a monotone coupling may be put in a more general context, namely as the question whether there exist random variables I and J, with values in a given partially ordered set S and with given distributions, such that I ≤ J a.s.; in our case, S is the finite set {0, 1}^{Γ\α} with the natural ordering (x_{1}, …, x_{n}) ≤ (y_{1}, …, y_{n}) if x_{i} ≤ y_{i} for all i. In general, such a coupling of I and J exists if and only if

E ϕ(I) ≤ E ϕ(J)

for every increasing indicator function ϕ on S, see e.g. Liggett (1985), page 72. In our case, this leads to the following result.

Proposition 1. The variables I_{α} are positively (negatively) related if and only if I_{α} and ϕ(I_{β}, β ≠ α) are positively (negatively) correlated for every α and every increasing indicator function ϕ.

This yields, by the FKG inequality, the following important case where Theorem 5 is applicable.

Proposition 2. Let (I_{α}, α ∈ Γ) be increasing functions of independent random variables X_{1}, …, X_{n}. Then the random variables I_{α} are positively related.

More generally, indicator variables that are associated in the sense of Esary, Proschan and Walkup (1967) are positively related. Similarly, indicator variables that are negatively associated in the sense of Joag-Dev and Proschan (1983) are negatively related. General results on (negatively) associated variables may thus be used to show that certain families of indicator variables I_{α} are positively or negatively related, which enables us to apply Theorem 5 or 6 in some applications.

5. Examples

We end by giving some examples of couplings that are useful in applications of the theorems above. For the resulting Poisson approximation error bounds, and conditions on the parameters that make the bounds small, we refer the interested reader to Barbour, Holst and Janson (1992).

Occupancy problems. Let r balls be thrown independently of each other into a number of boxes, with probability p_{α} of hitting box α. Let W be the number of empty boxes. Then W = ∑_{α} I_{α}, where I_{α} = I(box α is empty). In order to define a coupling (J_{αβ}), we remove all balls from box β and redistribute them according to the original distribution, repeating until box β is empty; we then define J_{αβ} = I(box α is empty). Obviously, J_{αβ} ≤ I_{α}, so the coupling is monotone and the variables I_{α} are negatively related. Thus Theorem 6 applies.

Similar arguments work for other occupancy problems, giving for example a Poisson approximation result for the hypergeometric distribution.

Random graphs. Consider the complete graph K_{n} with n vertices and \binom{n}{2} edges. Keep each edge with probability p independently of the other edges, and delete it otherwise; this gives a random graph K_{n,p}. Let G ⊂ K_{n} be a given graph with e(G) edges and v(G) vertices, and let Γ be the set of all copies of G in K_{n}, i.e. all subgraphs of K_{n} isomorphic to G. The number of subgraphs of K_{n,p} isomorphic to G can be written W = ∑_{α∈Γ} I_{α}, where I_{α} = I(α ⊂ K_{n,p}).

The variables I_{α} are increasing functions of the edge indicators, which by definition are independent. Hence Proposition 2 shows that the variables I_{α} are positively related, and Theorem 5 applies. This can also be shown directly, using the explicit coupling J_{βα} = I(β ⊂ (K_{n,p} ∪ α)) ≥ I_{β}, where the union of two graphs combines their vertex and edge sets.

Matching problems. We consider two examples; several others may be treated similarly. We prefer to use the indices i, j instead of α, β.

Treize. The game ‘Treize’ was studied already by de Montmort (1713). In this game 13 cards are drawn at random one at a time from an ordinary deck of 52 cards having 4 sets of face values 1, …, 13. A match occurs if a card with face value i appears in the ith drawing. The original problem is to find the probability that there is no match.

We can write the number of matches as W = ∑_{1}^{13} I_{i}, where I_{i} = I(match at drawing i). It is easy to construct a monotone coupling with J_{ij} ≥ I_{i}, namely by swapping the card obtained in the jth drawing with a card with face value j chosen at random. Hence I_{1}, …, I_{13} are positively related and we can apply Theorem 5 to obtain an estimate for d_{T V} (L(W), Po(1)).

The ménage problem. The classical ménage problem asks for the number of seatings of n couples at a circular table, with men and women alternating, so that no one sits next to his or her partner. More generally, we can ask for the probability that a random seating gives exactly k couples sitting together.

We number the places around the table from 1 to 2n, and let I_{i} = 1 if a couple occupies seats i and i + 1 (counting modulo 2n). Then W, the number of couples sitting next to each other, can be expressed as ∑_{1}^{2n} I_{i}. A coupling may be constructed by interchanging the person sitting on seat j with the partner of the person on seat j+1 and defining J_{ij} = 1 if a couple then occupies seats i and i + 1. For this coupling, J_{ij} = 0 ≤ I_{i} if i = j ± 1, but J_{ij} ≥ I_{i} for all other i. Hence, the coupling is not monotone, but of a mixed kind where monotonicity holds for the individual J_{ij}, although in different directions. Theorem 2 gives a good estimate for d_{T V} (L(W), Po(2)).

References

A.D. Barbour and G.K. Eagleson (1984). Poisson convergence for dissociated statistics. Journal of the Royal Statistical Society, B 46, 397–402.

A.D. Barbour and P. Hall (1984). On the rate of Poisson convergence. Mathematical Proceedings of the Cambridge Philosophical Society, 95, 473–80.

A.D. Barbour, L. Holst and S. Janson (1992). Poisson Approximation. Oxford University Press, Oxford.

L.H.Y. Chen (1975). Poisson approximation for dependent trials. Annals of Probability, 3, 534–45.

J.D. Esary, F. Proschan, and D.W. Walkup (1967). Association of random variables, with applications. Annals of Mathematical Statistics, 38, 1466–74.

K. Joag-Dev and F. Proschan (1983). Negative association of random variables, with applications. Annals of Statistics, 11, 286–95.

P.R. de Montmort (1713). Essay d’analyse sur les jeux de hazard, (2nd edn). Jacques Quillau, Paris.

T.M. Liggett (1985). Interacting particle systems. Springer, New York.

C. Stein (1986). Approximate computation of expectations. Institute of Mathematical Statistics Lecture Notes – Monograph Series, Vol. 7. Hayward, California.

Svante Janson, Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden

   E-mail address: svante.janson@math.uu.se