Stats Primer: Non-Parametric A/B Tests

Companion to Designing a Trustworthy A/B Test: the non-parametric (resampling) tests. Its sibling covers the parametric tests. Part of the inference arc, leading into sample size.

The parametric tests assume a distributional model. When those assumptions are shaky, or the metric is something like a median or 99th percentile with no simple standard-error formula, non-parametric resampling methods build the null distribution directly from the data. This post covers the two workhorses, the permutation test and the bootstrap, how they differ, and how many simulations each needs.

1. Permutation Test

A permutation test works by simulating the null hypothesis, that there is no difference between versions A and B, by repeatedly shuffling the observed data and seeing how often we get a result as extreme as the one we actually saw.

The fundamental difference is that z-tests and t-tests are parametric, meaning they assume the data follows a specific theoretical distribution (like a normal distribution). A permutation test is non-parametric: it makes no assumption about the shape of the data’s distribution, building the null distribution directly from our collected data. It is not, however, assumption-free. Its validity rests on exchangeability under the null (equivalently, the known randomization mechanism), and the shuffling must respect the experimental design: preserve blocks, clusters, strata, and paired structure rather than shuffling freely across them.

How a Permutation Test Works for an A/B Test

The core idea is to test the null hypothesis: “The labels ‘A’ and ‘B’ are meaningless.” If this were true, then randomly shuffling these labels among our data points shouldn’t matter.

Here’s the step-by-step process:

1. Calculate the Observed Difference: First, we run our A/B test and calculate the actual difference between Group A and Group B for our chosen metric (e.g., the difference in conversion rates). Let’s call this the observed statistic.

2. Pool the Data: Combine the results from both Group A and Group B into a single large dataset. By pooling the data, we are effectively assuming the null hypothesis is true (that the labels A and B don’t matter).

3. Shuffle and Re-assign: Randomly shuffle the pooled data. Then, create new “A” and “B” groups of the same size as our original groups.

4. Calculate a Permuted Statistic: Calculate the difference in the metric between our new, shuffled “A” and “B” groups. Record this value.

5. Repeat: Repeat steps 3 and 4 thousands of times (e.g., 10,000 times). Each time, we get a new “permuted statistic.”

6. Build the Null Distribution: The collection of all our permuted statistics forms a distribution centered around zero. This is our empirically-derived null distribution. It shows the range of differences we could expect to see if the treatment had no real effect.

7. Calculate the P-value: Finally, we count how many of the permuted statistics are as extreme or more extreme than our original observed statistic. This proportion is our p-value. For a Monte-Carlo permutation test (a random sample of $B$ shuffles rather than all of them), use the slightly conservative estimator $\hat{p} = (b+1)/(B+1)$, where $b$ is the number of permutations at least as extreme as observed. The $+1$ terms count the observed data itself as one valid arrangement and prevent an impossible p-value of exactly zero. For a two-sided test, use a two-sided statistic (for example the absolute difference).

Example: A/B Test for Conversion Rate

Let’s test if changing a “Buy Now” button from blue (A) to green (B) increases the conversion rate.

1. Observed Data

• Group A (Blue Button): 1,000 users, 80 converted. Conversion Rate = 8%
• Group B (Green Button): 1,000 users, 105 converted. Conversion Rate = 10.5%
• Observed Statistic (Difference): 10.5% - 8% = 2.5%

2. Permutation Test

• Pool: Combine all 2,000 users. This pool has a total of 185 conversions (80 + 105) and 1,815 non-conversions.

• Shuffle & Recalculate (One Iteration):
  • Randomly assign 1,000 users from the pool to a “new A” and the other 1,000 to a “new B.”
  • Let’s say in this shuffle, “new A” gets 90 conversions (9% rate) and “new B” gets 95 conversions (9.5% rate).
  • The first permuted statistic is 9.5% - 9% = 0.5%.

• Repeat 10,000 Times: We now have 10,000 simulated differences. Most will be close to zero.

• Calculate the P-value: We check how many of those 10,000 simulated differences were 2.5% or greater. Let’s say we find that 210 of them were.
  • P-value = 210 / 10,000 = 0.021

Conclusion

Since the p-value of 0.021 is less than our typical significance level of 0.05, we reject the null hypothesis. The permutation test shows that the observed 2.5% difference is unlikely to be a result of random chance, suggesting the green button is genuinely more effective.

The section below maintains the exact structure and example data to ensure continuity, followed by the comparison section.

2. Bootstrap Test

A bootstrap test works by using our data to estimate the “true” population distribution. Instead of shuffling labels to simulate a world where there is no difference (like the permutation test), the bootstrap simulates conducting the experiment over and over again to see how much the results fluctuate.

While the permutation test asks “Is this result just random noise?”, the bootstrap test asks “How confident are we in the specific magnitude of this result?”

How a Bootstrap Test Works for an A/B Test

The core idea is resampling with replacement. We treat our sample groups (A and B) as if they are the entire population, and we draw samples from them to estimate the variability of the metric.

Here’s the step-by-step process:

1. Calculate the Observed Difference: Just like before, calculate the actual difference between Group A and Group B. (e.g., Conversion Rate B - Conversion Rate A).

2. Keep Groups Separate: Unlike the permutation test, do not pool the data. Keep Group A and Group B distinct.

3. Resample with Replacement:
   • Create a “Bootstrap Sample A” by drawing $N_A$ observations from the original Group A, putting each observation back after drawing it (sampling with replacement).
   • Create a “Bootstrap Sample B” by drawing $N_B$ observations from the original Group B in the same way.

4. Calculate a Bootstrap Statistic: Calculate the conversion rate for “Bootstrap Sample A” and “Bootstrap Sample B,” then find the difference. Record this value.

5. Repeat: Repeat steps 3 and 4 thousands of times (e.g., 10,000 times).

6. Build the Sampling Distribution: The collection of these 10,000 differences forms a distribution centered around our observed difference. This shows the spread of possible results we might see if we repeated the experiment many times.

7. Calculate Confidence Interval: Instead of a p-value, we typically calculate a Confidence Interval (CI). For a 95% CI, we cut off the bottom 2.5% and top 2.5% of our bootstrap statistics. If this interval does not include zero, the result is statistically significant.

Example: A/B Test for Conversion Rate (Revisited)

We use the same data: Blue Button (A) vs. Green Button (B).

1. Observed Data

• Group A: 1,000 users, 80 converted (8%).
• Group B: 1,000 users, 105 converted (10.5%).
• Observed Statistic (Difference): 2.5%

2. Bootstrap Test

• Resample (One Iteration):
  • We draw 1,000 users from Group A (with replacement). Some users might be picked twice, some not at all. Let’s say this “Bootstrap A” has 75 conversions (7.5%).
  • We draw 1,000 users from Group B (with replacement). Let’s say “Bootstrap B” has 110 conversions (11.0%).
  • The first bootstrap statistic is 11.0% - 7.5% = 3.5%.

• Repeat 10,000 Times: We generate 10,000 variations of the difference. Some will be 2.5%, some 1%, some 4%, etc.

• Calculate the 95% Confidence Interval:
  • We sort all 10,000 differences from lowest to highest.
  • We look at the value at the 2.5th percentile (the 250th value) and the 97.5th percentile (the 9,750th value).
  • Let’s assume our interval comes out to [0.4%, 4.6%].

Conclusion

Because the 95% Confidence Interval [0.4%, 4.6%] does not contain 0.0%, we conclude that the difference is statistically significant. Moreover, we can say with 95% confidence that the Green Button increases conversion by somewhere between 0.4% and 4.6%.

Comparison: Permutation vs. Bootstrap

While both are powerful non-parametric methods that rely on simulation rather than complex formulas, they serve slightly different purposes.

Feature	Permutation Test	Bootstrap Test
Primary Goal	Hypothesis Testing: Testing if an effect exists.	Estimation: Estimating the accuracy/variance of an effect.
Mechanism	Shuffling: Destroys the relationship between the group and the outcome to simulate “random chance.”	Resampling: Preserves the relationship to simulate “repeating the experiment.”
Null Hypothesis	Assumes $H_0$ is true (Groups are identical).	Does not assume $H_0$ is true; assumes sample $\approx$ population.
Distribution Center	Centered around Zero (Null Distribution).	Centered around the Observed Difference.
Output	Produces a precise P-value.	Produces a Confidence Interval (and Standard Error).

When to Use Which?

Use a Permutation Test when:

• We strictly want a “Yes/No” answer on significance (P-value).
• We have a very small sample size where assumptions of normality (for Z/T-tests) definitely do not hold, and we want the most robust test against False Positives.
• We are testing a complex metric where the standard error is hard to derive mathematically, but we only care if Group B is different from Group A.

Use a Bootstrap Test when:

• We care about magnitude and uncertainty (Confidence Intervals). Business stakeholders usually prefer “The uplift is between 2% and 5%” over “P-value is 0.02.”
• We are analyzing a metric that is not a mean or proportion, such as a Median or 99th Percentile (e.g., “Does the new feature reduce the 99th percentile latency?”). There are no simple formulas for the standard error of a median, making Bootstrap the gold standard here.

Practical Differences

1. Hypothesis Testing (p-value): For testing the null hypothesis of no difference, both are reasonable choices and often agree, but not always. They answer subtly different questions (the permutation test conditions on the null; the bootstrap estimates sampling variability) and can diverge with small samples, heavy skew, or unequal variances. Neither is assumption-free: the bootstrap in particular assumes the sample represents the target population and that observations are independent (or that their dependence is modeled), and simple percentile intervals can undercover for skewed statistics (bias-corrected or studentized intervals are often better).

2. Confidence Intervals: This is the main difference. Because bootstrapping estimates the sampling distribution of our metric, it can be used to construct a confidence interval for the effect size (e.g., the true difference in P90 APE between the models). A permutation test cannot do this because its entire structure is based on the assumption of the null hypothesis (no difference).

How do We Decide on the Simulation Count

Determining the number of iterations (often denoted as $B$) involves balancing precision against computational time.

Here is the breakdown of how to decide the number of simulations for both Permutation Tests and Bootstrap Tests.

1. The Quick “Rules of Thumb”

If we want a standard answer that satisfies most reviewers and statistical requirements without doing math:

Goal	Recommended $B$	Why?
Initial / Debugging	100	Fast enough to check if code works; not accurate enough for results.
P-value ($\alpha = 0.05$)	1,000	Sufficient to distinguish if $p < 0.05$ reliably.
P-value ($\alpha = 0.01$)	5,000 - 10,000	We need more resolution to see “rare” events in the tail.
Confidence Intervals	2,000+	Estimating tails (2.5th and 97.5th percentiles) is harder than estimating the mean.
Publication Quality	10,000+	Computers are fast now; running 10k usually removes any doubt about simulation error.

2. The Technical Approach (Calculating $B$)

If we need to justify our choice or have a specific precision target, use these formulas.

A. For P-values (Permutation & Bootstrap Hypothesis Tests)

A simulation-based p-value ($\hat{p}$) is an estimate of the true p-value ($p$). The uncertainty of this estimate follows a binomial distribution. We can calculate the standard error ($SE$) of our estimated p-value:

\[SE(\hat{p}) = \sqrt{\frac{p(1-p)}{B}}\]

How to use this:

1. Guess the p-value: Assume the p-value is near our significance threshold (e.g., $p \approx 0.05$).
2. Set desired precision: Decide how much “noise” we can tolerate. For example, we want a standard error of 0.005 (so a true $0.05$ doesn’t accidentally look like $0.06$).

3. Solve for $B$:

   \[B = \frac{p(1-p)}{SE^2}\]

Example: To distinguish $p=0.05$ with a precision ($SE$) of $0.005$:

\[B = \frac{0.05(1-0.05)}{0.005^2} = \frac{0.0475}{0.000025} = 1,900 \text{ iterations}\]

B. For Confidence Intervals (Bootstrap)

Confidence intervals (CIs) require estimating the tails of the distribution (e.g., the 2.5th and 97.5th percentiles). The tails are much more volatile than the center (mean).

• Recommendation: Use at least 2,000 bootstraps.
• Pre-calculation: There is no simple formula like the one above, but studies show that for 95% CIs, $B=2,000$ stabilizes the endpoints sufficiently for most data.

3. The “Exact” Limit (When to Stop Simulating)

Sometimes the sample size is small enough that we don’t need to simulate. We can calculate every possible permutation. This is called an “Exact Test.”

Check the total number of permutations ($N_{perm}$) before we start:

• Two-Sample Test: If we have Group A ($n_a$) and Group B ($n_b$), the distinct combinations are:

  \[N_{perm} = \binom{n_a + n_b}{n_a}\]

• Paired/Correlation Test: For $n$ pairs, the permutations are often $2^n$ or $n!$ depending on the specific test.

Rule: If $N_{perm} < 10,000$, do not simulate. Just run every single permutation. It is more accurate and often faster.

• Example: Comparing 2 groups of 5 items each. $\binom{10}{5} = 252$. Don’t do 1,000 simulations. Just calculate all 252 exact combinations.

Summary Checklist

1. Check Exactness: Is the sample size small ($n < 10-15$)? If yes, calculate the exact theoretical limit. If it’s small, run the exact test.
2. Check Goal:
   • Hypothesis Test: Use $B = 1,000$ to $5,000$.
   • Confidence Interval: Use $B \geq 2,000$.
3. Check Resources: If our code takes 1 second to run 1 iteration, 10,000 iterations = ~3 hours. If that’s too long, use the precision formula (Section 2A) to find the minimum viable $B$.

---

Continue to sample size for A/B tests, or revisit experiment design.

Resources

• Efron, B. & Tibshirani, R. J. (1993). An Introduction to the Bootstrap. Chapman & Hall/CRC.
• Good, P. I. (2005). Permutation, Parametric, and Bootstrap Tests of Hypotheses (3rd ed.). Springer.