TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

Midpoint bit discretization has bounded coupling and CDF error

Statement

Assume Countable Choice and Dependent Choice as in Disjoint streams of independent fair bits produce independent uniform variables. Let $U = \sum_{j \geq 1} B_{j} 2^{- j}$ be the uniform variable from an independent fair-bit stream. For $b \geq 1$ , put $K_{b} = \sum_{j = 1}^{b} B_{j} 2^{b - j}, U_{b} = (K_{b} + 1 / 2) 2^{- b}, δ_{b} = 2^{- b - 1} .$ Then $K_{b}$ is uniform on ${0, \dots, 2^{b} - 1}$ , $∣ U - U_{b} ∣ \leq δ_{b}$ pointwise, the 1-Wasserstein and Kolmogorov distances between their laws are at most $δ_{b}$ , and their total-variation distance is exactly $1$ . We use $W_{1} (μ, ν) = \inf E ∣ X - Y ∣$ over couplings, $d_{K} (μ, ν) = \sup_{x} ∣ F_{μ} (x) - F_{ν} (x) ∣$ , and $d_{T V} (μ, ν) = \sup_{A} ∣ μ (A) - ν (A) ∣$ .

Facts & Assumptions

Given: An independent fair-bit stream, a bit budget $b \geq 1$ , and the definitions in the Statement.

[F1]

The bit-stream sum $U$ is uniform on $[0, 1]$ , and every finite bit prefix is uniform. Disjoint streams of independent fair bits produce independent uniform variables

[F2]

For probability laws, total variation here is the supremum of absolute event-probability differences. Total variation distance for probability laws

[F3]

Every half-open or closed interval has Lebesgue measure equal to its length, including degenerate intervals. A box in $R^{n}$ with parameters $a_{i} \leq b_{i}$ is Lebesgue measurable of measure $\prod_{i < n} (b_{i} - a_{i})$ , whichever of its faces are included

[A1]

The uniform law in [F1] is Lebesgue measure on $[0, 1]$ ; its CDF and strict CDF are both the clipped identity $x \mapsto \min (1, \max (0, x))$ by [F3]. Countable Choice is the assumption of [F3]. The Axiom of Countable Choice ( ${A C}_{ω}$ )

[A2]

The fair-bit product source in [F1] assumes Countable Choice and Dependent Choice. The Axiom of Countable Choice ( ${A C}_{ω}$ ), The axiom of dependent choice: a relation in which every element is related to something admits an $N$ -indexed chain

Proof

1.1givenF1A2algebra

The first $b$ independent fair bits give each of the $2^{b}$ binary prefixes probability $2^{- b}$ , so $K_{b}$ is uniform on the stated integer set. Write the remaining binary tail as $T_{b} = \sum_{j \geq 1} B_{b + j} 2^{- j} \in [0, 1]$ . Then $U = K_{b} 2^{- b} + 2^{- b} T_{b}$ , while $U_{b} = K_{b} 2^{- b} + 2^{- b - 1}$ , hence $∣ U - U_{b} ∣ = 2^{- b} ∣ T_{b} - 1 / 2 ∣ \leq 2^{- b - 1}$ .

2.1step 1.1F1F3A1algebra

The displayed coupling gives $W_{1} (L (U), L (U_{b})) \leq E ∣ U - U_{b} ∣ \leq δ_{b}$ by the infimum definition of $W_{1}$ . For non-strict CDFs, ${U \leq x - δ_{b}} \subseteq {U_{b} \leq x} \subseteq {U \leq x + δ_{b}}$ ; for strict CDFs, ${U < x - δ_{b}} \subseteq {U_{b} < x} \subseteq {U < x + δ_{b}}$ . Since both uniform CDFs equal the clipped identity by [A1], these inclusions bound each absolute discrepancy by $δ_{b}$ .

3.1F1F2step 1.1∎

The law of $U_{b}$ is supported on its finite midpoint grid, which has probability $1$ under $U_{b}$ and probability $0$ under the continuous uniform law of $U$ . By [F2], this event gives $d_{T V} (L (U), L (U_{b})) = 1$ , the maximal possible value.

Depends on

Used by

Dependency tree · two levels

42 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

Luc Devroye, Non-Uniform Random Variate Generation, Chapter XV §1, The Random Bit Model (standard reference, not scraped)