Permutation Designs with Blocks and Ties

Why Blocking and Ties Change the Permutation Problem

A permutation test is only as valid as its reference set: the assignments treated as possible under the null hypothesis. In a blocked design, labels may be exchangeable within a block but not across blocks. Pooling all observations and permuting labels freely can therefore compare assignments that the design or null model does not allow. Ties pose a different challenge: they make several observations share a rank, and several distinct assignments may produce the same test statistic.

These issues are especially visible in multivariate rank tests, where a score may be a vector rank, a depth-based score, or a scalar rank score computed from multivariate observations. The exact permutation principle does not require a particular rank construction. It does require that the assignment set reflect the design and that the statistic be evaluated consistently for every allowed assignment.

The Allowed Assignments in a Blocked Design

Definition: Suppose there are $B$ blocks. Block $b$ contains $n_b$ observational units, and the design assigns $n_{bg}$ units to group $g$, where $\sum_{g=1}^G n_{bg}=n_b$. The blocked assignment set $\Omega$ consists of all group-label allocations that preserve these group counts separately in every block. Its size is $$ |\Omega|=\prod_{b=1}^{B}\frac{n_b!}{\prod_{g=1}^{G}n_{bg}!}. $$

Under a randomization null, the treatment assignment is uniform on $\Omega$ if the design selected uniformly from these allocations. In an observational setting, the analogous assumption is that, under the null, group labels are exchangeable within each block conditional on the observed outcomes and the block-specific group counts. These are distinct justifications for the same conditional permutation calculation; neither permits arbitrary permutations across blocks.

Write the observed multivariate outcome for unit $i$ in block $b$ as $X_{bi}$, and let $A\in\Omega$ denote an assignment. A rank-based statistic can be written as $T(A;X)$, where $X$ denotes all outcomes. If $T$ is vector-valued, choose a prespecified extremeness function $e$ and compare $e(T(A;X))$ across assignments. For example, $e$ might be the absolute value of a scalar contrast or a norm of a vector contrast. The statistic and extremeness rule must be applied in the same way to every assignment.

Worked Example: Counting and Using Block-Respecting Permutations

There are two groups, A and B. In block 1, three units are assigned one to A and two to B. In block 2, four units are assigned two to A and two to B. Outcomes are scalar scores used to illustrate the assignment calculation; the same assignment rule applies when outcomes and rank scores are multivariate.

The number of allowed assignments is $$ \binom{3}{1}\binom{4}{2}=3\cdot 6=18. $$ A free permutation of the three A labels among all seven units would allow A counts other than one in block 1 and two in block 2, so those assignments are not in $\Omega$.

For a concrete rank statistic, suppose the within-block ranks in block 1 are $1,2,3$, and those in block 2 are $1,2,3,4$. Let $T(A;X)$ be the sum of A’s within-block ranks. The observed A units have ranks $3$ in block 1 and $3,4$ in block 2, so $T_{\mathrm{obs}}=3+3+4=10$.

In block 1, A’s rank can be $1,2,$ or $3$, one assignment for each. In block 2, the six possible pairs of ranks have sums $3,4,5,5,6,7$. A total of at least 10 can occur only when block 1 contributes 3 and block 2 contributes 7. There is exactly one such assignment among the 18. Thus the inclusive upper-tail permutation p-value is $1/18$. The calculation uses the block-specific ranks and the block-respecting assignment set.

Midranks and the Conditional Permutation Distribution

Definition: If $t$ observations tie for the ranks $r,r+1,\ldots,r+t-1$, their midrank is the average of those rank positions: $$ r+\frac{t-1}{2}. $$ A conditional permutation distribution is the distribution of $T(A;X)$ over $A\in\Omega$, holding the observed outcomes fixed and using the assignment probabilities specified by the design or null model.

Midranks assign equal scores to equal values rather than breaking ties by observation order. They retain the total of the ranks that the tied observations occupy: multiplying the midrank by $t$ gives $$ t\left(r+\frac{t-1}{2}\right)=tr+\frac{t(t-1)}{2} =\sum_{j=0}^{t-1}(r+j). $$ Thus the tie changes how ranks are distributed among tied units, but not their combined rank total.

With ties, different assignments in $\Omega$ can yield identical statistics. They remain separate assignments in the reference distribution: their probabilities add. For a uniform assignment set, the inclusive upper-tail p-value is $$ p=\frac{\#\{A\in\Omega:T(A;X)\geq T(A_{\mathrm{obs}};X)\}}{|\Omega|}. $$ For a two-sided or vector-valued test, replace $T$ in this formula by a prespecified extremeness measure. Including equality is important: it gives a valid, possibly conservative, p-value when the statistic has a discrete distribution.

Worked Example: Computing Midranks for Tied Observations

In one block, six scalar scores are $2,2,5,8,8,8$. Their ordered rank positions are $1,\ldots,6$. The two scores equal to 2 occupy positions 1 and 2, so each receives midrank $(1+2)/2=1.5$. The score 5 has rank 3. The three scores equal to 8 occupy positions 4, 5, and 6, so each receives midrank $(4+5+6)/3=5$.

Suppose group A contains one observation with score 2, the observation with score 5, and one observation with score 8. Its rank sum is $$ T_A=1.5+3+5=9.5. $$ Group B contains the remaining observations, with rank sum $1.5+5+5=11.5$. The combined total is $9.5+11.5=21$, matching $1+2+3+4+5+6=21$. The calculation also shows why tied units must receive the same midrank rather than ranks determined by their row order.

Worked Example: A Conditional Distribution with Ties

Consider one block with four fixed outcomes $1,1,3,3$, and assign two units to A and two to B. The two observations at 1 receive midrank $1.5$; the two at 3 receive midrank $3.5$. Use the rank sum $T_A$ as an upper-tail statistic. Suppose the observed A group contains one unit from each tied pair, so $T_{A,\mathrm{obs}}=1.5+3.5=5$.

There are $\binom{4}{2}=6$ equally likely assignments under the null. One selects both low observations and has rank sum $3$. Four select one low and one high and have rank sum $5$. One selects both high observations and has rank sum $7$. Consequently, the conditional distribution assigns probabilities $1/6,4/6,1/6$ to $3,5,7$, respectively.

The inclusive upper-tail p-value for the observed sum 5 is $(4+1)/6=5/6$. The four assignments with statistic 5 all count, even though they produce the same rank sum. If the observed A group had both high observations, its sum would be 7 and its p-value would be $1/6$. Counting only distinct statistic values would give the wrong reference probabilities.

Exactness Under the Blocked Null

Theorem: Conditional on the observed outcomes, suppose the assignment $A_{\mathrm{obs}}$ is uniform on the finite set $\Omega$. For any fixed statistic and extremeness rule, the inclusive upper-tail permutation p-value is super-uniform: $$ P(p\leq \alpha\mid X)\leq\alpha,\qquad 0\leq\alpha\leq 1. $$

This result applies to rank statistics with ties as well as statistics without ties. In a randomized experiment, the conditional uniformity follows from the assignment mechanism under the sharp null, which makes the outcomes fixed under each assignment. In an observational analysis, it requires the stated within-block exchangeability assumption; it does not follow merely from having collected data in blocks.

Proof. Fix the outcomes and list the $M=|\Omega|$ assignment-specific extremeness values in decreasing order, keeping repeated values as separate entries. For an assignment at a given value, its p-value is the number of assignments with extremeness at least that value, divided by $M$. This count includes every assignment tied at that value. Therefore, if the p-value is at most $\alpha$, the assignment belongs to an initial group of at most $\alpha M$ entries in the ordered list. Since all $M$ assignments are equally likely, the conditional probability of this event is at most $\alpha M/M=\alpha$. This proves the claim. $\square$

The inequality can be strict because attainable p-values are discrete. In particular, ties in the statistic do not invalidate the test; treating equal statistic values as equally extreme and retaining all assignment multiplicities is what preserves the argument.

Randomized Ranks and Safe Tie Handling

Midranks are deterministic and usually the clearest choice when tied values should remain indistinguishable. Another option is randomized tie-breaking. For a tied group occupying positions $r,\ldots,r+t-1$, one can assign those positions in a uniformly random order to its $t$ observations. This produces ordinary integer ranks while treating tied observations symmetrically.

For exact permutation inference, the auxiliary randomness must be handled consistently. One safe construction is to generate tie-breaking variables independently of the treatment labels, attach them to the units, and hold them fixed while enumerating assignments. Conditional on those variables, the assignment is still uniform on $\Omega$, so the exactness proof applies to the resulting statistic. Alternatively, the randomization mechanism can be incorporated into the reference distribution, provided it is applied symmetrically to every assignment. Randomly breaking ties only for the observed assignment, then comparing it with a distribution that uses a different tie rule, does not justify an exact p-value.

A third option is to keep the ties and use the conditional permutation distribution directly. This avoids adding auxiliary randomness and preserves the full set of possible assignments. For vector outcomes, ties may mean identical observations, equal depth or score values, or repeated rank vectors. Whichever rank construction is used, define how such ties are treated before comparing assignments.

Worked Example: Random Tie-Breaking Without Changing the Design

Return to the four outcomes $1,1,3,3$ with two A labels. The two low outcomes occupy rank positions 1 and 2. Suppose an independent random draw assigns these two rank positions to the two low-outcome units, and similarly assigns positions 3 and 4 to the high-outcome units. The draws are made without using group labels and are then held fixed across all six allowed assignments.

For any realized tie-breaking order, there are still six assignments in $\Omega$, each equally likely under the null. The assignment-specific rank sums may now distinguish units that had equal outcomes, but the exactness theorem still applies conditional on the realized tie-breaking order. The test’s reference distribution must use that same order for every assignment. By contrast, permuting labels across other blocks would not become valid merely because ties were randomized.

Common Mistakes and Practical Checks

Permuting across blocks: this assumes exchangeability across strata that may have different distributions or assignment rules. Restrict label permutations to the allowed within-block allocations.
Dropping duplicate statistics: each allowed assignment contributes its probability, even when several assignments give the same rank statistic. Keep multiplicities in the conditional distribution.
Breaking ties by row order: this can give identical observations different scores for an arbitrary reason. Use midranks or a prespecified, label-independent randomized rule.
Computing ranks inconsistently: if a rank construction depends on group labels, recompute it under every candidate assignment. If it depends only on the fixed outcomes, use the same scores throughout.
Confusing a permutation model with a design: blocking alone does not establish exchangeability. State why the assignments are uniform within blocks, or identify the assumptions that support the observational permutation analysis.

The central practical check is simple: write down the assignments allowed by the null before calculating a p-value. Then specify the tie rule, calculate the statistic for each allowed assignment, and include equal statistics with their full multiplicity. This keeps the test’s calibration connected to the design, even when multivariate rank scores are discrete.

Check Your Understanding

Use the design and tie rules stated in each question.

Three blocks have sizes 4, 3, and 5. In each block, two groups receive counts $(2,2)$, $(1,2)$, and $(3,2)$, respectively. How many assignments are in the block-respecting permutation set?
Why can an unrestricted permutation of labels be invalid even if the test statistic is calculated using within-block ranks?
Four observations tie for rank positions 6 through 9. What midrank does each receive, and what is their combined rank total?
In a conditional permutation distribution, five assignments yield statistic 4 and one yields statistic 7. For an observed statistic of 4 and an inclusive upper-tail test, what is the p-value?
What must be done with randomized tie-breaking variables to preserve the exact permutation argument?