Halfspace Depth and Tukey Location Tests

Why Halfspace Depth Gives a Location Test

A multivariate location is difficult to assess by looking in just one direction: a candidate can appear central in one projection and extreme in another. Halfspace depth turns this directional idea into a single number. It asks how little probability can lie in any closed halfspace that still contains the candidate. Small depth signals that at least one direction separates the candidate from most of the distribution.

The same construction applied to observed points gives an empirical depth. For testing a proposed location, the depth of that location is a lower-tail statistic: unusually small depth is evidence against the hypothesis. A valid test still needs a specified null model. Below, central symmetry supplies a finite-sample sign-flip calibration.

Population and Empirical Halfspace Depth

Definition: Let $X$ be a random vector in $\mathbb{R}^d$ with distribution $P$. A closed halfspace is a set of the form $H=\{z\in\mathbb{R}^d:u^\mathsf{T}z\ge c\}$, where $u\ne 0$ and $c\in\mathbb{R}$. The halfspace depth of $x\in\mathbb{R}^d$ is $$ D(x;P)=\inf_{H:\,x\in H}P(X\in H). $$ Equivalently, using unit vectors $u$, $D(x;P)=\inf_{\|u\|=1}P\{u^\mathsf{T}X\ge u^\mathsf{T}x\}$. For observations $X_1,\ldots,X_n$, the empirical halfspace depth is $$ D_n(x)=\inf_{\|u\|=1}\frac{1}{n}\sum_{i=1}^n \mathbf{1}\{u^\mathsf{T}X_i\ge u^\mathsf{T}x\}. $$

The directional expression follows because a halfspace with normal $u$ contains $x$ when its threshold is at most $u^\mathsf{T}x$. Raising that threshold to $u^\mathsf{T}x$ can only reduce its probability, so the least probability for that normal is attained by the halfspace whose boundary passes through $x$. The inequality is non-strict: observations on the boundary are counted. This convention matters for distributions with atoms and for empirical depth.

Worked Example: Depth Under a Uniform Distribution on an Interval

Let $X$ be uniform on $[0,1]$. In one dimension, the two directions give the closed rays extending to the left and right of $x$. For $0\le x\le 1$, their probabilities are $P(X\le x)=x$ and $P(X\ge x)=1-x$, so $$ D(x;P)=\min(x,1-x),\qquad 0\le x\le 1. $$

For $x<0$, the ray $(-\infty,x]$ has probability zero; for $x>1$, the ray $[x,\infty)$ has probability zero. Thus $D(x;P)=0$ outside $[0,1]$ as well. In particular, $D(0;P)=D(1;P)=0$, even though both endpoints belong to the convex support $[0,1]$. Zero depth therefore does not, by itself, mean that a point lies outside the convex support; it can also occur at its boundary.

Worked Example: The Center and Boundary of a Uniform Square

Let $X$ be uniform on the square $[-1,1]^2$. At the center $x=(0,0)$, every halfspace containing $x$ has probability at least $1/2$. To see this, write it as $\{z:u^\mathsf{T}z\ge c\}$, with $c\le 0$. It contains $\{z:u^\mathsf{T}z\ge 0\}$. The square is centrally symmetric, and the line $u^\mathsf{T}z=0$ has probability zero, so this latter halfspace has probability $1/2$. Taking $c=0$ attains that probability. Hence $D((0,0);P)=1/2$.

At $x=(1,0)$, the halfspace $\{z:z_1\ge 1\}$ contains $x$, but its intersection with the square has probability zero. Therefore $D((1,0);P)=0$. This is another boundary point of the convex support with zero depth.

Worked Example: Empirical Depth at a Triangle’s Centroid

Take three observations $X_1=(0,0)$, $X_2=(2,0)$, and $X_3=(0,2)$, and let $x=(2/3,2/3)$, their centroid. For any unit vector $u$, write $a_i=u^\mathsf{T}X_i$. Since $u^\mathsf{T}x=(a_1+a_2+a_3)/3$, at least one $a_i$ is greater than or equal to $u^\mathsf{T}x$; otherwise their average would be smaller than itself. Thus every halfspace through $x$ in the directional definition contains at least one observation, giving $D_3(x)\ge 1/3$.

For $u=(1,1)/\sqrt{2}$, the projections of the observations are $0,\sqrt{2},\sqrt{2}$, and the projection of $x$ is $2\sqrt{2}/3$. Exactly two observations have projection at least that of $x$, giving a count of two, not the minimum. Instead choose $u=(-1,-1)/\sqrt{2}$: the projections are $0,-\sqrt{2},-\sqrt{2}$, and the projection of $x$ is $-2\sqrt{2}/3$. Only the observation with projection $0$ is counted, so this direction gives a count of one. The direction $u=(1,-1)/\sqrt{2}$ has projections $0,\sqrt{2},-\sqrt{2}$, while $u^\mathsf{T}x=0$, so it counts two observations under the closed-boundary convention. The direction $u=(-1,-1)/\sqrt{2}$ gives a count of one, and the average-projection argument above guarantees a count of at least one in every direction. Thus $D_3(x)=1/3$.

Affine Equivariance

Halfspace depth respects nonsingular changes of coordinates, a useful property when the variables have different scales or are expressed in a different basis.

Theorem: Let $A$ be a nonsingular $d\times d$ matrix and $b\in\mathbb{R}^d$. If $Y=AX+b$, with distribution $P_Y$, then $$ D(Ax+b;P_Y)=D(x;P). $$ The same identity holds for empirical depth when every observation and the candidate point are transformed by $z\mapsto Az+b$.

Proof. The map $z\mapsto Az+b$ is a bijection. It takes each closed halfspace to a closed halfspace: for example, $u^\mathsf{T}z\ge c$ becomes $(A^{-\mathsf{T}}u)^\mathsf{T}(Az+b)\ge c+(A^{-\mathsf{T}}u)^\mathsf{T}b$. Conversely, every halfspace in the transformed coordinates is the image of a halfspace in the original coordinates, since $A$ is nonsingular. The halfspaces containing $x$ therefore correspond exactly to the halfspaces containing $Ax+b$. Corresponding halfspaces have equal probabilities under the transformed distribution, so their infima agree. The empirical argument is the same, with probabilities replaced by proportions of observations. $\square$

A Tukey-Depth Sign-Flip Test of Location

Suppose $X_1,\ldots,X_n$ are independent observations from a common location model $X_i=\theta+\varepsilon_i$, where the errors are centrally symmetric about zero: $\varepsilon_i$ and $-\varepsilon_i$ have the same distribution. To test $H_0:\theta=\theta_0$, form residuals $Y_i=X_i-\theta_0$. Under the null, the residuals are independent and centrally symmetric. Assume also that $P(Y_i=0)=0$; this avoids sign ambiguity at zero.

Definition: The Tukey-depth statistic for testing $H_0:\theta=\theta_0$ is $T(Y)=D_n(\theta_0;X_1,\ldots,X_n)$, the empirical halfspace depth of the hypothesized location among the observations. Equivalently, it is the minimum, over unit vectors $u$, of the fraction of residuals satisfying $u^\mathsf{T}Y_i\ge 0$. Small values indicate that some direction places few observations on the side of the hypothesized location.

The null calibration uses all $2^n$ sign patterns. For $s=(s_1,\ldots,s_n)\in\{-1,1\}^n$, compute $T(s_1Y_1,\ldots,s_nY_n)$. The lower-tail sign-flip p-value is $$ p(Y)=2^{-n}\sum_{s\in\{-1,1\}^n}\mathbf{1}\{T(s_1Y_1,\ldots,s_nY_n)\le T(Y_1,\ldots,Y_n)\}. $$ Reject when $p(Y)\le\alpha$. The weak inequality includes ties and makes the test conservative when the statistic has tied values.

Theorem: Under $H_0$, independent central symmetry of the residuals, and $P(Y_i=0)=0$, the sign-flip p-value is super-uniform: $P\{p(Y)\le\alpha\}\le\alpha$ for every $0\le\alpha\le1$. Thus the test has finite-sample size at most $\alpha$.

Proof. Under the null, the joint distribution of $(Y_1,\ldots,Y_n)$ is unchanged by any coordinatewise sign flip. Conditional on the orbit $\{(s_1Y_1,\ldots,s_nY_n):s\in\{-1,1\}^n\}$, the $2^n$ sign patterns are equally likely; the no-zero assumption makes these configurations distinct. List their statistic values in nondecreasing order, retaining ties. For any configuration, its p-value is the fraction of orbit values less than or equal to its own value. If a configuration has p-value at most $\alpha$, its rank position, including all tied values up to that value, is at most $\alpha 2^n$. Consequently no more than $\alpha 2^n$ configurations in the orbit can have p-value at most $\alpha$. Conditional on the orbit, the probability of rejection is therefore at most $\alpha$; averaging over orbits gives $P\{p(Y)\le\alpha\}\le\alpha$. $\square$

Worked Example: Exact Sign-Flip Calibration in One Dimension

Suppose $n=3$, the null value is $\theta_0=1$, and the observed values are $2,3,4$, so the residuals are $1,2,3$. All three observations exceed the null value. The halfspace $(-\infty,1]$ contains none of them, so the observed depth statistic is $T(Y)=0$.

Across the eight sign patterns, the statistic is zero for $+++$ and $---$: in each case, a closed ray through the null contains no observations on one side. In each of the other six patterns, one or two residuals have each sign, and the minimum half-line count is one, giving depth $1/3$. Therefore the lower-tail p-value is $2/8=0.25$. At level $\alpha=0.25$, the test rejects; at level $0.05$, it does not. The calculation also shows why the exact p-value can be coarse for small samples.

Interpretation and Common Pitfalls

This test is exact under its stated symmetry model; it is not a distribution-free test under arbitrary distributions. Central symmetry is the reason sign flips preserve the null distribution. Nor should one assume that the signs of projections in every direction are independent: the test calibrates the minimum over directions by recomputing the entire depth statistic for each sign pattern.

Mistake: treating zero depth as proof that a point is outside the convex support. The uniform distribution on $[0,1]$ has zero depth at $0$, which is in the convex support. Zero depth can occur on its boundary.
Mistake: counting only observations strictly beyond the boundary. Halfspace depth here uses closed halfspaces, so observations on the boundary are included. Changing to open halfspaces can change empirical depths and tests.
Mistake: using a one-dimensional sign-test calibration without accounting for the directional minimum. In multiple dimensions the statistic minimizes over directions. The sign-flip procedure recalculates that minimum for every transformed sample.
Mistake: claiming an exact level for every chosen $\alpha$. Finite sign-flip distributions are discrete. The p-value test is valid at every level, but its rejection probability may be strictly smaller than $\alpha$.

Halfspace depth supplies a geometric measure of how exposed a proposed location is, while sign-flip calibration converts that measure into a test with a transparent finite-sample guarantee. Its practical cost is computation: direct enumeration requires evaluating $2^n$ sign patterns, and the depth calculation itself can be demanding in high dimensions.

Check Your Understanding

Work through these questions using the closed-halfspace convention.

For a uniform distribution on $[0,1]$, calculate the depth at $x=1/4$ and explain why the depth at $x=0$ is zero.
Why does a nonsingular affine transformation preserve halfspace depth?
What is the null assumption that makes the sign-flip test valid?
For three nonzero residuals, how many sign patterns are used in the exact calibration?
Why can the sign-flip p-value be valid even when it is not equal to the nominal significance level?