LemmaStatement: AI-generatedProof: AI-generated

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.

Exact logarithmic binomial masses at bounded distance from an entropy root

Statement

Fix real $γ > 0$ and $a > 0$ . Put $μ = γ \log n$ , $p = μ / n$ , and $N = n - j$ , where $j$ is a fixed positive integer. For any integer sequence $k = a μ + O (1)$ , with the bounded error independent of $n$ , let $q_{n} = P (Bin (N, p) = k)$ and $I (a) = a \log a - a + 1$ . Then $\log q_{n} = - μ I (a) - \frac{1}{2} \log (2 π k) - (k - a μ) \log a + o (1) .$ In particular $q_{n} = Θ (n^{- γ I (a)} / \sqrt{\log n})$ : the ratio lies between positive constants for all sufficiently large integers $n$ . All constants may depend on the fixed parameters and the error bound.

Facts & Assumptions

[F1]

A binomial $(N, p)$ variable is a sum of $N$ independent Bernoulli $(p)$ variables (Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials). For $N \in N_{0}$ , $0 < p < 1$ and integer $0 \leq k \leq N$ , its mass at $k$ is $(\binom{N}{k}) p^{k} (1 - p)^{N - k}$ (The Binomial count has its usual probability mass function).

[F2]

Stirling's formula gives $k! = \sqrt{2 π k} (k / e)^{k} (1 + o (1))$ (Stirling's formula for factorials).

[F3]

The derivative of $\log x$ is $1 / x$ (The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t).

[F4]

The natural logarithm is strictly increasing and onto the real line, hence grows without bound, and grows more slowly than any positive power (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The logarithm grows more slowly than every positive real power).

[F5]

For integers $0 \leq k \leq N$ , $(\binom{N}{k}) k! = N^{\underline{k}} = \prod_{i = 0}^{k - 1} (N - i)$ (C(n, k) k! (n-k)! = n! for k ≤ n; hence C(n, k) k! = n^k̲, the quotient n!/(k!(n-k)!) is a natural number, and C(n, k) = C(n, n-k)).

[F6]

For a positive real base $x$ and real exponent $r$ , $x^{r} : = \exp (r \log x)$ (Real powers for positive bases, with the zero-base positive-exponent convention).

Proof

Given: The fixed parameters and integer sequences in the Statement.

Goal: Prove the mass expansion with its bounded rounding error.

1.1F1F2F3F4F5givenalgebra

Eventually $N$ and $k$ are positive integers with $0 < p < 1$ and $1 \leq k < N$ , by [F4] and the fixed positive integer $j$ . Combining the binomial definition and mass formula in [F1] with the falling factorial identity in [F5] gives $\log q_{n} = \sum_{i = 0}^{k - 1} \log (N - i) + k \log p - \log (k!) + (N - k) \log (1 - p)$ . Integrating the derivative in [F3] on an interval bounded away from zero gives $\log (1 - x) = - x + O (x^{2})$ for $0 \leq x \leq 1 / 2$ . Since $k = O (\log n)$ and $j$ is fixed, $\sum_{i = 0}^{k - 1} \log (N - i) = k \log n + O ((j k + k^{2}) / n)$ , and $(N - k) \log (1 - p) = - μ + O ((j + k) p + n p^{2})$ . Each error tends to zero by [F4]. Thus [F2] yields $\log q_{n} = - μ + k \log μ - k \log k + k - \frac{1}{2} \log (2 π k) + o (1)$ .

2.1F3F4F6step 1.1algebra∎

Set $t = k - a μ$ , which is bounded. The derivative in $k$ of $k \log (μ / k) + k$ is $\log (μ / k)$ ; integrating it between $a μ$ and $a μ + t$ gives the change $- t \log a + O (t^{2} / μ)$ . The value at $a μ$ is $a μ (1 - \log a)$ . Substitution in step 1.1 proves the displayed expansion. Since $k / (\log n) \to a γ > 0$ and $t$ remains bounded, exponentiation, with $\exp (- γ I (a) \log n) = n^{- γ I (a)}$ by [F6], gives both positive constant bounds in the Statement.

Depends on

Used by · 2

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.