Asymptotic equivalence and contiguity of some random graphs

Introduction

There are many different models of random graphs. Sometimes, the differences are minor, and it can be guessed that the asymptotic behaviour of two models are the same (for all or at least for some interesting properties). This note concerns some cases where it is possible to actually prove such results in a strong form. We begin by defining the two types of asymptotic equality that we will study. All unspecified limits are as ${n\to\infty}$.

Let $({\mathcal{X}}_{n},\mathcal{A}_{n})$, $n\geq 1$, be a sequence of arbitrary measurable spaces and let $P_{n}$ and $Q_{n}$ be two probability measures on $({\mathcal{X}}_{n},\mathcal{A}_{n})$.

The sequence $(P_{n})_{n}$ is asymptotically equivalent to $(Q_{n})_{n}$, denoted by $(P_{n})_{n}\cong(Q_{n})_{n}$, if for every sequence of measurable sets $A_{n}$ (i.e., $A_{n}\in\mathcal{A}_{n}$), we have $P_{n}(A_{n})-Q_{n}(A_{n})\to 0$.

The sequence $(P_{n})_{n}$ is contiguous with respect to $(Q_{n})_{n}$, denoted by $(P_{n})_{n}\vartriangleleft(Q_{n})_{n}$, if for every sequence of measurable sets $A_{n}$ such that $Q_{n}(A_{n})\to 0$, we also have $P_{n}(A_{n})\to 0$.

Note that asymptotic equivalence is a symmetric relation while contiguity is not; we say that $(P_{n})_{n}$ and $(Q_{n})_{n}$ are (mutually) contiguous, $(P_{n})_{n}\vartriangleleft\vartriangleright(Q_{n})_{n}$, if both $(P_{n})_{n}\vartriangleleft(Q_{n})_{n}$ and $(Q_{n})_{n}\vartriangleleft(P_{n})_{n}$, i.e., if $P_{n}(A_{n})\to 0\iff Q_{n}(A_{n})\to 0$ for any sequence of measurable sets $A_{n}\subseteq{\mathcal{X}}_{n}$. (And similarly for sequences of random variables $X_{n}$ and $Y_{n}$.)

Asymptotic equivalence implies contiguity, but not conversely (see e.g. Example 1.2 and Remark 1.6), so contiguity is a weaker property.

We illustrate these notions by two simple examples.

In the special case of two constant sequences, $P_{n}=P$ and $Q_{n}=Q$ where $P$ and $Q$ are two probability measures defined on the same space $({\mathcal{X}}_{n},\mathcal{A}_{n})=({\mathcal{X}};\mathcal{A})$, $(P_{n})_{n}\cong(Q_{n})_{n}$ if and only $P=Q$, and $(P_{n})_{n}\vartriangleleft(Q_{n})_{n}$ if and only if $P\ll Q$, i.e., $P$ is absolutely continuous with respect to $Q$. Hence asymptotic equivalence and contiguity can be thought of as asymptotic versions of equality and absolute continuity, respectively.

and thus $(Y_{n})_{n}\vartriangleleft(X_{n})_{n}$

In particular, we will study random graphs of the following type. If $p_{ij}$, $1\leq i<j\leq n$, are given probabilities in , let $G(n,\{p_{ij}\})$ be the random graph on $[n]$ where the edge $ij$ appears with probability $p_{ij}$ and the indicators I_{ij}:=\boldsymbol{1}[\text{edgeijappears}], $1\leq i<j\leq n$, are independent. (We will later also consider an extension to random $p_{ij}$, see Section 2.)

Consequently, $G(n,\{p_{ij}\})\cong G(n,\{p_{ij}^{\prime}\})$ if $\sum_{i<j}|p_{ij}-p_{ij}^{\prime}|\to 0$; a simple fact that has been used by many authors. It may be believed that this is essentially best possible, but, somewhat surprisingly, this is not so. In fact, by Corollary 2.12 below, provided $p_{ij}\leq 0.9$, say, $G(n,\{p_{ij}\})\cong G(n,\{p_{ij}^{\prime}\})$ if $\sum_{i<j}(p_{ij}-p_{ij}^{\prime})^{2}/p_{ij}\to 0$. (Moreover, Theorem 2.2(i) shows that this is best possible if, for example, $p_{ij}^{\prime}\leq 2p_{ij}$.)

For a particular case, suppose that $p_{ij}^{\prime}=p_{ij}+O(p_{ij}^{2})$, Then Corollary 2.13 shows that $G(n,\{p_{ij}\})\cong G(n,\{p_{ij}^{\prime}\})$ if $\sum_{i<j}p_{ij}^{3}\to 0$, while (1.1) implies this only under the stronger condition $\sum_{i<j}p_{ij}^{2}\to 0$. A typical case where this is an important improvement is when all $p_{ij}=\Theta(1/n)$ and $|p_{ij}^{\prime}-p_{ij}|=\Theta(1/n^{2})$. See further the examples in Section 3.

To see that such an improvement of (1.1) might be possible at all, consider as an example the case when all $p_{ij}$ are the same, so we consider the random graph $G(n,p)$:

It follows, using Theorem 4.2 again, that $G(n,p)\cong G(n,p^{\prime})$ if and only if $\alpha=0$, i.e. $N(p^{\prime}-p)/\sqrt{Np}\to 0$, which is equivalent to $\sum_{i<j}(p^{\prime}-p)^{2}/p=N(p^{\prime}-p)^{2}/p\to 0$. For example, if $p=1/n$ and $p^{\prime}=1-e^{-1/n}=p-\frac{1}{2}n^{-2}+O(n^{-3})$, then $N(p^{\prime}-p)^{2}/p=O(1/n)$, so $G(n,p)\cong G(n,p^{\prime})$, but $N|p-p^{\prime}|\to 1/4$, so (1.1) is not enough to show this.

We see that in this example, the trick to improve the simple and ’obvious’ edgewise coupling used in (1.1), is to first ignore the positions of the edges and couple their numbers only; this then is extended to a coupling of the random graphs by randomly reinserting the positions. Corollary 2.12(i) shows that couplings improving the simple edgewise coupling exist also when the edge probabilities are unequal, but in that case we do not know any explicit construction of such couplings.

We give the main results in Section 2 and a number of examples in Section 3; this includes an application to a recent result by van den Esker, van der Hofstad and Hooghiemstra (Example 3.6). Proofs are given in Section 5, after some preliminaries in Section 4.

We use the standard notations $o_{p}$ and $O_{p}$, see e.g. [14, Section 1.2], and we write whp (with high probability) for events with probability tending to 1 as ${n\to\infty}$.

There are also interesting examples of contiguity among random graphs of other types than $G(n,\{p_{ij}\})$. In particular, several different constructions of random regular graphs (or multigraphs) are known to yield distributions that are (mutually) contiguous but not asymptotically equivalent, see e.g. , [14, Section 9.5], . These examples are not covered by the present paper.

Results

We defined above the random graph $G(n,{\mathbf{p}})$, where ${\mathbf{p}}=\{p_{ij}\}_{1\leq i<j\leq n}$ is a vector of probabilities. We extend the definition of $G(n,{\mathbf{p}})$ to the case when ${\mathbf{p}}$ is a random vector (with entries in ) by conditioning on ${\mathbf{p}}$, i.e., given ${\mathbf{p}}=\{p_{ij}\}$, the edge indicators $I_{ij}$ are independent with $I_{ij}\sim\operatorname{Be}(p_{ij})$. Random graphs of this type have been studied in many papers, see for example Bollobás, Janson and Riordan 2007 and the further references given there.

We now state our main results on asymptotically equivalent and contiguity of such random graphs. Actually, the results have nothing to do with the graph structure and the way the indicator variables are indexed by pairs $ij$. It therefore seems more natural to consider the more general situation of a (finite or infinite) sequence $(I_{i})_{1}^{N}$ of indicator variables. (An indicator variable is a random variable with values in $\{0,1\}$, i.e. a random variable with a Bernoulli distribution $\operatorname{Be}(p)$ for some $p\in$.) The results for random graphs then follow by relabelling the indicators.

We define a function $\rho:^{2}\to[0,\infty)$ in Definition 2.1, where we also give some equivalent (within constant factors) alternative formulas that often are more convenient. Since the results below are not affected by changing $\rho$ within constant factors, we could use any of these alternative formulas (and several other similar ones) as our definition. (The motivation for the definition comes in Lemma 4.3.)

We write $x\asymp y$ (where $x,y\geq 0$) to denote that $cy\leq x\leq Cy$ for some positive constants $c,C$, i.e., that $x=\Theta(y)$ (or, equivalently, $x=O(y)$ and $y=O(x)$). Further, we use $x\vee y$ and $x\wedge y$ for the maximum and minimum, respectively, of $x$ and $y$. We interpret $0/0$ as 0.

Of course, the constant $0.9$ here and below is arbitrary and could be replaced by any number $<1$.

together with the similar result with $1-p$ and $1-q$. The second follows from $x+y\asymp x\vee y$ for $x,y\geq 0$ (used thrice). The third is equivalent to

which is easily verified, for example by assuming (by the symmetry $p\mapsto 1-p$, $q\mapsto 1-q$) that $p\leq 1/2$, in which case (2.6) easily reduces to $p\vee q\asymp p\vee|p-q|$. ∎

We state our results first for the simpler case of sequences of independent indicator variables with given (non-random) probabilities. The following theorem gives necessary and sufficient conditions for asymptotical equivalence and contiguity. (The asymptotical equivalence criterion follows by a simple and standard type of calculation with Hellinger distances, see the proof in Section 5 and, e.g., [16, p. 158], although we have not seen it stated in this form before. The contiguity criterion is a special case of a result by Oosterhoff and van Zwet 1979 for general sequences of independent variables.) The proofs of the theorems are given in Section 5.

Let $1\leq N(n)\leq\infty$ and let $X_{n}=(I_{ni})_{i=1}^{N(n)}$ and $X^{\prime}_{n}=(I_{ni}^{\prime})_{i=1}^{N(n)}$ be finite or infinite random vectors consisting of independent indicator variables $I_{ni}\sim\operatorname{Be}(p_{ni})$ and $I_{ni}^{\prime}\sim\operatorname{Be}(p_{ni}^{\prime})$.

$X_{n}\cong X_{n}^{\prime}$ if and only if

$X_{n}\vartriangleleft X_{n}^{\prime}$ if and only if

and, with $q_{ni}:=1-p_{ni}$ and $q_{ni}^{\prime}:=1-p_{ni}^{\prime}$,

By symmetry, $X_{n}\vartriangleright X_{n}^{\prime}$ is equivalent to (2.8) and

and thus $X_{n}\vartriangleleft\vartriangleright X_{n}^{\prime}$ is equivalent to (2.8), (2.9) and (2.10).

Often $p_{ni}\leq 0.9$ for all $n$ and $i$, and then the second sum in (2.9) vanishes for $C>10$ and can thus be omitted.

The condition (2.9) is only needed to take care of cases when $p_{ni}$ and $p_{ni}^{\prime}$ (or $q_{ni}$ and $q_{ni}^{\prime}$, in case $p_{ni}$ and $p_{ni}^{\prime}$ are close to 1) are not of the same order. If no such $p_{ni}$ and $p_{ni}^{\prime}$ appear, which is the typical case, then (2.8) is thus enough.

We may rewrite (2.9) in several ways. For example, it is equivalent to (following the formulation in in a more general case): for every sequence $C_{n}\to\infty$,

It is also equivalent to: For every $\varepsilon>0$, there exist $C$ and $n_{0}$ such that if $n\geq n_{0}$, then

As pointed out by Oosterhoff and van Zwet 1979, (2.8) does not imply (2.9) in general. A simple counter example is provided by $N(n)=n$, $p_{ni}=n^{-1}$, $p_{ni}^{\prime}=n^{-2}$. (On the other hand, it is easy to see, and also follows by the theorem, that (2.7) implies (2.9) and (2.10).)

We have stated Theorem 2.2 in terms of sequences of pairs of random vectors. It is possible (at least partly) to rephrase it in terms of estimates for a single pair $(X,X^{\prime})$, see Lemmas 5.1 and 5.2 below. Similar reformulations may be made for Theorem 2.9, but we leave these to the reader.

Let $1\leq N(n)\leq\infty$ and suppose that ${\mathbf{p}}_{n}=\{p_{ni}\}$ and ${\mathbf{p}}_{n}^{\prime}=\{p_{ni}^{\prime}\}$ are random vectors in $^{N(n)}$. Let $X_{n}=(I_{ni})_{i=1}^{N(n)}$ and $X^{\prime}_{n}=(I_{ni}^{\prime})_{i=1}^{N(n)}$ be random vectors of indicator variables such that the conditioned random vectors $(X_{n}\mid{\mathbf{p}}_{n})$ and $(X_{n}^{\prime}\mid{\mathbf{p}}_{n}^{\prime})$ are sequences of independent indicator variables with $(I_{ni}\mid{\mathbf{p}}_{n})\sim\operatorname{Be}(p_{ni})$ and $(I_{ni}^{\prime}\mid{\mathbf{p}}_{n}^{\prime})\sim\operatorname{Be}(p_{ni}^{\prime})$.

and, with $q_{ni}:=1-p_{ni}$ and $q_{ni}^{\prime}:=1-p_{ni}^{\prime}$, for every $\varepsilon>0$,

then $X_{n}\vartriangleleft X_{n}^{\prime}$.

In analogy to (2.11), the condition (2.15) is equivalent to: For every sequence $C_{n}\to\infty$,

As said above, Theorems 2.2 and 2.9 apply immediately to random graphs $G(n,{\mathbf{p}})$. We state a version of Theorem 2.9 for this case, where we have added some simplifying assumptions. Recall that $p_{ij}$ and $p_{ij}^{\prime}$ may (and typically do) depend on $n$, although we do not show that in our notation.

Let, for each $n$, ${\mathbf{p}}=\{p_{ij}\}$ and ${\mathbf{p}}^{\prime}=\{p_{ij}^{\prime}\}$ be random vectors of probabilities and suppose that whp $\max_{i,j}p_{ij}\leq 0.9$.

then $G(n,{\mathbf{p}})\cong G(n,{\mathbf{p}}^{\prime})$.

then $G(n,{\mathbf{p}})\vartriangleright G(n,{\mathbf{p}}^{\prime})$.

If (2.18) holds, and further, for some constant $c>0$, whp $cp_{ij}\leq p_{ij}^{\prime}\leq 0.9$ for all $i,j$, then $G(n,{\mathbf{p}})\vartriangleleft\vartriangleright G(n,{\mathbf{p}}^{\prime})$.

We specialize further to an important case.

Let, for each $n$, ${\mathbf{p}}=\{p_{ij}\}$ and ${\mathbf{p}}^{\prime}=\{p_{ij}^{\prime}\}$ be random vectors of probabilities and suppose that $p_{ij}^{\prime}=p_{ij}+O(p_{ij}^{2})$.

If $\sum_{i<j}p_{ij}^{3}=o_{p}(1)$, then $G(n,{\mathbf{p}})\cong G(n,{\mathbf{p}}^{\prime})$.

If $\sum_{i<j}p_{ij}^{3}=O_{p}(1)$, and further, for some constant $c>0$, whp $\max_{i,j}p_{ij}\leq 0.9$, $\max_{i,j}p_{ij}^{\prime}\leq 0.9$ and $p_{ij}^{\prime}\geq cp_{ij}$ for all $i,j$, then $G(n,{\mathbf{p}})\vartriangleleft\vartriangleright G(n,{\mathbf{p}}^{\prime})$.

Examples

Bollobás, Janson and Riordan 2007 study a general class of sparse random graphs $G(n,\kappa)$ which include many cases studied earlier by various authors. These random graphs are defined as $G(n,\{p_{ij}\})$ with

where $\kappa:{\mathcal{S}}\times{\mathcal{S}}\to[0,\infty)$ is a symmetric measurable function defined on some measurable space ${\mathcal{S}}$ and $x_{1},\dots,x_{n}$ is a random sequence of elements of ${\mathcal{S}}$, not necessarily i.i.d. but such that the empirical distribution of $x_{1},\dots,x_{n}$ converges to a probability measure $\mu$ on ${\mathcal{S}}$; see for details. (Some further technical conditions are assumed in ; they are not relevant here.) Typically, whp $\kappa(x_{i},x_{j})\leq n$ for all $i,j$, and then $p_{ij}$ equals the simpler $\hat{p}_{ij}$. Two natural variations, also treated in and used in various cases by various authors, are obtained by replacing (3.1) by

It was shown in that the same asymptotic results hold for these three versions for the properties studied there. We can now show that, under an extra condition, the three versions are asymptotically equivalent, and thus have the same asymptotic behaviour for any property. Indeed, Corollary 2.13 applies immediately and shows that if

We study some special cases in the following examples.

One common case of the construction in Example 3.1 uses $x_{1},\dots,x_{n}$ that are i.i.d. on ${\mathcal{S}}$ with distribution $\mu$. In this case, we show that the condition

implies (3.6) and thus asymptotic equivalence of the three versions. In particular, this holds if $\int_{{\mathcal{S}}\times{\mathcal{S}}}\kappa(x,y)^{2}\,d\mu(x)\,d\mu(y)<\infty$.

In fact, if $G(t):=\mu\times\mu\{(x,y):\kappa(x,y)>t)\}=o(t^{-2})$, then

Similarly, we can easily shown that (3.7), and thus at least partial contiguity, follows from

In this case, given $\varepsilon>0$, there exists $C_{1}$ such that

Another case of the construction in Example 3.1 uses ${\mathcal{S}}=(0,1]$ with $\mu$ = Lebesgue measure and the deterministic $x_{i}=i/n$, $i=1,\dots,n$. The homogeneous case $\kappa(x,y)=c/(x\vee y)$ yielding $\hat{p}_{ij}=c/(i\vee j)$, where $c>0$ is a constant, is particularly interesting and related to the CHKNS model, see Bollobás, Janson and Riordan 2007, Durrett 2003; Durrett 2007 and Riordan 2005 and the references given there.

In this case, $\sum_{1\leq i<j<\infty}p_{ij}^{3}\leq c^{3}\sum_{j\geq 2}j\cdot j^{-3}<\infty$, and thus $\sum_{i<j}p_{ij}^{3}=O(1)$; if we further for simplicity assume $c<2$ and thus $\max_{ij}\hat{p}_{ij}\allowbreak<1$, then Corollary 2.13(iii) implies that $G(n,p_{ij}^{(1)})\vartriangleleft\vartriangleright G(n,p_{ij}^{(2)})\vartriangleleft\vartriangleright G(n,p_{ij}^{(3)})$.

Note that in this case, $p_{12}^{(1)}$, $p_{12}^{(2)}$ and $p_{12}^{(3)}$ are constant and different, which shows that the three random graphs are not asymptotically equivalent (for a trivial reason).

We have $p_{ij}^{(3)}=c/(i\vee j+c)$; the same results hold for the further variation $p_{ij}=c/(i\vee j+d)$ for any $d>c-2$.

A related case uses the same ${\mathcal{S}}=(0,1]$, $\mu$ = Lebesgue measure and $x_{i}=i/n$, $i=1,\dots,n$, as Example 3.3, now with the homogeneous $\kappa(x,y)=c/\sqrt{xy}$ yielding $\hat{p}_{ij}=c/\sqrt{ij}$; this case is a mean-field version of the preferential attachment model by Barabási and Albert , see Bollobás, Janson and Riordan 2007 and Riordan 2005 and the references given there.

Also in this case, $\sum_{1\leq i<j<\infty}p_{ij}^{3}<\infty$, and thus $\sum_{i<j}p_{ij}^{3}=O(1)$ (in spite of the fact that (3.10) does not hold); if we further for simplicity assume $c<\sqrt{2}$, and thus $\max_{ij}\hat{p}_{ij}\allowbreak<1$, we obtain the same results as in Example 3.3.

A common case of Example 3.1 is when $\kappa(x,y)=\psi(x)\psi(y)$ for some function $\psi:{\mathcal{S}}\to[0,\infty)$, see [4, Section 16.4] for discussion and references to previous papers.

In this case, $\sum_{i<j}\kappa(x_{i},x_{j})^{3}\leq\bigl(\sum_{i}\psi(x_{i})^{3}\bigr)^{2}$, so (3.6) and (3.7) may be replaced by

If we combine this choice of $\kappa$ with the i.i.d. choice of $x_{i}$ in Example 3.2, it is easily seen, arguing as in (3.9) but now with $\sum_{i}\bigl(\psi(x_{i})\wedge n^{1/2}\bigr)$, that

implies (3.6) and thus asymptotic equivalence of the three versions; in particular this holds if $\int\psi(x)^{2}\,d\mu(x)<\infty$. Similarly,

implies (3.7) and thus at least partial contiguity.

van den Esker, van der Hofstad and Hooghiemstra 2008+ study a minor variation of the construction in Example 3.5; they let $\Lambda_{1},\dots,\Lambda_{n}$ be positive i.i.d. random variables with some fixed distribution and define $p_{ij}$ by (in our notation) (3.1), (3.3), (3.4) or more generally (3.5) with

(This too can be seen as an instance of the general construction in Example 3.1, see [4, Section 16.4].)

Our results are stated for graphs with a deterministic number of vertices, but can be extended to graphs with random vertex set too by conditioning on the vertex set. One interesting such case is obtained from Example 3.1 by letting $x_{1},\dots,x_{n}$ be the points of a Poisson process on ${\mathcal{S}}$ with intensity $\lambda\mu$, where $\lambda>0$ is our parameter and we consider asymptotics as $\lambda\to\infty$; thus $n$ is random with the distribution $\operatorname{Po}(\lambda)$.

Conditioned on $n$, we have the situation in Example 3.2. It follows, for example, that if (3.8) holds, then the random graphs defined in this way using (3.1), (3.3) and (3.4) are asymptotically equivalent; we omit the details.

Bollobás, Janson and Riordan 2007+ study a generalization of the model in Example 3.1 where small sets of edges are added at once, thus allowing a certain degree of clustering; more precisely, for every subgraph $F$ of the complete graph $K_{n}$, we have a certain probability of adding (the edges of) $F$, and these events are independent for different $F$. While this introduces dependencies between the edge indicators, the results of the present paper are still applicable to the sequence of indicators $I_{F}$ describing the added sets of edges, and asymptotic equivalence or contiguity for two versions of this sequence obviously implies asymptotic equivalence or contiguity for the resulting random graphs too.

We leave the explicit statement of results in this case to the reader.

In this final example, let us return to the case of deterministic ${\mathbf{p}}=\{p_{ij}\}$ and let us change all $p_{ij}$ proportionately to $p_{ij}^{\prime}:=(1+\delta_{n})p_{ij}$ for some $\delta_{n}$. Assume for simplicity that all $p_{ij}\leq 0.9$ and that $|\delta_{n}|\leq 1$.

By Corollary 2.12(i), if $\delta_{n}^{2}\sum_{i<j}p_{ij}\to 0$, then $G(n,{\mathbf{p}})\cong G(n,{\mathbf{p}}^{\prime})$. Further, by Corollary 2.12(iii), if $\delta_{n}^{2}\sum_{i<j}p_{ij}=O(1)$ and, for simplicity, $\delta_{n}\to 0$, then $G(n,{\mathbf{p}})\vartriangleleft\vartriangleright G(n,{\mathbf{p}}^{\prime})$.

In fact, by (2.5), $\rho(p_{ij},p_{ij}^{\prime})\asymp\delta_{n}^{2}p_{ij}\wedge|\delta_{n}|p_{ij}=\delta_{n}^{2}p_{ij}$, and thus by Theorem 2.2 the conditions $\delta_{n}^{2}\sum_{i<j}p_{ij}\to 0$ and $\delta_{n}^{2}\sum_{i<j}p_{ij}=O(1)$ are necessary too for asymptotic equivalence and contiguity, respectively. (The necessity can also be checked by considering the total number of edges, as in the special case in Example 1.5.)

As in Example 3.9, necessity in Theorem 2.2 can in many cases where $p_{ij}^{\prime}\leq p_{ij}$ for all $i$ and $j$ (or conversely) be proved by considering the total numbers $\sum_{i}I_{ni}$ and $\sum_{i}I_{ni}^{\prime}$, but this method does not suffice in all cases. A simple counter example is given by $N(n)=n^{4}+n^{8}$, $p_{ni}=n^{-1}$ for $1\leq i\leq n^{4}$ and $p_{ni}=n^{-3}$ for $i>n^{4}$, and $p_{ni}^{\prime}=p_{ni}-p_{ni}^{2}$; it is easily checked that then (2.7) and (2.8) do not hold, and thus we do not have asymptotic equivalence or even contiguity, but, using [2, Theorems 2.M and 1.C],

More on asymptotic equivalence and contiguity

We will use two metrics to measure the distance between probability distributions. We state some well-known definitions and facts, see e.g. [2, Appendix A.1] and [11, Chapter IV.1 and V.4a].

If $P$ and $Q$ are two probability measures on the same measurable space $({\mathcal{X}},\mathcal{A})$, and $R$ is any $\sigma$-finite measure on $({\mathcal{X}},\mathcal{A})$ such that $P\ll R$ and $Q\ll R$, define the total variation distance

(We can, at least symbolically, write (4.3) as $H(P,Q):=\int_{{\mathcal{X}}}\sqrt{dP\,dQ}$.) Note that these quantities do not depend on the choice of $R$. (We may thus take, e.g., $R=P+Q$.)

taking the minimum over all couplings $(X^{\prime},Y^{\prime})$ of $X$ and $Y$.

Let $X_{n}$ and $Y_{n}$ be random variables with values in ${\mathcal{X}}_{n}$. Then the following are equivalent.

This too is well-known and easy: (i)$\iff$(ii) by (4.4) and Definition 1.1; (ii)$\iff$(iii) by (4.5); (iii)$\iff$(iv) by (4.2); (ii)$\iff$(v) by (4.6). ∎

We calculate the Hellinger distance and integral for two Bernoulli distributions. (This is the origin of our function $\rho$ in Definition 2.1.)

Use (4.2) with $P=\operatorname{Be}(p)=p\delta_{0}+(1-p)\delta_{1}$, $Q=\operatorname{Be}(q)=q\delta_{0}+(1-q)\delta_{1}$ and $R=\delta_{0}+\delta_{1}$, together with the definition (2.1). ∎

Let $1\leq N\leq\infty$ and let, for $i\in[N]$, $P_{i}$ and $Q_{i}$ be probability measures on the same measurable space $({\mathcal{X}}_{i},\mathcal{A}_{i})$. If $P=\prod_{i=1}^{N}P_{i}$ and $Q=\prod_{i=1}^{N}Q_{i}$, then $H(P,Q)=\prod_{i=1}^{N}H(P_{i},Q_{i})$.

This is stated in, e.g., [11, Proposition IV.1.73], but for completeness we give the simple proof.

If $N<\infty$, the result is an immediate consequence of (4.3) and Fubini’s theorem, choosing e.g. $R_{i}=P_{i}+Q_{i}$ and $R=\prod_{i=1}^{N}R_{i}$.

If $N=\infty$, let $\mathcal{F}_{n}$ be the $\sigma$-field on $\prod_{i=1}^{\infty}{\mathcal{X}}_{i}$ given by $\{A\times\prod_{n+1}^{\infty}{\mathcal{X}}_{i}:A\in\prod_{1}^{n}\mathcal{A}_{i}\}$, and let $\overline{P}_{n}:=P|_{\mathcal{F}_{n}}$ and $\overline{Q}_{n}:=Q|_{\mathcal{F}_{n}}$. Then, using the finite case,

Proofs

and thus $H(X_{n},X_{n}^{\prime})\to 1\iff\sum_{1}^{N(n)}\rho(p_{ni},p_{ni}^{\prime})\to 0$, which yields the result by Theorem 4.2.

(ii): This is, in view of Lemma 4.3 and the equivalence of (2.9) and (2.11), a special case of [16, Theorem 1], to which we refer for a complete proof. Nevertheless, for completeness, we sketch a proof of the more important “if” direction.

First, we can by a simpler version of the argument in the proof of Theorem 2.9 below assume that $p_{ni}\leq C_{2}p_{ni}^{\prime}$ and $q_{ni}\leq C_{2}q_{ni}^{\prime}$ for some constant $C_{2}$. (We define $p_{ni}^{\prime\prime\prime}$ by (5.3) with $p_{ni}^{\prime\prime}:=p_{ni}$ and use (5.4)–(5.5).) Under this assumption, if we let $P_{ni}:={\mathcal{L}}(I_{ni})=\operatorname{Be}(p_{ni})$, $P_{n}:=\prod_{i}P_{ni}$, $P_{ni}^{\prime}:={\mathcal{L}}(I_{ni}^{\prime})=\operatorname{Be}(p_{ni}^{\prime})$, $P_{n}^{\prime}:=\prod_{i}P_{ni}^{\prime}$, we have by Fubini, using $\int(dP_{ni}/dP_{ni}^{\prime})\,dP_{ni}^{\prime}=1$ and (2.2),

and thus for any sets $A_{n}$, by the Cauchy–Schwarz inequality,

and thus $P_{n}\vartriangleleft P_{n}^{\prime}$, which is the same as $X_{n}\vartriangleleft X_{n}^{\prime}$. ∎

We say that a finite or infinite random vectors of indicator variables $X=(I_{i})_{i=1}^{N}$ has distribution $\operatorname{Be}({\mathbf{p}})$, where ${\mathbf{p}}=\{p_{i}\}_{i=1}^{N}$ is a deterministic vector with elements in $$, if the random variables$I_{i}$are independent indicator variables with$I_{i}\sim\operatorname{Be}(p_{i})$.

More generally, if ${\mathbf{p}}=\{p_{i}\}_{i=1}^{N}$ is a random vector with elements in $$, with$N\leq\infty$, we say that random vectors of indicator variables$X=(I_{i})_{i=1}^{N}$has distribution$\operatorname{Be}({\mathbf{p}})$if the conditioned random vector$(X\mid{\mathbf{p}})$is a sequence of independent indicator variables with$(I_{i}\mid{\mathbf{p}})\sim\operatorname{Be}(p_{i})$.

We next give two results comparing two random vectors with distributions $\operatorname{Be}({\mathbf{p}})$ and $\operatorname{Be}({\mathbf{p}}^{\prime})$ with deterministic ${\mathbf{p}}$ and ${\mathbf{p}}^{\prime}$. The first result is easily seen to be equivalent to the “if” direction of Theorem 2.2(i), while the second is equivalent to a special case of the “if” direction of Theorem 2.2(ii).

On the other hand, (2.8) and (2.9) hold for these random vectors (since the sums in (2.9) vanish for any $C\geq C_{2}$), and thus Theorem 2.2(ii) yields $X_{n}\vartriangleleft X_{n}^{\prime}$, which is a contradiction. ∎

for every measurable $A\subseteq{\mathcal{X}}_{n}=\{0,1\}^{N(n)}$, it follows that

(ii): Let $(A_{n})_{n}$ be an arbitrary sequence measurable sets with $A_{n}\subseteq{\mathcal{X}}_{n}=\{0,1\}^{N(n)}$ and let $\varepsilon>0$.

in the sequel we consider only $n\geq n_{0}$.

Define ${\mathbf{p}}_{n}^{\prime\prime}=\{p_{ni}^{\prime\prime}\}_{i=1}^{N(n)}$ by

Moreover, by the construction, with $q_{ni}^{\prime\prime}:=1-p_{ni}^{\prime\prime}$,

Next, define $p_{ni}^{\prime\prime\prime}=\{p_{ni}^{\prime\prime\prime}\}_{i=1}^{N(n)}$ by

We can construct $X_{n}^{\prime\prime\prime}\sim\operatorname{Be}({\mathbf{p}}_{n}^{\prime\prime\prime})$ using maximal couplings of $(I_{ni}^{\prime\prime\prime}\mid{\mathbf{p}}_{n}^{\prime\prime\prime})$ and $(I_{ni}^{\prime\prime}\mid{\mathbf{p}}_{n}^{\prime\prime})$ so that, using (5.3) and (5.2),

Furthermore, by (5.3), $p_{ni}^{\prime\prime\prime}\leq C_{2}p_{ni}^{\prime}$ and $q_{ni}^{\prime\prime\prime}:=1-p_{ni}^{\prime\prime\prime}\leq C_{2}q_{ni}^{\prime}$ and by (5.3) and (5.2),

In order to apply Theorem 2.9, we reorder $\{p_{ij}\}_{i<j}$ to $\{p_{ni}\}_{i=1}^{N(n)}$; we do this without further comment. We also let $q_{ij}:=1-p_{ij}$ and $q_{ij}^{\prime}:=1-p_{ij}^{\prime}$.

(i): By (2.5), whp $\rho(p_{ij},p_{ij}^{\prime})\leq C_{0}(p_{ij}-p_{ij}^{\prime})^{2}/p_{ij}$ for some $C_{0}$, and thus (2.17) implies (2.13), and the conclusion follows by Theorem 2.9(i).

(ii): Similarly, by (2.5) again, (2.18) implies (2.14). Moreover, for any $C\geq 2$,

(iii): The extra assumptions allow us to interchange ${\mathbf{p}}$ and ${\mathbf{p}}^{\prime}$ in the assumptions. Hence (ii) yields both $G(n,{\mathbf{p}})\vartriangleright G(n,{\mathbf{p}}^{\prime})$ and $G(n,{\mathbf{p}}^{\prime})\vartriangleright G(n,{\mathbf{p}})$. ∎

An immediate consequence of Corollary 2.12, since now $(p_{ij}-p_{ij}^{\prime})^{2}/p_{ij}=O(p_{ij}^{3})$; note also that the assumption in (i) implies $\max_{i,j}p_{ij}=o_{p}(1)$ and thus $\max_{i,j}p_{ij}<0.9$ whp. ∎

References