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.

Certified bisection controls CDF residual, spatial error, and distribution error

Statement

For the fixed-depth procedure of Certified bracketed bisection for a continuous CDF, a successful call uses two endpoint evaluations and $N$ midpoint evaluations, at most $N + 2$ CDF evaluations in total. For every continuous CDF on its compact bracket, some finite depth meets each positive modulus tolerance. The bracket invariant holds and its returned point satisfies $∣ F (\hat{x}) - u ∣ \leq ε$ . For $u \in (0, 1)$ , if the exact quantile $Q (u)$ lies in $[a, b]$ and a density $f$ satisfies $F (y) - F (x) = \int_{x}^{y} f (t) d t$ and $f \geq m > 0$ almost everywhere on the bracket, then $∣ \hat{x} - Q (u) ∣ \leq ε / m$ .

For the distribution bound, assume the procedure is run with one fixed depth and bracket on every $u \in [0, 1]$ , with $\tilde{F} (a) = 0$ , $\tilde{F} (b) = 1$ , and residual at most $ε$ for a continuous CDF $\tilde{F}$ . Let $g (u)$ be its returned point. Then $g$ is nondecreasing. If $\sup_{x} ∣ F (x) - \tilde{F} (x) ∣ \leq η$ for another CDF $F$ , then $d_{K} (L (g (U_{q})), F) \leq δ_{q} + ε + η,$ where $U_{q}$ is the $q$ -bit midpoint uniform, $q \geq 1$ , and $δ_{q} = 2^{- q - 1}$ . If the target is unbounded, the finite-bracket algorithm alone has no global distribution guarantee; its outside-bracket status remains tail-unresolved. Here $d_{K} (μ, ν) = \sup_{x} ∣ F_{μ} (x) - F_{ν} (x) ∣$ .

Facts & Assumptions

Given: The algorithm inputs and hypotheses in the Statement. The Kolmogorov distance is $d_{K} (μ, ν) = \sup_{x} ∣ F_{μ} (x) - F_{ν} (x) ∣$ .

[F1]

For $u \in (0, 1)$ , the generalized inverse satisfies $Q (u) \leq x$ exactly when $u \leq F (x)$ . Generalized inverse sublevel identity for a CDF

[F2]

A $q$ -bit midpoint input has both strict and non-strict CDF discrepancies at most $δ_{q} = 2^{- q - 1}$ . Midpoint bit discretization has bounded coupling and CDF error

[F3]

A continuous real-valued function on a compact interval is uniformly continuous. Every continuous map from a nonempty compact Hausdorff space to a uniform space is uniformly continuous

[F4]

The geometric sequence $2^{- N}$ tends to zero. For $∣ r ∣ < 1$ the sequence $r^{k}$ is null, and for $∣ r ∣ > 1$ the sequence $∣ r ∣^{k}$ diverges to $+ \infty$

[A4]

For the spatial claim, the density identity and lower bound in the Statement imply $F (y) - F (x) \geq m (y - x)$ on the bracket by integrating $f \geq m$ .

[A1]

The bisection depth, bracket, tolerance, modulus, and evaluation budget satisfy the algorithm's Definition. A returned $\hat{x}$ comes from a successful call that passed its endpoint bracket test. The distribution claim additionally has a single fixed depth and full-support bracket.

[A2]

The approximate CDF $\tilde{F}$ is continuous, nondecreasing, and satisfies the stated uniform CDF error bound $η$ .

[A5]

The generalized-inverse supplier in [F1] assumes Countable Choice. The Axiom of Countable Choice ( ${A C}_{ω}$ )

[A6]

When $U_{q}$ in [F2] is realized from the countable fair-bit product, its source model assumes Countable Choice and Dependent Choice; the distribution bound is conditional on that stated midpoint law. 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.1givenF3F4algebra

Initially $F (ℓ) \leq u \leq F (r)$ by the algorithm's bracket test. If $F (m) \leq u$ , replacing $ℓ$ by $m$ preserves both inequalities by monotonicity; if $F (m) > u$ , replacing $r$ by $m$ preserves them. After $N$ steps, $r - ℓ = (b - a) 2^{- N}$ , so the modulus certificate gives $F (r) - F (ℓ) \leq ε$ . Since $\hat{x} \in [ℓ, r]$ , monotonicity puts both $F (\hat{x})$ and $u$ in this range, proving $∣ F (\hat{x}) - u ∣ \leq ε$ . For a continuous $F$ , uniform continuity [F3] supplies a positive distance tolerance; since $(b - a) 2^{- N} \to 0$ by [F4], some finite $N$ meets it. A successful run evaluates the two endpoints once and one midpoint per update, hence uses $N + 2$ CDF evaluations; the budget explicitly includes these endpoints.

1.2givenA1algebrainduction

For fixed depth $N$ , the grid consists of the $2^{N}$ cells in the partition of $[a, b]$ ; their left endpoints are $a + j (b - a) 2^{- N}$ for $0 \leq j < 2^{N}$ . At each bisection, the tested midpoint separates the remaining candidate left endpoints into lower and upper halves, and the rule keeps the upper half exactly when $\tilde{F} (m) \leq u$ . Induction on the $N$ updates shows that the final $ℓ$ is the greatest such left endpoint and $r$ is the next grid point. As $u$ increases, the predicate set can only grow, so the selected cell midpoint $g (u)$ is nondecreasing.

2.1givenF1A1A4A5step 1.1algebra

The successful call's endpoint test gives $F (a) \leq u \leq F (b)$ . By [F1], $Q (u) \leq Q (u)$ gives $u \leq F (Q (u))$ , while every $y < Q (u)$ satisfies $F (y) < u$ . If $Q (u) = a$ , the endpoint test and [F1] give $F (Q (u)) = u$ . If $Q (u) > a$ , take $y_{n} = Q (u) - (Q (u) - a) / (n + 1)$ for $n \in N$ ; then $y_{n} \in [a, Q (u))$ and $y_{n} ↑ Q (u)$ . Continuity of $F$ on $[a, b]$ gives $F (Q (u)) = \lim_{n} F (y_{n}) \leq u$ . Thus $F (Q (u)) = u$ in either case. Since $Q (u), \hat{x} \in [a, b]$ , [A4] gives $m ∣ \hat{x} - Q (u) ∣ \leq ∣ F (\hat{x}) - F (Q (u)) ∣ \leq ε$ by step 1.1.

2.2A1A2F2A6step 1.2algebra

Fix $x$ and set $E = {u \in [0, 1] : g (u) \leq x}$ and $t = \sup (E \cup {0})$ . Monotonicity makes $E$ an initial interval. If $u < t$ , then $u \in E$ , so $\tilde{F} (x) \geq \tilde{F} (g (u)) \geq u - ε$ . If $u > t$ , then $u \notin E$ , so $g (u) > x$ and $\tilde{F} (x) \leq \tilde{F} (g (u)) \leq u + ε$ . Taking one-sided limits gives $∣ \tilde{F} (x) - t ∣ \leq ε$ ; if $t = 0$ or $1$ , the missing side follows from $0 \leq \tilde{F} (x) \leq 1$ . The set $E$ is either an initial closed or open interval, or empty/all; its $q$ -bit midpoint-grid probability differs from $t$ by at most $δ_{q}$ , using the strict or non-strict CDF bound in [F2]. Thus $d_{K} (L (g (U_{q})), \tilde{F}) \leq δ_{q} + ε$ .

3.1A2step 2.2algebra∎

The uniform CDF error implies $d_{K} (\tilde{F}, F) \leq η$ . The triangle inequality for the supremum norm of CDF differences and step 2.2 give the stated $δ_{q} + ε + η$ bound.

Depends on

Used by

A vanishing density prevents a uniform linear spatial inverse bound Example

Dependency tree · two levels

49 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 II §2.2, bisection inversion (standard reference, not scraped)
D. Pollard, A User's Guide to Measure Theoretic Probability, generalized inverse discussion (standard reference, not scraped)