Try
Four independently sampled, exactly recorded proportions are 0.1, 0.3, 0.6 and 0.9. The null hypothesis specifies their entire distribution: each is Uniform[0,1], independently of the others. There is no parameter estimated from these observations. How surprising is their ECDF discrepancy under that precise model?
From the two-sided jump calculation, the right-gap candidates are .15,.20,.15,.10 and the left-gap candidates are .10,.05,.10,.15. Thus D=.20. A value of D is not itself a probability. Calibration compares it with the distribution of D from new samples of the same size under the null. The name one-sample Kolmogorov–Smirnov statistic, or KS statistic, refers here to this supremum distance from a specified CDF.
Predict
Suppose someone generates nine null samples, counts the discrepancies at least as large as the observed one, and divides by nine. If none exceed it, should they report an exact p-value of zero? Predict what changes when the observed record is counted as one of ten exchangeable records.
Also compare two contracts: a CDF fixed before seeing data, and a CDF whose parameters are estimated from those same data. The first is our subject. The second changes the statistic and its reference distribution; replacing an unknown parameter by an estimate does not preserve this proof automatically.
Experiment
For the live calculation, return to the shared discrepancy and calibration lab. Select the specified uniform model, record the sample, seed and replicate count before running, and compare its result with the proof below. Its fitted option belongs to a different procedure, explained in the following lesson.
Use the following schematic statistic record, not claimed output from a random-number generator. Its observed discrepancy is .20. The nine reference discrepancies are .14, .16, .20, .22, .30, .40, .18, .15 and .25. Mark each comparison using “greater than or equal,” including the tie.
| Record | Observed | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|
| D | .20 | .14 | .16 | .20 | .22 | .30 | .40 | .18 | .15 | .25 |
|---|
| D ≥ .20? | yes | no | no | yes | yes | yes | yes | no | no | yes |
|---|
There are five qualifying reference records. The upper-rank Monte Carlo p-value is (1+5)/(9+1)=.60. The raw reference-tail estimate is 5/9; it answers a different numerical question. Neither number is the analytically evaluated finite-sample KS tail for D=.20. With nine replicates the rank p-value cannot be smaller than .10, even if the observation exceeds all nine.
If the table consists of rounded displays, comparisons must use the retained statistic values, not recomputed ranks from rounded labels. If rounding is deliberately part of the statistic, apply exactly the same rule to observed and reference records. Then the tie argument below applies to that rounded statistic, whose calibration is different from the unrounded one.
Understand
Why a specified continuous null becomes uniform
Let F₀ be a continuous CDF and X have that distribution. For 0<u<1 let q be the supremum of all real x with F₀(x)≤u. CDF limits at infinity make this set nonempty and bounded above. Continuity and monotonicity give F₀(q)=u: a value below u would allow larger x, and a value above u contradicts continuity from values in the set. Moreover F₀(x)≤u exactly for x≤q. Therefore P(F₀(X)≤u)=P(X≤q)=F₀(q)=u. Limits handle u=0 and 1. This proves the probability-integral transform, including a continuous CDF with flat portions. Continuity is essential; for a point mass at 0 the value F₀(X) is always 1, not uniform.
Independent X₁,…,Xₙ give independent Uᵢ=F₀(Xᵢ), because deterministic transformations applied separately preserve independence. The ordered-jump formulas express D entirely through the ordered U values and the ranks i/n. Thus, for every fully specified continuous F₀, its null D distribution is exactly the same as for iid uniforms on [0,1]. This is a distributional theorem, not a claim that a finite simulation gives its exact CDF. Rounding observations or retaining dependence can invalidate the assumed continuous iid model even when the code computes D correctly.
For one observation, D=max(U,1−U). As an independent analytic check, P(D≥d)=2(1−d) for 1/2≤d≤1, with tail 1 below 1/2 and 0 above 1. Thus an observed U=.8 has D=.8 and exact null tail .4. This special calculation is not a formula for larger n.
An exact finite-randomization guarantee under its assumptions
Fix a statistic T and sample size n before the calculation. Let T₀ be the observed statistic and T₁,…,Tᴮ the statistics from B independent ideal null samples, independent of the original sample. Under the null the B+1 statistics are iid, hence exchangeable: permuting their labels does not change their joint law. Independence is sufficient here; the rank proof itself needs exchangeability.
Define M=B+1 and pᴹᶜ=(1+number of j≥1 with Tⱼ≥T₀)/M. For any fixed list of M values, assign to each position i the upper-tail count Rᵢ=number of positions j with Tⱼ≥Tᵢ. For an integer k, at most k positions have Rᵢ≤k. To see this, sort from largest downward and group ties; every member of a tied block receives the block’s last rank. The qualifying positions consist of whole initial blocks ending no later than k.
By exchangeability all positions have the same probability of meeting Rᵢ≤k. Averaging their indicators and using the deterministic bound gives P(R₀≤k)≤k/M. Taking k=floor(Mα) proves
P(pᴹᶜ≤α)≤floor(Mα)/M≤α.
This is a null rejection-probability guarantee over repeated observations and reference sampling, not a guarantee conditional on a particular observed dataset. Ties make the test conservative; no ties give uniform ranks and equality at attainable grid levels. For example, if every statistic equals the same value, pᴹᶜ=1 always. Using strict exceedances would instead give 1/M and could reject an all-equal null almost surely. A separate independent randomized tie-breaking scheme can be valid, but it is not the deterministic rule taught here.
The added 1 and denominator B+1 are substantive. With B=1 and iid continuous null statistics, the naive proportion of references exceeding T₀ is zero with probability 1/2. Rejecting whenever that naive value is at most .05 would have size 1/2. The corrected rank value is at least 1/2 and never rejects at .05.
Three different errors and one reproducible protocol
Conditional on an observed statistic t, the reference exceedance count K is Binomial(B,θ), where θ=P(T≥t) under the specified null. The raw estimator K/B has conditional variance θ(1−θ)/B, at most 1/(4B). That describes Monte Carlo estimation error for the fixed tail θ. It is not the same object as the finite-rank test guarantee, and neither addresses model misspecification.
For an implementation, record the null CDF, n, statistic convention, seed, B and comparison rule. Generate reference samples independently under the declared model, recompute the same statistic for every sample, retain full-precision values, and round only for display. A reproducible pseudorandom generator and finite-precision CDF are implementations of this mathematical experiment, not a proof that their outputs are ideal iid continuous variables. State numerical approximations and generator limitations. If the statistic has a known numerical error bound, uncertain comparisons need an explicit policy rather than silently choosing a favorable side.
Repeating a simulation until its p-value crosses a preferred threshold is not this fixed-B procedure. Larger B improves resolution and tail estimation, but cannot fix biased observation collection, an incorrect null, an omitted parameter fit or dependent observations.
Apply
An analyst chooses B=19 before sampling and obtains no reference discrepancy at least as large as the observed one. Calculate the rank p-value and the raw tail estimate. Can the test reject at α=.01? Then suppose 99 reference records contain four qualifying values. Give the p-value, its resolution, and the largest possible conditional standard deviation of the raw tail estimator.
Check the decisions and their limits
For B=19, pᴹᶜ=1/20=.05, while K/B=0. The fixed-rank rule cannot reject at .01. For B=99 and K=4 it gives 5/100=.05, with grid spacing .01. The raw estimator is 4/99 and its conditional standard deviation is at most 1/(2√99), approximately .0503. This worst-case bound is not a confidence interval and does not say the actual error equals its bound. The model and ideal-randomization assumptions remain necessary.
Continue
Keep the discrepancy computation, reference law and decision rule as separate records. Reuse randomized testing for the distinction between a statistic and a null-error guarantee, and resampling limitations for failures that more replicates cannot repair. The next question is how estimating a parameter from the same sample changes the statistic and why each reference replicate may need its own fit. The present proof must not be relabeled a general fitted-null bootstrap theorem.
