ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passverified 2026-10-22 (gpt-6.1-sol)

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.

Product-law overlap explosion

Example

Let $S$ be a finite nonempty set and let $p_{0}, p_{1} : S \to (0, 1]$ be distinct strictly positive probability mass functions, so $\sum_{s \in S} p_{i} (s) = 1$ for $i = 0, 1$ . For strictly positive probability mass functions $ν, μ : T \to (0, 1]$ on any finite nonempty set $T$ (so $\sum_{x \in T} ν (x) = \sum_{x \in T} μ (x) = 1$ ), define $χ^{2} (ν ∥ μ) = \sum_{x \in T} μ (x) (ν (x) / μ (x) - 1)^{2}$ . For each integer $m \geq 1$ , define $π_{i}^{(m)} : S^{m} \to (0, 1]$ by $π_{i}^{(m)} (x_{1}, \dots, x_{m}) : = \prod_{j = 1}^{m} p_{i} (x_{j})$ ; these are the positive product probability mass functions. Then

$1 + χ^{2} (π_{1}^{(m)} ∥ π_{0}^{(m)}) = {(1 + χ^{2} (p_{1} ∥ p_{0}))}^{m} .$

On a probability space $(Ω, F, P)$ , let $X_{1}, \dots, X_{N} : Ω \to (S^{m}, P (S^{m}))$ be independent random variables with common law $π_{0}^{(m)}$ , where $N \geq 1$ . Define the one-stage raw-ratio estimator $\hat{r} = N^{- 1} \sum_{j = 1}^{N} π_{1}^{(m)} (X_{j}) / π_{0}^{(m)} (X_{j})$ . Its relative variance is $((1 + χ^{2} (p_{1} ∥ p_{0}))^{m} - 1) / N$ . Since $p_{0} \neq p_{1}$ , keeping this relative variance at most a fixed $ε > 0$ requires $N \geq ((1 + χ^{2} (p_{1} ∥ p_{0}))^{m} - 1) / ε$ , an exponential sample-size bound for this one-stage estimator.

Example references

Finite partition-ratio estimator and overlap variance

Facts & Assumptions

Given: A finite nonempty alphabet $S$ , distinct strictly positive probability mass functions $p_{0}, p_{1}$ , integers $m, N \geq 1$ , a tolerance $ε > 0$ , and the product laws in the Example.

[F1]

Finite partition-ratio estimator and overlap variance: for finite positive weights and $N$ independent draws with common reference law, the relative variance of the raw-weight partition-ratio estimator is $χ^{2} (π_{1} ∥ π_{0}) / N$ .

Verification

Given: [F1] and the finite product laws in the Example.

1.1givenalgebra

For $x = (x_{1}, \dots, x_{m}) \in S^{m}$ , the likelihood ratio is $π_{1}^{(m)} (x) / π_{0}^{(m)} (x) = \prod_{j = 1}^{m} p_{1} (x_{j}) / p_{0} (x_{j})$ . Factoring the finite sum gives $1 + χ^{2} (π_{1}^{(m)} ∥ π_{0}^{(m)}) = \sum_{x} π_{0}^{(m)} (x) (π_{1}^{(m)} (x) / π_{0}^{(m)} (x))^{2} = {(\sum_{s \in S} p_{0} (s) (p_{1} (s) / p_{0} (s))^{2})}^{m} = (1 + χ^{2} (p_{1} ∥ p_{0}))^{m}$ .

2.1F1givenstep 1.1algebra∎

Because $p_{0} \neq p_{1}$ and $p_{0} (s) > 0$ at every $s$ , at least one term in $\sum_{s} p_{0} (s) (p_{1} (s) / p_{0} (s) - 1)^{2}$ is positive, so $ρ : = 1 + χ^{2} (p_{1} ∥ p_{0}) > 1$ . Applying [F1] with $N$ draws gives relative variance $(ρ^{m} - 1) / N$ ; the bound $(ρ^{m} - 1) / N \leq ε$ forces $N \geq (ρ^{m} - 1) / ε$ . This establishes exponential growth for the stated one-stage estimator and makes no cost claim for bridge or other methods.

Depends on

Finite partition-ratio estimator and overlap variance