OFFSET
1,2
COMMENTS
For X ~ Bin(m,p) and k = 0..m, let [L(m,k), U(m,k)] be the two-sided exact Clopper-Pearson (CP) 95% interval for p. Let W(m) = max_{0<=k<=m} (U(m,k) - L(m,k)). Then a(n) = min{ m >= 1 : W(m) <= 1/n }.
As m increases, W(m) is nonincreasing (hence a(n) is well-defined). Individual widths U(m,k) - L(m,k) may show small nonmonotonicities in m due to discreteness.
The maximum width typically occurs near k ~ m/2.
Clopper-Pearson intervals are conservative, that is, the coverage is at least the nominal 95%.
An upper bound from Hoeffding's inequality is a(n) <= ceiling(2*log(40)*n^2).
A tighter but heuristic bound using a continuity-corrected normal approximation with z = z(0.975) = 1.959963984... = A220510 is N_cc(n) = ceiling(4 / (-z + sqrt(z^2 + 4/n))^2), which is usually within a few units (often 1 to 3) of a(n) for small n (empirically).
As n -> infinity, a(n) ~ z(0.975)^2 * n^2, where z(0.975)^2 = 3.841458820694....
a(n) <= A182868(n) = 4*n^2 + n - 1 for 1 <= n <= 48 with equality at n = 2..5. Conjecture: this strict inequality holds for all n >= 6.
LINKS
Pablo Cadena-Urzúa, Table of n, a(n) for n = 1..80
L. D. Brown, T. T. Cai, and A. DasGupta, Interval estimation for a binomial proportion, Statistical Science 16 (2001), 101-133.
C. J. Clopper and E. S. Pearson, The use of confidence or fiducial limits illustrated in the case of the binomial, Biometrika 26 (1934), 404-413.
FORMULA
a(n) = min{ m >= 1 : W(m) <= 1/n } where W(m) = max_{0<=k<=m} (U(m,k) - L(m,k)) with L(m,k) = I^(-1)(k, m-k+1; 0.025) and U(m,k) = I^(-1)(k+1, m-k; 0.975) for 0 < k < m, where I^(-1)(a,b; q) is the inverse regularized incomplete beta function.
Extremes: L(m,0) = 0, U(m,0) = 1 - (0.025)^(1/m); L(m,m) = (0.025)^(1/m), U(m,m) = 1.
As n -> infinity, a(n)/n^2 -> z(0.975)^2.
EXAMPLE
First terms (95% level): a(1) = 1, a(2) = 17, ..., a(15) = 892.
For n = 10, a(10) = 402; with m = 402 trials the worst-case 95% CP width is <= 0.1.
MATHEMATICA
(* --- Clopper-Pearson 95% (two-sided) --- *)
cpL[m_, k_] := If[k == 0, 0., N@InverseBetaRegularized[k, m - k + 1, 0.025]];
cpU[m_, k_] := If[k == m, 1., N@InverseBetaRegularized[k + 1, m - k, 0.975]];
cpWidth[m_Integer?NonNegative] := Module[{ks, Ls, Us},
ks = Range[0, m];
Ls = cpL[m, #] & /@ ks;
Us = cpU[m, #] & /@ ks;
Max[Us - Ls]
];
(* z = z_{0.975} and continuity-corrected normal bound *)
z = InverseCDF[NormalDistribution[], 0.975];
Ncc[n_Integer?Positive] := Ceiling[ 4./(-z + Sqrt[z^2 + 4./n])^2 ];
(* Sequence: smallest m with W(m) <= 1/n *)
a[n_Integer?Positive] := Module[{m = Ncc[n]},
(* Ensure the condition in case Ncc underestimates *)
While[cpWidth[m] > 1./n, m++];
(* Minimize: step down while it still holds *)
While[m > 1 && cpWidth[m - 1] <= 1./n, m--];
m
];
(* Example: first 80 terms *)
Table[a[n], {n, 1, 80}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Pablo Cadena-Urzúa, Sep 23 2025
STATUS
approved