LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Hypergeometric and binomial composition counts are contiguous

Statement

Assume AC. For each $N$ , let $M_{N}$ of $N$ objects be marked, with $p_{N} = M_{N} / N \to p \in (0, 1)$ , and let $k_{N} / N \to s \in (0, 1)$ . Let $B_{N} \sim Bin (k_{N}, p_{N})$ and let $H_{N}$ count marked objects in a uniform size- $k_{N}$ sample without replacement from the $N$ objects. Then the law of $H_{N}$ is contiguous to the law of $B_{N}$ : for every sequence of sets $A_{N}$ , if $P (B_{N} \in A_{N}) \to 0$ , then $P (H_{N} \in A_{N}) \to 0$ .

More precisely, the likelihood ratio $L_{N} (j) = P (H_{N} = j) / P (B_{N} = j)$ satisfies

$L_{N} (B_{N}) \Rightarrow (1 - s)^{- 1 / 2} \exp ⁣ (- \frac{s}{2 (1 - s)} Z^{2}), Z \sim N (0, 1),$

and this nonnegative limit has mean $1$ .

Facts & Assumptions

Given: AC, marked-object proportions $p_{N} \to p \in (0, 1)$ , sampling proportions $k_{N} / N \to s \in (0, 1)$ , a binomial count, and a uniform sample without replacement.

[F1]

Lindeberg-Feller central limit theorem: sufficiency gives a standard-normal limit for a centered independent triangular array under the Lindeberg condition, assuming AC.

[F2]

Stirling's formula for factorials states $j! \sim \sqrt{2 π j} (j / e)^{j}$ as positive integers $j \to \infty$ .

[F3]

Identical distribution and IID families defines IID as mutual independence together with a common law.

[F4]

Moments, variance, and covariance on a probability space defines variance as the centered second moment.

[F5]

For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique supplies the finite product probability measure used for that Bernoulli row.

[F6]

Expectations factor over finite products of independent random variables factors expectations of products of integrable functions of independent variables.

[A1]

AC is used exactly through [F1]. The Axiom of Choice

Proof

Given: The hypotheses in the Statement. Prove the likelihood-ratio limit and the stated direction of contiguity.

1.1givenalgebra

The exact mass ratio, with $q_{N} = 1 - p_{N}$ , is $L_{N} (j) = \frac{(\binom{M_{N}}{j}) (\binom{N - M_{N}}{k_{N} - j})}{(\binom{N}{k_{N}}) (\binom{k_{N}}{j}) p_{N}^{j} q_{N}^{k_{N} - j}}$ on the hypergeometric support, and is zero off that support.

1.2F3F5givenconstructalgebra

By [F5], form the $k_{N}$ -fold product of the law assigning masses $p_{N}$ and $q_{N}$ to $1$ and $0$ . The rectangle formula makes its coordinate indicators $I_{N, i}$ independent with that common Bernoulli law, hence IID in the sense of [F3]. Each binary vector with $j$ ones has mass $p_{N}^{j} q_{N}^{k_{N} - j}$ , and there are $(\binom{k_{N}}{j})$ such vectors. Their sum therefore has the specified binomial law, so we may realize $B_{N} = \sum_{i = 1}^{k_{N}} I_{N, i}$ on this space.

2.1F4F6step 1.2algebra

Each indicator has mean $p_{N}$ and variance $p_{N} q_{N}$ by [F4]. Factorization [F6] gives $E [I_{N, i} I_{N, j}] = p_{N}^{2}$ for $i \neq j$ , so the row sum has mean $k_{N} p_{N}$ and variance $k_{N} p_{N} q_{N}$ .

3.1A1F1step 2.1givenalgebra

Each centered summand has magnitude at most $1$ , while the row standard deviation is $\sqrt{k_{N} p_{N} q_{N}} ≍ \sqrt{N}$ . Thus for each fixed $ε > 0$ all Lindeberg tail terms are zero for large $N$ ; under AC [A1], [F1] gives $Z_{N} : = \frac{B_{N} - k_{N} p_{N}}{\sqrt{k_{N} p_{N} q_{N}}} \Rightarrow Z \sim N (0, 1) .$

4.1F2step 1.1step 3.1algebra

Put $s_{N} = k_{N} / N$ and $δ_{N} = B_{N} - k_{N} p_{N}$ . By [step 3.1], $δ_{N} = O_{P} (\sqrt{N})$ , so the event $∣ δ_{N} ∣ \leq N^{2 / 3}$ has probability tending to one. On this event, all factorial arguments in [step 1.1] are bounded below by a positive multiple of $N$ , since $p_{N} \to p$ and $s_{N} \to s$ with $p, s \in (0, 1)$ . Let $H (a, x) = a \log a - x \log x - (a - x) \log (a - x)$ and $H (t) = H (1, t)$ . Stirling's formula [F2], uniformly for these arguments, expands each log-binomial coefficient as $H (a, x) - \frac{1}{2} \log (2 π x (a - x) / a) + o (1)$ . The order- $N$ terms at $δ = 0$ cancel because $H (p_{N} N, s_{N} p_{N} N) = p_{N} N H (s_{N})$ , $H (q_{N} N, s_{N} q_{N} N) = q_{N} N H (s_{N})$ , and $H (s_{N} N, s_{N} p_{N} N) = s_{N} N H (p_{N})$ . For $F_{N} (δ) = H (p_{N} N, s_{N} p_{N} N + δ) + H (q_{N} N, s_{N} q_{N} N - δ) - H (N, s_{N} N) - H (s_{N} N, s_{N} p_{N} N + δ) - (s_{N} p_{N} N + δ) \log p_{N} - (s_{N} q_{N} N - δ) \log q_{N}$ , use $H_{a}^{'} (x) = \log ((a - x) / x)$ and $H_{a}^{''} (x) = - 1 / x - 1 / (a - x)$ ; direct substitution gives $F_{N} (0) = 0$ , $F_{N}^{'} (0) = 0$ and $F_{N}^{''} (0) = - \frac{1}{p_{N} N s_{N} (1 - s_{N})} - \frac{1}{q_{N} N s_{N} (1 - s_{N})} + \frac{1}{s_{N} N p_{N} q_{N}} = - \frac{1}{p_{N} q_{N} N (1 - s_{N})} .$ The third derivative is bounded by $C / N^{2}$ throughout this event because every argument remains at least $c N$ . The square-root terms at $δ = 0$ sum to $- \frac{1}{2} \log \frac{(2 π p_{N} N s_{N} (1 - s_{N})) (2 π q_{N} N s_{N} (1 - s_{N}))}{(2 π N s_{N} (1 - s_{N})) (2 π s_{N} N p_{N} q_{N})} = - \frac{1}{2} \log (1 - s_{N}),$ and their change is $O (∣ δ_{N} ∣ / N) = o_{P} (1)$ . Taylor's formula therefore gives $\log L_{N} (B_{N}) = - \frac{1}{2} \log (1 - s_{N}) - \frac{δ_{N}^{2}}{2 p_{N} q_{N} N (1 - s_{N})} + O_{P} (∣ δ_{N} ∣^{3} / N^{2}) + o_{P} (1) = - \frac{1}{2} \log (1 - s_{N}) - \frac{s_{N}}{2 (1 - s_{N})} Z_{N}^{2} + o_{P} (1) .$ The Taylor remainder is $o_{P} (1)$ because $δ_{N} = O_{P} (\sqrt{N})$ , and the omitted event has probability tending to zero by [step 3.1].

5.1step 3.1step 4.1algebra

Since $s_{N} \to s$ , [step 3.1] and [step 4.1] imply the displayed likelihood-ratio limit. Its mean is $(1 - s)^{- 1 / 2} E \exp ⁣ (- \frac{s}{2 (1 - s)} Z^{2}) = (1 - s)^{- 1 / 2} \sqrt{1 - s} = 1,$ by direct integration against the standard-normal density.

6.1step 5.1algebra

Each $L_{N} (B_{N}) \geq 0$ and $E [L_{N} (B_{N})] = 1$ by the likelihood-ratio definition. Nonnegative convergence in distribution to a variable with the same mean implies uniform integrability: for fixed $K$ , $E [L_{N} \land K] \to E [L \land K]$ , so ${lim sup}_{N} E [(L_{N} - K)_{+}] = 1 - E [L \land K] \to 0$ as $K \to \infty$ . This also controls $E [L_{N} 1_{{L_{N} > 2 K}}]$ .

7.1step 6.1algebra∎

If $P (B_{N} \in A_{N}) \to 0$ , then for every $K > 0$ , $P (H_{N} \in A_{N}) = E [L_{N} (B_{N}) 1_{{B_{N} \in A_{N}}}] \leq K P (B_{N} \in A_{N}) + E [L_{N} (B_{N}) 1_{{L_{N} (B_{N}) > K}}] .$ The first term tends to zero for fixed $K$ and the second is uniformly small for large $K$ by step 6.1. Therefore $P (H_{N} \in A_{N}) \to 0$ . This proves the required direction of contiguity; the reverse direction is not needed here.

Depends on

Used by

Consistency transfers from IID mixture samples to permuted groups Lemma

Dependency tree · two levels

40 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

E. Y. Chung and J. P. Romano, Exact and Asymptotically Robust Permutation Tests, Stanford Technical Report 2011-05, §3.4 and Appendix A, Lemma 3.2 proof (standard reference, not scraped)