Asymptotic Statistics in Non-Sparse Networks
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
Exchangeable arrays have been studied since the late 70’s (Aldous (1983), Kallenberg (2005)). Eagleson and Weber (1978) and Silverman (1976) establish Strong Law of Large Numbers and Central Limit Theorems for such arrays. Because non-sparse networks and multiway clustering are related to exchangeable arrays, they have received recent attention in statistics and econometrics (Davezies, D’Haultfœuille, and Guyonvarch (2018), Davezies, D’Haultfœuille, and Guyonvarch (2021), Menzel (2018)). We focus below on non-sparse networks and present uniformity results at the basis of the asymptotic normality of many nonlinear estimators. We also show the general validity of a bootstrap scheme adapted to such data.
Non-sparse Networks, Dyadic data and exchangeability
Dyadic data are random variables (or vectors) Yi,j indexed by i and j, two units from the same population. For instance, Yi,j could be exports from country i to country j. Another example is taken from digital networks where Yi,j could be, e.g., the numbers of messages from i to j. It is useful to represent such data as arrays:
In this set set-up, the n(n−1) variables are potentially dependent
because Yi,j is likely correlated with Yi′,j′ if
{i,j}∩{i′,j′}≠∅. In the first example, exports from
i to j are correlated with exports from j to i, but also with
other exports or imports of i or j. The following assumptions allow
for such correlations, while keeping important aspects of iid sampling:
Joint exchangeability: (Yi,j)(i,j)∈N∗2,i≠j has the same distribution as (Yπ(i),π(j))(i,j)∈N∗2,i≠j, for any permutation π of N∗,Dissociation: (Yi,j)(i,j)∈{1,…,k}2,i≠j and (Yi,j)(i,j)∈{k+1,k+2,…}2,i≠j are independent,for any k∈N∗.
These notions generalize “iidness”: if (Xi)i≥1 are i.i.d., then Yi,j=Xi, for any i≠j, defines a jointly exchangeable and dissociated array.
Simple law of large numbers (LLN) and central limit theorems (CLT)
The following results generalize the usual LLN and CLT for iid data to jointly exchangeable and dissociated arrays:
These results actually hold for “multiadic” data, viz. data indexed by
k-tuples instead of pairs. This has a nice consequence. If the
variables (Yi,j)i≠j are jointly exchangeable and
dissociated, the variables
Zi,j,k=(Yi,j+Yj,i)(Yi,k+Yk,i)′ (with i,j and k all
distinct) also are. Then by the LLN above, we have, if
E(|Y1,2|2)<∞,
1n(n−1)(n−2)∑1≤i,j,k≤nZi,j,ka.s.→E((Y1,2+Y2,1)(Y1,3+Y3,1)′).
Uniform LLN and CLT
The previous results are nonetheless insufficient in many cases,
especially with nonlinear (e.g., M- or Z-) estimators. A common way to
handle such problems, then, is to render “simple’’ LLN and CLT
uniform over suitable classes of functions. Specifically, for
f∈F a class of bounded functions with values in
Rk, let
Pn(f)=1n(n−1)∑1≤i,j≤nf(Yi,j) and
Gn(f)=√n(Pn(f)−E(f(Y1,2))).
The class F is called Glivenko-Cantelli if, basically,
limnsupf∈F|Pn(f)−E(f(Y1,2))|a.s.→0.
Results (1) and (2) have been shown for iid data under various conditions. We consider two standard ones involving the so-called covering numbers of F. First, we introduce additional notation. For any η>0 and any seminorm ||⋅|| on a space including F, N(η,F,||⋅||) denotes the minimal number of ||⋅||-closed balls of radius η with centers in F needed to cover F. The seminorms we consider hereafter are |f|μ,r=(∫|f|rdμ)1/r for any r≥1 and probability measure μ. Hereafter, an envelope of F is a measurable function F satisfying F(u)≥supf∈F|f(u)|. We let Q denote the set of probability measures with finite support. Finally, P denotes the distribution of one random variable.
The conditions for (1) and (2) to hold with iid data are then:
Condition CG(F): ∀η>0,supQ∈QN(η|F|Q,1,F,|.|Q,1)<∞, with |F|P,1<∞.
Condition D(F): ∫+∞0supQ∈Q√logN(η|F|Q,2,F,|.|Q,2)dη<+∞, with |F|P,2<∞.
Remarkably, these results directly extend to jointly exchangeable and dissociated arrays:
If Condition CG(F) holds then (1) holds.
If Condition D(F) holds then (2) holds, with G having a covariance kernel K defined by K(f1,f2)=Cov(f1(Y1,2)+f1(Y2,1),f2(Y1,3)+f2(Y3,1)).
Uniform LLN and CLT also hold using standard conditions on bracketing numbers, instead of covering numbers as above.
Take-away: the main asymptotic results used to establish the properties of nonlinear estimators with iid data also hold with jointly exchangeable and dissociated arrays.
Hence, asymptotically normal estimators with iid data are also asymptotically normal with jointly exchangeable and dissociated arrays. The only difference lies in their rate of convergence and their asymptotic variance V. If V is not singular, inference can be based on consistent estimation of V, as explained above. But a simple bootstrap scheme can also be used.
Bootstrapping exchangeable arrays
The main message here is that even if the parameters of interest
depend on “edges” distribution, we have to bootstrap vertices!
Specifically, consider (1∗,2∗,…,n∗) and iid
sample drawn uniformly from {1,…,n}, and consider the bootstrap
sample (Yi∗,j∗)i≠j,i∗≠j∗.
To illustrate the bootstrap scheme, imagine a 5-vertices network, and a bootstrap sample of vertices (1∗,2∗,3∗,4∗,5∗)=(2,1,2,5,4), the corresponding bootstrapped network is:
Figure 1: Bootstrapped network for (1∗,2∗,3∗,4∗,5∗)=(2,1,2,5,4)}
The bootstrapped average is P∗n(f)=1n(n−1)∑1≤i,j≤nf(Yi∗,j∗)1{i∗≠j∗}, while the bootstrapped process is G∗n(f)=√n(P∗n(f)−Pn(f)).
As with iid data, the bootstrap scheme above leads to consistent
inference if Condition D(F) holds. Specifically, we then
have, conditional on (Yi,j)i,j∈N2 and almost
surely,
G∗nd⟶G,
Bibliography
R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.