Multivariate Dependence Testing · Tutorial 447 of 975

Exact Permutation Tests for Independence

You will derive the invariance behind exact permutation tests and use it to calculate distance-covariance and HSIC permutation p-values.

Advanced 12 min read

What You'll Learn

State the iid sampling and independence assumptions that justify permuting one variable.
Prove finite-sample validity of the permutation upper-tail p-value, including when statistics have ties.
Construct permutation statistics for biased sample distance covariance and HSIC.
Calculate exact permutation p-values by enumerating all index permutations.
Interpret discrete p-values and recognize when permutation validity does not apply.

Why Permuting One Variable Can Test Independence

A paired sample records $n$ observations $(X_i,Y_i)$, where each pair links a value of $X$ to a value of $Y$. To test whether the variables are independent, one can keep the observed $X$'s fixed and rearrange the $Y$'s among them. Under independence, the original matching has no special status: the data distribution is unchanged by any such rearrangement. This symmetry, rather than a large-sample approximation, is the reason the resulting test can be valid in finite samples.

The argument requires independent and identically distributed pairs and the null hypothesis $X\perp Y$. It does not require continuous variables, normality, or a particular choice of dependence statistic. Ties are allowed, although they can make the test conservative at a chosen significance level.

Definition: Let $(X_1,Y_1),\ldots,(X_n,Y_n)$ be iid pairs, and let $T$ be a real-valued statistic where larger values count as stronger evidence against independence. For a permutation $\pi$ of $\{1,\ldots,n\}$, define $T_\pi=T(X_1,\ldots,X_n;Y_{\pi(1)},\ldots,Y_{\pi(n)})$. The full-permutation upper-tail p-value is $$ p=\frac{1}{n!}\sum_{\pi} \mathbf{1}\{T_\pi\geq T_{\mathrm{id}}\}, $$ where $\mathrm{id}$ is the identity permutation. The comparison includes equality, so tied statistics contribute to the tail.

The Finite-Sample Validity Argument

Under the null $X\perp Y$, the vector $(X_1,\ldots,X_n)$ is independent of $(Y_1,\ldots,Y_n)$. The $Y_i$'s are iid, so their joint distribution is invariant under index permutations. Consequently, the distribution of the full data is unchanged if the $Y$ indices are permuted while the $X$'s remain fixed. The next result turns this invariance into a p-value guarantee.

Theorem: Suppose the paired observations are iid and $X\perp Y$. For any measurable real-valued statistic $T$, the full-permutation p-value defined above satisfies $$ P(p\leq \alpha)\leq \alpha \qquad \text{for every } 0\leq\alpha\leq 1. $$ This holds without a continuity assumption on the data or on the distribution of $T$.

Proof. Fix a possible data set and form its orbit by applying all $n!$ permutations to its $Y$-indices. The orbit is the set of distinct permuted data sets. Under the null, the full data distribution is invariant under every such permutation. Conditional on an orbit, the observed data point is therefore uniform over the distinct points in that orbit.

To account for repeated points caused by tied $Y$-values, consider instead the list of all $n!$ permutations, with repetitions retained. Every distinct orbit point occurs the same number of times: if one permutation produces that point, exactly the permutations in a coset of its stabilizer produce it. Thus, choosing a uniformly random permutation from the list gives the same relative frequencies as choosing a uniformly random point from the orbit.

Now sort the $n!$ statistic values from smallest to largest, retaining ties. For any value in this list, its upper-tail fraction is the number of list entries greater than or equal to it, divided by $n!$. Among list entries whose upper-tail fraction is at most $\alpha$, there can be no more than $\lfloor \alpha n!\rfloor$ entries: those entries must lie among the last $\lfloor \alpha n!\rfloor$ positions, and ties can only increase their upper-tail fractions. Hence, conditional on the orbit, the probability that the observed entry has p-value at most $\alpha$ is at most $\lfloor \alpha n!\rfloor/n!\leq\alpha$. Averaging over orbits proves the stated bound. $\square$

The result gives finite-sample control: rejecting when $p\leq\alpha$ has null rejection probability no greater than $\alpha$. It need not equal $\alpha$. The finite set of permutations and tied statistic values often make the p-value discrete. In particular, the smallest possible full-permutation p-value is at least $1/n!$, because the identity permutation is always counted in its own upper tail.

Applying the Argument to Distance Covariance

For observed vectors $X_1,\ldots,X_n$ and $Y_1,\ldots,Y_n$, let $D^X_{ij}$ and $D^Y_{ij}$ be their pairwise Euclidean distances. Define the doubly centered distance matrices $$ A=HD^XH,\qquad B=HD^YH,\qquad H=I_n-\frac{1}{n}\mathbf{1}\mathbf{1}^{\mathsf T}. $$ Here $\mathbf{1}$ is the $n$-vector of ones. A common nonnegative dependence statistic is the biased sample squared distance covariance $$ T_{\mathrm{dCov}}=\frac{1}{n^2}\sum_{i=1}^n\sum_{j=1}^n A_{ij}B_{ij}. $$

For a permutation $\pi$, recompute the matching by pairing $X_i$ with $Y_{\pi(i)}$. If $P_\pi$ is the permutation matrix, the permuted centered distance matrix is $P_\pi B P_\pi^{\mathsf T}$. The statistic on that rearrangement is $n^{-2}\sum_{i,j} A_{ij}(P_\pi B P_\pi^{\mathsf T})_{ij}$. Thus the validity theorem applies to the upper tail of these $n!$ values under iid sampling and independence.

Worked Example: Exact Distance-Covariance Test With Three Observations

Take scalar observations $X=(0,1,2)$ and $Y=(0,1,2)$, and use the biased squared distance-covariance statistic. The distance matrix for either sample is $$ D=\begin{pmatrix}0&1&2\\1&0&1\\2&1&0\end{pmatrix}. $$ Each row mean is $1$, and the grand mean is $8/9$. Double-centering gives $$ A=B=\frac{1}{9}\begin{pmatrix}-10&-1&8\\-1&-10&-1\\8&-1&-10\end{pmatrix}. $$ For the observed matching, the sum of squared entries in the numerator is $(300+132)/81=16/3$: the diagonal contributes $3(100)/81$, and the off-diagonal entries contribute $2(1+1+64)/81$. Therefore $T_{\mathrm{dCov}}=(16/3)/9=16/27$.

There are six permutations. The centered distance matrix has its unique larger off-diagonal pair at the two indices assigned the endpoint values 0 and 2. Two permutations preserve that pair, giving statistic $16/27$. In each of the other four permutations the larger pair differs; the numerator is $(300-30)/81=10/3$, giving statistic $10/27$. The exact upper-tail p-value is therefore $2/6=1/3$. At level $0.05$, this test does not reject independence.

Applying the Argument to HSIC

Let $K$ and $L$ be Gram matrices from fixed positive semidefinite kernels on the observed $X$'s and $Y$'s. With the same centering matrix $H$, the biased sample HSIC statistic is $$ T_{\mathrm{HSIC}}=\frac{1}{n^2}\operatorname{tr}(KHLH) =\frac{1}{n^2}\sum_{i,j}(HKH)_{ij}(HLH)_{ij}. $$ When $Y$ is permuted, $L$ is replaced by $P_\pi L P_\pi^{\mathsf T}$, and HSIC is recalculated. This is a statistic of the permuted paired sample, so the same finite-sample result applies. Kernel choices or preprocessing based on the separate $X$- and $Y$-marginal samples are compatible with the argument when they do not depend on the original pairing.

Worked Example: HSIC With a Linear Kernel

Let $n=3$, $X=(-1,0,1)$, and $Y=(-1,0,1)$, and use the scalar linear kernel $k(u,v)=uv$ for both variables. The centered vectors already have mean zero. For any matching, the linear-kernel Gram matrices are $xx^{\mathsf T}$ and $y_\pi y_\pi^{\mathsf T}$, so the HSIC statistic is $$ T_\pi=\frac{(x^{\mathsf T}y_\pi)^2}{n^2}. $$ The six permutations give dot products $2,-2,1,1,-1,-1$. For example, the matching $(-1,1,0)$ gives $(-1)(-1)+0(1)+1(0)=1$, while the reversed matching gives $(-1)(1)+0(0)+1(-1)=-2$. Thus two statistics equal $4/9$, and four equal $1/9$. The observed matching has statistic $4/9$, so its exact upper-tail p-value is $2/6=1/3$.

Worked Example: Permutation Resolution for a Four-Point HSIC Test

Take $X=Y=(-3,-1,1,3)$ and again use the scalar linear kernel. Both vectors are centered, so $T_\pi=(x^{\mathsf T}y_\pi)^2/16$. To enumerate the dot products, group permutations by their ordered endpoint values $(y_{\pi(1)},y_{\pi(4)})=(a,d)$. The two remaining values $b,c$ can occupy the middle positions in either order, producing $$ x^{\mathsf T}y_\pi=-3a-b+c+3d=3(d-a)+(c-b). $$ For endpoint pairs $(-3,-1),(-3,1),(-3,3)$, the two dot products are respectively $(8,4),(16,8),(20,16)$. For $(-1,-3),(-1,1),(-1,3)$, they are $(-4,-8),(12,0),(16,8)$. For $(1,-3),(1,-1),(1,3)$, they are $(-8,-16),(0,-12),(8,4)$. For $(3,-3),(3,-1),(3,1)$, they are $(-16,-20),(-8,-16),(-4,-8)$. These are all 24 permutations.

Only two dot products have squared value $400$, namely $20$ and $-20$. The observed matching has dot product $20$ and statistic $400/16=25$, so its exact p-value is $2/24=1/12$. It rejects at level $0.10$, but not at level $0.05$. This illustrates why an exact test’s attainable p-values are discrete rather than a continuous range.

Conditions, Ties, and Common Mistakes

The essential condition is invariance under the proposed permutations. Iid paired observations and $X\perp Y$ guarantee that invariance for unrestricted permutations of the $Y$-indices. If observations have a clustered, temporal, or otherwise structured dependence, arbitrary permutations may not preserve the null distribution; the permutation scheme must respect the sampling design. That issue is distinct from the independent-pairs argument proved here.

A frequent error is to assume that a permutation test is valid merely because the statistic is recalculated many times. The number of rearrangements does not establish validity. Validity comes from the null distribution being invariant under the rearrangements used. Another error is to count only permutations with $T_\pi>T_{\mathrm{id}}$. The upper-tail p-value uses $\geq$; omitting equal values can make the test anti-conservative, particularly when data or statistics have ties. If only a random subset of permutations is drawn, the resulting Monte Carlo procedure is not the full enumeration above; its p-value calculation must account for the observed arrangement and the sampling scheme.

Key takeaway: Under iid sampling and independence, permuting one variable leaves the joint data distribution invariant. The resulting full-permutation upper-tail p-value is finite-sample superuniform for any measurable statistic, including distance covariance and HSIC, with ties handled by counting equality.

Check Your Understanding

Use the invariance argument and calculations above to answer the following.

Which sampling and null assumptions justify unrestricted permutations of the $Y$-indices?
Why does the upper-tail definition count permutations for which $T_\pi=T_{\mathrm{id}}$?
For $n=3$, what is the smallest possible full-permutation p-value, and why?
In the linear-kernel HSIC example with $n=3$, how many permutations attain the observed maximum statistic?
Why does the fact that a statistic is recalculated for every permutation not, by itself, guarantee a valid test?

Back to Tutorials