[This article was first published on YoungStatS, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
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 LargeNumbers and Central Limit Theorems for such arrays. Because non-sparsenetworks 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 networksand present uniformity results at the basis of the asymptotic normalityof many nonlinear estimators. We also show the general validity of abootstrap scheme adapted to such data.
Non-sparse Networks, Dyadic data and exchangeabilityDyadic data are random variables (or vectors) (Y_{i,j}) indexed by (i)and (j), two units from the same population. For instance, (Y_{i,j})could be exports from country (i) to country (j). Another example istaken from digital networks where (Y_{i,j}) could be, e.g., the numbersof messages from (i) to (j). It is useful to represent such data asarrays:
In this set set-up, the (n(n-1)) variables are potentially dependentbecause (Y_{i,j}) is likely correlated with (Y_{i',j'}) if({i,j}\cap{i',j'}\neq \emptyset). In the first example, exports from(i) to (j) are correlated with exports from (j) to (i), but also withother exports or imports of (i) or (j). The following assumptions allowfor such correlations, while keeping important aspects of iid sampling:[\begin{align}\textbf{Joint exchangeability: } & (Y_{i,j})_{(i,j)\in \mathbb{N}^{\ast 2}, i\neq j}\text{ has the same distribution as }(Y_{\pi(i),\pi(j)})_{(i,j)\in \mathbb{N}^{\ast 2}, i\neq j}, \& \text{ for any permutation }\pi \text{ of }\mathbb{N}^{\ast}, \\textbf{Dissociation: } & (Y_{i,j})_{(i,j)\in {1,…,k}^2, i\neq j}\text{ and } (Y_{i,j})_{(i,j)\in {k+1,k+2,…}^2, i\neq j} \text{ are independent,} \ & \text{for any }k \in \mathbb{N}^{\ast}.\end{align}]
These notions generalize “iidness”: if ((X_i)_{i\geq 1}) are i.i.d.,then (Y_{i,j}=X_i), for any (i\neq j), defines a jointly exchangeableand 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 tojointly 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 thevariables ((Y_{i,j})_{i\neq j}) are jointly exchangeable anddissociated, the variables(Z_{i,j,k}=(Y_{i,j}+Y_{j,i})(Y_{i,k}+Y_{k,i})') (with (i, j) and (k) alldistinct) also are. Then by the LLN above, we have, if(\mathbb{E}\left(|Y_{1,2}|^2\right)<\infty),[\frac{1}{n(n-1)(n-2)}\sum_{1\leq i,j,k\leq n}Z_{i,j,k}\xrightarrow{a.s.}\mathbb{E} \left((Y_{1,2}+Y_{2,1})(Y_{1,3}+Y_{3,1})'\right).]Next, if we let(\overline{Y}_i=\frac{1}{n-1}\sum_{\substack{1\leq j \leq n\ j\neq i}}(Y_{i,j}+Y_{j,i}))and (\overline{Y}=\frac{1}{n}\sum_{i=1}^{n}\overline{Y}_{i}), we obtain[\widehat{V}=\frac{1}{n}\sum_{1\leq i \leq n}(\overline{Y}_i-\overline{Y})(\overline{Y}_i-\overline{Y})'\xrightarrow{a.s.} V.]Hence, t-tests or F-tests of the hypothesis(\mathbb{E}(Y_{1,2})=\theta_0) using (\widehat{V}) are asymptoticallyvalid as soon as (V) is non-singular.
Uniform LLN and CLTThe previous results are nonetheless insufficient in many cases,especially with nonlinear (e.g., M- or Z-) estimators. A common way tohandle such problems, then, is to render “simple’’ LLN and CLTuniform over suitable classes of functions. Specifically, for(f\in \mathcal{F}) a class of bounded functions with values in(\mathbb{R}^k), let(\mathbb{P}_n(f)=\frac{1}{n(n-1)}\sum_{1\leq i,j\leq n}f(Y_{i,j})) and(\mathbb{G}_n(f)=\sqrt{n}\left(\mathbb{P}_n(f)-E(f(Y_{1,2}))\right)).The class (\mathcal{F}) is called Glivenko-Cantelli if, basically,[\begin{align}%\text{ almost-surely and in }L^1 : \lim_n \sup_{f\in \mathcal{F}}\left|\mathbb{P}_n(f)-\mathbb{E}(f(Y_{1,2}))\right|\xrightarrow{a.s.} 0.\label{eq1}\tag{1}\end{align}] Similarly, The class (\mathcal{F}) is Donsker for thedistribution of ((Y_{i,j})_{i\neq j\geq 1}) if[\begin{align}\mathbb{G}_n\stackrel{d}{\longrightarrow}\mathbb{G},\label{eq2}\tag{2}\end{align}]with (\mathbb{G}) a Gaussian process indexed on (\mathcal{F}).
Results (\eqref{eq1}) and (\eqref{eq2}) have been shown for iid data undervarious conditions. We consider two standard ones involving theso-called covering numbers of (\mathcal{F}). First, we introduceadditional notation. For any (\eta > 0) and any seminorm (||\cdot||) ona space including (\mathcal{F}), (N(\eta, \mathcal{F}, ||\cdot||))denotes the minimal number of (||\cdot||)-closed balls of radius (\eta)with centers in (\mathcal{F}) needed to cover (\mathcal{F}). Theseminorms we consider hereafter are(|f|_{\mu,r} = \left(\int |f|^rd\mu\right)^{1/r}) for any (r \geq 1) andprobability measure (\mu). Hereafter, an envelope of (F) is a measurablefunction (F) satisfying (F(u) \geq \sup_{f\in \mathcal{F}} |f(u)|). Welet (\mathcal{Q}) denote the set of probability measures with finitesupport. Finally, (P) denotes the distribution of one random variable.
The conditions for (\eqref{eq1}) and (\eqref{eq2}) to hold with iid data arethen:
Remarkably, these results directly extend to jointly exchangeable anddissociated arrays:
Uniform LLN and CLT also hold using standard conditions on bracketingnumbers, instead of covering numbers as above.
Take-away: the main asymptotic results used to establish theproperties of nonlinear estimators with iid data also hold with jointlyexchangeable and dissociated arrays.
Hence, asymptotically normal estimators with iid data are alsoasymptotically normal with jointly exchangeable and dissociated arrays.The only difference lies in their rate of convergence and theirasymptotic variance (V). If (V) is not singular, inference can be basedon consistent estimation of (V), as explained above. But a simplebootstrap scheme can also be used.
Bootstrapping exchangeable arraysThe main message here is that even if the parameters of interestdepend on “edges” distribution, we have to bootstrap vertices!
Specifically, consider ((1^{\ast}, 2^{\ast},…,n^{\ast})) and iidsample drawn uniformly from ({1,…,n}), and consider the bootstrapsample ((Y_{i^{\ast},j^{\ast}})_{i\neq j, i^\neq j^}).
To illustrate the bootstrap scheme, imagine a 5-vertices network, and abootstrap sample of vertices((1^{\ast},2^{\ast},3^{\ast},4^{\ast},5^{\ast})=(2,1,2,5,4)), thecorresponding bootstrapped network is:
Figure 1: Bootstrapped network for((1^{\ast},2^{\ast},3^{\ast},4^{\ast},5^{\ast})=(2,1,2,5,4))}
The bootstrapped average is(\mathbb{P}_n^{\ast}(f)=\frac{1}{n(n-1)}\sum_{1\leq i,j\leq n}f(Y_{i^{\ast},j^{\ast}})\mathbb{1}_{{i^{\ast}\neq j^{\ast}}}),while the bootstrapped process is(\mathbb{G}_n^{\ast}(f)=\sqrt{n}\left(\mathbb{P}_n^{\ast}(f)-\mathbb{P}_n(f)\right)).
As with iid data, the bootstrap scheme above leads to consistentinference if Condition (D(\mathcal{F})) holds. Specifically, we thenhave, conditional on ((Y_{i,j})_{i,j\in \mathbb{N}^2}) and almostsurely,[\begin{align}\mathbb{G}_n^{\ast}\stackrel{d}{\longrightarrow}\mathbb{G},\end{align}]where (\mathbb{G}) is the same Gaussian process as above. This ensuresthe validity of the bootstrap in many nonlinear contexts.
BibliographyAldous, D. J. 1983. Exchangeability and Related Topics. Springer Verlag.Davezies, Laurent, Xavier D’Haultfœuille, and Yannick Guyonvarch. 2018. “Asymptotic Results Under Multiway Clustering.” ArXiv e-Prints, Eprint 1807.07925.———. 2021. “Empirical Process Results for Exchangeable Arrays.” The Annals of Statistics.Eagleson, G. K., and N. C. Weber. 1978. Limit Theorems for Weakly Exchangeable Arrays. Mathematical Proceedings of the Cambridge Philosophical Society.Kallenberg, O. 2005. Probabilistic Symmetries and Invariance Principles. Springer.Menzel, Konrad. 2018. “Bootstrap with Clustering in Two or More Dimensions.” Working Paper.Silverman, B. W. 1976. “Empirical Process Results for Exchangeable Arrays.” Advances in Applied Probability.To leave a comment for the author, please follow the link and comment on their blog: YoungStatS.
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.Continue reading: Asymptotic Statistics in Non-Sparse Networks