Ordering-Free Dependence and Resampling
A block bootstrap needs to know which observations belong together. If dependence has no observed ordering, that choice may be unavailable. (Song 2018) instead draws small random subsets and builds a statistic whose randomization law can be controlled when dependence is weak on average.
1. Measure how often dependence matters
The dependence coefficients average over index sets, so relabeling observations changes none of them. This allows assumptions about the frequency of dependence without locating each dependent pair. A time-series mixing coefficient uses different information: separation in a known temporal order.
Write \(X_1,\ldots,X_n\in\mathbb R^p\), suppressing the triangular-array subscript. Start with the case without a common shock. For disjoint nonempty sets \(A_1,A_2\), define
The function classes specify which forms of dependence matter. Take them to be invariant under permutations of their arguments, with square-integrable evaluations; a zero-variance correlation is assigned value zero. The paper uses coordinate monomials up to a fixed degree for its moment arguments.
Let \(\mathcal P(A)\) denote the partitions of \(A\) into two nonempty sets. For \(|A|\ge2\), put
The minimum asks whether there is at least one independent split of the selected set. Such a split makes \(c_n(A)=0\), even if some observations within \(A\) are dependent. It does not compare the set with its complement in the sample. The singleton convention is \(c_n(A)=1\), so decay assertions begin at \(k\ge2\).
To recover the permutation definition, each \(k\)-element set appears as the first \(k\) entries of exactly \(k!(n-k)!\) permutations. Thus
If \(Y_i=X_{\sigma(i)}\), then \(c_n^Y(A)=c_n^X(\sigma(A))\). Since \(A\mapsto\sigma(A)\) is a bijection on the \(k\)-element sets, the last average is unchanged. This is the precise sense in which the coefficient is ordering-free.
The conditional version replaces correlations by correlations given \(\mathcal C_n\). Its mean-inference setup also requires \(\mathbb{E}[X_i\mid\mathcal C_n]=\mu_0\): a common shock cannot shift the mean being tested arbitrarily.
Proposition 1. Suppose \(G_n\) is a dependency graph: whenever two disjoint vertex sets have no edges between them, their observation vectors are independent. If its maximum degree is \(d_n\), then for each fixed \(k\ge2\) and sufficiently large \(n\),
The constant \(C_k\) depends only on \(k\). The same bound holds almost surely for the conditional coefficient when the graph is a conditional dependency graph.
2. Count connected sets correctly
If \(G_n[A]\) is disconnected, its components give a partition without crossing edges. Independence across that partition implies \(c_n(A)=0\). On connected sets, the absolute correlation bound of one gives
The selected vertices need only induce a connected subgraph; they need not form an entire connected component of \(G_n\).
Now count growth orders of distinct vertices. There are \(n\) choices for the root. Once \(j\) vertices have been selected, the next vertex must be adjacent to at least one of them. There are at most \(jd_n\) choices, even before excluding repeated vertices. Therefore
Every connected set has at least one such order: root a spanning tree and list parents before children. A connected set has \(k!\) arbitrary orderings, so the number of ordered distinct tuples inducing a connected graph is at most \(k!\) times the growth-order count. If \((n)_k\triangleq n(n-1)\cdots(n-k+1)\), it follows that
For \(n\ge2k\), every denominator factor is at least \(n/2\), proving the proposition with \(C_k=2^{k-1}k!(k-1)!\). The constant is loose; the exponent of \(n\) is what is needed.
A connected set need not have a path visiting all its vertices. At each stage the new vertex may attach to any earlier vertex; this includes stars and is why the spanning-tree count covers all connected sets.
For \(k=2\), count edges directly to obtain the sharper bound
Lemma 2.2 of the paper gives the analogous \(n^{-(k-1)}\) rate for separated random fields under its spatial summability conditions. That result requires a spatial argument in addition to the graph calculation above.
3. Two calculations with random subsets
First consider independent clusters of sizes \(m_1,\ldots,m_G\). A set meeting two clusters can be split across clusters, so
where \((m)_k=0\) when \(m<k\). This is an equality in the scalar model \(X_i=Z_g\) for every unit in cluster \(g\), with independent, nondegenerate, square-integrable \(Z_g\) and function classes containing coordinate projections. Within one cluster, every partition has correlation one; across clusters there is an independent split.
For equal cluster size \(m\), the first two coefficients are therefore
Bounded clusters give the displayed graph rate. With a fixed number of equal clusters, the coefficients instead approach \(G^{1-k}\). Adding copies within those clusters increases the sample size without reducing the average dependence in the required way.
Second, let \(I_1,\ldots,I_b\) be a uniform draw of distinct indices. Count the graph edges in this subsample:
Each pair is uniform over distinct population indices, giving
Thus \(b^2d_n/n\to0\) suffices for the selected graph to be edgeless with probability tending to one. For any fixed edgeless index set, the observations are mutually independent by the dependency-graph assumption. This calculation makes the small-subsample intuition concrete; the full inference theorem need not require every subsample to be edgeless.
4. Conditional mean and variance of the mean statistic
Assume \(n>1\), \(1\le b<n\), and the sample covariance is nonsingular. Let \(\overline X=n^{-1}\sum_iX_i\) and define
Here \(\mu\) is the candidate mean, and the inverse square root is symmetric. By construction,
Write \(\mathbb{E}_\pi\) and \(\operatorname{Var}_\pi\) for expectation and variance over the random indices conditional on the entire observed sample. For two distinct sampled positions,
Sampling without replacement explains the negative conditional covariance. This identity holds for the fixed observed array and says nothing about the sign of covariance in the original sampling process.
For an independently drawn permutation \(\pi_r\), the paper’s mean contribution is
Its conditional moments follow by counting the \(b\) diagonal terms and \(b(b-1)\) off-diagonal terms:
These are finite-population identities conditional on the data. Dependence assumptions enter later, when controlling how far the observed sample mean is from the null mean.
5. From conditional randomization to a limit theorem
For \(R\) independent permutations, set
Then the squared-mean statistic has the exact decomposition
The two terms have different sources of randomness. Conditional on the data, \(W_n\) fluctuates across repeated subsampling, while \(a\) is fixed. To see the conditional CLT directly, let \(\widetilde M_r=M_r-\mathbb{E}_\pi M_r\) and \(V_n=(n-b)I_p/[p(n-1)]\). A third-order Taylor bound gives, for fixed \(t\in\mathbb R^p\),
Raise this expression to the \(R\)th power, using conditional independence. If \(R\to\infty\), \(b/n\to0\), and \(\mathbb{E}_\pi\|\widetilde M_r\|^3/\sqrt R\to_p0\), the conditional characteristic function approaches \(\exp(-\|t\|^2/(2p))\). Thus \(W_n\) has the conditional Gaussian limit \(\mathcal{N}(0,I_p/p)\).
It remains to control the drift. Under the null, suppose \(\mathbb{E}X_i=\mu_0\) and \(\max_i\mathbb{E}\|X_i-\mu_0\|^2\le C\). A dependency graph leaves at most \(nd_n\) ordered off-diagonal covariance terms. Cauchy–Schwarz then gives
If \(\|\widehat\Sigma^{-1}\|=O_p(1)\), Markov’s inequality implies
Proposition 2. For fixed \(p\), under the moment, covariance, and conditional-CLT premises just stated, \(Rb(1+d_n)/n\to0\) gives
Indeed, the drift is \(o_p(1)\), and \(Rb/n\to0\) also makes the displayed adjustment negligible. Apply the conditional CLT and the continuous mapping theorem to the squared norm. The higher-order dependence conditions in the size and power analysis supply primitive ways to verify the moment premises; conditional independence of the permutations alone would not prove them.
For example, with bounded \(d_n\), \(b_n=\lfloor n^{1/4}\rfloor\) and \(R_n=\lfloor n^{1/2}\rfloor\) give \(R_nb_n/n\asymp n^{-1/4}\). The graph bounds also give \(b_n^k\lambda_n(k)=O(n^{1-3k/4})\) for fixed \(k\ge2\). These choices satisfy the dependence-rate restrictions; the data still need the moment and covariance assumptions.
The conditional moments also show what is learned by increasing \(R\) while holding the data fixed. Write \(c_{n,b}=(n-b)/(n-1)\). For \(S_M(\mu)=\|R^{-1/2}\sum_rM_r(\mu)\|^2\),
The normalization keeps the randomization fluctuation at order one, so the first term stays fixed as repetitions increase. The second term grows with \(R\). Under a conditional Gaussian approximation,
where the argument is the noncentrality parameter. This is a conditional approximation for the given sample, not a finite-sample chi-square identity. It makes the drift visible even under a true null: \(a\) contains the sample mean’s estimation error, which usually is not exactly zero.
For scalar data consisting of \(G\) independent clusters of \(h\) identical copies of a variance-one shock, \(n=Gh\) and \(\operatorname{Var}(\overline X)=1/G=h/n\). Using the population standardizer in this illustration, the mean drift has squared size of order \(Rb/G\). Thus the relevant restriction becomes \(Rb/G\to0\). Doubling the number of copied observations per cluster while holding \(G\) fixed does not help satisfy it. The average-dependence coefficient \((h-1)/(n-1)\) records precisely this lack of new information.
Randomization removes the need to identify where dependent pairs occur. Their overall frequency still determines the sample mean’s error and thus how many repetitions the statistic can tolerate.
6. The quadratic term and the bias adjustments
The off-diagonal statistic makes the same drift appear quadratically. For \(b\ge2\), use the raw contribution
There are \(b(b-1)\) ordered pairs. The preceding covariance identity gives
In particular, even \(U_r(\overline X)\) has conditional mean \(-(b-1)/(n-1)\). Removing diagonal products does not make the raw statistic conditionally centered.
More information comes from comparing the two centerings using the same permutations. Expanding each product, every selected \(Z_{\pi_r(j)}\) appears \(b-1\) times in each cross-term, so
After summing over repetitions,
The linear term has conditional variance
while the second term is a conditional drift. Under the null with bounded degree, these have orders \(O_p(b/n)\) and \(O_p(\sqrt R\,b/n)\), respectively. The second order is for the drift itself, not its variance. This explains why quadratic aggregation leads to a restriction involving \(Rb^2/n^2\).
Finally, the paper subtracts \(Rb/n\) from \(S_M\) and \(\sqrt R(b-1)/n\) from \(S_U\). To see the benchmark behind both corrections, temporarily use the population covariance \(\Sigma\) and independent observations with this covariance. Then
Substitution gives both benchmark adjustments. It averages over independent original observations with a population standardizer, rather than centering exactly conditional on the observed sample. Under dependence, the remaining cross-covariances must be bounded by the rate assumptions.
These identities concern the raw \(U\) statistic and its drift; a Gaussian limit additionally requires its variance normalization and higher-order moment control. The simpler resampled mean and pair statistics make a related tradeoff with a different subsampling construction.
7. What ordering-free does not mean
The procedure therefore replaces knowledge of the dependence locations with a restriction on average dependence. An unrestricted common shock affecting most observations does not satisfy the information requirement merely because subsamples are drawn at random.
Repeated subsampling retains the same full-sample mean error. Its contribution grows with the repetition count, as the two decompositions show. Repetition can therefore improve detection of a false mean only within rates that keep this error negligible under the null.