Degree-degree distribution in a power law

random intersection graph with clustering

Mindaugas Bloznelis

Vilnius University, Lithuania

<EMAIL_ADDRESS>
22 November 2014

###### Abstract

The bivariate distribution of degrees of adjacent vertices (degree-degree
distribution) is an important network characteristic defining the statistical
dependencies between degrees of adjacent vertices. We show the asymptotic
degree-degree distribution of a sparse inhomogeneous random intersection graph
and discuss its relation to the clustering and power law properties of the
graph.

key words: degree-degree distribution, power law, clustering coefficient,
random intersection graph, affiliation network, assortativity coefficient,
random walk

##  1 Introduction

Correlations between degrees of adjacent vertices influence many network
properties including the component structure, epidemic spreading, network
robustness, etc., see [8], [14], [19], [20] and references therein. The
correlations are defined by the degree-degree distribution, i.e., the
bivariate distribution of degrees of endpoints of a randomly chosen edge. In
this paper we present an analytic study of the degree-degree distribution in a
mathematically tractable random graph model of an affiliation network
possessing power law degrees and non-vanishing clustering coefficient. Our
study is motivated firstly by the interest in tracing the relation between the
degree-degree distribution and clustering properties in a power law network.
Secondly, the degree-degree distribution shows up in the analysis of the
simple random walk on network, namely, it defines the transition matrix of the
corresponding Markov chain, when sites are identified with vertex degrees (not
the vertices themselves), see [2].

Next in this section we introduce the random graph model and present our
results. Proofs are postponed to Section 2.

Affiliation network and random intersection graph. An affiliation network
defines adjacency relations between actors by using an auxiliary set of
attributes. Let $V$ denote the set of actors (nodes of the network) and $W$
denote the auxiliary set of attributes. Every actor $v\in V$ is prescribed a
collection $S_{v}\subset W$ of attributes and two actors $u,v\in V$ are
declared adjacent in the network if they share some common attributes. For
example one may interpret elements of $W$ as weights and declare two actors
adjacent whenever the total weight of shared attributes is above some
threshold value. Here we consider the simplest case, where $u,v\in V$ are
called adjacent whenever they share at least one common attribute, i.e.,
$S_{u}\cap S_{v}\not=\emptyset$. Two popular examples of real affiliation
networks are the film actor network, where two actors are declared adjacent if
they have played in the same movie, and the collaboration network, where two
scientists are declared adjacent if they have coauthored a publication.

A plausible model of a large affiliation network is obtained by prescribing
the collections of attributes to actors at random. Furthermore, in order to
model the heterogeneity of human activity, every actor $v_{j}\in V$ is
prescribed a random weight $y_{j}$ reflecting its activity. Similarly, a
random weight $x_{i}$ is prescribed to each attribute $w_{i}\in W$ to model
its attractivity. Now an attribute $w_{i}\in W$ is included in the collection
$S_{v_{j}}$ at random and with probability proportional to the attractivity
$x_{i}$ and activity $y_{j}$. In this way we obtain a random graph on the
vertex set $V$, sometimes called the inhomogeneous random intersection graph
([3], [4], [5], [9], [21], see also [16]). This random graph possesses desired
properties of a complex network (non-vanishing clustering coefficient, power
law degree distribution and short distances). Before giving a detailed
definition of this random graph model let us mention a recent publication
[18], which argues convincingly that in some social networks the ’heavy-tailed
degree distribution is causally determined by similarly skewed distribution of
human activity’. The empirical evidence reported in [18] suggests that the
inhomogeneous random intersection graph can be considered as a realistic model
of a power law affiliation network.

Inhomogeneous random intersection graph. Let
$X_{1},\dots,X_{m},Y_{1},\dots,Y_{n}$ be independent non-negative random
variables such that each $X_{i}$ has the probability distribution $P_{1}$ and
each $Y_{j}$ has the probability distribution $P_{2}$. Given realized values
$X=\\{X_{i}\\}_{i=1}^{m}$ and $Y=\\{Y_{j}\\}_{j=1}^{n}$ we define the random
bipartite graph $H_{X,Y}$ with the bipartition $V\cup W$, where
$V=\\{v_{1},\dots,v_{n}\\}$ and $W=\\{w_{1},\dots,w_{m}\\}$. Every pair
$\\{w_{i},v_{j}\\}$ is linked in $H_{X,Y}$ with probability

$p_{ij}=\min\\{1,\lambda_{ij}\\},\qquad{\text{where}}\quad\lambda_{ij}=\frac{X_{i}Y_{j}}{\sqrt{nm}},$

independently of the other pairs $\\{i,j\\}\in[m]\times[n]$. The inhomogeneous
random intersection graph $G=G(P_{1},P_{2},n,m)$ defines the adjacency
relation on the vertex set $V$: vertices $u,v\in V$ are declared adjacent
(denoted $u\sim v$) whenever $u$ and $v$ have a common neighbor in $H_{X,Y}$.
We call this neighbor a witness of the adjacency relation $u\sim v$.

The random graph $G$ has several features that make it a convenient
theoretical model of a complex network. Firstly, the statistical dependence of
neighboring adjacency relations in $G$ mimics that of real affiliation
networks. In particular, $G$ admits a tunable clustering coefficient: For
$m/n\to\beta\in(0,+\infty)$ as $m,n\to+\infty$, we have, see [7],

${\bf{P}}(v_{1}\sim v_{2}|v_{1}\sim v_{3},\,v_{2}\sim
v_{3})=\frac{\kappa}{\kappa+\sqrt{\beta}}+o(1).$ (1)

Here $\kappa:=b_{1}b_{2}^{-1}a_{3}a_{2}^{-2}$ and $a_{i}={\bf{E}}X_{1}^{i}$,
$b_{j}={\bf{E}}Y_{1}^{j}$.

Another important feature of the model is its ability to produce a rich class
of (asymptotic) degree distributions including the power law distributions.
The following result of [4] will be used below and we present it here for
convenience.

######  Theorem 1.

Let $m,n\to\infty$.

(i) Assume that $m/n\to\beta$ for some $\beta\in(0,+\infty)$. Suppose that
${\bf{E}}X_{1}^{2}<\infty$ and ${\bf{E}}Y_{1}<\infty$. Then $d(v_{1})$
converges in distribution to the random variable

$d_{*}=\sum_{j=1}^{\Lambda_{1}}\tau_{j},$ (2)

where $\tau_{1},\tau_{2},\dots$ are independent and identically distributed
random variables independent of the random variable $\Lambda_{1}$. They are
distributed as follows. For $r=0,1,2,\dots$, we have

${\bf{P}}(\tau_{1}=r)=\frac{r+1}{{\bf{E}}\Lambda_{0}}{\bf{P}}(\Lambda_{0}=r+1)\qquad{\text{and}}\qquad{\bf{P}}(\Lambda_{i}=r)={\bf{E}}\,e^{-\lambda_{i}}\frac{\lambda_{i}^{r}}{r!},\qquad
i=0,1.$ (3)

Here $\lambda_{0}=X_{1}b_{1}\beta^{-1/2}$ and
$\lambda_{1}=Y_{1}a_{1}\beta^{1/2}$.

(ii) Assume that $m/n\to+\infty$. Suppose that ${\bf{E}}X_{1}^{2}<\infty$ and
${\bf{E}}Y_{1}<\infty$. Then $d(v_{1})$ converges in distribution to a random
variable $\Lambda_{3}$ having the probability distribution

${\bf{P}}(\Lambda_{3}=r)={\bf{E}}e^{-\lambda_{3}}\frac{\lambda_{3}^{r}}{r!},\qquad
r=0,1,\dots.$ (4)

Here $\lambda_{3}=Y_{1}a_{2}b_{1}$.

(iii) Assume that $m/n\to 0$. Suppose that that ${\bf{E}}X_{1}<\infty$. Then
${\bf{P}}(d(v_{1})=0)=1-o(1)$.

We say that an integer valued non-negative random variable $Z$ has a power law
distribution with exponent $\varkappa>1$ if for some $c>0$ we have
${\bf{P}}(Z=r)\approx cr^{-\varkappa}$ as $r\to+\infty$. Here and below for
real sequences $\\{t_{r}\\}_{r\geq 1}$ and $\\{s_{r}\\}_{r\geq 1}$ we denote
$t_{r}\approx s_{r}$ whenever $t_{r}/s_{r}\to 1$ as $r\to+\infty$. More
generally, we say that the distribution of a non-negative random variable $Z$
has property ${\cal A}_{c,\varkappa}$ if either $Z$ is integer valued and
satisfies ${\bf{P}}(Z=r)\approx cr^{-\varkappa}$, or $Z$ is absolute
continuous with density $f_{Z}$ satisfying $f_{Z}(t)=(c+o(1))t^{-\varkappa}$
as $t\to+\infty$.

In Lemma 3, see Appendix B, we show that if $Y_{1}$ has a power law
distribution with exponent $\varkappa>2$, then $\Lambda_{3}$ has a power law
distribution with the same exponent $\varkappa$. In particular,
${\bf{P}}(Y_{1}=r)\approx cr^{-\varkappa}$ implies
${\bf{P}}(\Lambda_{3}=r)\approx c(a_{2}b_{1})^{\varkappa-1}r^{-\varkappa}$.
The question about the power law property of $d_{*}$ is a bit more subtle.
Despite the fact that the tail behavior of randomly stopped sums, like
$d_{*}$, is quite well understood (roughly speaking, the tail
${\bf{P}}(d_{*}>t)$ of $d_{*}$ is as heavy as the heavier one of $Y_{1}$ and
$\tau_{1}$, see, e.g., [1]) not much is known about the asymptotics of the
local probabilities of randomly stopped sums in the case where the
distribution of the number of summands is heavy tailed. One may expect that,
generally, under appropriate regularity conditions, the asymptotics of the
local probabilities of randomly stopped sums follows a similar pattern to that
of the tail probabilities. This is indeed the case when the summands are heavy
tailed and the number of summands has a light tail, see, e.g., Theorem 4.30 in
[11]. Several examples are considered in Remark 1.

######  Remark 1.

Let $c,x>0$, $\varkappa>2$.

(i) Assume that ${\bf{E}}e^{aY_{1}}<\infty$ for some $a>0$. Assume that the
distribution of $X_{1}$ has property ${\cal A}_{c,\varkappa}$. Then
${\bf{P}}(d_{*}=r)\approx
cb_{1}^{\varkappa-1}\beta^{(3-\varkappa)/2}r^{1-\varkappa}$.

(ii) Assume that ${\bf{P}}(X_{1}=x)=1$. Assume that the distribution of
$Y_{1}$ has property ${\cal A}_{c,\varkappa}$. Then ${\bf{P}}(d_{*}=r)\approx
c(x^{2}b_{1})^{\varkappa-1}r^{-\varkappa}$.

Degree-degree distribution. We are interested in the bivariate distribution of
degrees of adjacent vertices. Let

$p(k_{1},k_{2})={\bf{P}}(d(v_{1})=k_{1}+1,d(v_{2})=k_{2}+1\,|\,v_{1}\sim
v_{2}),\qquad k_{1},k_{2}=0,1,\dots$ (5)

denote the probabilities defining the conditional bivariate distribution of
the ordered pair $(d(v_{1}),d(v_{2}))$, given the event that vertices $v_{1}$
and $v_{2}$ are adjacent. We note that $p(k_{1},k_{2})=p(k_{2},k_{1})$, for
any $k_{1},k_{2}=0,1,\dots$, since the probability distribution of graph $G$
is invariant under permutations of its vertices. In Theorem 2 below we show a
first order asymptotics of $p(k_{1},k_{2})$ as $n,m\to+\infty$. Before
formulation of Theorem 2 we introduce some notation.

We remark that $d_{*}$ defined by (2) depends on $Y_{1}$. By conditioning on
the event $\\{Y_{1}=y\\}$ we obtain another random variable, denoted
$d^{*}_{y}$, which has the compound Poisson distribution

${\bf{P}}(d^{*}_{y}=r)={\bf{P}}(d_{*}=r|Y_{1}=y)={\bf{P}}\Bigl{(}\sum_{j=1}^{N}\tau_{j}=r\Bigr{)},\qquad
r=0,1,\dots.$

Here $N=N_{y}$ denotes a Poisson random variable which is independent of the
iid sequence $\\{\tau_{j}\\}_{j\geq 1}$ and has mean
${\bf{E}}N_{y}=ya_{1}\beta^{1/2}$, $y\geq 0$. Given integers
$k_{1},k_{2},r\geq 0$, denote

$\displaystyle
q_{r}={\bf{E}}\bigl{(}Y_{1}{\bf{P}}(d^{*}_{Y_{1}}=r)\bigr{)}={\bf{E}}\bigl{(}Y_{1}{\bf{P}}(d_{*}=r|Y_{1})\bigr{)},$
$\displaystyle
p_{\beta}(k_{1},k_{2})=\frac{\beta}{b_{1}^{4}a_{2}}\sum_{r=0}^{k_{1}\wedge
k_{2}}(r+1)(r+2){\bf{P}}(\Lambda_{0}=r+2)q_{k_{1}-r}q_{k_{2}-r},$
$\displaystyle{\tilde{p}}(r)=r{\bf{P}}(\Lambda_{3}=r)\bigl{(}{\bf{E}}\Lambda_{3}\bigr{)}^{-1},\qquad
p_{\infty}(k_{1},k_{2})={\tilde{p}}(k_{1}+1){\tilde{p}}(k_{2}+1).$

Our main result is the following theorem.

######  Theorem 2.

Let $m,n\to\infty$. Suppose that ${\bf{E}}X_{1}^{2}<\infty$ and
${\bf{E}}Y_{1}<\infty$.

(i) Assume that $m/n\to\beta$ for some $\beta\in(0,+\infty)$. Then for every
$k_{1},k_{2}\geq 0$ we have

$p(k_{1},k_{2})=p_{\beta}(k_{1},k_{2})+o(1),$ (6)

(ii) Assume that $m/n\to+\infty$. Then for every $k_{1},k_{2}\geq 0$ we have

$p(k_{1},k_{2})=p_{\infty}(k_{1},k_{2})+o(1).$ (7)

We note that the moment conditions ${\bf{E}}X_{1}^{2}<\infty$ and
${\bf{E}}Y_{1}<\infty$ of Theorem 2 are the minimal ones as each of the
numbers $a_{2}={\bf{E}}X_{1}^{2}$ and $b_{1}={\bf{E}}Y_{1}$ enters both
formulas (6) and (7).

######  Remark 2.

In the case where $m/n\to+\infty$, the size biased probability distribution
$\\{{\tilde{p}}(r)\\}_{r\geq 1}$ is the limiting distribution of $d(v_{1})$
conditioned on the event $v_{1}\sim v_{2}$, i.e.,

${\bf{P}}(d(v_{1})=r|v_{1}\sim v_{2})={\tilde{p}}(r)+o(1),\qquad r=1,2,\dots.$
(8)

######  Remark 3.

Theorem 2 and Remark 2 remain valid if we replace $(v_{1},v_{2})$ by any other
ordered pair of vertices $(v_{i},v_{j})$, or by an ordered pair of distinct
vertices $(u^{*},v^{*})$ chosen uniformly at random, since the probability
distribution of graph $G$ is invariant under permutation of its vertices.

Let us examine how the clustering property (presence of nonvanishing
clustering coefficient) affects the structure of the asymptotic degree-degree
distribution. Firstly we consider the case $m/n\to+\infty$, where the
clustering coefficient vanishes (cf. (1)). In this case one may expect that
the statistical dependence between neighboring adjacency relations fade as
$m,n\to+\infty$ and that degrees of adjacent vertices are asymptotically
independent. This is indeed the case as (7) and (8) imply that

$p(k_{1},k_{2})={\bf{P}}(d(v_{1})=k_{1}+1,|\,v_{1}\sim
v_{2}){\bf{P}}(d(v_{2})=k_{2}+1\,|\,v_{1}\sim v_{2})+o(1).$

For $m/n\to\beta\in(0,+\infty)$ the random graph $G$ admits a nonvanishing
clustering coefficient. Now, the neighboring adjacency relations remain
statistically dependent and the asymptotic bivariate degree-degree
distribution (6) is no more a product of marginal asymptotic degree
distributions. One can show that in this case the degrees of adjacent vertices
are positively correlated (because heavy weight attributes are likely to be
shared by high degree vertices) and $G$ admits a non-vanishing and positive
Newman’s assortativity coefficient, provided that the vertex degree
distribution has a finite third moment (cf. [6]).

Several examples of power law degree-degree distributions are considered in
Corollary 1 below.

######  Corollary 1.

Let $c,x>0$ and $\varkappa>2$.

(i) Assume that ${\bf{E}}X_{1}^{2}<\infty$. Assume that the distribution of
$Y_{1}$ has property ${\cal A}_{c,\varkappa}$. Then for
$k_{1},k_{2}\to+\infty$ we have

$p_{\infty}(k_{1},k_{2})=(1+o(1))c^{2}a_{2}^{2\varkappa-4}b_{1}^{2\varkappa-6}(k_{1}k_{2})^{1-\varkappa}.$
(9)

(ii) Assume that ${\bf{E}}e^{aY_{1}}<\infty$ for some $a>0$. Assume that the
distribution of $X_{1}$ has property ${\cal A}_{c,\varkappa}$. Let
$k_{1},k_{2}\to+\infty$ so that $k_{1}\leq k_{2}$. Suppose that either
$k_{2}-k_{1}\to+\infty$ or $k_{2}-k_{1}=k$, for an arbitrary, but fixed
integer $k\geq 0$. Then

$p_{\beta}(k_{1},k_{2})=(1+o(1))\frac{\beta}{b_{1}^{4}a_{2}}\times\begin{cases}c^{*}_{1}c^{*}_{2}k_{1}^{2-\varkappa}(k_{2}-k_{1})^{1-\varkappa}&\text{if
\ \ $k_{2}-k_{1}\to+\infty$,}\\\
c^{*}_{1}c^{*}_{3,k}k_{1}^{2-\varkappa}&\text{if \ \
$k_{2}-k_{1}=k$.}\end{cases}$ (10)

Here $c^{*}_{1}=c(b_{1}\beta^{-1/2})^{\varkappa-1}$,
$c^{*}_{2}=cb_{1}^{\varkappa-2}b_{2}\beta^{(3-\varkappa)/2}$, and
$c^{*}_{3,k}=\sum_{i\geq 0}q_{i}q_{k+i}$. Furthermore, we have $q_{r}\approx
c_{2}^{*}r^{1-\varkappa}$.

(iii) Assume that ${\bf{P}}(X_{1}=x)=1$. Assume that the distribution of
$Y_{1}$ has property ${\cal A}_{c,\varkappa}$. For $k_{1},k_{2}\to+\infty$ we
have

$p_{\beta}(k_{1},k_{2})=(1+o(1))c^{2}x^{4\varkappa-8}b_{1}^{2\varkappa-6}(k_{1}k_{2})^{1-\varkappa}.$
(11)

It seems a bit surprising that the limiting degree-degree distribution
$p_{\beta}(k_{1},k_{2})$ of example (iii) of the corollary, which refers to
the clustering regime $m/n\to\beta\in(0,+\infty)$, has asymptotically
independent marginals for $k_{1},k_{2}\to+\infty$.

Our final remark is about the case where $m/n\to 0$. By Theorem 1, in this
case the edges of a sparse inhomogeneous random intersection graph span a
subgraph on $o(n)$ randomly selected vertices leaving the remaining
$(1-o(1))n$ vertices isolated. Consequently, the subgraph is relatively dense
and we do not expect stochastically bounded degrees of endpoints of adjacent
vertices.

Related work. The influence of degree-degree correlations on the network
properties have been studied by many authors, see, e.g., [8], [14], [19], [20]
and references therein. The asymptotic degree-degree distribution in a
preferential attachment random graph with tunable power law degree
distribution was shown in [13]. Our model and approach are much different. To
our best knowledge the present paper is the first attempt to trace the
relation between the degree-degree distribution and the clustering property in
a power law network. Connections between Newman’s assortativity coefficient
and the clustering coefficient in a related random graph model has been
discussed in [6].

##  2 Proof

Here we prove Theorem 2, Corollary 1 and Remarks 1, 2.

Before the proof we collect some notation. We will assume throughout the proof
that $m=m(n)\to+\infty$ as $n\to+\infty$. The expressions $o(\cdot)$,
$O(\cdot)$ will always refer to the case where $n\to+\infty$. We use the
notation $o_{P}(\cdot)$ and $O_{P}(\cdot)$ consistently with [15]. Given two
real sequences $\\{a_{n}\\}_{n\geq 1}$ and $\\{b_{n}\\}_{n\geq 1}$ we write
$a_{n}\approx b_{n}$ to denote the fact that $(a_{n}-b_{n})mn=o(1)$. By
${\mathbb{I}}_{\cal A}$ we denote the indicator function of an event ${\cal
A}$. ${\bar{\mathbb{I}}}_{\cal A}=1-{\mathbb{I}}_{\cal
A}={\mathbb{I}}_{\bar{\cal A}}$ denotes the indicator of the complement event
${\bar{\cal A}}$.

In the proof we often use the following facts: For a random variable $Z$ and a
sequence of events $\\{{\cal K}_{n}\\}_{n\geq 1}$ defined on the same
probability space we have that ${\bf{E}}|Z|<\infty$ and
$\lim_{n}{\bf{P}}({\cal K}_{n})=0$ imply ${\bf{E}}({\mathbb{I}}_{{\cal
K}_{n}}Z)=o(1)$; for a sequence of random variables $\\{Z_{n}\\}_{n\geq 1}$
the conditions $\exists C>0$ such that $|Z_{n}|\leq C$ almost surely $\forall
n$, and $Z_{n}=o_{P}(1)$ imply ${\bf{E}}|Z_{n}|=o(1)$.

We denote by ${\bf{P}}^{\star}$ and ${\bf{E}}^{\star}$ (respectively
${\tilde{\bf{P}}}$ and ${\tilde{\bf{E}}}$) the conditional probability and
expectation given $X_{1},Y_{1},Y_{2}$ (respectively $X,Y$). For random
variables $\xi,\zeta$ defined on the same probability space as $X,Y$ we denote
by $d^{\star}_{TV}(\xi,\zeta)$ (respectively ${\tilde{d}}_{TV}(\xi,\zeta)$)
the total variation distance between the conditional distributions of $\xi$
and $\zeta$ given $X_{1},Y_{1},Y_{2}$ (respectively $X,Y$). Given a sequence
of random variables $\\{Z_{n}\\}_{n\geq 1}$, defined on the same probability
space as $Y_{1},Y_{2},X_{1}$, the notation $Z_{n}=o_{P^{\star}}(1)$ means
that, for any realized values $Y_{1},Y_{2},X_{1}$ and any $\varepsilon>0$, we
have ${\bf{P}}^{\star}(Z_{n}>\varepsilon)=o(1)$. We note that for
$\\{Z_{n}\\}_{n\geq 1}$ independent of $Y_{1},Y_{2},X_{1}$ we have
$Z_{n}=o_{P^{\star}}(1)\Leftrightarrow Z_{n}=o_{P}(1)$.

The degree of a vertex $v_{i}\in V$ is denoted $d_{i}=d(v_{i})$. The number of
common neighbors of $v_{i},v_{j}\in V$ is denoted $d_{ij}$. For a vertex $v\in
V$ and attribute $w\in W$ we denote by $\\{w\to v\\}$ the event that $v$ and
$w$ are linked in $H$. Introduce the events ${\cal A}_{i}=\\{w_{i}\to
v_{1},w_{i}\to v_{2}\\}$, $1\leq i\leq m$. We write for short

${\mathbb{I}}_{ij}={\mathbb{I}}_{\\{w_{i}\to
v_{j}\\}},\qquad{\bar{\mathbb{I}}}_{ij}=1-{\mathbb{I}}_{ij},\qquad{\bf
I}_{ij}={\mathbb{I}}_{\\{\lambda_{ij}\leq 1\\}},\qquad{\bar{\bf
I}}_{ij}=1-{\bf I}_{ij}.$

Let ${\bf L}=(L_{0},L_{1},L_{2})$ denote the random vector with marginal
random variables

$L_{0}=u_{1},\qquad L_{1}=\sum_{2\leq i\leq m}{\mathbb{I}}_{i1}u_{i},\qquad
L_{2}=\sum_{2\leq i\leq m}{\mathbb{I}}_{i2}u_{i},\qquad u_{i}=\sum_{3\leq
j\leq n}{\mathbb{I}}_{ij},\quad 1\leq i\leq m.$

Let $\Lambda_{0},\Lambda_{1},\Lambda_{2},\Lambda_{3},\Lambda_{4}$ denote
random variables having mixed Poisson distributions

${\bf{P}}(\Lambda_{i}=r)={\bf{E}}(e^{-\lambda_{i}}\lambda_{i}^{r}/r!),\qquad
r=0,1,2,\dots,\quad i=0,1,2,3,4.$ (12)

Here

$\lambda_{0}=X_{1}b_{1}\beta^{-1/2},\quad\lambda_{1}=Y_{1}a_{1}\beta^{1/2},\quad\lambda_{2}=Y_{2}a_{1}\beta^{1/2},\quad\lambda_{3}=Y_{1}a_{2}b_{1},\quad\lambda_{4}=Y_{2}a_{2}b_{1}.$

We assume that conditionally, given $Y_{1},Y_{2},X_{1}$, the random variables
$\Lambda_{i}$, $0\leq i\leq 4$ are independent. Define random variables
$d^{*}_{Y_{1}}=\sum_{i=1}^{\Lambda_{1}}\tau_{i}$ and
$d^{*}_{Y_{2}}=\sum_{i=1}^{\Lambda_{2}}\tau^{\prime}_{i}$. Here
$\tau_{i},\tau^{\prime}_{i},i\geq 1$ are independent and identically
distributed random variables, which are independent of $Y_{1},Y_{2},X_{1}$ and
have distribution (3). Define the events

$\displaystyle{\cal
U}_{k_{1},k_{2}}=\\{d_{1}=k_{1}+1,d_{2}=k_{2}+1\\},\qquad{\cal
U}_{r,r_{1},r_{2}}^{*}=\\{{\bf L}=(r,r_{1},r_{2})\\},$ $\displaystyle{\cal
U}_{r,r_{1},r_{2}}^{**}=\\{\Lambda_{0}=r,d^{*}_{Y_{1}}=r_{1},d^{*}_{Y_{2}}=r_{2}\\},\qquad{\cal
U}_{r_{1},r_{2}}^{***}=\\{\Lambda_{3}=r_{1},\Lambda_{4}=r_{2}\\}.$

Define random variables ${\hat{a}}_{j}=m^{-1}\sum_{2\leq i\leq m}X_{i}^{j}$
and ${\hat{b}}_{j}=n^{-1}\sum_{3\leq i\leq n}Y_{i}^{j}$.

###### Proof of Theorem 2.

Proof of (i). The intuition behind formula (6) is that the adjacency relation
$v_{1}\sim v_{2}$ together with the common neighbors of $v_{1}$ and $v_{2}$
are witnessed, with a high probability, by a single attribute (all attributes
having equal chances). Furthermore, conditionally on the event that this
attribute is $w_{1}$, and given $Y_{1},Y_{2},X_{1}$, we have that the random
variables $d_{12}$, $d_{1}-1-d_{12}=:d_{1}^{\prime}$,
$d_{2}-1-d_{12}=:d_{2}^{\prime}$ are asymptotically independent. We note that
$d^{\prime}_{1}$ and $d^{\prime}_{2}$ count individual (not shared) neighbors
of $v_{1}$ and $v_{2}$. The asymptotic independence comes from the fact that
(conditionally given $Y_{1},Y_{2},X_{1}$) these random variables are mainly
related via average characteristics ${\hat{a}}_{1}$, ${\hat{b}}_{1}$ which are
asymptotically constant, by the law of large numbers. Now, using Theorem 1 we
identify limiting distributions of $d^{\prime}_{1},d^{\prime}_{2}$. The
limiting distribution of $d_{12}$ (conditioned on the event ${\cal A}_{1}$) is
that of $\Lambda_{0}$.

We briefly outline the proof. In the first step we show that

$p(k_{1},k_{2})=\frac{{\bf{P}}({\cal U}_{k_{1},k_{2}}\cap\\{v_{1}\sim
v_{2}\\})}{{\bf{P}}(v_{1}\sim v_{2})}=\frac{{\bf{P}}({\cal
U}_{k_{1},k_{2}}\cap(\cup_{i}{\cal A}_{i}))}{{\bf{P}}(\cup_{i}{\cal
A}_{i}))}=\frac{nm}{a_{2}b_{1}^{2}}{\bf{P}}({\cal U}_{k_{1},k_{2}}\cap{\cal
A}_{1})+o(1).$ (13)

Then using the total probability formula we split

${\bf{P}}({\cal U}_{k_{1},k_{2}}\cap{\cal A}_{1})=\sum_{r=0}^{k_{1}\wedge
k_{2}}{\bf{P}}({\cal U}_{k_{1},k_{2}}\cap\\{d_{12}=r\\}\cap{\cal A}_{1}).$
(14)

In the second step we show that for every $r=0,1,\dots,k_{1}\wedge k_{1}$

${\bf{P}}({\cal U}_{k_{1},k_{2}}\cap\\{d_{12}=r\\}\cap{\cal
A}_{1})\approx{\bf{P}}({\cal U}^{*}_{r,k_{1}-r,k_{2}-r}\cap{\cal A}_{1}).$
(15)

In the final step we show that for $r,r_{1},r_{2}=0,1,2\dots$

${\bf{P}}({\cal U}^{*}_{r,r_{1},r_{2}}\cap{\cal
A}_{1})\approx{\bf{E}}\bigl{(}\lambda_{11}\lambda_{12}{\bf{P}}^{\star}({\cal
U}^{**}_{r,r_{1},r_{2}})\bigr{)}.$ (16)

Now the simple identity

$nm{\bf{E}}\bigl{(}\lambda_{11}\lambda_{12}{\bf{P}}^{\star}({\cal
U}^{**}_{r,r_{1},r_{2}})\bigr{)}=\frac{\beta}{b_{1}^{2}}(r+1)(r+2){\bf{P}}(\Lambda_{0}=r+2)q_{r_{1}}q_{r_{2}}$

completes the proof of (6). Finally, we remark that in order to prove the
result under the minimal moment conditions ${\bf{E}}Y_{1}<\infty$ and
${\bf{E}}X^{2}_{1}<\infty$, we invoke, when necessary, a truncation argument,
which makes our presentation some more involved.

Step 1. Here we prove (13). To this aim we show that

$\displaystyle{\bf{P}}({\cal U}_{k_{1},k_{2}}\cap\\{v_{1}\sim
v_{2}\\})=m{\bf{P}}({\cal U}_{k_{1},k_{2}}\cap{\cal A}_{1})+o(n^{-1}),$
$\displaystyle{\bf{P}}(\\{v_{1}\sim v_{2}\\})=n^{-1}a_{2}b_{1}^{2}+o(n^{-1}).$
(17)

Since ${\bf{P}}({\cal
A}_{i})\leq{\bf{E}}\lambda_{i1}\lambda_{i2}=a_{2}b_{1}^{2}(nm)^{-1}$,
relations (17) imply (13). We only prove the second relation. The proof of the
first one is much the same. Fix small $0<\delta<1$ and introduce events ${\cal
H}_{i}=\\{Y_{i}<\delta\sqrt{n}\\}$, $i=1,2$. We have

$\displaystyle{\bf{P}}(\\{v_{1}\sim v_{2}\\})$ $\displaystyle=$
$\displaystyle{\bf{P}}(\\{v_{1}\sim v_{2}\\}\cap{\cal H}_{1}\cap{\cal
H}_{2})+{\bf{P}}(\\{v_{1}\sim v_{2}\\}\cap{\bar{\cal H}}_{1}\cap{\cal H}_{2})$
$\displaystyle+$ $\displaystyle{\bf{P}}(\\{v_{1}\sim v_{2}\\}\cap{\cal
H}_{1}\cap{\bar{\cal H}}_{2})+{\bf{P}}(\\{v_{1}\sim v_{2}\\}\cap{\bar{\cal
H}}_{1}\cap{\bar{\cal H}}_{2})$ $\displaystyle=:$ $\displaystyle
p^{\prime}_{1}+p^{\prime}_{2}+p^{\prime}_{3}+p^{\prime}_{4}.$

Now we evaluate $p^{\prime}_{1}$ and construct upper bounds for
$p^{\prime}_{i}$, $i=2,3,4$. Using the independence of $Y_{1},Y_{2}$ and
Markov’s inequality we obtain

$p^{\prime}_{4}\leq{\bf{P}}({\bar{\cal H}}_{1}\cap{\bar{\cal
H}}_{2})\leq\delta^{-2}n^{-1}({\bf{E}}(Y_{1}{\bar{\mathbb{I}}}_{H_{1}}))^{2}.$
(19)

Next, using the identity $\\{v_{1}\sim v_{2}\\}=\cup_{1\leq i\leq m}{\cal
A}_{i}$ and inequality

${\bf{P}}({\cal A}_{1}\cap{\bar{\cal H}}_{1})={\bf{E}}({\bf{P}}^{\star}({\cal
A}_{1}){\mathbb{I}}_{{\bar{\cal
H}}_{1}})\leq{\bf{E}}(\lambda_{11}\lambda_{21}{\bar{\cal H}}_{1})$

we obtain

$\displaystyle p^{\prime}_{2}\leq\sum_{1\leq i\leq m}{\bf{P}}({\cal
A}_{i}\cap{\bar{\cal H}}_{1})=m{\bf{P}}({\cal A}_{1}\cap{\bar{\cal
H}}_{1})\leq\frac{a_{2}b_{1}}{n}{\bf{E}}Y_{1}{\bar{\mathbb{I}}}_{{\cal
H}_{1}}.$ (20)

Clearly, (20) extends to $p^{\prime}_{3}$. An upper bound on $p^{\prime}_{1}$
is obtained in a similar way,

$p^{\prime}_{1}\leq{\bf{P}}(\\{v_{1}\sim v_{2}\\})\leq\sum_{1\leq i\leq
m}{\bf{P}}({\cal A}_{i})\leq\sum_{1\leq i\leq
m}{\bf{E}}\lambda_{1i}\lambda_{2i}=n^{-1}a_{2}b_{1}^{2}.$ (21)

To get a lower bound we invoke inclusion-exclusion. We have

$\displaystyle p^{\prime}_{1}\geq\sum_{1\leq i\leq m}{\bf{P}}({\cal
A}_{i}\cap{\cal H}_{1}\cap{\cal H}_{2})-\sum_{1\leq i<j\leq m}{\bf{P}}({\cal
A}_{i}\cap{\cal A}_{j}\cap{\cal H}_{1}\cap{\cal
H}_{2})=:mp^{\prime}-{\tbinom{m}{2}}p^{\prime\prime},$ (22)

where $p^{\prime}={\bf{P}}({\cal A}_{1}\cap{\cal H}_{1}\cap{\cal H}_{2})$ and
$p^{\prime\prime}={\bf{P}}({\cal A}_{1}\cap{\cal A}_{2}\cap{\cal
H}_{1}\cap{\cal H}_{2})$. In order to evaluate
$p^{\prime}={\bf{E}}\bigl{(}{\bf{P}}^{\star}({\cal A}_{1}){\mathbb{I}}_{{\cal
H}_{1}\cap{\cal H}_{2}}\bigr{)}$ we invoke the inequalities

$(1-{\bar{\bf I}}_{11}-{\bar{\bf I}}_{12})\lambda_{11}\lambda_{12}\leq{\bf
I}_{11}{\bf I}_{12}\lambda_{11}\lambda_{12}={\bf I}_{11}{\bf
I}_{12}{\bf{P}}^{\star}({\cal A}_{1})\leq{\bf{P}}^{\star}({\cal
A}_{1})\leq\lambda_{11}\lambda_{12}.$ (23)

We obtain

$p^{\prime}\geq{\bf{E}}\bigl{(}{\bf{P}}^{\star}({\cal
A}_{1}){\mathbb{I}}_{{\cal H}_{1}\cap{\cal H}_{2}}{\bf I}_{11}{\bf
I}_{12}\bigr{)}\geq(nm)^{-1}(a_{2}b_{1}^{2}-R),$ (24)

where $R={\bf{E}}\bigl{(}Y_{1}Y_{2}X_{1}^{2}({\bar{\bf I}}_{11}+{\bar{\bf
I}}_{12}+{\bar{\mathbb{I}}}_{{\cal H}_{1}\cap{\cal H}_{2}})\bigr{)}$. The next
upper bound for $p^{\prime\prime}$ is simple

$p^{\prime\prime}={\bf{E}}\bigl{(}{\bf{P}}^{\star}({\cal
A}_{1}){\bf{P}}^{\star}({\cal A}_{2}){\mathbb{I}}_{{\cal H}_{1}\cap{\cal
H}_{2}}\bigr{)}\leq{\bf{E}}(\lambda_{11}\lambda_{12}\lambda_{21}\lambda_{22}{\mathbb{I}}_{{\cal
H}_{1}\cap{\cal
H}_{2}})\leq\delta^{2}n^{-1}m^{-2}{\bf{E}}(Y_{1}Y_{2}X_{1}^{2}X_{2}^{2}).$
(25)

Collecting (24), (25) in (22) we obtain a lower bound for $p_{1}^{\prime}$.
Combining this lower bound with (21) we obtain

$n^{-1}(a_{2}b_{1}^{2}-R-\delta^{2}a_{2}^{2}b_{1}^{2})\leq p_{1}^{\prime}\leq
n^{-1}a_{2}b_{1}^{2}.$ (26)

Finally, we choose $\delta=\delta_{n}$ converging to $0$ slowly enough so that
$\delta\sqrt{n}\to+\infty$ and
$\delta^{-1}{\bf{E}}(Y_{1}{\bar{\mathbb{I}}}_{H_{1}})\to 0$. We obtain from
(19), (20) that $p^{\prime}_{2},p^{\prime}_{3},p^{\prime}_{4}=o(n^{-1})$ and
(26) implies that $p^{\prime}_{1}=n^{-1}a_{2}b_{1}^{2}+o(n^{-1})$. Hence (17)
follows from (2).

Step 2. Here we prove (15). Let us note that event ${\cal A}_{1}$ implies that
$L_{0}$ counts common neighbors of $v_{1}$ and $v_{2}$ witnessed by $w_{1}$.
In the case where $L_{0}\not=d_{12}$ there should be a common neighbor of
$v_{1},v_{2}$ witnessed by some attribute $w_{i}$ other than $w_{1}$ or
witnessed by two different attributes, say $w_{i_{1}},w_{i_{2}}\in
W\setminus\\{w_{1}\\}$. We introduce related events

$\displaystyle{\cal B}_{00}=\\{{\mathbb{I}}_{i1}{\mathbb{I}}_{i2}=1\
{\text{for some}}\ 2\leq i\leq m\\},$ $\displaystyle{\cal
B}_{01}=\\{{\mathbb{I}}_{i_{1}1}{\mathbb{I}}_{i_{1}j}{\mathbb{I}}_{i_{2}2}{\mathbb{I}}_{i_{2}j}=1\
{\text{for some}}\ 3\leq j\leq n\ {\text{and}}\ 2\leq i_{1}\not=i_{2}\leq
m\\}$

and observe that on the event ${\cal A}_{1}\cap{\overline{({\cal
B}_{00}\cup{\cal B}_{01})}}$ we have $L_{0}=d_{12}$. Next, assuming that
events ${\cal A}_{1}$ and $L_{0}=d_{12}$ hold we consider $L_{k}$ for $k=1,2$.
The sum $L_{k}$ counts pairs $w_{i}\to v_{j}$, for $i\geq 1$, $j\geq 3$, such
that $v_{j}$ is a neighbor of $v_{k}$ witnessed by $w_{i}$. Generally, we have
$L_{k}\geq d_{k}-1-d_{12}$. This inequality is strict if some common neighbor
of $v_{1},v_{2}$ witnessed by $w_{1}$ is also witnessed as a neighbor of
$v_{k}$ by some other attribute $w_{i}$, $i\geq 2$. The inequality is also
strict in the case where some neighbor of $v_{k}$ is witnessed by two or more
distinct attributes. If we rule out both of these possibilities, we have the
equality $L_{k}=d_{k}-1-d_{12}$. We introduce the corresponding undesired
events

$\displaystyle{\cal
B}_{k0}=\\{{\mathbb{I}}_{ik}{\mathbb{I}}_{ij}{\mathbb{I}}_{1j}=1\ {\text{for
some}}\ 3\leq j\leq n\ {\text{and}}\ 2\leq i\leq m\\},$ $\displaystyle{\cal
B}_{k1}=\\{{\mathbb{I}}_{i_{1}k}{\mathbb{I}}_{i_{1}j}{\mathbb{I}}_{i_{2}k}{\mathbb{I}}_{i_{2}j}=1\
{\text{for some}}\ 3\leq j\leq n\ {\text{and}}\ 2\leq i_{1}<i_{2}\leq m\\}.$

Finally, we conclude that if ${\cal A}_{1}$ holds and at least one of the
following three relations fails

$L_{0}=d_{12},\quad L_{1}+L_{0}=d_{1}-1,\quad L_{2}+L_{0}=d_{2}-1$

then at least one of the events ${\cal B}_{l},{\cal B}_{lj}$, $0\leq l\leq 2$,
$0\leq j\leq 1$, occurs. Hence, we have

$\displaystyle\bigl{|}{\bf{P}}({\cal
U}_{k_{1},k_{2}}\cap\\{d_{12}=r\\}\cap{\cal A}_{1})-{\bf{P}}({\cal
U}^{*}_{r,k_{1}-r,k_{2}-r}\cap{\cal A}_{1})\bigr{|}\leq\sum_{0\leq l\leq
2}\sum_{0\leq j\leq 1}{\bf{P}}({\cal A}_{1}\cap{\cal B}_{lj}).$

Next we prove that the quantity on the right is $o((nm)^{-1})$. For this
purpose we estimate

$\displaystyle{\bf{P}}({\cal A}_{1}\cap{\cal
B}_{lj})={\bf{E}}\bigl{(}{\bf{P}}^{\star}({\cal A}_{1}){\bf{P}}^{\star}({\cal
B}_{lj})\bigr{)}\leq(mn)^{-1}{\bf{E}}(Y_{1}Y_{2}X_{1}^{2}{\bf{P}}^{\star}({\cal
B}_{lj}))$ (27)

and show that for any realized values $Y_{1},Y_{2},X_{1}$ we have

${\bf{P}}^{\star}({\cal B}_{lj})=o(1),\qquad{\text{for}}\qquad 0\leq l\leq
2,\quad 0\leq j\leq 1.$ (28)

Since ${\bf{P}}^{*}(\cdot)\leq 1$ and ${\bf{E}}Y_{1}Y_{2}X_{1}^{2}<\infty$,
Lebesgue’s dominated convergence theorem then implies the desired bound
${\bf{E}}(Y_{1}Y_{2}X_{1}^{2}{\bf{P}}^{\star}({\cal B}_{lj}))=o(1)$.

Let us show (28). For this purpose we write events ${\cal B}_{lj}$ in the form
${\cal B}_{lj}=\\{S_{lj}\geq 1\\}$, where

$\displaystyle S_{00}=\sum_{2\leq i\leq
m}{\mathbb{I}}_{i1}{\mathbb{I}}_{i2},\qquad\qquad\qquad S_{01}=\sum_{3\leq
j\leq n}\sum_{2\leq i_{1}\not=i_{2}\leq
m}{\mathbb{I}}_{i_{1}1}{\mathbb{I}}_{i_{1}j}{\mathbb{I}}_{i_{2}2}{\mathbb{I}}_{i_{2}j},$
$\displaystyle S_{k0}=\sum_{3\leq j\leq n}\sum_{2\leq i\leq
m}{\mathbb{I}}_{ik}{\mathbb{I}}_{ij}{\mathbb{I}}_{1j},\qquad\ \
S_{k1}=\sum_{3\leq j\leq n}\sum_{2\leq i_{1}<i_{2}\leq
m}{\mathbb{I}}_{i_{1}k}{\mathbb{I}}_{i_{1}j}{\mathbb{I}}_{i_{2}k}{\mathbb{I}}_{i_{2}j},$
(29)

and apply the inequality

${\bf{P}}^{\star}(S_{lj}\geq
1)\leq\varepsilon+{\bf{P}}^{\star}({\tilde{\bf{E}}}S_{lj}\geq\varepsilon),\qquad\forall\varepsilon>0.$
(30)

Let us briefly explain (30). We apply the trivial inequality
$Z\leq\varepsilon+Z{\mathbb{I}}_{\\{Z>\varepsilon\\}}$ to the random variable
$Z={\tilde{\bf{P}}}(S_{lj}\geq 1)$ and obtain

${\tilde{\bf{P}}}(S_{lj}\geq
1)\leq\varepsilon+{\mathbb{I}}_{\\{{\tilde{\bf{P}}}(S_{lj}\geq
1)>\varepsilon\\}}\leq\varepsilon+{\mathbb{I}}_{\\{{\tilde{\bf{E}}}S_{lj}>\varepsilon\\}}.$
(31)

The last inequality follows by Markov’s inequality,
${\tilde{\bf{P}}}(S_{lj}\geq 1)\leq{\tilde{\bf{E}}}S_{lj}$. Taking
${\bf{E}}^{\star}$-expected values in (31) we arrive to (30) since
${\bf{P}}^{\star}(S_{lj}\geq
1)={\bf{E}}^{\star}\bigl{(}{\tilde{\bf{P}}}(S_{lj}\geq 1)\bigr{)}$.

Now, (28) follows from (30) and the fact that
${\tilde{\bf{E}}}S_{lj}=o_{P^{\star}}(1)$ for any realized values
$Y_{1},Y_{2},X_{1}$. To show that the latter bound holds true we estimate

$\displaystyle{\tilde{\bf{E}}}S_{00}\leq\sum_{2\leq i\leq
m}\lambda_{i1}\lambda_{i2}=Y_{1}Y_{2}n^{-1}{\hat{a}}_{2}=o_{P^{\star}}(1),$
$\displaystyle{\tilde{\bf{E}}}S_{01}\leq\sum_{3\leq j\leq n}\sum_{2\leq
i_{1}\not=i_{2}\leq
m}\lambda_{i_{1}1}\lambda_{i_{1}j}\lambda_{i_{2}2}\lambda_{i_{2}j}\leq
Y_{1}Y_{2}({\hat{a}}_{2})^{2}{\hat{b}}_{2}n^{-1}=o_{P^{\star}}(1),$
$\displaystyle{\tilde{\bf{E}}}S_{k0}\leq\sum_{3\leq j\leq n}\sum_{2\leq i\leq
m}{\lambda}_{ik}{\lambda}_{ij}{\lambda}_{1j}\leq
Y_{1}X_{1}\beta_{n}^{-1/2}{\hat{a}}_{2}{\hat{b}}_{2}n^{-1}=o_{P^{\star}}(1),$
$\displaystyle{\tilde{\bf{E}}}S_{k0}\leq\sum_{3\leq j\leq n}\sum_{2\leq
i_{1}<i_{2}\leq
m}{\lambda}_{i_{1}k}{\lambda}_{i_{1}j}{\lambda}_{i_{2}k}{\lambda}_{i_{2}j}\leq
Y_{k}^{2}({\hat{a}}_{2})^{2}{\hat{b}}_{2}n^{-1}=o_{P^{\star}}(1).$

Here we used the fact that ${\bf{E}}X_{1}^{2}<\infty$ implies
${\hat{a}}_{2}=O_{P}(1)$ and ${\bf{E}}Y_{1}<\infty$ implies
${\hat{b}}_{2}n^{-1}=o_{P}(1)$.

Step 3. Here we prove (16). Denote

$\Delta_{1}={\bf{P}}^{\star}({\cal
U}^{*}_{r,r_{1},r_{2}})-{\bf{P}}^{\star}({\cal
U}^{**}_{r,r_{1},r_{2}}),\qquad\Delta_{2}={\bf{P}}^{\star}({\cal
A}_{1})-\lambda_{11}\lambda_{12}.$

From identities

${\bf{P}}({\cal U}^{*}_{r,r_{1},r_{2}}\cap{\cal
A}_{1})={\bf{E}}\bigl{(}{\bf{P}}^{\star}({\cal
U}^{*}_{r,r_{1},r_{2}}){\bf{P}}^{\star}({\cal
A}_{1})\bigr{)},\quad{\bf{P}}({\cal U}^{**}_{r,r_{1},r_{2}}\cap{\cal
A}_{1})={\bf{E}}\bigl{(}{\bf{P}}^{\star}({\cal
U}^{**}_{r,r_{1},r_{2}}){\bf{P}}^{\star}({\cal A}_{1})\bigr{)}$

we obtain

${\bf{P}}({\cal U}^{*}_{r,r_{1},r_{2}}\cap{\cal
A}_{1})-\lambda_{11}\lambda_{12}{\bf{P}}({\cal
U}^{**}_{r,r_{1},r_{2}})={\bf{E}}\bigl{(}\Delta_{1}{\bf{P}}^{\star}({\cal
A}_{1})\bigr{)}+{\bf{E}}\bigl{(}\Delta_{2}{\bf{P}}^{\star}({\cal
U}^{**}_{r,r_{1},r_{2}})\bigr{)}.$ (32)

We shall show in Lemma 2 below that for any realized values
$Y_{1},Y_{2},X_{1}$ we have $\Delta_{1}=o(1)$. This, together with the
inequality ${\bf{P}}^{\star}({\cal A}_{1})\leq\lambda_{11}\lambda_{12}$
implies

${\bf{E}}(\Delta_{1}{\bf{P}}^{\star}({\cal
A}_{1}))\leq(nm)^{-1}{\bf{E}}(\Delta_{1}Y_{1}Y_{2}X_{1}^{2})=o((nm)^{-1}),$
(33)

by Lebesgue’s dominated convergence theorem. Furthermore, (23) implies

$\bigl{|}{\bf{E}}\bigl{(}\Delta_{2}{\bf{P}}^{\star}({\cal
U}^{**}_{r,r_{1},r_{2}})\bigr{)}\bigr{|}\leq{\bf{E}}|\Delta_{2}|\leq(nm)^{-1}{\bf{E}}Y_{1}Y_{2}X_{1}^{2}({\bar{\bf
I}}_{11}+{\bar{\bf I}}_{12})=o((nm)^{-1}).$ (34)

Collecting (33) and (34) in (32) we obtain (16).

Proof of (ii). The proof (7) is similar to that of (6). It makes use the
observation that the typical adjacency relation is witnessed by a single
attribute. One difference is that now the size of the collection of
attributes, prescribed to the typical vertex, tends to infinity as
$n,m\to+\infty$. Since our intersection graph is sparse, this implies that the
number of vertices linked (in $H$) to any given single attribute is most
likely $0$, it is $1$ with a small probability, but it is almost never larger
than $1$. As a consequence we obtain that $d_{12}=o_{P}(1)$. Another
consequence is that the number of neighbors of a given vertex is distributed
as Poisson mixture ${\cal P}(\lambda)$, where random variable $\lambda$
accounts for the size of the collection of attributes prescribed to the
vertex.

The first several steps of the proof are the same as that of (6). Namely,
relations (13), (14), (15) hold true as their proof remains valid for
$m/n\to+\infty$. Further steps of the proof are a bit different. We show that

${\bf{P}}({\cal U}^{*}_{r,k_{1}-r,k_{2}-r}\cap{\cal A}_{1})\approx
0,\qquad{\text{for}}\qquad r=1,2,\dots,$ (35)

and

${\bf{P}}({\cal U}^{*}_{0,k_{1},k_{2}}\cap{\cal
A}_{1})\approx{\bf{P}}(\\{L_{1}=k_{1},L_{2}=k_{2}\\}\cap{\cal A}_{1}).$ (36)

Finally, we show that

${\bf{P}}(\\{L_{1}=k_{1},L_{2}=k_{2}\\}\cap{\cal
A}_{1})\approx{\bf{E}}\bigl{(}\lambda_{11}\lambda_{12}{\bf{P}}^{\star}({\cal
U}^{***}_{k_{1},k_{2}})\bigr{)}.$ (37)

Now the simple identity

$a_{2}^{-1}b_{1}^{-2}nm{\bf{E}}\bigl{(}\lambda_{11}\lambda_{12}{\bf{P}}^{\star}({\cal
U}^{***}_{k_{1},k_{2}})\bigr{)}={\tilde{p}}(k_{1}+1){\tilde{p}}(k_{2}+1)$

completes the proof of (7). It remains to prove (35), (36), (37).

Let us prove (35), (36). Denote $R^{\prime}={\bf{P}}(\\{L_{0}\geq
1\\}\cap{\cal A}_{1})$. Relations (35), (36) follow from inequalities

$\displaystyle{\bf{P}}({\cal U}^{*}_{r,k_{1}-r,k_{2}-r}\cap{\cal A}_{1})\leq
R^{\prime},\qquad r=1,2,\dots,$ (38) $\displaystyle
0\leq{\bf{P}}(\\{L_{1}=k_{1},L_{2}=k_{2}\\}\cap{\cal A}_{1})-{\bf{P}}({\cal
U}^{*}_{0,k_{1},k_{2}}\cap{\cal A}_{1})\leq R^{\prime},$ (39)

and the bound $R^{\prime}=o((nm)^{-1})$. To prove the latter bound we write

$R^{\prime}={\bf{E}}\bigl{(}{\bf{P}}^{\star}(L_{0}\geq
1){\bf{P}}^{\star}(A_{1})\bigr{)}\leq(nm)^{-1}{\bf{E}}(Y_{1}Y_{2}X_{1}^{2}{\bf{P}}^{\star}(L_{0}\geq
1))=o((nm)^{-1}).$ (40)

Here we used inequalities ${\bf{P}}^{\star}({\cal
A}_{1})\leq\lambda_{11}\lambda_{12}\leq(nm)^{-1}Y_{1}Y_{2}X_{1}^{2}$ and the
bound ${\bf{E}}(Y_{1}Y_{2}X_{1}^{2}{\bf{P}}^{\star}(L_{0}\geq 1))=o(1)$, which
follows by Lebesque’s dominated convergence theorem, since

${\bf{P}}^{\star}(L_{0}\geq 1)\leq{\bf{E}}^{\star}L_{0}\leq\sum_{3\leq j\leq
n}\lambda_{1j}=b_{1}X_{1}((n-2)/n)\beta_{n}^{-1/2}=o(1).$

Let us prove (37). The proof is similar to that of (16). We write

${\bf{P}}(\\{L_{1}=k_{1},L_{2}=k_{2}\\}\cap{\cal
A}_{1})-\lambda_{11}\lambda_{12}{\bf{P}}({\cal
U}^{***}_{k_{1},k_{2}})={\bf{E}}\bigl{(}\Delta_{3}{\bf{P}}^{\star}({\cal
A}_{1})\bigr{)}+{\bf{E}}\bigl{(}\Delta_{2}{\bf{P}}^{\star}({\cal
U}^{***}_{k_{1},k_{2}})\bigr{)},$ (41)

where

$\Delta_{2}={\bf{P}}^{\star}({\cal
A}_{1})-\lambda_{11}\lambda_{12},\qquad\Delta_{3}={\bf{P}}^{\star}(L_{1}=k_{1},L_{2}=k_{2})-{\bf{P}}^{\star}({\cal
U}_{k_{1},k_{2}}^{***})$

and show that both summands in the right of (41) are $o((nm)^{-1})$, cf. proof
of (16) above. In fact, the only think what remains to show is that for any
realized values $Y_{1},Y_{2},X_{1}$ we have $\Delta_{3}=o(1)$. This is shown
in Lemma 3 below.

∎

###### Proof of Remark 1.

Let us prove (i). Lemma 4 implies

${\bf{P}}(\Lambda_{0}=r)\approx
c^{*}_{1}r^{-\varkappa},\qquad{\text{where}}\qquad
c^{*}_{1}=c(b_{1}\beta^{-1/2})^{\varkappa-1}.$ (42)

Consequently,

${\bf{P}}(\tau_{1}=r)\approx
ca_{1}^{-1}(b_{1}\beta^{-1/2})^{\varkappa-2}r^{1-\varkappa}.$ (43)

From the latter relation we conclude that the sequence of probabilities
$\\{{\bf{P}}(\tau_{1}=r)\\}_{r\geq 0}$ is longtailed and subexponential, that
is, it satisfies conditions of Theorem 4.30 of [11]. This theorem implies
${\bf{P}}(\sum_{1\leq
i\leq\Lambda_{1}}{\tau_{i}}=r)\approx{\bf{P}}(\tau_{1}=r){\bf{E}}\Lambda_{1}$,
thus completing the proof.

Let us prove (ii). We observe that $\tau_{1}$ has Poisson distribution with
mean $\lambda_{0}=xb_{1}\beta^{-1/2}$. Hence, given $\Lambda_{1}$, the random
variable $d_{*}$ has Poisson distribution with mean $\lambda_{0}\Lambda_{1}$.
Now statement (iii) of Lemma 4 implies that ${\bf{P}}(\Lambda_{1}=r)\approx
c_{*}r^{-\varkappa}$, where $c_{*}=c(a_{1}\beta^{1/2})^{\varkappa-1}$. Next,
we apply statement (iii) of Lemma 4 once again and obtain
${\bf{P}}(d_{*}=r)\approx c_{*}\lambda_{0}^{\varkappa-1}r^{-\varkappa}$.

∎

###### Proof of Remark 2.

Let us prove (8). The proof is standard and simple. We present it here for
reader’s convenience. Let $(v_{1}^{\prime},v_{2}^{\prime})$ denote an ordered
pair of distinct vertices drawn uniformly at random and let
${\bf{P}}^{\prime}$ and ${\bf{E}}^{\prime}$ denote the conditional probability
and expectation given all the random variables considered, but
$(v_{1}^{\prime},v_{2}^{\prime})$. We have

${\bf{P}}(d(v_{1})=r|v_{1}\sim v_{2})=\frac{{\bf{P}}(d(v_{1})=r,v_{1}\sim
v_{2})}{{\bf{P}}(v_{1}\sim
v_{2})}=\frac{{\bf{P}}(d(v^{\prime}_{1})=r,v^{\prime}_{1}\sim
v^{\prime}_{2})}{{\bf{P}}(v_{1}\sim v_{2})}.$ (44)

The denominator is evaluated in (17): We have

${\bf{P}}(\\{v_{1}\sim
v_{2}\\})=n^{-1}a_{2}b_{1}^{2}+o(n^{-1})=n^{-1}{\bf{E}}\Lambda_{3}+o(n^{-1}).$

In the last step we used the simple identities
${\bf{E}}\Lambda_{3}={\bf{E}}\lambda_{3}=a_{2}b_{1}^{2}$. In order to evaluate
the numerator we combine identities

$\displaystyle{\bf{P}}^{\prime}(d(v^{\prime}_{1})=r,v^{\prime}_{1}\sim
v^{\prime}_{2})={\bf{P}}^{\prime}(v^{\prime}_{1}\sim
v^{\prime}_{2}|d(v^{\prime}_{1})=r){\bf{P}}^{\prime}(d(v^{\prime}_{1})=r)=\frac{r}{n-1}{\bf{P}}^{\prime}(d(v^{\prime}_{1})=r)$
$\displaystyle{\bf{P}}(d(v^{\prime}_{1})=r,v^{\prime}_{1}\sim
v^{\prime}_{2})={\bf{E}}\bigl{(}{\bf{P}}^{\prime}(d(v^{\prime}_{1})=r,v^{\prime}_{1}\sim
v^{\prime}_{2})\bigr{)}.$

We obtain ${\bf{P}}(d(v^{\prime}_{1})=r,v^{\prime}_{1}\sim
v^{\prime}_{2})=(r/(n-1)){\bf{P}}(d(v_{1})=r)$. Hence, by (44),

${\bf{P}}(d(v_{1})=r|v_{1}\sim
v_{2})=r{\bf{P}}(d(v_{1})=r)({\bf{E}}\Lambda_{3})^{-1}+o(1).$

Now, the statement (ii) of Theorem 1 completes the proof of (8). ∎

###### Proof of Corollary 1.

(i) follows from the relation ${\bf{P}}(\Lambda_{3}=r)\approx
c(a_{2}b_{1})^{\varkappa-1}r^{-\varkappa}$, see Lemma 4.

In the proof of (ii) and (iii) we assume that $k_{1}\leq k_{2}$ and use the
notation

$S_{A}=\sum_{r\in
A}(r+1)(r+2){\bf{P}}(\Lambda_{0}=r+2)q_{k_{1}-r}q_{k_{2}-r},\qquad
A\in[0,k_{1}].$

Let us prove (ii). We observe that ${\bf{E}}(e^{aY_{1}})<\infty$ implies that
${\bf{E}}Y_{1}e^{a^{\prime}\Lambda_{1}}<\infty$ for some $a^{\prime}>0$. Using
this observation and the fact that the sequence of probabilities
$\\{{\bf{P}}(\tau_{1}=r)\\}_{r\geq 0}$ is longtailed and subexponential (see
(43) and [11]) we show that

${\bf{E}}\bigl{(}Y_{1}{\bf{P}}(d^{*}_{Y_{1}}=r)\bigl{)}\approx\bigl{(}{\bf{E}}(Y_{1}\Lambda_{1})\bigr{)}{\bf{P}}(\tau_{1}=r).$
(45)

The proof of (45) is much the same as that of Theorem 4.30 in [11]. Now, we
invoke in (45) the identity
${\bf{E}}(Y_{1}\Lambda_{1})={\bf{E}}(Y_{1}\lambda_{1})=a_{1}b_{2}\beta^{1/2}$
and (43), and obtain

${\bf{E}}\bigl{(}Y_{1}{\bf{P}}(d^{*}_{Y_{1}}=r)\bigl{)}\approx
c^{*}_{2}r^{1-\varkappa},\qquad{\text{where}}\qquad
c^{*}_{2}=cb_{1}^{\varkappa-2}b_{2}\beta^{(3-\varkappa)/2}.$

Hence we have $q_{r}\approx c^{*}_{2}r^{1-\varkappa}$ and
${\bf{P}}(\Lambda_{0}=r)\approx c^{*}_{1}r^{-\varkappa}$, see (42).

Now we are ready to prove (11). Let
$\varepsilon=\ln(k_{1}\wedge(k_{2}-k_{1}))$ for $k_{2}-k_{1}\to+\infty$, and
$\varepsilon=\ln k_{1}$ otherwise. Split
$S_{[0,k_{1}]}=S_{A_{1}}+S_{A_{2}}+S_{A_{3}}$, where

$A_{1}=[0,k_{1}/2],\qquad A_{2}=(k_{1}/2,k_{1}-\varepsilon],\qquad
A_{3}=(k_{1}-\varepsilon,k_{1}].$

In the remaining part of the proof we shall show that $S_{A_{1}},S_{A_{2}}$
are negligibly small compared to $S_{A_{3}}$ and determine the first order
asymptotics of $S_{A_{3}}$ as $k_{1},k_{2}\to+\infty$. We have for some
${\bar{c}}>0$ (independent of $k_{1},k_{2}$)

$\displaystyle S_{A_{1}}\leq{\bar{c}}\sum_{i\in
A_{1}}\frac{1}{(k_{1}-i)^{\varkappa-1}}\frac{1}{(k_{2}-i)^{\varkappa-1}}\frac{1}{(1+i)^{\varkappa-2}}=O\Bigl{(}k_{1}^{4-2\varkappa}k_{2}^{1-\varkappa}(1+\Delta)\Bigr{)}.$

Here $\Delta=\ln n$ for $\varkappa=3$ and $\Delta=0$ otherwise. Furthermore,
for $k_{2}-k_{1}$ bounded we have

$S_{A_{2}}\leq\frac{{\bar{c}}}{k_{1}^{\varkappa-2}}\sum_{i\in
A_{2}}\frac{1}{(k_{1}-i)^{2\varkappa-2}}=O\Bigl{(}\varepsilon^{3-2\varkappa}k_{1}^{2-\varkappa}\Bigr{)}=o(k_{1}^{2-\varkappa}).$

For $k_{2}-k_{1}\to+\infty$ we have

$S_{A_{2}}\leq\frac{{\bar{c}}}{k_{1}^{\varkappa-2}}\sum_{i\in
A_{2}}\frac{1}{(k_{1}-i)^{\varkappa-1}}\frac{1}{(k_{2}-i)^{\varkappa-1}}\leq\frac{{\bar{c}}}{k_{1}^{\varkappa-2}(k_{2}-k_{1})^{\varkappa-1}}\sum_{i\in
A_{2}}\frac{1}{(k_{1}-i)^{\varkappa-1}}.$

Since $\sum_{i\in
A_{2}}\frac{1}{(k_{1}-i)^{\varkappa-1}}=O(\varepsilon^{2-\varkappa})=o(1)$ we
obtain
$S_{A_{2}}=o\bigl{(}k_{1}^{2-\varkappa}(k_{2}-k_{1})^{1-\varkappa}\bigr{)}$.

Finally, using the approximation $(i+1)(i+2){\bf{P}}(\Lambda_{0}=i+2)\approx
c^{*}_{1}k_{1}^{2-\varkappa}$ uniformly in $i\in A_{3}$ we obtain for
$k_{2}-k_{1}\to+\infty$

$S_{A_{3}}=\frac{c^{*}_{1}(1+o(1))}{k_{1}^{\varkappa-2}}\sum_{i\in
A_{3}}q_{k_{1}-i}q_{k_{2}-i}\approx\frac{c^{*}_{1}}{k_{1}^{\varkappa-2}}\frac{c^{*}_{2}}{(k_{2}-k_{1})^{\varkappa-1}}\sum_{i\in
A_{3}}q_{k_{1}-i}\approx\frac{c^{*}_{1}c^{*}_{2}}{k_{1}^{\varkappa-2}(k_{2}-k_{1})^{\varkappa-1}}.$

Similarly, in the case where $k_{2}-k_{1}=k$ for some fixed $k$ we have

$S_{A_{3}}=\frac{c^{*}_{1}(1+o(1))}{k_{1}^{\varkappa-2}}\sum_{i\in
A_{3}}q_{k_{1}-i}q_{k_{2}-i}\approx\frac{c^{*}_{1}c^{*}_{3,k}}{k_{1}^{\varkappa-2}},\quad{\text{where}}\quad
c^{*}_{3,k}=\sum_{i\geq 0}q_{i}q_{k+i}.$

Let us prove (iii). We observe that $\Lambda_{0}$ has the Poisson distribution
with (non-random) mean $\lambda_{0}$. Using the identity
$(r+1)(r+2){\bf{P}}(\Lambda_{0}=r+2)=\lambda_{0}^{2}{\bf{P}}(\Lambda_{0}=r)$
we write

$\displaystyle
S_{[0,k_{1}]}=\lambda_{0}^{2}\sum_{r=0}^{k_{1}}{\bf{P}}(\Lambda_{0}=r)q_{k_{1}-r}q_{k_{2}-r}=\lambda_{0}^{2}{\bf{E}}\bigl{(}q_{k_{1}-\Lambda_{0}}q_{k_{2}-\Lambda_{0}}\bigr{)}=\lambda_{0}^{2}(J_{1}+J_{2}),$
$\displaystyle
J_{1}={\bf{E}}\bigl{(}q_{k_{1}-\Lambda_{0}}q_{k_{2}-\Lambda_{0}}\bigr{)}{\mathbb{I}}_{\\{\Lambda_{0}<\sqrt{k}_{1}\\}},\qquad
J_{2}={\bf{E}}\bigl{(}q_{k_{1}-\Lambda_{0}}q_{k_{2}-\Lambda_{0}}\bigr{)}{\mathbb{I}}_{\\{\sqrt{k_{1}}\leq\Lambda_{0}\leq
k_{1}\\}}.$

Next, combining the fast decay of Poisson tail probability
${\bf{P}}(\Lambda_{0}>t)$ as $t\to+\infty$ with the relation, which is shown
below,

$q_{r}\approx c_{0}r^{1-\varkappa},\qquad c_{0}=c(x^{2}b_{1})^{\varkappa-2},$
(46)

we estimate $J_{1}=(1+o(1))c_{0}^{2}(k_{1}k_{2})^{1-\varkappa}$ and
$J_{2}=o((k_{1}k_{2})^{1-\varkappa}$. We obtain that
$S_{[0,1]}=(1+o(1))\lambda_{0}^{2}J_{1}$. Now the identity
$p_{\beta}(k_{1},k_{2})=\beta b_{1}^{-4}x^{-2}S_{[0,k_{1}]}$ completes the
proof of (11).

Now, we prove (46). Since $\tau_{1}$ has Poisson distribution with mean
$\lambda_{0}=xb_{1}\beta^{-1/2}$, we obtain

${\bf{P}}(d^{*}_{y}=k)={\bf{E}}\Bigl{(}e^{-\lambda_{0}\Lambda_{1}}\frac{(\lambda_{0}\Lambda_{1})^{k}}{k!}\Bigl{|}Y_{1}=y\Bigr{)}=\sum_{i\geq
0}e^{-\lambda_{0}i}\frac{(\lambda_{0}i)^{k}}{k!}e^{-By}\frac{(By)^{i}}{i!}.$

Here we denote $B=x\beta^{1/2}$. After we write the product
$y{\bf{P}}(d^{*}_{y}=k)$ in the form

$\sum_{i\geq
0}e^{-\lambda_{0}i}\frac{(\lambda_{0}i)^{k}}{k!}e^{-By}\frac{(By)^{i+1}}{(i+1)!}\frac{i+1}{B}={\bf{E}}\Bigl{(}e^{-\lambda_{0}(\Lambda_{1}-1)}\frac{(\lambda_{0}(\Lambda_{1}-1))^{k}}{k!}\frac{\Lambda_{1}}{B}{\mathbb{I}}_{\\{\Lambda_{1}\geq
1\\}}\Bigr{|}Y_{1}=y\Bigr{)}$

we obtain the following expression for the expectation
$q_{k}={\bf{E}}\bigl{(}Y_{1}{\bf{P}}(d^{*}_{Y_{1}}=k)\bigr{)}$

$q_{k}=\frac{{\bf{P}}(\Lambda_{1}\geq 1)}{B}(I_{1,k}+I_{2,k}),\quad
I_{1,k}={\bf{E}}\Bigl{(}e^{-\lambda_{0}Z}\frac{(\lambda_{0}Z)^{k}}{k!}\Bigr{)},\quad
I_{2,k}={\bf{E}}\Bigl{(}Ze^{-\lambda_{0}Z}\frac{(\lambda_{0}Z)^{k}}{k!}\Bigr{)}.$
(47)

Here $Z$ denotes a random variable with the distribution

${\bf{P}}(Z=r)={\bf{P}}(\Lambda_{1}=r+1)/{\bf{P}}(\Lambda_{1}\geq 1),\qquad
r=0,1,\dots.$

We note that

${\bf{P}}(Z=r)\approx c^{\prime}r^{-\varkappa},\qquad{\text{ where}}\qquad
c^{\prime}=cB^{\varkappa-1}/{\bf{P}}(\Lambda_{1}\geq 1).$ (48)

Indeed, (48) follows from the relation ${\bf{P}}(\Lambda_{1}=r)\approx
cB^{\varkappa-1}r^{-\varkappa}$, which is a simply consequence of the property
${\cal A}_{c,\varkappa}$ of the distribution of $Y_{1}$, see Lemma 4. Next, we
show that

$I_{1,k}\approx c^{\prime}\lambda_{0}^{\varkappa-1}k^{-\varkappa},\qquad
I_{2,k}\approx c^{\prime}\lambda_{0}^{\varkappa-2}k^{1-\varkappa}.$ (49)

The first relation follows from (48), by Lemma 4. The second relation follows
from the first one via the simple identity
$I_{2,k}=(k+1)\lambda_{0}^{-1}I_{1,k+1}$. Finally invoking (49) in (47) we
obtain (46).

∎

##  3 Appendix A

Here we prove the bounds $\Delta_{1}=o(1)$ and $\Delta_{3}=o(1)$, see (32) and
(41) above. In the proof we apply and further extend the approach of [4]. An
important tool used below is the following inequality referred to as LeCam’s
lemma, see e.g., [22].

######  Lemma 1.

Let $S={\mathbb{I}}_{1}+{\mathbb{I}}_{2}+\dots+{\mathbb{I}}_{n}$ be the sum of
independent random indicators with probabilities
${\bf{P}}({\mathbb{I}}_{i}=1)=p_{i}$. Let $\Lambda$ be Poisson random variable
with mean $p_{1}+\dots+p_{n}$. The total variation distance between the
distributions $P_{S}$ of $P_{\Lambda}$ of $S$ and $\Lambda$

$\sup_{A\subset\\{0,1,2\dots\\}}|{\bf{P}}(S\in A)-{\bf{P}}(\Lambda\in
A)|=\frac{1}{2}\sum_{k\geq
0}|{\bf{P}}(S=k)-{\bf{P}}(\Lambda=k)|\leq\sum_{i}p_{i}^{2}.$ (50)

######  Lemma 2.

Assume that conditions of part (i) of Theorem 2 are satisfied. Then for any
realized values $Y_{1},Y_{2},X_{1}$ and any integers $r,r_{1},r_{2}\geq 0$ we
have

${\bf{P}}^{\star}({\cal U}^{*}_{r,r_{1},r_{2}})-{\bf{P}}^{\star}({\cal
U}^{**}_{r,r_{1},r_{2}})=o(1).$ (51)

###### Proof of Lemma 2.

Denote

${\bf
L}^{(0)}=(L_{0}^{(0)},L_{1}^{(0)},L_{2}^{(0)}):=(L_{0},L_{1},L_{2}),\qquad{\bf
L}^{(4)}=(L_{0}^{(4)},L_{1}^{(4)},L_{2}^{(4)}):=(\Lambda_{0},d^{*}_{Y_{1}},d^{*}_{Y_{2}}).$

In the proof we construct random vectors ${\bf
L}^{(h)}=(L_{0}^{(h)},L_{1}^{(h)},L_{2}^{(h)})$, $h=1,2,3$, defined on the
same probability space as $Y_{1},Y_{2},X_{1}$ such that for any realized
values $Y_{1},Y_{2},X_{1}$ we have

$\displaystyle d^{\star}_{TV}({\bf L}^{(h)},{\bf L}^{(h+1)})=o(1),\qquad
h=0,1,$ (52) $\displaystyle{\bf{P}}^{\star}\bigl{(}{\bf
L}^{(h)}=(r,r_{1},r_{2})\bigr{)}-{\bf{P}}^{\star}\bigl{(}{\bf
L}^{(h+1)}=(r,r_{1},r_{2})\bigr{)}=o(1),\qquad h=2,3,$ (53)

for any integers $r,r_{1},r_{2}\geq 0$. We note that (52), (53) imply (51).

Let us define random vectors ${\bf L}^{(h)}$, $h=1,2,3$. Given $X,Y$, let
$\\{\eta_{ki}\\}_{i=2}^{m}$, $k=1,2$ and $\\{\xi_{hi}\\}_{i=1}^{m}$, $h=2,3$,
be sequences of Poisson random variables which are (conditionally, given
$X,Y$) independent within each sequence and have mean values

${\tilde{\bf{E}}}\eta_{ki}=\lambda_{ki},\qquad{\tilde{\bf{E}}}\xi_{2i}=\sum_{3\leq
j\leq
n}\lambda_{ij},{\tilde{\bf{E}}}\xi_{3i}=\frac{b_{1}}{\sqrt{\beta}}X_{i}.$

In addition, we assume that (conditionally, given $X,Y$) the sequences
$\\{\eta_{ki}\\}_{i=2}^{m}$, $k=1,2$, are independent and they are independent
of the sequences $\\{\xi_{hi}\\}_{i=1}^{m}$, $h=2,3,4$. Denote for $k=1,2$ and
$h=2,3$

$L_{0}^{(1)}=u_{1},\qquad L_{0}^{(h)}=\xi_{h1},\qquad L_{k}^{(1)}=\sum_{2\leq
i\leq m}\eta_{ki}u_{i},\qquad L_{k}^{(h)}=\sum_{2\leq i\leq
m}\eta_{ki}\xi_{hi}.$

Let us prove (52) for $h=0$. In the proof we use the following simple
inequalities. Let ${\tilde{d}}^{*}_{TV}(\zeta,\theta)$ denote the total
variation distance between the conditional distributions of random
variables/vectors $\zeta$ and $\theta$ given $X,Y,u_{1},\dots,u_{m}$. Then we
have

${\tilde{d}}_{TV}(\zeta,\theta)\leq{\tilde{\bf{E}}}{\tilde{d}}^{*}_{TV}(\zeta,\theta),\qquad
d^{\star}_{TV}(\zeta,\theta)\leq{\bf{E}}^{\star}{\tilde{d}}_{TV}(\zeta,\theta)\leq{\bf{E}}^{\star}{\tilde{d}}^{*}_{TV}(\zeta,\theta).$
(54)

Introduce random variables for $k=1,2$ and $t=1,\dots,m$

$L_{k}^{[t]}=\sum_{2\leq i\leq t}{\mathbb{I}}_{ik}u_{i}+\sum_{t+1\leq i\leq
m}\eta_{ki}u_{i}.$

Note that $L_{k}^{[1]}=L_{k}^{(1)}$ and $L_{k}^{[m]}=L_{k}^{(0)}$. We have, by
the triangle inequality,

${\tilde{d}}^{*}_{TV}(L_{k}^{[1]},L_{k}^{[m]})\leq\sum_{2\leq t\leq
m}{\tilde{d}}^{*}_{TV}(L_{k}^{[t-1]},L_{k}^{[t]})\leq\sum_{t=2}^{m}\lambda^{2}_{tk}.$

Here we estimated each summand

${\tilde{d}}^{*}_{TV}(L_{k}^{[t-1]},L_{k}^{[t]})\leq{\tilde{d}}^{*}_{TV}({\mathbb{I}}_{tk},\eta_{kt})\leq\lambda^{2}_{tk}.$
(55)

In the first inequality of (55) we use the fact that $L_{k}^{[t-1]}$ and
$L_{k}^{[t]}$ only differ in the $t$-th summand. The second inequality is
trivial for $\lambda_{tk}\geq 1$ and it follows by LeCam’s inequality, see
Lemma 1, for $\lambda_{tk}<1$.

Next, we use the fact that given $X,Y,u_{1},\dots,u_{m}$ the random vectors
${\bf L}^{(0)}$ and ${\bf L}^{(1)}$ have conditionally independent marginals.
In particular, we can apply the triangle inequality

${\tilde{d}}^{*}_{TV}({\bf L}^{(0)},{\bf L}^{(1)})\leq\sum_{0\leq k\leq
2}{\tilde{d}}^{*}_{TV}(L_{k}^{(0)},L_{k}^{(1)})\leq\sum_{2\leq t\leq
m}(\lambda_{t1}^{2}+\lambda_{t2}^{2}).$

In the last step we use ${\tilde{d}}^{*}_{TV}(L_{0}^{(0)},L_{0}^{(1)})=0$.
Finally, (54) implies

$d^{\star}_{TV}({\bf L}^{(0)},{\bf L}^{(1)})\leq{\bf{E}}^{\star}\sum_{2\leq
t\leq
m}(\lambda_{t1}^{2}+\lambda_{t2}^{2})=\frac{2}{n}\frac{m-2}{m}a_{2}(Y_{1}^{2}+Y_{2}^{2})=o(1).$

Let us prove (52) for $h=1$. We note that conditionally, given $X,Y$, the
random variable $L_{0}^{(1)}$ is independent of $(L_{1}^{(1)},L_{2}^{(1)})$,
and $L_{0}^{(2)}$ is independent of $(L_{1}^{(2)},L_{2}^{(2)})$. Hence, we
have, by triangle inequality,

${\tilde{d}}_{TV}\bigl{(}{\bf L}^{(1)},{\bf
L}^{(2)}\bigr{)}\leq{\tilde{d}}_{TV}(L_{0}^{(1)},L_{0}^{(2)})+{\tilde{d}}_{TV}\bigl{(}(L_{1}^{(1)},L_{2}^{(1)}),(L_{1}^{(2)},L_{2}^{(2)})\bigr{)}=:Z_{1}+Z_{2}.$

We shall show that ${\bf{E}}^{\star}Z_{i}=o(1)$, $i=1,2$. These bounds
combined with the second inequality of (54) imply $d^{\star}_{TV}\bigl{(}{\bf
L}^{(1)},{\bf L}^{(2)}\bigr{)}=o(1)$.

We firstly estimate $Z_{1}$. We have

$Z_{1}={\tilde{d}}_{TV}(u_{1},\xi_{21})\leq\sum_{3\leq j\leq
n}\lambda^{2}_{1j}=\beta_{n}^{-1}X_{1}^{2}{\hat{b}}_{2}n^{-1}.$ (56)

Indeed, for $\max_{j}\lambda_{1j}<1$ this inequality follows by Lemma 1.
Otherwise the inequality is trivial, since the total variation distance is
always less than or equal to $1$. Next, we use the fact that
${\bf{E}}Y_{1}<\infty$ implies ${\hat{b}}_{2}n^{-1}=o_{P}(1)$. We obtain
$Z_{1}=o_{P^{\star}}(1)$. This bound together with the inequality $Z_{1}\leq
1$ implies ${\bf{E}}^{\star}Z_{1}=o(1)$.

We secondly estimate $Z_{2}$. Introduce random variables for $k=1,2$ and
$t=1,\dots,m$

$L_{k}^{\\{t\\}}=\sum_{2\leq i\leq t}\eta_{ki}u_{i}+\sum_{t+1\leq i\leq
m}\eta_{ki}\xi_{2i}.$

Note that $L_{k}^{\\{1\\}}=L_{k}^{(2)}$ and $L_{k}^{\\{m\\}}=L_{k}^{(1)}$. We
apply triangle inequality

${\tilde{d}}_{TV}\bigl{(}(L_{1}^{\\{m\\}},L_{2}^{\\{m\\}}),(L_{1}^{\\{1\\}},L_{2}^{\\{1\\}})\bigr{)}\leq\sum_{t=2}^{m}{\tilde{d}}_{TV}\bigl{(}(L_{1}^{\\{t-1\\}},L_{2}^{\\{t-1\\}}),(L_{1}^{\\{t\\}},L_{2}^{\\{t\\}})\bigr{)}$
(57)

and estimate each summand as follows

$\displaystyle{\tilde{d}}_{TV}\bigl{(}(L_{1}^{\\{t-1\\}},L_{2}^{\\{t-1\\}}),(L_{1}^{\\{t\\}},L_{2}^{\\{t\\}})\bigr{)}$
$\displaystyle\leq$
$\displaystyle{\tilde{d}}_{TV}\bigl{(}(u_{t}\eta_{t1},u_{t}\eta_{t2}),(\xi_{2t}\eta_{t1},\xi_{2t}\eta_{t2})\bigr{)}$
(58) $\displaystyle\leq$
$\displaystyle{\tilde{\bf{P}}}\bigl{(}(\eta_{t1},\eta_{t2})\not=(0,0)\bigr{)}{\tilde{d}}_{TV}(u_{t},\xi_{2t})$
(59) $\displaystyle\leq$
$\displaystyle(\lambda_{t1}+\lambda_{t2})\min\bigl{\\{}1,\,\beta_{n}^{-1}X_{t}^{2}{\hat{b}}_{2}n^{-1}\bigr{\\}}.$
(60)

In (58) we use the fact that $L_{k}^{\\{t-1\\}}$ and $L_{k}^{\\{t\\}}$ only
differ in the $t$-th summand. In (59) we first estimate the total variation
distance between conditional distributions of
$(u_{t}\eta_{t1},u_{t}\eta_{t2})$ and $(\xi_{2t}\eta_{t1},\xi_{2t}\eta_{t2})$
given $\eta_{t1},\eta_{t2},X,Y$ from above by
${\mathbb{I}}_{\\{(\eta_{t1},\eta_{t2})\not=(0,0)\\}}{\tilde{d}}_{TV}(u_{t},\xi_{2t})$
and then take the expected value ${\tilde{\bf{E}}}$. In (60) we estimate
${\tilde{\bf{P}}}\bigl{(}(\eta_{t1},\eta_{t2})\not=(0,0)\bigr{)}\leq\lambda_{t1}+\lambda_{t2}$.
This bound is trivial for $\lambda_{t1}+\lambda_{t2}\geq 1$. Otherwise it
follows from the inequalities

${\tilde{\bf{P}}}\bigl{(}(\eta_{t1},\eta_{t2})\not=(0,0)\bigr{)}\leq{\tilde{\bf{P}}}(\eta_{t1}\not=0)+{\tilde{\bf{P}}}(\eta_{t2}\not=0)=e^{0}-e^{-\lambda_{t1}}+e^{0}-e^{-\lambda_{t2}}\leq\lambda_{t1}+\lambda_{t2}.$

In(60) we invoke the inequality
${\tilde{d}}_{TV}(u_{t},\xi_{2t})\leq\min\bigl{\\{}1,\,\beta_{n}^{-1}X_{t}^{2}{\hat{b}}_{2}n^{-1}\bigr{\\}}$,
cf. (56) above.

Next, using the identities $L_{k}^{\\{1\\}}=L_{k}^{(2)}$ and
$L_{k}^{\\{m\\}}=L_{k}^{(1)}$ we obtain from (57), (60) that

$\displaystyle
Z_{2}\leq\sum_{t=2}^{m}(\lambda_{t1}+\lambda_{t2})\min\bigl{\\{}1,\,\frac{X_{t}^{2}{\hat{b}}_{2}}{\beta_{n}n}\bigr{\\}}=(Y_{1}+Y_{2})\beta_{n}^{1/2}\sum_{t=2}^{m}\frac{X_{t}}{m}\bigl{\\{}1,\,\frac{X_{t}^{2}{\hat{b}}_{2}}{\beta_{n}n}\bigr{\\}}.$
(61)

Finally, we have,

${\bf{E}}^{\star}Z_{2}=\beta^{1/2}(Y_{1}+Y_{2}){\bf{E}}^{\star}X_{2}\bigl{\\{}1,\,X_{2}^{2}{\hat{b}}_{2}\beta_{n}^{-1}n^{-1}\bigr{\\}}=\beta^{1/2}(Y_{1}+Y_{2}){\bf{E}}X_{2}\bigl{\\{}1,\,X_{2}^{2}{\hat{b}}_{2}\beta_{n}^{-1}n^{-1}\bigr{\\}}=o(1),$

since ${\hat{b}}_{2}$ is independent of $X_{2}$ and ${\bf{E}}X_{2}<\infty$,
and ${\hat{b}}_{2}n^{-1}=o_{P}(1)$.

Let us prove (53) for $h=2$. Given $X,Y$, let $\\{\xi_{i}\\}_{i=1}^{m}$,
$\\{\Delta^{\prime}_{i}\\}_{i=1}^{m}$,
$\\{\Delta^{\prime\prime}_{i}\\}_{i=1}^{m}$ be independent Poisson random
variables, which are independent of $\\{\eta_{i1}\\}_{i=2}^{m}$,
$\\{\eta_{i2}\\}_{i=2}^{m}$, and have mean values

${\tilde{\bf{E}}}\xi_{i}=bX_{i},\qquad{\tilde{\bf{E}}}\Delta^{\prime}_{i}=\delta^{\prime}X_{i},\qquad{\tilde{\bf{E}}}\Delta^{\prime\prime}_{i}=\delta^{\prime\prime}X_{i},\qquad
1\leq i\leq m.$ (62)

Here $\delta^{\prime}={\hat{b}}_{1}\beta_{n}^{-1/2}-b$ and
$\delta^{\prime}=b_{1}\beta^{-1/2}-b$, and
$b=\min\\{{\hat{b}}_{1}\beta_{n}^{-1/2},b_{1}\beta^{-1/2}\\}$. Define the
random vectors ${\bar{\bf L}}^{(2)}$ and ${\bar{\bf L}}^{(3)}$ in the same way
as ${\bf L}^{(2)}$ and ${\bf L}^{(3)}$ above, but with $\xi_{2i}$ and
$\xi_{3i}$ replaced by ${\bar{\xi}}_{2i}=\xi_{i}+\Delta^{\prime}_{i}$ and
${\bar{\xi}}_{3i}=\xi_{i}+\Delta^{\prime\prime}_{i}$ respectively. We note
that given $Y_{1},Y_{2},X_{1}$ the random vector ${\bar{\bf L}}^{(2)}$ has the
same conditional distribution as ${\bf L}^{(2)}$, and ${\bar{\bf L}}^{(3)}$
has the same conditional distribution as ${\bf L}^{(3)}$. Hence in order to
prove (53) for $h=2$ it suffices to show that for any realized values
$Y_{1},Y_{2},X_{1}$ we have

${\bf{P}}^{\star}(|{\bar{L}}_{k}^{(2)}-{\bar{L}}_{k}^{(3)}|\geq 1)=o(1),\qquad
k=0,1,2.$ (63)

Here ${\bar{L}}_{k}^{(i)}$ denotes the $k$-th coordinate of the vector
${\bar{\bf L}}^{(i)}$. We derive (63) from the bounds
${\tilde{\bf{E}}}|{\bar{L}}_{k}^{(2)}-{\bar{L}}_{k}^{(3)}|=o_{P^{\star}}(1)$
using (30). To prove these bounds we calculate

$\displaystyle{\tilde{\bf{E}}}|{\bar{L}}_{0}^{(2)}-{\bar{L}}_{0}^{(3)}|=(\delta^{\prime}+\delta^{\prime\prime})X_{1},$
$\displaystyle{\tilde{\bf{E}}}|{\bar{L}}_{k}^{(2)}-{\bar{L}}_{k}^{(3)}|=\sum_{2\leq
i\leq
m}{\tilde{\bf{E}}}\eta_{ki}(\delta^{\prime}+\delta^{\prime\prime})X_{i}=\beta_{n}^{1/2}Y_{k}{\hat{a}}_{2}(\delta^{\prime}+\delta^{\prime\prime}),\qquad
k=1,2$

and use the fact that
$\delta^{\prime}+\delta^{\prime\prime}=|{\hat{b}}_{1}\beta_{n}^{-1/2}-b_{1}\beta^{-1/2}|=o_{P}(1)$.
Indeed, we have $\beta_{n}\to\beta$ and, by the law of large numbers,
${\hat{b}}_{1}-b_{1}=o_{P}(1)$.

Let us prove (53) for $h=3$. We note that $L_{0}^{(3)}$ has the same
distribution as $\Lambda_{0}$. Furthermore, given $Y_{1},Y_{2},X_{1}$, the
random variable $L_{0}^{(3)}$ is conditionally independent of
$(L_{1}^{(3)},L_{2}^{(3)})$. Hence, it suffices to show that
${\bf{P}}^{*}((L_{1}^{(3)},L_{2}^{(3)})=(r_{1},r_{2}))-{\bf{P}}^{*}((L_{1}^{(4)},L_{2}^{(4)})=(r_{1},r_{2}))=o(1)$
for any integers $r_{1},r_{2}\geq 0$. For this purpose we prove the
convergence of the conditional characteristic functions

${\bf{E}}^{\star}e^{{\bf i}tL_{1}^{(3)}+{\bf
i}sL_{2}^{(3)}}\to{\bf{E}}^{\star}e^{{\bf i}tL_{1}^{(4)}+{\bf
i}sL_{2}^{(4)}},\qquad\forall s,t\in(-\infty,+\infty).$ (64)

Here ${\bf i}$ denotes the imaginary unit.

In the proof of (64) we exploit the compound Poisson structure of the
distributions of $L_{k}^{(h)}$, $h=2,3$, $k=1,2$. Using the fact that, given
$Y_{1},Y_{2},X_{1}$, the marginals of $(L_{1}^{(4)},L_{2}^{(4)})$ are
conditionally independent and have compound Poisson distributions, we write
the characteristics function in the form

${\bf{E}}^{\star}e^{{\bf i}tL_{1}^{(4)}+{\bf
i}sL_{2}^{(4)}}=\bigl{(}{\bf{E}}^{\star}e^{{\bf
i}tL_{1}^{(4)}}\bigr{)}\cdot\bigl{(}{\bf{E}}^{\star}e^{{\bf
i}sL_{2}^{(4)}}\bigr{)}=e^{(f_{\tau}(t)-1)\lambda_{1}}\cdot
e^{(f_{\tau}(s)-1)\lambda_{2}}.=:f_{1}(t)\cdot f_{2}(s).$ (65)

Here $f_{\tau}(t)={\bf{E}}e^{it\tau}$ denotes the characteristic function of
$\tau$. Similarly, using the fact that given $X,Y,\xi_{32},\dots,\xi_{3m}$ the
marginals of $(L_{1}^{(3)},L_{2}^{(3)})$ are conditionally independent and
have compound Poisson distributions, we write the conditional characteristics
function in the form

${\hat{\bf{E}}}e^{{\bf i}tL_{1}^{(3)}+{\bf
i}sL_{2}^{(3)}}=\bigl{(}{\hat{\bf{E}}}e^{{\bf
i}tL_{1}^{(3)}}\bigr{)}\cdot\bigl{(}{\hat{\bf{E}}}e^{{\bf
i}sL_{2}^{(3)}}\bigr{)}=e^{({\hat{f}}_{\tau}(t)-1){\hat{\lambda}}_{1}}\cdot
e^{({\hat{f}}_{\tau}(s)-1){\hat{\lambda}}_{2}}=:g_{1}(t)\cdot g_{2}(s).$ (66)

Here ${\hat{\bf{E}}}$ denotes the conditional expectation given
$X,Y,\xi_{32},\dots,\xi_{3m}$. Furthermore, we denote
${\hat{\lambda}}_{k}=\sum_{2\leq j\leq m}\lambda_{jk}$ and

${\hat{f}}_{\tau}(t)=\sum_{r\geq
0}e^{itr}{\hat{p}}_{r},\qquad{\text{where}}\qquad{\hat{p}}_{r}={\hat{\lambda}}_{1}^{-1}\sum_{2\leq
j\leq m}\lambda_{j1}{\mathbb{I}}_{\\{\xi_{3j}=r\\}}.$

We observe that ${\hat{\lambda}}_{k}=Y_{k}{\hat{a}}_{1}\sqrt{\beta_{n}}$ and
each ratio $\lambda_{jk}/{\hat{\lambda}}_{k}=X_{j}/{\hat{a}}_{1}$ does not
depend on $k=1,2$.

Finally, using (65), (66) we write

${\bf{E}}^{\star}e^{{\bf i}tL_{1}^{(3)}+{\bf
i}sL_{2}^{(3)}}-{\bf{E}}^{\star}e^{{\bf i}tL_{1}^{(4)}+{\bf
i}sL_{2}^{(4)}}={\bf{E}}^{\star}\bigl{(}g_{1}(t)-f_{1}(t)\bigr{)}g_{2}(s)+{\bf{E}}^{\star}\bigl{(}g_{2}(s)-f_{2}(s)\bigr{)}f_{1}(t)$

and invoke the bounds
${\bf{E}}^{\star}\bigl{(}g_{1}(t)-f_{1}(t)\bigr{)}g_{2}(s)=o(1)$ and
${\bf{E}}^{\star}\bigl{(}g_{2}(s)-f_{2}(s)\bigr{)}f_{1}(t)=o(1)$, which are
obtained in the same way as relation (22) in [4]. We note that the proof of
(22) in [4] uses the moment conditions ${\bf{E}}X_{1}^{2}<\infty$,
${\bf{E}}Y_{1}<\infty$ that are assumed to hold in the statement of our
Theorem 2. ∎

######  Lemma 3.

Assume that conditions of part (ii) of Theorem 2 are satisfied. Then for any
realized values $Y_{1},Y_{2},X_{1}$ and any integers $k_{1},k_{2}\geq 0$ we
have

${\bf{P}}^{\star}(L_{1}=k_{1},L_{2}=k_{2})-{\bf{P}}^{\star}({\cal
U}^{***}_{k_{1},k_{2}})=o(1).$ (67)

###### Proof of Lemma 3.

Before the proof we introduce some notation. Let $\varepsilon>0$. For $2\leq
i\leq m$ denote

${\mathbb{I}}^{\prime}_{i}={\mathbb{I}}^{\prime}_{i}(\varepsilon)={\mathbb{I}}_{\\{X_{i}\beta_{n}^{-1/2}b_{1}<\varepsilon\\}},\quad\
\gamma_{i}=X_{i}\beta_{n}^{-1/2}b_{1}{\mathbb{I}}^{\prime}_{i}\quad\
{\text{and}}\quad\ \theta_{k}=\sum_{2\leq i\leq m}\lambda_{ik}\gamma_{i},\quad
k=1,2.$

Given $X,Y$, let ${\tilde{\mathbb{I}}}_{2},\dots,{\tilde{\mathbb{I}}}_{m}$ be
independent Bernoulli random variables with success probabilities

${\tilde{\bf{P}}}({\tilde{\mathbb{I}}}_{i}=1)=1-{\tilde{\bf{P}}}({\tilde{\mathbb{I}}}_{i}=0)=\gamma_{i},$

and let ${\bar{\xi}}_{hi}$, $2\leq i\leq m$, $h=1,2$, be independent Poisson
random variables with mean values

${\tilde{\bf{E}}}{\bar{\xi}}_{1i}=\sum_{3\leq j\leq
n}\lambda_{ij},\qquad{\tilde{\bf{E}}}{\bar{\xi}}_{2i}=\frac{b_{1}}{\sqrt{\beta_{n}}}X_{i}.$

We assume that given $X,Y$ the sequences $\\{{\mathbb{I}}_{i}\\}_{i=2}^{m}$,
$\\{{\tilde{\mathbb{I}}}_{i}\\}_{i=2}^{m}$, and
$\\{{\bar{\xi}}_{hi}\\}_{i=2}^{m}$, $h=1,2$ are independent. Next, we
introduce random vectors ${\bar{\bf
L}}^{(h)}=({\bar{L}}_{1}^{(h)},{\bar{L}}_{2}^{(h)})$, $0\leq h\leq 6$. Denote

${\bar{\bf
L}}^{(0)}=({\bar{L}}_{1}^{(0)},{\bar{L}}_{2}^{(0)}):=(L_{1},L_{2}),\qquad{\bar{\bf
L}}^{(6)}=({\bar{L}}_{1}^{(6)},{\bar{L}}_{2}^{(6)}):=(\Lambda_{3},\Lambda_{4}).$

For $k=1,2$ and $h=1,2$ denote

$\displaystyle{\bar{L}}_{k}^{(h)}=\sum_{2\leq i\leq
m}{\mathbb{I}}_{ik}{\bar{\xi}}_{hi},\qquad{\bar{L}}_{k}^{(3)}=\sum_{2\leq
i\leq
m}{\mathbb{I}}_{ik}{\mathbb{I}}^{\prime}_{i}{\bar{\xi}}_{2i},\qquad{\bar{L}}_{k}^{(4)}=\sum_{2\leq
i\leq m}{\mathbb{I}}_{ik}{\tilde{\mathbb{I}}}_{i}.$

Furthermore, given $X,Y$, let ${\bar{L}}_{1}^{(5)}$ and ${\bar{L}}_{2}^{(5)}$
be independent Poisson random variables with mean values
${\tilde{\bf{E}}}{\bar{L}}_{k}^{(5)}=\theta_{k}$.

We shall show below that for any integers $r_{1},r_{2}\geq 0$ we have

$\displaystyle d^{\star}_{TV}({\bf L}^{(0)},{\bf L}^{(1)})=o(1),$ (68)
$\displaystyle{\bf{P}}^{\star}\bigl{(}{\bar{\bf
L}}^{(1)}=(r_{1},r_{2})\bigr{)}-{\bf{P}}^{\star}\bigl{(}{\bar{\bf
L}}^{(2)}=(r_{1},r_{2})\bigr{)}=o(1),$ (69)
$\displaystyle{\bf{E}}^{\star}|L_{k}^{(2)}-L_{k}^{(3)}|=o(1),\qquad k=1,2,$
(70) $\displaystyle d^{\star}_{TV}({\bf L}^{(3)},{\bf
L}^{(4)})\leq\varepsilon(Y_{1}+Y_{2})a_{2}b_{1},$ (71)
$\displaystyle\bigl{|}{\bf{P}}^{\star}\bigl{(}{\bar{\bf
L}}^{(4)}=(r_{1},r_{2})\bigr{)}-{\bf{P}}^{\star}\bigl{(}{\bar{\bf
L}}^{(6)}=(r_{1},r_{2})\bigr{)}\bigr{|}\leq\varepsilon(Y_{1}+Y_{2})a_{2}b_{1}+o(1).$
(72)

Since $\varepsilon>0$ can be chosen arbitrarily small, relations (68), (69),
(70), (71), and (72) imply (67).

Let us prove (68). Introduce random variables

${\bar{L}}_{k}^{\\{t\\}}=\sum_{2\leq i\leq
t}{\mathbb{I}}_{ik}u_{i}+\sum_{t+1\leq i\leq
m}{\mathbb{I}}_{ik}{\bar{\xi}}_{1i},\qquad t=1,\dots,m,\quad k=1,2.$

Note that ${\bar{L}}_{k}^{\\{1\\}}={\bar{L}}_{k}^{(1)}$ and
${\bar{L}}_{k}^{\\{m\\}}={\bar{L}}_{k}^{(0)}$. We apply triangle inequality

${\tilde{d}}_{TV}\bigl{(}({\bar{L}}_{1}^{\\{m\\}},{\bar{L}}_{2}^{\\{m\\}}),({\bar{L}}_{1}^{\\{1\\}},{\bar{L}}_{2}^{\\{1\\}})\bigr{)}\leq\sum_{t=2}^{m}{\tilde{d}}_{TV}\bigl{(}({\bar{L}}_{1}^{\\{t-1\\}},{\bar{L}}_{2}^{\\{t-1\\}}),({\bar{L}}_{1}^{\\{t\\}},{\bar{L}}_{2}^{\\{t\\}})\bigr{)}$
(73)

and estimate each summand as follows

$\displaystyle{\tilde{d}}_{TV}\bigl{(}({\bar{L}}_{1}^{\\{t-1\\}},{\bar{L}}_{2}^{\\{t-1\\}}),({\bar{L}}_{1}^{\\{t\\}},{\bar{L}}_{2}^{\\{t\\}})\bigr{)}$
$\displaystyle\leq$
$\displaystyle{\tilde{d}}_{TV}\bigl{(}({\mathbb{I}}_{t1}u_{t},{\mathbb{I}}_{t2}u_{t}),({\mathbb{I}}_{t1}{\bar{\xi}}_{1t},{\mathbb{I}}_{t2}{\bar{\xi}}_{1t})\bigr{)}$
(74) $\displaystyle\leq$
$\displaystyle{\tilde{\bf{P}}}\bigl{(}({\mathbb{I}}_{t1},{\mathbb{I}}_{t2})\not=(0,0)\bigr{)}{\tilde{d}}_{TV}(u_{t},{\bar{\xi}}_{1t})$
(75) $\displaystyle\leq$
$\displaystyle(\lambda_{t1}+\lambda_{t2})\beta_{n}^{-1/2}X_{t}({\hat{b}}_{2}n^{-1})^{1/2}.$
(76)

In (74) we use the fact that ${\bar{L}}_{k}^{\\{t-1\\}}$ and
${\bar{L}}_{k}^{\\{t\\}}$ only differ in the $t$-th summand. In (75) we first
estimate the total variation distance between conditional distributions of
$({\mathbb{I}}_{t1}u_{t},{\mathbb{I}}_{t2}u_{t})$ and
$({\mathbb{I}}_{t1}{\bar{\xi}}_{1t},{\mathbb{I}}_{t2}{\bar{\xi}}_{1t})$ given
${\mathbb{I}}_{t1},{\mathbb{I}}_{t2},X,Y$ from above by
${\mathbb{I}}_{\\{(\eta_{t1},\eta_{t2})\not=(0,0)\\}}{\tilde{d}}_{TV}(u_{t},{\bar{\xi}}_{1t})$
and then take the expected value ${\tilde{\bf{E}}}$. In (76) we estimate
${\tilde{\bf{P}}}\bigl{(}({\mathbb{I}}_{t1},{\mathbb{I}}_{t2})\not=(0,0)\bigr{)}\leq\lambda_{t1}+\lambda_{t2}$
and invoke the inequality

${\tilde{d}}_{TV}(u_{t},{\bar{\xi}}_{1t})\leq\min\bigl{\\{}1,\,\beta_{n}^{-1}X_{t}^{2}{\hat{b}}_{2}n^{-1}\bigr{\\}}\leq\bigl{(}\beta_{n}^{-1}X_{t}^{2}{\hat{b}}_{2}n^{-1}\bigr{)}^{1/2},$

cf. (56) above.

Next, using the identities ${\bar{L}}_{k}^{\\{1\\}}={\bar{L}}_{k}^{(1)}$ and
${\bar{L}}_{k}^{\\{m\\}}={\bar{L}}_{k}^{(0)}$ we obtain from (73), (76) that

$\displaystyle{\tilde{d}}_{TV}({\bar{\bf L}}^{(0)},{\bar{\bf
L}}^{(1)})\leq\sum_{t=2}^{m}(\lambda_{t1}+\lambda_{t2})\beta_{n}^{-1/2}X_{t}({\hat{b}}_{2}n^{-1})^{1/2}=(Y_{1}+Y_{2}){\hat{a}}_{2}({\hat{b}}_{2}/n)^{1/2}.$
(77)

Finally, since ${\bf{E}}X_{1}^{2}<\infty$ and ${\bf{E}}Y_{1}<\infty$ imply
${\hat{a}}_{2}=O_{P}(1)$ and ${\hat{b}}_{2}/n=o_{P}(1)$, we conclude that
${\tilde{d}}_{TV}({\bar{\bf L}}^{(0)},{\bar{\bf L}}^{(1)})=o_{P^{\star}}(1)$.
Hence,

$d^{\star}_{TV}({\bar{\bf L}}^{(0)},{\bar{\bf
L}}^{(1)})={\bf{E}}^{\star}{\tilde{d}}_{TV}({\bar{\bf L}}^{(0)},{\bar{\bf
L}}^{(1)})={\bf{E}}^{\star}\min\bigl{\\{}1,{\tilde{d}}_{TV}({\bar{\bf
L}}^{(0)},{\bar{\bf L}}^{(1)})\bigr{\\}}=o(1).$

Let us prove (69). We proceed as in the proof of (53) for $h=2$ above. Denote
$b=\min\\{{\hat{b}}_{1},b_{1}\\}$ and $\delta^{\prime}={\hat{b}}_{1}-b$,
$\delta^{\prime\prime}=b_{1}-b$. Given $X,Y$, let ${\hat{\xi}}_{i}$,
${\hat{\Delta}}^{\prime}_{i}$, ${\hat{\Delta}}^{\prime\prime}_{i}$, $2\leq
i\leq m$, be independent Poisson random variables, which are independent of
${\mathbb{I}}_{2},\dots,{\mathbb{I}}_{m}$, and having mean values

${\tilde{\bf{E}}}{\hat{\xi}}_{i}=\beta_{n}^{-1/2}X_{i}b,\qquad{\tilde{\bf{E}}}{\hat{\Delta}}^{\prime}_{i}=\beta_{n}^{-1/2}X_{i}\delta^{\prime},\qquad{\tilde{\bf{E}}}{\hat{\Delta}}^{\prime\prime}_{i}=\beta_{n}^{-1/2}X_{i}\delta^{\prime\prime}.$

Denote

${\hat{L}}_{k}^{(1)}=\sum_{2\leq i\leq
m}{\mathbb{I}}_{ik}({\hat{\xi}}_{i}+{\hat{\Delta}}^{\prime}_{i}),\qquad{\hat{L}}_{k}^{(2)}=\sum_{2\leq
i\leq
m}{\mathbb{I}}_{ik}({\hat{\xi}}_{i}+{\hat{\Delta}}^{\prime\prime}_{i}),\quad
k=1,2.$

We note that ${\hat{\bf L}}^{(h)}:=({\hat{L}}_{1}^{(h)},{\hat{L}}_{2}^{(h)})$
has the same distribution as ${\bf{\bar{L}}}^{(h)}$, $h=1,2$. Hence it
suffices to show (69) for ${\hat{\bf L}}^{(1)},{\hat{\bf L}}^{(2)}$.
Proceeding as in the proof of (53) for $h=2$ above, we reduce the problem to
showing that

${\tilde{\bf{E}}}|{\hat{L}}_{k}^{(1)}-{\hat{L}}_{k}^{(2)}|=\sum_{2\leq i\leq
m}\lambda_{ik}\beta_{n}^{-1}(\delta^{\prime}+\delta^{\prime\prime})=Y_{k}{\hat{a}}_{2}|{\hat{b}}_{1}-b_{1}|=o(1),\qquad
k=1,2.$

Let us prove (70). We have, for $k=1,2$,

${\tilde{\bf{E}}}|L_{k}^{(2)}-L_{k}^{(3)}|=\sum_{2\leq i\leq
m}(1-{\mathbb{I}}^{\prime}_{i})\bigl{(}{\tilde{\bf{E}}}{\mathbb{I}}_{ik}\bigr{)}\bigl{(}{\tilde{\bf{E}}}{\bar{\xi}}_{2i}\bigr{)}\leq
Y_{k}b_{1}m^{-1}\sum_{2\leq i\leq m}(1-{\mathbb{I}}^{\prime}_{i})X_{i}^{2}.$

Taking ${\bf{E}}^{\star}$ expected value we obtain

${{\bf{E}}}^{\star}|L_{k}^{(2)}-L_{k}^{(3)}|={{\bf{E}}}^{\star}\bigl{(}{\tilde{\bf{E}}}|L_{k}^{(2)}-L_{k}^{(3)}|\bigr{)}\leq
Y_{k}b_{1}{\bf{E}}X_{2}^{2}{\mathbb{I}}_{\\{X_{2}\beta_{n}^{-1/2}b_{1}\geq\varepsilon\\}}=o(1).$

We note that the expectation on right tends to zero since
$\beta_{n}\to+\infty$.

Let us prove (71). We proceed as in the proof of (68) for $h=0$ above. We have

${\tilde{d}}_{TV}({\bf L}^{(3)},{\bf L}^{(4)})\leq\sum_{2\leq i\leq
m}{\mathbb{I}}^{\prime}_{i}{\tilde{\bf{P}}}\bigl{(}{\mathbb{I}}_{i1},{\mathbb{I}}_{i2})\not=(0,0)\bigr{)}{\tilde{d}}_{TV}({\bar{\xi}}_{2i},{\tilde{\mathbb{I}}}_{i}).$

Next, we estimate
${\mathbb{I}}_{i}^{\prime}{\tilde{d}}_{TV}({\bar{\xi}}_{2i},{\tilde{\mathbb{I}}}_{i})\leq\gamma_{i}^{2}$,
by LeCam’s inequality (50), and invoke the inequality
${\tilde{\bf{P}}}\bigl{(}{\mathbb{I}}_{i1},{\mathbb{I}}_{i2})\not=(0,0)\bigr{)}\leq\lambda_{i1}+\lambda_{i2}$.
We obtain

${\tilde{d}}_{TV}({\bf L}^{(3)},{\bf L}^{(4)})\leq\sum_{2\leq i\leq
m}{\mathbb{I}}_{i}^{\prime}(\lambda_{i1}+\lambda_{i2})\gamma_{i}^{2}\leq\varepsilon\sum_{2\leq
i\leq
m}{\mathbb{I}}_{i}^{\prime}(\lambda_{i1}+\lambda_{i2})\gamma_{i}\leq\varepsilon(Y_{1}+Y_{2})b_{1}{\hat{a}}_{2}.$

Here we used inequality $\gamma_{i}^{2}\leq\varepsilon\gamma_{i}$. It follows
now that

$d^{\star}_{TV}({\bf L}^{(3)},{\bf
L}^{(4)})\leq{{\bf{E}}}^{\star}{\tilde{d}}_{TV}({\bf L}^{(3)},{\bf
L}^{(4)})\leq\varepsilon(Y_{1}+Y_{2})b_{1}a_{2}.$

Let us prove (72). For $A\subset W$ denote ${\tilde{S}}(A)=\sum_{w_{i}\in
A}{\tilde{\mathbb{I}}}_{i}$. For $k=1,2$ we write
${\bar{L}}_{k}^{(4)}={\tilde{S}}({\bf A}_{k})$, where ${\bf A}_{k}$ denote the
set attributes from $W\setminus\\{w_{1}\\}$ that are prescribed to $v_{k}$,
i.e., ${\bf A}_{k}=\\{w_{i}\in W\setminus\\{w_{1}\\}:\,w_{i}\to v_{k}\\}$.
Given $r_{1},r_{2}\geq 0$ introduce events ${\cal D}_{k}=\\{{\tilde{S}}({\bf
A}_{k})=r_{k}\\}$, $k=1,2$, and ${\cal D}=\\{|{\bf A}_{1}\cap{\bf A}_{2}|\geq
1\\}$.

We first show that

${\bf{P}}^{\star}({\bar{L}}_{1}^{(4)}=r_{1},{\bar{L}}_{2}^{(4)}=r_{2})={\bf{E}}^{\star}\bigl{(}{\tilde{\bf{P}}}({\bar{L}}_{1}^{(4)}=r_{1}){\tilde{\bf{P}}}({\bar{L}}_{2}^{(4)}=r_{2})\bigr{)}+o(1).$
(78)

It is convenient to write (78) in the form

${\bf{P}}^{\star}({\cal D}_{1}\cap{\cal
D}_{2})={\bf{E}}^{\star}\bigl{(}{\tilde{\bf{P}}}({\cal
D}_{1}){\tilde{\bf{P}}}({\cal D}_{2})\bigr{)}+o(1).$

Now, we observe that given $X,Y$, and ${\bf A}_{1},{\bf A}_{2}$, satisfying
${\bf A}_{1}\cap{\bf A}_{2}=\emptyset$, the random variables ${\tilde{S}}({\bf
A}_{1})$ and ${\tilde{S}}({\bf A}_{2})$ are independent. Hence for ${\bf
A}_{1}\cap{\bf A}_{2}=\emptyset$ we have

${\tilde{\bf{P}}}\bigl{(}{\cal D}_{1}\cap{\cal D}_{2}|{\bf A}_{1},{\bf
A}_{2}\bigr{)}={\tilde{\bf{P}}}({\cal D}_{1}|{\bf
A}_{1}){\tilde{\bf{P}}}({\cal D}_{2}|{\bf A}_{2}).$

This identity implies

${\tilde{\bf{P}}}({\cal D}_{1}\cap{\cal D}_{2}\cap{\bar{\cal
D}})={\tilde{\bf{E}}}\bigl{(}{\tilde{\bf{P}}}({\cal D}_{1}\cap{\cal
D}_{2}|{\bf A}_{1},{\bf A}_{2}){\bar{\mathbb{I}}}_{{\cal
D}}\bigr{)}={\tilde{\bf{E}}}\bigl{(}{\tilde{\bf{P}}}({\cal D}_{1}|{\bf
A}_{1}){\tilde{\bf{P}}}({\cal D}_{2}|{\bf A}_{2}){\bar{\mathbb{I}}}_{{\cal
D}}\bigr{)}.$ (79)

Next, combining inequalities

$\displaystyle 0\leq{\tilde{\bf{P}}}({\cal D}_{1}\cap{\cal
D}_{2})-{\tilde{\bf{P}}}({\cal D}_{1}\cap{\cal D}_{2}\cap{\bar{\cal
D}})\leq{\tilde{\bf{P}}}({\cal D}),$ $\displaystyle
0\leq{\tilde{\bf{E}}}\bigl{(}{\tilde{\bf{P}}}({\cal D}_{1}|{\bf
A}_{1}){\tilde{\bf{P}}}({\cal D}_{2}|{\bf
A}_{2})\bigr{)}-{\tilde{\bf{E}}}\bigl{(}{\tilde{\bf{P}}}({\cal D}_{1}|{\bf
A}_{1}){\tilde{\bf{P}}}({\cal D}_{2}|{\bf A}_{2}){\bar{\mathbb{I}}}_{{\cal
D}}\bigr{)}\leq{\tilde{\bf{P}}}({\cal D})$

with (79) and using the identity (which holds, since given $X,Y$, the random
sets ${\bf A}_{1}$ and ${\bf A}_{2}$ are independent)

${\tilde{\bf{E}}}\bigl{(}{\tilde{\bf{P}}}({\cal D}_{1}|{\bf
A}_{1}){\tilde{\bf{P}}}({\cal D}_{2}|{\bf
A}_{2})\bigr{)}=\bigl{(}{\tilde{\bf{E}}}{\tilde{\bf{P}}}({\cal D}_{1}|{\bf
A}_{1})\bigr{)}\bigl{(}{\tilde{\bf{E}}}{\tilde{\bf{P}}}({\cal D}_{2}|{\bf
A}_{2})\bigr{)}={\tilde{\bf{P}}}({\cal D}_{1}){\tilde{\bf{P}}}({\cal D}_{2})$

we obtain that

$\bigl{|}{\bf{P}}^{\star}({\cal D}_{1}\cap{\cal
D}_{2})-{\bf{E}}^{\star}\bigl{(}{\tilde{\bf{P}}}({\cal
D}_{1}){\tilde{\bf{P}}}({\cal
D}_{2})\bigr{)}\bigr{|}\leq{\bf{E}}^{\star}{\tilde{\bf{P}}}({\cal D}).$

It remains to show that ${\bf{E}}^{\star}{\tilde{\bf{P}}}({\cal D})=o(1)$. To
this aim we apply Markov’s inequality

${\tilde{\bf{P}}}({\cal D})\leq\sum_{2\leq i\leq
m}{\tilde{\bf{E}}}{\mathbb{I}}_{i1}{\mathbb{I}}_{i2}\leq\sum_{2\leq i\leq
m}{\bf{E}}\lambda_{i1}\lambda_{i2}=n^{-1}Y_{1}Y_{2}{\hat{a}}_{2}$ (80)

and obtain ${\bf{E}}^{\star}({\tilde{\bf{P}}}({\cal D}))\leq
n^{-1}Y_{1}Y_{2}a_{2}=o(1)$ thus completing the proof of (78).

We secondly show that

${\bf{E}}^{\star}\bigr{|}{\tilde{\bf{P}}}({\bar{L}}_{1}^{(4)}=r_{1}){\tilde{\bf{P}}}({\bar{L}}_{2}^{(4)}=r_{2})-{\tilde{\bf{P}}}({\bar{L}}_{1}^{(5)}=r_{1}){\tilde{\bf{P}}}({\bar{L}}_{2}^{(5)}=r_{2})\bigr{|}\leq\varepsilon(Y_{1}+Y_{2})b_{1}a_{2}.$
(81)

Denote, for short, the expression $|\cdots|=|q_{1}q_{2}-h_{1}h_{2}|$ in (81).
Since $0\leq q_{1},q_{2},h_{1},h_{2}\leq 1$, we have
$|q_{1}q_{2}-h_{1}h_{2}|\leq|q_{1}-h_{1}|+|q_{2}-h_{2}|$. We apply LeCam’s
inequality (50) and obtain

$|q_{k}-h_{k}|\leq\sum_{2\leq i\leq
m}{\mathbb{I}}^{\prime}_{i}\lambda_{ik}\gamma_{i}^{2}\leq\varepsilon\sum_{2\leq
i\leq m}{\mathbb{I}}^{\prime}_{i}\lambda_{ik}\gamma_{i}\leq\varepsilon
Y_{1}b_{1}{\hat{a}}_{2},\qquad k=1,2.$

Here we estimate $\gamma_{i}^{2}\leq\varepsilon\gamma_{i}$. Clearly,
inequality ${\bf{E}}^{\star}|q_{k}-h_{k}|\leq\varepsilon Y_{k}b_{1}a_{2}$
imply (81).

Finally, we show that

${\bf{E}}^{\star}\bigl{(}{\tilde{\bf{P}}}({\bar{L}}_{1}^{(5)}=r_{1}){\tilde{\bf{P}}}({\bar{L}}_{2}^{(5)}=r_{2})\bigr{)}\to{\bf{P}}^{\star}(\Lambda_{3}=r_{1}){\bf{P}}^{\star}(\Lambda_{4}=r_{2}).$
(82)

Here we will use the fact that the almost sure convergence ${\hat{a}}_{2}\to
a_{2}$ implies the convergence in probability

$(\theta_{1},\theta_{2})\xrightarrow{P}(\lambda_{3},\lambda_{4}).$ (83)

Since for $s,t\geq 0$ the function $(s,t)\to
e^{-t-s}s^{r_{1}}t^{r_{2}}/(r_{1}!r_{2}!)$ is continuous and bounded, (83)
implies the convergence of expected values

${\bf{E}}^{\star}\frac{e^{-\theta_{1}}e^{-\theta_{2}}\theta_{1}^{r_{1}}\theta_{2}^{r_{2}}}{r_{1}!r_{2}!}\to{\bf{E}}^{\star}\frac{e^{-\lambda_{3}}e^{-\lambda_{4}}\lambda_{3}^{r_{1}}\lambda_{4}^{r_{2}}}{r_{1}!r_{2}!}=\frac{e^{-\lambda_{3}}e^{-\lambda_{4}}\lambda_{3}^{r_{1}}\lambda_{4}^{r_{2}}}{r_{1}!r_{2}!}.$
(84)

We observe that the quantities on the left (right) sides of (82) and (84) are
the same. Hence (84) implies (82).

It remains to prove (83). Denote
${\hat{\lambda}}_{k+2}=Y_{k}b_{1}{\hat{a}}_{2}$, $k=1,2$. We have for any
$\delta>0$

${\bf{P}}^{\star}(|\theta_{k}-{\hat{\lambda}}_{2+k}|\geq\delta)\leq\delta^{-1}{\bf{E}}^{\star}|\theta_{k}-{\hat{\lambda}}_{2+k}|\leq\delta^{-1}Y_{k}b_{1}{\bf{E}}X_{2}^{2}(1-{\mathbb{I}}^{\prime}_{2})=o(1).$
(85)

In the last step we used
${\bf{E}}X_{2}^{2}(1-{\mathbb{I}}^{\prime}_{2})=o(1)$. Now, (83) follows from
(85) and the bounds ${\hat{\lambda}}_{k+2}-\lambda_{k+2}=o_{P}(1)$, $k=1,2$,
which are simple consequences of the fact that ${\bf{E}}X_{1}^{2}<\infty$
implies ${\hat{a}}_{2}-a_{2}=o_{P}(1)$. ∎

##  4 Appendix B

######  Lemma 4.

Let $c,\varkappa,h>0$. Let $Z,\Lambda_{Z}$ be non-negative random variables
such that ${\bf{P}}(\Lambda_{Z}=r)={\bf{E}}\bigl{(}e^{-Z}Z^{r}/r!\bigr{)}$,
$r=0,1,\dots$.

(i) The relation ${\bf{P}}(Z>t)=(c+o(1))t^{-\varkappa}$ as $t\to+\infty$
implies

${\bf{P}}(\Lambda_{Z}>t)=(c+o(1))t^{-\varkappa}\qquad{\text{as}}\quad
t\to+\infty.$ (86)

(ii) If the distribution of $Z$ has property ${\cal A}_{c,\varkappa}$ then
${\bf{P}}(\Lambda_{Z}=r)\approx cr^{-\varkappa}$.

(iii) If $hZ$ is integer valued and satisfies ${\bf{P}}(hZ=r)\approx
c(h/r)^{\varkappa}$ then ${\bf{P}}(\Lambda_{Z}=r)\approx chr^{-\varkappa}$.

###### Proof of Lemma 4.

Let us prove (i). We first collect auxiliary inequalities. For a Poisson
random variable $\Lambda$ with mean $z>0$ and $0<s<z<t$ we have, see [17],

${\bf{P}}(\Lambda\geq t)\leq e^{-z}(ez/t)^{t},\qquad{\bf{P}}(\Lambda\leq
s)\leq e^{-z}(ez/s)^{s}.$ (87)

For $0<x<1$ and $y>1$ we have

$\ln(1-x)\leq-x-0.5x^{2},\qquad\ln(1+x)\leq x-0.25x^{2},\qquad\ln(1+y)\leq
y\ln 2.$ (88)

In order to prove (86) we split the probability
${\bf{P}}(\Lambda_{Z}>t)=P_{1}+P_{2}+P_{3}$, where

$\displaystyle P_{1}={\bf{P}}(\Lambda_{Z}>t,Z<t_{1}),\quad
P_{2}={\bf{P}}(\Lambda_{Z}>t,Z\in[t_{1},t_{2}]),\quad
P_{3}={\bf{P}}(\Lambda_{Z}>t,Z>t_{2}),$ $\displaystyle
t_{1}=t(1-\varepsilon),\qquad
t_{2}=t(1+\varepsilon),\qquad\varepsilon=t^{-1/3},$

and show that $P_{2}=(c+o(1))t^{-\varkappa}$ and $P_{k}=o(t^{-\varkappa})$,
$k=1,2$.

We have

$P_{2}\leq{\bf{P}}(t_{1}\leq Z\leq
t_{2})=(c+o(1))(t_{1}^{-\varkappa}-t_{2}^{-\varkappa})=o(t^{-\varkappa}).$

Next, we estimate $P_{1}$. Given $z<t_{1}$ we denote ${\bar{z}}=1-z/t$. Using
(87), (88) we obtain

${\bf{P}}(\Lambda_{Z}>t|Z=z)\leq
e^{-z}(ez/t)^{t}=e^{t-z+t\ln(1-{\bar{z}})}\leq
e^{t-z-t{\bar{z}}-0.5t{\bar{z}}^{2}}=e^{-0.5t{\bar{z}}^{2}}\leq
e^{-0.5t\varepsilon^{2}}.$

Hence,
$P_{1}={\bf{E}}\bigl{(}{\bf{P}}(\Lambda_{Z}>t|Z){\mathbb{I}}_{\\{Z<t_{1}\\}}\bigr{)}\leq
e^{-0.5\varepsilon^{2}t}=o(t^{-\varkappa})$. In order to evaluate $P_{3}$ we
observe that ${\bf{P}}(Z>t_{2})=(c+o(1))t^{-\varkappa}$ and write

$P_{3}={\bf{P}}(Z>t_{2})-{\bf{P}}(\Lambda_{Z}\leq t,Z>t_{2}).$

Then we estimate

${\bf{P}}(\Lambda_{Z}\leq t,Z>t_{2})={\bf{E}}\bigl{(}{\bf{P}}(\Lambda_{Z}\leq
t|Z){\mathbb{I}}_{\\{Z>t\\}}\bigr{)}=o(t^{-\varkappa})$

using the inequality

${\bf{P}}(\Lambda_{Z}\leq
t|Z=z)\leq\max\bigl{\\{}e^{-0.25\varepsilon^{2}t},e^{-t\ln(e/2)}\bigr{\\}},\qquad\forall\
z>t_{2}.$ (89)

It remains to prove (89). We have, see (87),

${\bf{P}}(\Lambda_{Z}\leq t|Z=z)\leq e^{-z}(ez/t)^{t}=e^{t-z+t\ln(1+y)}.$

Here $y=zt^{-1}-1$. For $0<y<1$ the quantity on the right is less than
$e^{-0.25\varepsilon^{2}t}$, by the second inequality of (88). For $y\geq 1$,
by the third inequality of (88), the quantity on the right is less than
$e^{-(z-t)(1-\ln 2)}\leq e^{-t\ln(e/2)}$, since $z-t=ty\geq t$.

Let us prove (ii). We only consider the case of integer valued $Z$. For an
absolute continuous $Z$ proof is the same. Denote $\varepsilon_{r}=r^{-1/2}\ln
r$. We split

$\displaystyle{\bf{P}}(\Lambda_{Z}=r)={\bf{E}}\bigl{(}e^{-Z}Z^{r}/r!\bigr{)}=J_{1}+J_{2}+J_{3},\qquad
J_{k}={\bf{E}}\bigl{(}{\mathbb{I}}_{\\{Z\in Q_{k}\\}}e^{-Z}Z^{r}/r!\bigr{)},$
$\displaystyle Q_{1}=[0,r(1-\varepsilon_{r})),\qquad
Q_{2}=[r(1-\varepsilon_{r}),r(1+\varepsilon_{r})],\qquad
Q_{3}=(r(1+\varepsilon_{r}),+\infty),$

and show that

$J_{1}=o(r^{-\varkappa}),\qquad J_{3}=o(r^{-\varkappa}),\qquad
J_{2}=(c+o(1))r^{-\varkappa}\qquad{\text{as}}\quad r\to+\infty.$ (90)

In the proof we use the following bounds related to the integral
representation of Euler’s Gamma function. Given interval
$Q\subset[0,+\infty)$, denote

$I_{Q}=\int_{Q}\frac{e^{-x}x^{r}}{r!}dx,\qquad S_{Q}=\sum_{j\in
Q_{k}}\frac{e^{-j}j^{r}}{r!}.$

For large $r$ we have

$I_{Q_{1}}\leq r^{-0.3\ln r},\qquad I_{Q_{3}}\leq r^{-0.3\ln r},\qquad
1-2r^{-0.3\ln r}\leq I_{Q_{2}}\leq 1.$ (91)

Relations (90) follow from (91) and the approximation
$S_{Q_{k}}=(1+o(1))I_{Q_{k}}$, $k=1,2,3$,

$\displaystyle J_{k}$ $\displaystyle=$ $\displaystyle\sum_{j\in
Q_{k}}\frac{e^{-j}j^{r}}{r!}{\bf{P}}(Z=r)\leq
S_{Q_{k}}=(1+o(1))I_{Q_{k}},\qquad k=1,3,$ $\displaystyle J_{2}$
$\displaystyle=$ $\displaystyle\sum_{j\in
Q_{2}}\frac{e^{-j}j^{r}}{r!}{\bf{P}}(Z=r)=\frac{c+o(1)}{r^{\varkappa}}S_{Q_{2}}=\frac{c+o(1)}{r^{\varkappa}}(1+o(1))I_{Q_{2}}.$

For reader’s convenience we provide a proof of (91). We note that the third
relation of (91) follows from the first two and the well known fact that
$I_{[0,+\infty)}=1$. In the proof, for sufficiently small $\varepsilon>0$, we
apply the inequalities, which follow by Taylor’s expansion,

$e^{\varepsilon}(1-\varepsilon)\leq 1-\varepsilon^{2}/3,\qquad
e^{-\varepsilon}(1+\varepsilon)\leq 1-\varepsilon^{2}/3.$

Since the function $x\to e^{-x}x^{r}$ increases on $Q_{1}$, we have
$I_{Q_{1}}\leq ze^{-z}z^{r}/r!$, where $z=r(1-\varepsilon_{r})$ is the right
end-point of $Q_{1}$. Using Stirling’s formula we obtain for large $r$

$ze^{-z}z^{r}/r!=(1+o(1))e^{r\varepsilon_{r}}(1-\varepsilon_{r})^{r+1}(r/2\pi)^{1/2}\leq
r^{1/2}(1-\varepsilon_{r}^{2}/3)^{r}\leq r^{-0.3\ln r}.$

In the last step we used $1-\varepsilon\leq e^{-\varepsilon}$. Furthermore,
for $y=r(1+\varepsilon_{r})$ we have decreases on $Q_{3}$ we have

$I_{Q_{3}}\leq\frac{e^{-y}y^{r}}{r!}\int_{y}^{+\infty}e^{-(x-y)}\Bigl{(}1+\frac{x-y}{y}\Bigr{)}^{r}dx.$
(92)

Using Stirling’s formula we obtain

$e^{-y}y^{r}/r!=(1+o(1))\bigl{(}e^{-\varepsilon_{r}}(1+\varepsilon_{r})\bigr{)}^{r}(2\pi
r)^{-1/2}\leq r^{-1/2}(1-\varepsilon_{r}^{2}/3)^{r}\leq r^{-0.5-0.3\ln r}.$

Combining this inequality with the following upper bound on the integral of
(92)

$\int_{0}^{+\infty}e^{-t}(1+t/y)^{r}dt\leq\int_{0}^{+\infty}e^{-t}e^{(rt/y)}dt=1+\varepsilon_{r}^{-1}\leq
r^{1/2}$

we obtain (91). Here we used the inequality $(1+t/y)^{r}\leq e^{(rt/y)}$.

We omit the proof of (iii) since it is similar to that of (ii). ∎

Acknowledgement. The present study was motivated by a question of Konstantin
Avratchenkov about the degree-degree distribution in a random intersection
graph. A discussion with Konstantin Avratchenkov and Jerzy Jaworski about the
influence of the clustering property on the degree-degree distribution was the
starting point of this research.

## References

  * [1] A. Aleškevičienė, R. Leipus and J. Šiaulys.  Tail behavior of random sums under consistent variation with applications to the compound renewal risk model.  Extremes, 11:261-279, 2008.
  * [2] K. Avratchenkov, N. M. Markovich, J.K. Sreedharan.  Distribution and dependence of extremes in network sampling processes.  Research report $n^{o}$ 8578, INRIA Sophia Antipolis. 2014\.
  * [3] A. D. Barbour and G. Reinert.  The shortest distance in random multi-type intersection graphs.  Random Structures and Algorithms, 39:179–209, 2011.
  * [4] M. Bloznelis, J. Damarackas.  Degree distribution of an inhomogeneous random intersection graph.  Electron. J. Combin., 20(3), $\\#$P3, 2013.
  * [5] M. Bloznelis, E. Godehardt, J. Jaworski, V. Kurauskas, and K. Rybarczyk.  Recent Progress in Complex Network Analysis \- Properties of Random Intersection Graphs.  In B. Lausen, S. Krolak-Schwerdt, M. Böhmer, Eds., Data Science, Learning by Latent Structures, and Knowledge Discovery. Springer, 2015.
  * [6] M. Bloznelis, J. Jaworski, and V. Kurauskas.  Assortativity and clustering coefficient of sparse random intersection graphs.  Electronic journal of probability, 18, N-38, 2013.
  * [7] M. Bloznelis, V. Kurauskas.  Clustering function: a measure of social influence.  arXiv:1207.4941, 2012.
  * [8] M. Boguna, R. Pastor-Satorras, and A. Vespignani.  Epidemic spreading in complex networks with degree correlations.  Statistical Mechanics of Complex Networks. Lecture Notes in Physics, 625:127–147, 2003.
  * [9] M. Bradonjic, A. Hagberg, N. W. Hengartner, and A. G. Percus.  Component Evolution in General Random Intersection Graphs.  In The 7th Workshop on Algorithms and Models for the Web Graph, WAW2010, Lecture Notes in Comput. Sci., 6516:36–49. 2010.
  * [10] M. Deijfen and W. Kets.  Random intersection graphs with tunable degree distribution and clustering.  Probab. Engrg. Inform. Sci., 23:661–674, 2009.
  * [11] S. Foss, D. Korshunov, and S. Zachary.  An Introduction to Heavy-Tailed and Subexponential Distributions. 2nd Edition Springer, New York, 2013.
  * [12] E. Godehardt and J. Jaworski.  Two models of random intersection graphs and their applications.  Electronic Notes in Discrete Mathematics, 10:129–132, 2001.
  * [13] E. A. Grechnikov.  The degree distribution and the number of edges between vertices of given degrees in the Buckley-Osthus model of a random web graph.  Internet Mathematics, 8:257-287, 2012.
  * [14] R. van der Hofstad, N. Litvak.  Degree-degree dependencies in random graphs with heavy-tailed degrees.  Internet Mathematics,10: 287-334, 2014.
  * [15] S. Janson, T. Łuczak and A. Ruciński.  Random Graphs.  Wiley, New York, 2001\.
  * [16] M. Karoński, E. R. Scheinerman, and K. B. Singer-Cohen.  On random intersection graphs: The subgraph problem.  Combinatorics, Probability and Computing, 8:131–159, 1999.
  * [17] M. Mitzenmacher, E. Upfal.  Probability and Computing. Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. 2005.
  * [18] L. Muchnik, S. Pei, L. C. Parra, S. D. S. Reis, J. S. Jr Andrade, S. Havlin, and H. A. Makse.  Origins of power-law degree distribution in the heterogeneity of human activity in social networks.  Scientific Reports, 3: 1783, 2013\.
  * [19] M.E.J. Newman.  Assortative mixing in networks.  Physical review letters, 89(20):208701, 2002.
  * [20] M. E.J. Newman.  Mixing patterns in networks.  Physical Review E, 67(2):026126, 2003\.
  * [21] S. Nikoletseas, C. Raptopoulos, and P. G. Spirakis.  The existence and efficient construction of large independent sets in general random intersection graphs.  In ICALP (2004), J. Daz, J. Karhumki, A. Lepist, and D. Sannella, Eds., volume 3142 of Lecture Notes in Comput. Sci., pages 1029–1040. Springer, 2004.
  * [22] J. M. Steele.  Le Cam’s inequality and Poisson approximations.  The American Mathematical Monthly, 101:48–54, 1994.