Permutation p-values
(WIP, personal notes)

I need to clarify permutation tests in their diverse forms, and how to best prove their p-values. For this, I need also to look at order statistics in more details.

TODO:

• Talk about $π_l,π_r$ and the bisided $π_b$
• Clarify equality almost surely in claim 1
• Talk about the applications for hypothesis testing
• Cover all TODOs.

Order vectors

If $x = (x_0,…,x_n)$ is a vector, let $o(x) = x_{()}$ its order vector. TODO:

• Definition
• It is well-defined
• invariance under permutations
• different counting (in)equalities needed later: it’s easier if we wlog assume that the vector is already sorted. Prove that this is OK to do.

Claim B

For a vector $t = (t_0,…,t_m)$, and any $x∈ℝ$: $$x>t_{(k)}\quad ⇔\quad  ♯\{i: x > t_i\} ≥ k+1.$$

Proof of claim B.

TODO!!

Claim A

For a vector $t = (t_0,…,t_m)$ $$♯\{i: t_0 ≤ t_i\} ≤ k \quad ⇔\quad t_0 > t_{(m-k)}$$

Proof of claim A

$$\begin{aligned} &♯\{i: t_0 ≤ t_i\} ≤ k \\ ⇔ \quad &♯\{i: t_0 > t_i\} ≥ (m+1)-k \quad & \text{( $\{i:t_0>t_i\}⊔\{i:t_0≤t_i\}=\{0,…,m\}$)} \\ ⇔ \quad &t_0 > t_{(m-k)} \quad & \text{([claim B])} \\ \end{aligned}$$

Order statistics

An order statistics is the order vector associated to a random vector. TODO:

• It is measurable
• something else?

Finite group of permutations

Let $G$ be a finite group and $U(G)$ the uniform distribution on $G$. Assume that $G$ acts on some space $𝓧$.

Claim G2

If $X$ is a random variable with value in $𝓧$, then the following are equivalent:

• $gX ∼ X$ for all $g∈G$;
• $gX ∼ X$, with $g∼U(G)$ independent from $X$.

Claim G1

Fix $g,g_1,…,g_m$ random elements of $G$.

• If $g ∼ U(G)$, then $g⁻¹ ∼ U(G)$ and $gg_1, g_1g ∼ U(G)$.
• $g$ is independent from $(g_1,…,g_m)$ iff it is independent from $(g_1g,…,g_mg)$.
• $(g_1,…,g_m)$ is independent iff $(g_1g,…,g_mg)$ is independent
• In particular, $(g,g_1,…,g_m)$ is independent iff $(g,g_1g,…,g_mg)$ is.¹

Proof of Claim G1

TODO $$P(g = a, g_ig = a_i ∀i≥1) = P(g=a, g_i = a⁻¹a_i ∀i≥1) = P(g=a) ∏_i P(g_i = a⁻¹a_i) = P(g=a) ∏_i P(g_ia = a_i) = P(g=a) ∏_i P(g_ig = a_i) … ?$$

Permutation tests

Let $T = (T_0,…,T_m)$ be a random vector, and let $T_{()} = (T_{(0)},…,T_{(m)})$ its order statistics²

Consider the following condition, call it (C): $$∀i,j,k:\ P(T_i ≤ T_{(k)}) = P(T_j ≤ T_{(k)}).$$

Recall also that $T$ is called exchangeable iff $T ∼ σT$ for any permutation $σ ∈ S_n$ (where $(σT)_i = T_{σi}$ by definition). ³ We have that exchangeability implies condition (C): Take $σ$ with $σi = j$: $$\begin{aligned} & P(T_i ≤ T_{(k)}) \\ =\quad & P((σT)_i ≤ (σT)_{(k)}) \quad & \text{(exchangeability)}\\ =\quad & P((T)_{σi} ≤ (σT)_{(k)}) \quad & \text{(def)}\\ =\quad & P((T)_{j} ≤ (σT)_{(k)}) \quad & \text{(choice of $σ$)}\\ =\quad & P((T)_{j} ≤ (T)_{(k)}) \quad & \text{(order vectors are stable for permutation)}. \end{aligned}$$

Question

Is exchangeability actually equivalent to condition (C)?

Claim 1

Under (C), we have $$P(T_0 ≤ T_{(k)}) ≥ \frac{(k+1)}{(m+1)}.$$ with equality if ⁴ the coordinates of $T$ are distinct almost surely.

Proof of claim 1

$$\begin{aligned} P(T_0 ≤ T_{(k)}) &= (m+1)⁻¹ ∑_i P(T_i ≤ T_{(k)}) &&\quad \text{(because of (C))} \\ &= (m+1)⁻¹ ∑_i E 𝟭(T_i ≤ T_{(k)}) &&\quad \text{($P(A) = E𝟭(A)$)} \\ &= E ∑_i \frac{𝟭(T_i ≤ T_{(k)})}{m+1} &&\quad \text{(linearity of $E$)} \\ &= E \frac{♯\{i: T_i ≤ T_{(k)}\}}{m+1} &&\quad \text{(sum of indicators is count)} \\ &≥ E \frac{k+1}{m+1} &&\quad \text{(property of order vector (holds pointwise))} \\ &= \frac{k+1}{m+1} &&\quad \text{(expectation of a constant)}. \end{aligned}$$ Note that for a fixed vector $t$, $♯\{i: t_i ≤ t_{(k)}\} ≥ k+1$ with equality iff $t_{(k)}≠t_{(k+1)}$. In particular, if the $T_i$s are disjoint almost surely, $T_{(k)}≠T_{(k+1)}$ holds almost surely, and the inequality above is an equality.

Question

Do we have, in the above claim, that the inequality is an equality iff the coordinates are distinct almost surely? I think what we have is: the coordinates are distinct a.s. iff for each $k$, we have an equality. TODO: check this.

Claim 2

Let $X$ a random variable with values in a space $𝓧$, $t:𝓧 → ℝ$ some statistics, and $G ≔ \{g_0,…,g_m\}$ be a finite group acting on $𝓧$ such that $gX ∼ X$ for all $g∈G$. Define $T(X) ≔ (t(g_0X),…,t(g_mX))$. Then $T(X)$ satisfies condition (C).

Proof of claim 2

Note that $T(X)_{()} = T(gX)_{()}$ for all $g ∈ G$. Indeed, this is equivalent to saying that $T(X)$ and $T(gX)$ are permutations of each other, which holds since $(g_0X,…,g_mX)$ and $(g_0gX,…,g_mgX)$ are permutations of each other (because in turn $(g_0,…,g_m)$ and $(g_0g,…,g_mg)$ are permutations of each other). Fix then $i,j$ and $k$, we get: $$\begin{aligned} P(T(X)_i ≤ T(X)_{(k)}) &= P(T(g_i⁻¹g_jX)_i ≤ T(g_i⁻¹g_jX)_{(k)}) &&\quad \text{(by $g_i⁻¹g_jX ∼ X$)} \\ &= P(T(g_i⁻¹g_jX)_i ≤ T(X)_{(k)}) &&\quad \text{(by $T(X)_{()} = T(g_i⁻¹g_jX)_{()}$)} \\ &= P(T(X)_j ≤ T(X)_{(k)}) &&\quad \text{(by $T(g_i⁻¹g_jX)_{i} = t(g_ig_i⁻¹g_jX) = t(g_jX) = T(X)_j$)}. \end{aligned}$$

Claim 3

Let $X$ a random variable with values in a space $𝓧$, $t:𝓧 → ℝ$ some statistics, and $G ≔ \{g_0,…,g_m\}$ be a finite group acting on $𝓧$ such that $gX ∼ X$ for all $g∈G$. Let $g_1,…,g_m \overset{iid}{∼} U(G)$⁵. Define $T(X) ≔ (t(X),t(g_1X),…,t(g_mX))$. Then $T(X)$ satisfies condition (C).

Proof of claim 3

It suffices to see that $T(X)$ is exchangeable (since exchangeability implies (C)): Note that if $g_0,g_1, …,g_m \overset{iid}{∼} U(G)$, then $(g_0X,…,g_mX)$ is exchangeable, since $(g_0,…,g_m)$ itself is exchangeable (because an iid vector is always exchangeable). From $gX ∼ X$ with $g ∼ U(G)$, we get $$(X,g_1X,…,g_mX) ∼ (gX, g_1gX,…g_mgX).$$ Furthermore, from claim g1, we have that $g, g_1g, …, g_mg \overset{iid}{∼} U(G)$. It follows that $$(X,g_1X,…,g_mX) ∼ (gX,g_1gX,…,g_mgX)$$ is exchangeable, and so is then the vector $$T(X) = (tX,tg_1X,…,tg_mX) ∼ (tgX,tg_1gX,…,tg_mgX).$$

Question

How to deal with sampling the $g_i$s without replacement instead of with replacement? Does claim 3 hold if $(g_1,…,g_m) ∈ U(G^{m*})$, with $G^{m*} = \{(g_1,…g_m) ∈ G^m: ∀i, g_i ≠ 1, ∀i,j g_i≠g_ij\}$ ? Then

• $(g_1,…,g_m)$ is exchangeable, but we don’t care about that
• $X ∼ gX$ implies $(X,g_1X,…,g_mX) ∼ (gX, g_1gX, …, g_mgX)$
• so that $(tX,tg_1X,…,tg_mX) ∼ (tgX, tg_1gX, …, tg_mgX)$
• and it suffices to check that $(tgX, tg_1gX, …, tg_mgX)$ is exchangeable
• for which it suffices to show that $(g, g_1g, …, g_mg)$ is exchangeable,
• but I think that latter is $∼ G^{m+1} - Δ^{m+1}(G) = \{(g_0,…,g_m) ∈ G: ∀i≠j, g_i≠g_j\}$.

So I think everything holds

Claim 4

In the context of claim 1, letting $π_r ≔ \frac{♯\{i: T_0 ≤ T_i\}}{m+1}$, we have $$P\left(π_r ≤ \frac{k}{m+1}\right) ≤ \frac{k}{m+1}.$$

Proof of claim 4

This essentially follows from claim 1 using also claim a: $$\begin{aligned} P\left(π_r ≤ \frac{k}{m+1}\right) &= P\left(♯\{i: T_0 ≤ T_i\} ≤ k\right) \quad & \text{} \\ &= P\left(T_0 > T_{(m-k)}\right) \quad & \text{(Claim A)} \\ &= 1 - P\left(T_0 ≤ T_{(m-k)}\right) \quad & \text{} \\ &≤ 1 - \frac{m-k+1}{m+1} \quad & \text{(Claim 1)} \\ &= \frac{k}{m+1} \quad & \text{} \\ \end{aligned}$$

References