Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
63,340 characters · 8 sections · 36 citation commands
\email{[email removed]}
The aim of this paper is developing bootstrap approaches for the sample mean of network dependent processes studied in \citet*[hereafter KMS]{Kojevnikov/Marmer/Song:20}. A network dependent process is a random field indexed by the set of nodes of a given undirected network. This network governs the stochastic dependence between the elements of the associated random field. Specifically, the latter is assumed to satisfy a conditional version of the $\psi$-weak dependence condition of Doukhan/Louhichi:99 given a common shock of a general form. \citealias{Kojevnikov/Marmer/Song:20} show that the pointwise Law of Large Numbers and the Central Limit Theorem hold for a sequence of such processes under suitable assumptions on the networks' denseness and the strength of the stochastic dependence. In addition, they provide nonparametric HAC estimators of the variance-covariance matrix for the vector of sample moments, which is similar to the spatial HAC estimator developed in Kelejian/Prucha:07.
These results provide an asymptotic approximation of the distribution of the sample mean which can be used for inference on the true mean of a network dependent process. However, this approximation relies on the network HAC estimator which has two major drawbacks. First, unlike its spatial or time-series counterparts it is not guaranteed to yield a positive semi-definite estimate. Second, these estimators are known to have poor finite sample properties Matyas:99:GMM. The aim of the current work is to provide an alternative nonparametric way to conduct inference in these settings.
The nonparametric bootstrap methods for the case of weakly dependent observations have been studies since the introduction of the non-overlapping block bootstrap in Carlstein:86 and the moving block bootstrap in Kunsch:89 and Liu/Singh:92 for stationary, mixing time-series. Since then, a number of block-based methods have been considered in the statistics literature. They share the idea of resampling groups of consecutive observations to capture the stochastic dependence in the original series and include, among others, the circular block bootstrap Politis/Romano:92, the stationary bootstrap Politis/Romano:94 and the tapered block bootstrap Paparoditis/Politis:01. A detailed exposition and comparison of some of these methods can be found in Lahiri:03:Resampling. Block-based bootstrap was also successfully applied to the case of weakly dependent random fields satisfying certain mixing conditions Lahiri:03:Resampling.
More recent developments in this area of research are discussed in Goncalves:11. In particular, the dependent wild bootstrap proposed in Buhlmann:93 and Shao:10 departs from other methods. Instead of using blocks, it tries to mimic the autocovariance structure of the original data by introducing auxiliary random variables and can be applied to irregularly spaced data. A related method, the dependent random weighting, was recently introduced in Sengupta/Shao:15 and has wider applicability; specifically, it can be directly applied to irregularly spaced spatial data.
Another useful resampling technique developed for stationary and nonstationary times-series and homogenous random fields under mixing is subsampling. A comprehensive treatment of this method is given in Politis:99. Interestingly, in the time-series case subsampling is similar to the moving block bootstrap where a single block is resampled. Finally, it is worth mentioning the spatial smoothed bootstrap suggested in Garcia:13. In this instance, assuming homogeneity of the underlying data generating process, bootstrap pseudo-samples are drawn from the estimated joint distribution of a given sample.
Network dependent processes are closely related to random fields indexed by elements of a lattice in $\R^d$ Comets/Janzura:98,Conley:99. However, they are not a special case of the latter and so the existing bootstrap methods cannot be directly applied to our framework. The main reason for that is the irregularity of the structure of underlying networks. In particular, subsampling and all types of the block bootstrap for time-series and spatial data rely on the existence of ordered blocks of closely-located observations. The dependent wild bootstrap uses a well-known property of kernel functions that guarantees the positive semi-definiteness of certain weighting matrices. However, as argued in \citealias{Kojevnikov/Marmer/Song:20}, this relation does not necessarily hold when applied to networks. Finally, the homogeneity assumption of the spatial smoothed bootstrap and the spatial subsampling, that is the invariance of joint distributions under spatial shifts is not suitable for our case.
We propose two bootstrap approaches for constructing asymptotically valid confidence sets for the mean of a network dependent process and establish the first-order consistency of these methods for smooth functions of means conditionally on the common shock. The first approach is a block-based method in which blocks are constructed from certain neighborhoods of each node in a network. The second is a modification of the dependent wild bootstrap that employs the topology of a given graph to generate random weights instead of using a fixed kernel function. In addition, we provide the bootstrap variance estimators of the scaled sample mean which yield positive semi-definite estimates and can be used as an alternative to the network HAC estimator. We find that the consistency of the modified dependent wild bootstrap and the corresponding variance estimator holds under weaker conditions as compared with the block bootstrap. However, the bootstrap distribution corresponding to the former method may fail to match the higher-order cumulants of the underlying data generating process, thus preventing improvements over asymptotic approximations.
The rest of the paper is organized as follows. The next section describes a modification of network dependent processes allowing for weighted networks. This modification can be useful for handling dense graphs once varying intensity of links is assumed. Section (ref) provides some general result regarding the conditional bootstrap. Specifically, we use the almost sure convergence of probability kernels to ensure that the bootstrap is valid for (almost) every realization of the common shock, which may also represent the stochastic network formation process. In Section (ref) we present the above-mentioned bootstrap methods in detail and establish sufficient conditions for their conditional consistency. All the proofs and other technical details are presented in the Appendices (ref)-(ref).
We consider a variation of network dependent processes characterized in \citealias{Kojevnikov/Marmer/Song:20}. Namely, let $G\equiv(N,E)$ be an undirected graph (possibly infinite), where $N$ is the set of nodes and $E$ denotes the set of links (we identify $N$ with integers $\{1,2,\ldots\}$). Each edge $e\in E$ is associated with a weight $W(e)\in\bar{\R}$. Also let the function $d:N\times N\to\bar{\R}_{\ge 0}$ be a distance on $G$; for example, the shortest path distance for an unweighted graph. An $\X$-valued network dependent process $Y\equiv (Y,G)$ is a collection of $\X$-valued random elements defined on a common probability space indexed by $N$, i.e., $\{Y_i:i\in N\}$. The network $G$ governs the stochastic dependence between random elements. In this paper we consider $\X=\R^v$ with $v\ge 1$.
Further, suppose that we observe a sequence of network dependent processes $\seq{(Y_n,G_n)}$ defined on a common probability space $(\Omega,\H,\PM)$, where each $G_n\equiv(N_n,E_n)$ is a finite graph of size $m_n\to\infty$ as $n\to\infty$; w.l.o.g. we set $m_n=n$. Here, the sequence $\seq{G_n}$ can be a sequence of subgraphs of an infinite network $(N_{\infty},E_{\infty})$. In general, however, these graphs can be unrelated. In order to emphasize the dependence of the distance between two nodes on $n$, we denote it as $d_n(\csdot,\csdot)$. Additionally, since the distance function may implicitly depend on weights associated with the edges of a graph, we impose the following restriction in order to employ the results established in \citealias{Kojevnikov/Marmer/Song:20} with the least possible change.
For example, if $W(e)\in [0,1]$ for all $e\in E$, which can be interpreted as the intensity of links, then the shortest weighed distance associated with $1/W(\csdot)$ satisfies this assumption, where implicitly we set $1/0\equiv\infty$. In this case an unweighted network $(N,E)$ is equivalent to a complete graph $(N,E')$, where for $e\in E'$, $W(e)=\ind\{e\in E\}$. In a similar manner, the (at most countable) parameter space of a random field on a metric space $(\mathcal{Z},\rho)$ can be modelled as a compete graph of suitable cardinality, where $W(x\leftrightarrow y)$ is a function of the distance $\rho$ between two points $x,y\in \mathcal{Z}$. Then Assumption (ref) corresponds to the case of increasing domain asymptotics Conley:99,Jenish/Prucha:09.
Let $\CS\subset \H$ be a given sub-$\sigma$-field. We assume that the sequence of network dependent processes is conditionally weakly dependent given $\CS$. Specifically, for $a,b\in\N$ and $s\ge 0$ let \[ \PS_n(a,b;s)\eqdef \{(A,B)\subset N_n^2: \abs{A}=a,\abs{B}=b,d_n(A,B)\ge s\} \] with $d_n(A,B)\eqdef\min_{i\in A,j\in B}d_n(i,j)$ and let $\L_v$ be the family of real-valued, bounded, Lipschitz functions, i.e.,
\[ \L_v\eqdef \bigcup_{a\ge 1}\L_{v,a}, \] where \[ \L_{v,a}\eqdef \{f:\R^{v\times a}\to \R: \norm{f}_{\infty}<\infty, \Lip(f)<\infty\}. \] The functions in $\L_{v,a}$ are Lipschitz with respect to the distance $\delta_a$ on $\R^{v\times a}$ given by \[ \delta_a(\vec{x},\vec{y})\eqdef\sum_{l=1}^a\norm{x_l-y_l}, \] where $\norm{\csdot}$ is a norm on $\R^v$ and $\vec{x}\equiv(x_1,\ldots,x_a)$ and $\vec{y}\equiv(y_1,\ldots,y_a)$ are points in $\R^{v\times a}$. In addition, for a set of nodes $A\subset N_n$ we write $Y_{n,A}\equiv\{Y_{n,i}:i\in A\}$.
A number of examples of network dependent processes that are $(\L_v,\psi,\CS)$-weakly dependent are given in \citealias{Kojevnikov/Marmer/Song:20}. For instance, strong mixing processes correspond to $\psi_{a,b}(f,g)=4\norm{f}_{\infty}\norm{g}_{\infty}$. Also associated and Gaussian processes and their certain derivatives are $(\L_v,\psi,\CS)$-weakly dependent with $\psi_{a,b}(f,g)=ab\Lip(f)\Lip(g)$. It is worth mentioning that the corresponding weak dependence coefficients may depend on the topology of the underlying networks.
Conditioning on a $\sigma$-field $\CS$ can be useful in various cases. First, if the underlying graphs are realizations of a stochastic network formation process, then one can potentially condition on the $\sigma$-field generated by that process and treat the observed graphs as fixed. Second, fixing nodes with high degree centrality may help to obtain local stochastic dependence.
In order to facilitate the exposition, throughout the paper we consider a sequence of network dependent processes $\seq{Y_n}$ satisfying the covariance bound (ref) with a specific form of the function $\psi_{a,b}$ and bounded weak dependence coefficients. The restricted $\psi_{a,b}$ function is fairly general and covers many useful examples of weakly dependent processes.
It should be noted that processes satisfying Assumption (ref) possess some hereditary properties. Specifically, if $\seq{Y_n}$ is $(\L_v,\psi,\CS)$-weakly dependent with the weak dependence coefficients $\arr{\gamma_{n,s}}$, then for any Lipschitz function $h:\R^v\to\R^w$ the sequence $\seq{h(Y_{n,i}):i\in N_n}$ is $(\L_w,\psi,\CS)$-weakly dependent with the same weak dependence coefficients. Moreover, this type of weak dependence is preserved under some locally Lipschitz functions as shown in Proposition (ref) below, which is an extension of Proposition 2.1. in \citet*{Dedecker/Doukhan:07:WeakDep} to our settings.
Introducing weighted networks is useful in several scenarios. First, as we have already mentioned it allows incorporating some additional random processes into the current framework. Second, assuming varying intensity of connections enables one to handle denser networks in the sense of the total number of links. Finally, some commonly used statistical models explicitly use weights and can be adapted to our framework, e.g., the spatial Cliff-Ord-type linear model in Kelejan/Prucha:07_2.
For a given network $G_n$ let $N_n(i;s)$ denote the open neighborhood of radius $s>0$ around $i\in N_n$, i.e, \[ N_n(i;s)\eqdef\{j\in N_n:d_n(i,j)<s\},\footnote{ Note that this definition of the open neighborhood of a node differs from one commonly used in graph theory. } \] and let $N_n^{\partial}(i;s)\eqdef N_n(i;s+1)\setminus N_n(i;s)$. In addition, we define the following aggregate measures of the network denseness:
It is straightforward to see that under Assumption (ref), which restricts the minimum distance between any two nodes of a network, the asymptotic results derived in \citealias{Kojevnikov/Marmer/Song:20} remain valid once we replace their measures of network denseness with those given in (ref) and redefine $H_n(s,m)$ as follows:
In the case of random networks, however, the measures of network denseness are also random. Therefore, one needs a conditional version of the Law of Large Numbers in order to be able to condition on the common shock $\CS$. Note that the other result are stated in the conditional form and can be directly applied to this case if we assume certain measurability conditions. Let $\D(G_n)$ denote the distance matrix associated with $G_n$, i.e., $[\D(G_n)]_{ij}=d_n(i,j)$. If $\D(G_n)$ is $\CS$-measurable, then $N_n(i;s)=\sum_{j\in N_n}\ind\{[\D(G_n)]_{ij}<s\}$ is also $\CS$-measurable as well as the quantities given in (ref) and (ref). We make the following assumption:
In addition, we introduce the notion of asymptotically negligible random functions, which is useful for defining the conditional versions of the asymptotic tightness and uniform integrability.
Finally, let $\bar{Y}_n\eqdef n^{-1}\sum_{i\in N_n}Y_{n,i}$ and $\Sigma_n\eqdef \Var(\sqrt{n}\bar{Y}_n\mid \CS)$. Then the network HAC estimator of $\Sigma_n$,
where $\kappa:\bar{\R}\to[-1,1]$ is a kernel function satisfying: $\kappa(0)=1$, $\kappa(z)=\kappa(-z)$, and $\kappa(z)=0$ for $\abs{z}>1$ and $b_n$ is the lag truncation parameter, is consistent under the same set of assumptions. Unfortunately, due to the irregularity of a network's structure, this estimator is not guaranteed to be positive semi-definite. However, once the minimal eigenvalue of $\Sigma_n$ is a.s.\ bounded from below or it converges to an a.s.\ positive definite matrix, a simple way to fix this issue is available. The details are given in Appendix (ref).
In this section we present some general result regarding the conditional bootstrap. The latter is useful for an inference which is asymptotically valid for almost all $\omega\in \Omega$ (or almost all realizations of the common shock). These results do not depend on the underlying data generating process. However, we use the present framework for convenience.
Suppose that $\seq{(Y_n, G_n)}$ is a sequence of network dependent processes. For a given $n\ge 1$ let $\theta_n$ be a $\CS$-measurable parameter taking values in $\Theta\subseteq \R^w$ with $w\ge 1$ and let \[ T_n(\theta_n)\eqdef\T_n(Y_n,\theta_n;\vartheta_n), \] where $\T_n$ is a measurable, real-valued function and $\vartheta_n$ is a $\CS$-measurable nuisance parameter, denote a statistic used to conduct inference on $\theta_n$ based on a realization of $(Y_n,G_n)$ conditionally on $\CS$.
Let $\FD{n}{}$ denote the conditional cdf of $T_n$ given $\CS$.\footnote{ A (regular) conditional cdf $\FD{X}{\F}$ of $X\in \R$ given $\F\subset\H$ satisfies: (i) $\forall x\in \R$, $\FD{X}{\F}(\csdot,x)$ is a version of $\PR{X\le x\mid \F}$, and (ii) $\forall \omega\in \Omega$, $\FD{X}{\F}(\omega,\csdot)$ is a distribution function. We omit the subscript $X$ or the superscript $\F$ whenever clear from the context. } The goal of this section is to provide sufficient conditions for the conditional first-order consistency of resampling estimators of $\FD{n}{}$. Specifically, let $\G_n\eqdef \CS \vee \sigma(Y_n)$ and let $Y_n^{*}$ be a pseudo-sample drawn using a realization of $Y_n$. Then the bootstrap counterpart of $T_n$ is $T_n^{*}\eqdef \T_m(Y_n^{*},\theta_n^{*})$, where $m$ is the size of $Y_n^{*}$ and $\theta_n^{*}\equiv \theta_n^{*}(Y_n)$ is an estimator of $\theta_n$. The conditional cdf $\FD{n}{*}$ of $T_n^{*}$ is used as an approximation of $\FD{n}{}$. If the latter explicitly depends on the nuisance parameter $\vartheta_n$, then one needs to provide its consistent estimator based on both $Y_n$ and $Y_n^{*}$.
A typical way of showing the consistency of the bootstrap estimators is bounding the Kolmogorov distance between the cdfs of $T_n$ and $T_n^{*}$ Shao:95:Bootstrap. For random variables $X$ and $Y$ and sub-$\sigma$-fields $\F\subset\G\subset\H$ the conditional version of the latter is defined by \[ \DK{X,Y\mid \G,\F}\eqdef \sup_{x\in \R}\abs{\FD{X}{\G}(\csdot,x)-\FD{Y}{\F}(\csdot,x)},\footnote{ Note that $\DK{\csdot,\csdot\mid \G,\F}$ is $\G$-measurable because $\seq{Z_x}$, where $Z_x\eqdef\abs{\FD{X}{\G}(\csdot,x)-\FD{Y}{\F}(\csdot,x)}$, is a c\'adl\'ag stochastic process). } \] where $\FD{X}{\G}$ and $\FD{Y}{\F}$ are the conditional cdfs of $X$ and $Y$, respectively (when $\F=\G$ we denote this measure by $\DK{X,Y\mid \F}$). In addition, we define the conditional convergence in probability and the almost sure convergence of conditional distributions.\footnote{ A (regular) conditional distribution $\QM_X^{\F}$ of $X\in \R^v$ given $\F\subset\H$ satisfies: (i) $\forall B\in \B(\R^v)$, $\QM_X^{\F}(\csdot, B)$ is a version of $\PR{X\in B\mid \F}$ and (ii) $\forall \omega\in\Omega$, $\QM_X^{\F}(\omega,\csdot)$ is a probability measure on $(\R,\B(\R^v))$. We omit the subscript $X$ or the superscript $\F$ whenever clear from the context. }
Assume for a moment that $\CS=\{\emptyset,\Omega\}$. Then if there exists a sequence of random variables $\seq{S_n}$ such that $\DK{T_n,S_n\mid \CS}$ converges to 0 as $n\to\infty$ and $\DK{T_n^{*},S_n\mid \G_n,\CS}$ converges to $0$ a.s.\ (in probability), then the bootstrap estimator is first-order strongly (weakly) consistent. Moreover, if $S_n$ converges weakly to a continuous limit, then the conditional quantiles of $\FD{n}{*}$ are a good approximation to those of $\FD{n}{}$. This typically happens when the statistic $T_n$ is pivotal. However, in the case of a non-pivotal statistic, which is useful when a consistent estimator of $\vartheta_n$ is hard to obtain or the available estimators have poor finite sample properties, the cdfs of $\seq{T_n}$ need not converge.\footnote{ Consider, for example, the case of the linearized statistic $T_n'$ given in (ref). It does not have a nondegenerate weak limit when the sequence of parameters $\seq{\theta_n}$ is not convergent. } In this case, the convergence of the Kolmogorov distance between $T_n^{*}$ and $T_n$ to zero does not necessarily imply that $\FD{n}{}(c_n^{*}(\alpha))\to \alpha$ as $n\to\infty$, where $c_n^{*}(\alpha)$ is the conditional $\alpha$-quantile of $\FD{n}{*}$. Nevertheless, as shown in the next result, a sufficient condition for the latter to happen is the continuity of the cdfs of $\seq{S_n}$.
Typically it is not hard to show that condition (a) of Theorem (ref) holds (for example, when the elements of $Y_n^{*}$ are conditionally i.i.d.\ given $\G_n$). On contrary, establishing (b) may be a difficult task, especially when $T_n$ is a nonlinear transformation of $Y_n$ in the presence of stochastic dependence between its elements as in the current framework. However, in the case when the statistic $T_n$ converges $\CS$-weakly to $S$ and the limiting kernel (i.e., the regular conditional cdf of $S$ given $\CS$) is continuous, Lemma (ref) implies that this convergence is equivalent to one with respect to the conditional Kolmogorov distance. In addition, by Lemma (ref) the almost sure convergence of conditional distributions enjoys a number of useful properties associated with the usual weak convergence such as the continuous mapping theorem, converging together lemma, and the Cram\'er–Wold device. In this situation we have the following simple corollary.
Next, we consider the case in which the statistic $T_n$ takes the following form: \[ T_n(\theta_n)=\tau_n\left(\phi(\hat{\theta}_n)-\phi(\theta_n)\right), \] where $\phi:\Theta\to \R$ is a continuously differentiable function, $\hat{\theta}_n$ is a consistent estimator of $\theta_n$ (in the sense of Definition (ref)) and $\tau_n$ is a normalizing coefficient. In particular, the smooth function model (see, e.g., Lahiri:03:Resampling and Hall:92:Bootstrap) falls into this case. The resampling version of the statistic $T_n$ is \[ T_n^{*}=\tau_n^{*}\left(\phi(\hat{\theta}_n^{*})-\phi(\theta_n^{*})\right), \] where $\theta_n^{*}$ is a consistent estimator of $\theta_n$, which may differ from $\hat{\theta}_n$, and $\tau_n^{*}$ is the bootstrap counterpart of $\tau_n$. Let $\xi_n\eqdef \tau_n(\hat{\theta}_n-\theta_n)$ and $\xi_n^{*}\eqdef \tau_n^{*}(\hat{\theta}_n^{*}-\theta_n^{*})$. Consider the linearized statistics
The following result shows that it suffices to find a “smooth” approximation $S_n'$ of the linearized statistics in order to apply Theorem (ref) to this setup. In particular, the result largely depends on the asymptotic behavior of the conditional L\'evy concentration function of $S_n'$. For a random variable $X$, $\epsilon>0$, and a sub-$\sigma$-field $\F\subset\H$ the latter is given by \[ \LC{\epsilon,X\mid \F}\eqdef \sup_{x\in \R}\left(\FD{X}{\F}(\csdot,x+\epsilon)-\FD{X}{\F}(\csdot,x-)\right). \]
Consequently, the continuity of the conditional cdfs of $\seq{S_n'}$ ensures the bootstrap consistency in the sense of Definition (ref).
Similarly to the general case, when $\xi_n$ converges $\CS$-weakly to some random vector $\xi$ and the sequence of parameters $\seq{\theta_n}$ converges a.s.\ to a $\CS$-measurable random variable $\theta$, Lemma (ref) implies that $T_n'$ converges $\CS$-weakly to $\nabla\phi(\theta)^{\top}\xi$. In addition, if the conditional cdf of the latter is (a.s.) continuous, it satisfies assumption (b) of Lemma (ref).
Consider a sequence of network dependent processes $\seq{(Y_n, G_n)}$ satisfying Assumptions (ref), (ref), and (ref). As an application of the results given in the preceding section, we consider the mean of a $Y_n$, $\mu_n\equiv \E[Y_{n,i}\mid \CS]$ which may vary with $n$ but not across $i\in N_n$.\footnote{ It is possible to extend the results of this paper to the case of heterogeneous means as in Goncalves/White:02. However, such a setup makes it difficult to isolate the effect of the structure of underlying networks on the consistency of the proposed bootstrap methods. } The parameter of interest $\mu_n$ is estimated using the sample mean $\bar{Y}_n$ which is a consistent estimator of $\mu_n$ under the assumptions of Theorem (ref). In this section we provide a number of resampling based methods for constructing the asymptotically valid confidence sets for $\mu_n$. In addition, we establish consistency of a restricted version of the smooth function model in which we are interested in $\phi(\mu_n)$ for a continuously differential function $\phi:\R^v\to \R$. When the elements of $Y_n$ have the same marginal conditional distributions given $\CS$, we may consider $\phi(\E[f(Y_{n,1})\mid \CS])$, where $f:\R^v\to \R^w$ is a locally Lipschitz function satisfying (ref) and the domain of $\phi$ is $\R^w$ in this case. Since the process $\seq{f(Y_{n,i}):i\in N_n}$ is $(\L_w,\psi,\CS)$-weakly dependent by Proposition (ref), without loss of generality we examine the first version. In addition, we provide consistent positive semi-definite estimators of $\Sigma_n$.
The corresponding test statistics are given by
where $\norm{\csdot}$ is the Euclidean norm on $\R^v$. Their conditional distributions given $\CS$ are denoted by $\FD{1,n}{}$ and $\FD{2,n}{}$, respectively, and the bootstrap approximations of these distributions are denoted by $\FD{1,n}{*}$ and $\FD{2,n}{*}$. The confidence sets for $\mu_n$ are obtained by test inversion, i.e \[ CS_{n,1-\alpha}\eqdef \left\{\mu\in \R^v: T_{1,n}(\mu)\le c_{n,1-\alpha}^{*}\right\}, \] where $c_{n,\alpha}^{*}(\omega)\eqdef\inf\{x:\FD{1,n}{*}(\omega,x)\ge \alpha\}$ is the conditional $\alpha$-quantile of $\FD{1,n}{*}$. In practice, if the exact distribution of $T_{j,n}^{*}$, $j=1,2$ is not available, it can be replaced with a suitable Monte-Carlo estimator.
First, we suggest a variant of the block bootstrap, which is extensively studied in the time-series and spatial literature. Specifically, we choose the maximal block radius $s_n>0$ and define $n$ overlapping blocks $\{B_{n,1},\ldots,B_{n,n}\}$ with $B_{n,k}\eqdef N_n(k;s_n+1)$. That is $B_{n,k}$ is an $(s_n+1)$ open neighborhood of the node $k$. Then we randomly select $K_n\eqdef \floor{n/\delta_n(s_n)}$ blocks $\{B_{n,1}^{*},\ldots,B_{n,K_n}^{*}\}$ with replacement (note that $\delta_n(s_n)$ is the average block size) which yields a bootstrap sample \[ Y_n^{*}=\big\{Y_{n,B_{n,k}^{*}}:1\le k\le K_n\big\}. \] Formally, let $\{u_1,\ldots,u_{K_n}\}$ be i.i.d.\ $U\{1,n \}$ random variables defined on $(\Omega,\H,\PM)$ and independent of $\G_n$. Then the $k$-th resampled block is defined as $B_{n,k}^{*}=B_{n,u_k}$ and, therefore, for $1\le k\le K_n$ and $1\le l\le n$, $\PR{B_{n,k}^{*}=B_{n,l}\mid \G_n}=n^{-1}$ a.s. For the ease of exposition we assume that $n/\delta_n(s_n)$ is an integer.
The size of the bootstrap sample $L_n\eqdef\sum_{k=1}^{K_n}\abs{B_{n,k}^{*}}$ is random conditional on the data and depends on the distribution of $\abs{N_n(\csdot;s_n)}$ given the network $G_n$. However, on average it is expected to be close to $n$, (in fact, the conditional expectation of $L_n$ given $\CS$ is exactly $n$). Also in the time series case this approach reduces to a variant of the moving blocks bootstrap with unequally sized blocks such that blocks located near the endpoints have smaller size.
Let $Z_{n,k}^{*}\eqdef\sum_{j\in B_{n,k}^{*}}Y_{n,j}$ and let $\tilde{Y}_n^{*}\eqdef n^{-1}\sum_{k=1}^{K_n}Z_{n,k}^{*}$ be the quasi-average of the bootstrap sample $Y_n^{*}$, which replaces the sample average in the bootstrap versions of $T_{1,n}$ and $T_{2,n}$. We could also consider the true average of a pseudo-sample, i.e., $\bar{Y}_n^{*}\eqdef L_n^{-1}\sum_{k=1}^{K_n}Z_{n,k}^{*}$. However, $L_n$ is not independent of the blocks sums and, as mentioned before, its distribution depends on the underlying network topology. As a result, it is relatively difficult to find a “smooth” approximation of the distribution of $\sqrt{L_n}\bar{Y}_n^{*}$ which guarantees the first-order consistency of the bootstrap (in particular, the suggested resampling scheme may not be appropriate in this case). In addition, since the conditional expectation of $\tilde{Y}_n$ given $\G_n$ differs from the sample average, we replace the true parameter $\mu_n$ with $\mu_n^{*}\eqdef \E[\tilde{Y}_n^{*}\mid \G_n]$. As indicated in Lahiri:92 in the time-series context, replacing $\mu_n$ with $\bar{Y}_n$ introduces an additional bias which does not allow for second-order improvements over the normal approximation Lahiri:03:Resampling. The BB counterparts of the test statistics in (ref) are given by
The conditional variance of the scaled sample mean $\Sigma_n$ can be estimated using the bootstrap version $\Sigma_n^{*}\equiv \Var(\sqrt{n}\tilde{Y}_n^{*}\mid \G_n)$. Since $\{Z_{n,1}^{*},\ldots,Z_{n,K_n}^{*}\}$ are conditionally independent given $\G_n$, \[ \Sigma_n^{*}=\frac{1}{\delta_n(s_n)}\left(\frac{1}{n}\sum_{i\in N_n}Z_{n,i}Z_{n,i}^{\top}-\bar{Z}_n\bar{Z}_n^{\top}\right) \qtext{a.s.}, \] where $Z_{n,i}\eqdef \sum_{j\in B_{n,j}}Y_{n,j}$ and $\bar{Z}_n\eqdef n^{-1}\sum_{i\in N_n}Z_{n,i}$. By construction the matrix $\Sigma_n^{*}$ is positive semidefinite and its form is similar to the network HAC estimator (ref). To see this let
(when $i=j$ we denote this quantity by $\omega_n(i)$). Then \[ \Sigma_n^{*}=\frac{1}{n}\sum_{i,j\in N_n}\omega_n(i,j)(Y_{n,i}-\mu_n)(Y_{n,j}-\mu_n)^{\top}+R_n \qtext{a.s.}, \] where $\E[\norm{R_n}_F\mid \CS]\to 0$ a.s.\ under some conditions, given later. It is worth mentioning that when $\mu_n=0$ a.s., the remainder term $R_n=0$ a.s. Unlike a typical kernel, the weighting functions $\omega_n(\csdot,\csdot)$ depends on the network topology and it is not bounded by $1$. However, for fixed $i\in N_n$ it is decreasing in the distance between $i$ and $j$. Let $\tilde{\omega}\eqdef \sup_{n}\max_{i\ne j}\omega_n(i,j)$, $\tilde{\mu}_p\eqdef\sup_{n,i\in N_n}\norm{Y_{n,i}}_{\CS,p}$ for $p>0$, and
which is the $k$-th absolute central moment of the sizes of the $(s+1)$-neighborhoods. The following assumptions provide sufficient conditions for the consistency of $\Sigma_n^{*}$.
Assumption (ref) imposes restrictions on admissible networks topologies. Specifically, the consistency of $\Sigma_n^{*}$ requires a certain degree of homogeneity of the resampled blocks which is characterized by various moments of the weights $\seq{\omega_n(i,j):i,j\in N_n}$. For example, condition $(a)$ requires that the sample variance of $\{\abs{B_{n,i}}\}$ increases at a lower rate than the average block size. It also guarantees that $\mu_n^{*}$ is a consistent estimator of the mean $\mu_n$ and that for large samples the size of a pseudo-sample, $L_n$ is close to $n$. In fact, $\E[\abs{L_n/n-1}\mid \CS]\to 0$ a.s.\ because
This condition is clearly satisfied in the time series context when $s_n=o(\sqrt{n})$ (although, it has been shown that the consistency of the moving block bootstrap in this case holds for $s_n=o(n)$ Calhoun:18). However, it does not hold for unweighted “star” networks and $s_n\equiv 1$ because $\Delta_n(1;2)\ge [\Delta_n(1;1)]^2\to 4$ and $\delta_n(1)\to 3$ as $n\to \infty$. In practice, one can compute $\Delta_n(s_n;2)$ for a given graph to see whether this quantity is small relative to the average block size.
Condition (c) ensures that all the non-zero autocovariances are estimated consistently. It is similar to an assumption on kernel functions used in HAC estimation, that is in the limit the value of a kernel at each $s$ must converge to 1. In addition, if $\tilde{\gamma}_s>0$ with positive probability for all $s\ge 1$, then the parameter $s_n$ must go to infinity for this condition to hold.
The conditions of Assumption (ref) are similar to those needed for the consistency of the network HAC estimator (ref). In particular, condition (b) gives a rule of thumb for the choice of the truncation parameter $s_n$ (see \citealiasp{Kojevnikov/Marmer/Song:20}, Section 4.1). Also condition (a) implies that the elements of the true variance $\Sigma_n$ do not diverge to $\pm\infty$. To see this note that for $1\le k,l\le v$ and some constant $C>0$, \[ \abs{[\Sigma_n]_{kl}}\le C(\tilde{\mu}_{2r}^2\vee 1)\left(1+\sum_{s\ge 1}\delta_n^{\partial}(s)\gamma_{n,s}^{1-\frac{2}{r}}\right) \qtext{a.s.} \] Therefore, $\limsup_{n\ge 1}\abs{[\Sigma_n]_{kl}}<\infty$ a.s.
The result of Proposition (ref) implies that $\Sigma_n^{*}$ is a consistent estimator of $\Sigma_n$. Therefore, assuming that $\Sigma_n\to \Sigma$ a.s.\ and $\sqrt{n}(\bar{Y}_n-\mu_n)$ converges $\CS$-weakly to a conditionally normal random vector with variance $\Sigma$, we may use Corollaries (ref) and (ref) to establish the consistency of the bootstrap distributions. For example, one may employ Theorem 3.2 in \citealias{Kojevnikov/Marmer/Song:20} together with the Cram\'er–Wold device and Lemma (ref).
In addition, we introduce the local versions of some measures of the network denseness. Specifically, for $s,m\ge 0$ we define
These measures are constructed in a way such that for any $m\ge 0$, $\delta_{loc,n}^{\partial}(0,m)=h_{loc,n}(0,m)=1$. Also note that $h_{loc,n}(s,m)\le \delta_{loc,n}^{\partial}(s,m)$.
When the following summability condition holds: \[ \limsup_{n\to\infty}\sum_{s\ge 1}\delta_{loc,n}^{\partial}(s,s_n)\gamma_{n,s}^{1-\frac{2}{p}}<\infty \qtext{a.s.}, \] Assumption (ref) reduces to $\delta_n^{5/2}(s_n)/n\to 0$ a.s. In particular, if for each $n\ge 1$ the blocks $\seq{B_{n,k}}$ have the same size $l_n<n$, it suffices to assume that the weak dependence coefficients raised to the power $1-2/p$ are a.s.\ summable and $l_n=o(n^{2/5})$. Note that this assumption also explicitly requires $K_n\to\infty$ as $n\to\infty$.
The dependent wild bootstrap for time-series was introduced in Shao:10. This method approximates the finite-sample distribution of $T_n$ by mimicking the autocovariance structure of the underlying sample. In particular, adapting to our framework, assume that $\CS=\{\emptyset,\Omega\}$ and let $G_n$ be an unweighted “line” network. Consider an $n$-dimensional, zero mean random vector $W_n$ defined on $(\Omega,\H,\PM)$ and independent of $Y_n$ such that $\Var(W_{n,i})=1$ and $\Cov(W_{n,i},W_{n,j})=\kappa(d_n(i,j)/(s_n+1))$, where $\kappa(\csdot)$ is a positive-definite kernel function and $s_n$ is a bandwidth parameter. The DWB pseudo-sample $Y_n^{*}$ is defined as follows: \[ Y_{n,i}^{*}=\bar{Y}_n+(Y_{n,i}-\bar{Y}_n)W_{n,i},\quad i\in N_n. \]
Let $\bar{Y}_n^{*}\eqdef n^{-1}\sum_{i\in N_n}Y_{n,i}^{*}$. By construction, $\E[\bar{Y}_n^{*}\mid \G_n]=\bar{Y}_n$ so that in contrast to the block bootstrap, the statistic $\sqrt{n}(\bar{Y}_n^{*}-\bar{Y}_n)$ is unbiased given $\G_n$. In addition, noticing that $\kappa(0)=1$, the conditional variance of the scaled bootstrap mean given $\G_n$ is
which is a version of the network HAC estimator (ref). Then under certain regularity conditions the DWB is first-order consistent for smooth functions of the mean.
For general graphs, however, positive definiteness of the kernel function $\kappa$ does not imply that the matrix $[\kappa(d_n(i,j)/(s_n+1))]_{i,j\in N_n}$ is positive semi-definite (see \citealiasp{Kojevnikov/Marmer/Song:20}, Section 4.1). Therefore, in general, we cannot guarantee the existence of a random vector with the required covariance structure. A simple way to overcome this issue is to rely on the topology of a given network. Consider the matrix $\Omega_n=[\omega_n(i,j)]_{i,j\in N_n}$, where $\omega_n$ is defined in (ref).
Consequently, we consider a random vector $W_n$ satisfying the following assumption.
Under Assumption (ref) the bootstrap variance estimator given by
is positive semi-definite. We impose the next conditions on the sequence of networks, which in combination with Assumption (ref), ensure the consistency of $\Sigma_n^{*}$.
The conditions given in Assumption (ref) are clearly weaker than those needed for the consistency of the BB variance estimator, which follows from the fact that $\Delta_n(s_n;1)\le \sqrt{\Delta_n(s_n;2)}$ and $\delta_n(s_n)\le n$. Therefore, the DWB estimator (ref) is likely to be consistent for a wider class of networks. As in the case of the block bootstrap we assume that the true variance $\Sigma_n$ converges a.s.\ to a $\CS$-measurable matrix $\Sigma$.
First, we consider the Gaussian case. That is, we take $W_n=\Omega_n^{1/2}\zeta_n$, where $\zeta_n$ is the standard normal random vector in $\R^n$ independent of $\G_n$. From the practical perspective it is a convenient choice, especially when $n$ is large because a sample from a multivariate normal distribution can be easily generated. Moreover, efficient algorithms for finding the square root of positive semidefinite matrices are available. We refer to Higham:08:FM for details. As noted in Shao:10, although the DWB sample with Gaussian weights may not match non-zero higher-order cumulants of the original process, it is difficult to choose the joint distribution of $W_n$ that fits those cumulants, and performance of the DWB primarily depends on the choice of the truncation parameter $s_n$.
In this case, conditionally on $\G_n$, the statistic \[ \sqrt{n}(\bar{Y}_n^{*}-\bar{Y}_n)=\frac{1}{\sqrt{n}}\sum_{i\in N_n}W_{n,i}(Y_{n,i}-\bar{Y}_n) \] is also normal with zero mean and variance given in (ref). Therefore, the conditional distribution of the DWB counterpart of the test statistic $T_{1,n}$, \[ T_{1,n}^{*}=\sqrt{n}\norm{\bar{Y_n}^{*}-\bar{Y}_n} \] given $\G_n$ is known and is the same as the conditional distribution of the asymptotic Gaussian approximation $\normin{\Sigma_n^{*1/2} \eta}$, where $\eta$ is as $v$-dimensional standard normal random vector independent of $\G_n$, and the latter converges $\CS$-weakly to $\normin{\Sigma^{1/2}\eta}$ by Lemma (ref). A more interesting case, however, arises when considering the second test statistic $T_{2,n}$ because for nonlinear transformations the conditional distribution of its bootstrap analog, \[ T_{2,n}^{*}=\sqrt{n}\left(\phi(\bar{Y_n}^{*})-\phi(\bar{Y}_n)\right), \] is typically unavailable. Then in the Gaussian case the DWB is consistent without any further restriction on the topology of the sequence of networks $\seq{G_n}$. We only need to assume that $\sqrt{n}(\bar{Y}_n-\mu_n)$ converges $\CS$-weakly to a conditionally normal random vector and the asymptotic variance of $T_{2,n}$ is a.s.\ positive.
Given another choice of $W_n$, the process $\arr{\xi_{n,i}\eqdef W_{n,i}(Y_{n,i}-\bar{Y}_n):i\in N_n}$ is $s_n$-dependent conditionally on $\G_n$, i.e., $\xi_{n,i}$ and $\xi_{n,j}$ are conditionally independent given $\G_n$ whenever $j\notin B_{n,i}\eqdef N_n(i;s_n+1)$. Consequently, in addition to the assumptions of Proposition (ref), we need to control the behavior of the third conditional moments of $W_n$ and the neighborhoods $\seq{B_{n,i}}$ such that the bootstrap distributions $\FD{1,n}{*}$ and $\FD{2,n}{*}$ in this case approach ones under the Gaussian weights as $n\to \infty$.
Nonparametric bootstrapping for time series and spatial processes has been extensively studied in the past decades. Thus, various resampling methods are now available for statistical analysis of dependent data in these cases. However, the lack of regular structure in networks renders the use of these techniques for bootstrap-based inference in the case of network dependent processes impracticable. In this paper we proposed a block-based method and a variant of the dependent wild bootstrap suitable for the latter processes satisfying the conditional version of Doukhan/Louhichi:99's $\psi$-weak dependence condition. We established the first-order validity of these methods to construct confidence sets for the mean of a network dependent process. In addition, we showed their consistency under the smooth function model conditionally on a common shock of a general form. Finally, the corresponding bootstrap variance estimators can be used for asymptotic inference instead of the network HAC estimator, which is not necessarily positive semi-definite.
As for the future directions, having a continuity theorem and other related results similar to ones established in Belyaev:00 but under convergence in conditional probability would significantly weaken the bootstrap consistency conditions derived in this paper. In addition, an extension of these methods for bootstrapping $M$-estimators and empirical processes is of great importance for applied research.