Pipeline-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.

Rare event importance sampling and multilevel splitting — Examples

1 · Prerequisites

2 · Summary

These worked cases calculate a Gaussian tail-tilt contribution, compare independent splitting allocations at equal work for a two-period queue, and show that a cross-entropy pilot can miss a positive-probability event. The counterexamples separate correct level marginals from independent level samples and distinguish a zero SIR particle prefix from a zero event probability. A deterministic path shows a finite grid can miss a crossing. The discrete importance-sampling example has finite mean and infinite second moment.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

Gaussian barrier under the prescribed exponential tilt

Example

Assume AC. Take $P = N (0, 1)$ , target $A = [2, \infty)$ , and proposal $Q = N (2, 1)$ . The likelihood contribution is $Z = 1_{{X \geq 2}} \exp (- 2 X + 2)$ . The one-draw estimator is unbiased with finite second moment, with $E_{Q} Z = \overset{ˉ}{Φ} (2)$ and $E_{Q} Z^{2} = e^{4} \overset{ˉ}{Φ} (4)$ .

Facts & Assumptions

Given: The standard-normal target, barrier $2$ , translated-normal proposal, and likelihood contribution above.

[F1]

Gaussian tail tilting is logarithmically efficient but not bounded-relative-error: For $a > 0$ and $Q_{a} = N (a, 1)$ , the event contribution has mean $\overset{ˉ}{Φ} (a)$ and second moment $e^{a^{2}} \overset{ˉ}{Φ} (2 a)$ .

Verification

technique · direct

1.1F1givenalgebra

Set $a = 2$ in [F1]. Then $A_{a} = [2, \infty)$ , $Q_{a} = N (2, 1)$ , and the density ratio on the event is $\exp (- 2 X + 2)$ , giving the displayed contribution and moments.

2.1F1step 1.1algebra∎

Since $\overset{ˉ}{Φ} (2) > 0$ and $\overset{ˉ}{Φ} (4) < \infty$ , the mean is positive and finite and the second moment is finite. Thus the example has finite variance, while the asymptotic divergence in relative error concerns the family $a \to \infty$ , not this single barrier.

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

Two-stage queue overflow and a redundant split at equal work

Example

Consider a two-period single-server queue with no service during these two periods and independent Bernoulli arrivals $B_{1}, B_{2}$ , each with probability $1 / 2$ . Capacity is one, so overflow occurs when both arrivals occur. Let $A_{1} = {B_{1} + B_{2} \geq 1}$ and $A_{2} = {B_{1} + B_{2} = 2}$ . Then $P (A_{1}) = 3 / 4$ , $P (A_{2} ∣ A_{1}) = 1 / 3$ , and $P (A_{2}) = 1 / 4$ .

Under unit cost per conditional draw, use two draws at each of the two levels for work $4$ . Compare with an augmented chain having two repeated $A_{1}$ levels before $A_{2}$ , and one draw at each of four levels, also work $4$ . The added levels have conditional probability one but the estimator has larger relative variance.

Facts & Assumptions

Given: The two independent Bernoulli arrivals, nested events $A_{1} \supseteq A_{2}$ , unit draw cost, and the two stated independent-splitting designs.

[F1]

Independent fixed-level splitting: The estimator is a product of independent sample means of level indicators, with $N$ conditional draws per level.

[F2]

Independent splitting estimator moments and work: Its relative variance is $\prod_{ℓ} (1 + (1 - p_{ℓ}) / (N p_{ℓ})) - 1$ , and unit-cost work for $L$ levels is $N L$ .

Verification

technique · direct

1.1givenalgebra

The four arrival outcomes are equiprobable. Exactly three have at least one arrival and exactly one has two arrivals; hence $P (A_{1}) = 3 / 4$ , $P (A_{2}) = 1 / 4$ , and $p_{2} = (1 / 4) / (3 / 4) = 1 / 3$ .

2.1F1F2step 1.1algebra

The two designs use the product estimator specified in [F1]. With two levels and $N = 2$ , [F2] gives relative variance $(1 + \frac{1 / 4}{2 (3 / 4)}) (1 + \frac{2 / 3}{2 (1 / 3)}) - 1 = \frac{7}{6} \cdot 2 - 1 = \frac{4}{3} .$ The work is $2 \cdot 2 = 4$ .

2.2F2step 1.1algebra

In the augmented chain, the conditional probabilities are $3 / 4, 1, 1, 1 / 3$ , and $N = 1, L = 4$ . The two unit-probability factors in [F2] equal one, while the other factors are $4 / 3$ and $3$ ; the relative variance is $4 - 1 = 3$ , with work $1 \cdot 4 = 4$ .

3.1step 2.1step 2.2algebra∎

Since $3 > 4 / 3$ , equal work does not make the redundant-level design equally precise. Its unit-probability stages add cost without reducing the one-draw randomness left in the two nontrivial levels.

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

A pilot with no rare-event hit returns failure

Example

Let $P$ be Bernoulli on ${0, 1}$ with $P ({1}) = 1 / 10$ , set $A = {1}$ , and use the one-member proposal family $q = P$ . A pilot of size $m \geq 1$ misses $A$ with positive probability even though the target probability is positive.

Facts & Assumptions

Given: $Y_{1}, \dots, Y_{m}$ are IID Bernoulli $(1 / 10)$ , the target event is $A = {1}$ , and the pilot rule in Independent-pilot cross-entropy proposal fitting and production is used.

[F1]

Independent-pilot cross-entropy proposal fitting and production: If no pilot sample lies in $A$ , the algorithm returns the status pilot-no-hit.

[F2]

Independent cross-entropy production is conditionally unbiased: Conditional unbiasedness applies only after a successful pilot and admissible production proposal.

Verification

technique · direct

1.1givenalgebra

By the IID assumption, $P (Y_{1} \notin A, \dots, Y_{m} \notin A) = \prod_{j = 1}^{m} P (Y_{j} = 0) = (9 / 10)^{m} > 0.$ Also $P (A) = 1 / 10 > 0$ .

2.1F1F2step 1.1given∎

On this positive-probability pilot event, [F1] returns pilot-no-hit, so no fitted proposal or production estimate is returned. The positive target probability therefore does not imply pilot success; [F2] makes no production-unbiasedness assertion on this failure branch.

CounterexampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

Correct level marginals do not justify a dependent product

Statement refuted

Correct marginal success probabilities at every level suffice for the product of level sample means to be unbiased when the level samples are dependent.

Facts & Assumptions

Given: Let $Ω = {1, 2, 3, 4}$ with uniform $P$ , $A_{1} = {1, 2}$ , $A_{2} = {1}$ , and use one sample at each level.

[F1]

Nested rare-event levels and conditional laws: The level probabilities are $p_{1} = P (A_{1})$ , $p_{2} = P (A_{2}) / P (A_{1})$ , and the target is $P (A_{2}) = p_{1} p_{2}$ .

[F2]

Independent fixed-level splitting: The two-level product estimator is the product of the two level indicator means; the prescribed algorithm requires independent level arrays.

[F3]

Independent splitting estimator moments and work: Under level independence, the product estimator has expectation $p_{1} p_{2}$ .

Counterexample

1.1F1givenconstruct

Let $U, V$ be independent Bernoulli $(1 / 2)$ . Construct the level-one sample by $X_{1} = 1 + V$ if $U = 1$ , and $X_{1} = 3 + V$ if $U = 0$ ; then $X_{1} \sim P$ . Construct $X_{2} = 1$ if $U = 1$ , and $X_{2} = 2$ if $U = 0$ ; then $X_{2} \sim P (\cdot ∣ A_{1})$ .

2.1F1F2step 1.1algebra

The correct marginal success probabilities are $P (X_{1} \in A_{1}) = 1 / 2$ and $P (X_{2} \in A_{2}) = 1 / 2$ . But the two indicators both equal $U$ , so their product has expectation $1 / 2$ , while $P (A_{2}) = 1 / 4$ . Thus dependence biases the product despite both correct marginals, and it violates the independence condition in [F2].

3.1F2F3step 2.1∎

The unbiasedness conclusion in [F3] has the stated independence hypothesis; it cannot be applied to this coupling. The target counterexample refutes the proposed implication.

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

A zero-particle prefix does not prove a zero event probability

Example

Take $Ω = {0, 1}$ with uniform law, a single level $A_{1} = {0}$ , and $N = 2$ SIR particles. The event probability is positive, but the all-zero first event-potential branch has positive probability and returns the zero estimate.

Facts & Assumptions

Given: $P$ is uniform on ${0, 1}$ , $A_{1} = {0}$ , and the full-resampling SIR splitting algorithm is used with $L = 1, N = 2$ .

[F1]

Nested rare-event levels and conditional laws: A one-level target has probability $P (A_{1})$ .

[F2]

Full-resampling fixed-level SIR splitting with invariant mutations: If any incremental event-weight average is zero, the algorithm returns status zero-particle-prefix and estimate zero.

[F3]

Fixed-level full-resampling SIR splitting is unbiased: The estimator is unbiased in expectation under the theorem's positive-prefix model.

Verification

technique · direct

1.1F1givenalgebra

$P (A_{1}) = 1 / 2 > 0$ . The two initial particles are IID from $P$ , so the probability that both equal $1$ and therefore both have zero $A_{1}$ -weight is $(1 / 2)^{2} = 1 / 4$ .

2.1F2F3step 1.1given∎

On this branch resampling the initial population still selects only particles equal to $1$ , and the identity transition $M_{1}$ leaves them there. Thus the first average event weight, from $G_{1} = 1_{A_{1}}$ , is zero, so [F2] returns estimate zero despite $P (A_{1}) > 0$ . This does not contradict [F3]: unbiasedness is an expectation over all branches and does not imply that each realization is positive.

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

A finite grid can miss a continuous-time crossing

Example

On $[0, 1]$ , let the deterministic continuous path be $x (t) = 1 - 2 ∣ t - 1 / 2 ∣$ , and define the target crossing event as ${\sup_{0 \leq t \leq 1} x (t) \geq 3 / 4}$ . Sampling only at grid times ${0, 1}$ misses the crossing.

Facts & Assumptions

Given: The path $x (t) = 1 - 2 ∣ t - 1 / 2 ∣$ , the threshold $3 / 4$ , and the endpoint grid ${0, 1}$ .

[F1]

Finite-budget stopped-event kernel with a cemetery outcome: A finite-budget status reports a target hit only when that target is reached at an inspected state within the budget.

[F2]

Finite-budget stopped-kernel measurability and event normalizer: The finite-budget normalizer is the probability of a target hit by the budget.

[F3]

Truncation and total-variation errors for stopped crossings: A grid-detected event contained in the continuous target has probability bias equal to the probability of the missed-crossing event; no rate follows without an additional bound.

Verification

technique · direct

1.1givenalgebra

The path satisfies $x (0) = x (1) = 0 < 3 / 4$ , while $x (1 / 2) = 1 \geq 3 / 4$ . Thus the continuous crossing event occurs and endpoint-grid detection fails.

2.1F1F2F3step 1.1given∎

The model is deterministic, so its continuous crossing probability is $1$ and the grid-detected probability is $0$ ; their absolute bias is $1$ . This is exactly the missed-crossing event in [F3], and no error rate in grid spacing can be inferred from this single example.

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

An unbiased importance-sampling weight can have infinite second moment

Example

Let $Ω = {1, 2, \dots}$ , $P (k) = c_{2} / k^{2}$ , and $Q (k) = c_{3} / k^{3}$ , where $c_{s} = (\sum_{k = 1}^{\infty} k^{- s})^{- 1}$ . For $A_{m} = {k \geq m}$ , the ordinary importance-sampling contribution is unbiased and integrable, but its second moment is infinite.

Facts & Assumptions

Given: The probability mass functions above, the event $A_{m}$ for fixed $m \geq 1$ , and proposal law $Q$ .

[F1]

Ordinary importance sampling: The single-draw contribution is $1_{A_{m}} (X) P (X) / Q (X)$ for $X \sim Q$ .

[F2]

Ordinary importance sampling is unbiased: If the target event law is absolutely continuous with respect to the proposal and the weighted contribution is integrable, its expectation is $P (A_{m})$ .

[F3]

Ordinary importance sampling has finite variance and a CLT under a weighted second moment: A finite weighted second moment is a sufficient condition for finite variance.

[F4]

Rare-event efficiency and work criteria: Efficiency criteria record whether the second moment is finite; finite variance is not implied by unbiasedness alone.

Verification

technique · direct

1.1givenalgebra

Both constants are finite and positive because the defining series converge for exponents $2$ and $3$ , and $Q (k) > 0$ for every $k$ ; hence $P ≪ Q$ . The likelihood ratio is $P (k) / Q (k) = (c_{2} / c_{3}) k$ .

2.1F1F2step 1.1algebra

By [F1], $E_{Q} Z = \sum_{k = m}^{\infty} \frac{c_{3}}{k^{3}} \frac{c_{2}}{c_{3}} k = c_{2} \sum_{k = m}^{\infty} k^{- 2} = P (A_{m}) \in (0, \infty),$ so [F2] confirms unbiasedness.

3.1F3F4step 1.1algebra∎

The second moment is $E_{Q} Z^{2} = \sum_{k = m}^{\infty} \frac{c_{3}}{k^{3}} {(\frac{c_{2}}{c_{3}} k)}^{2} = \frac{c_{2}^{2}}{c_{3}} \sum_{k = m}^{\infty} \frac{1}{k} = \infty$ by divergence of the harmonic tail. Thus the weighted second-moment hypothesis in [F3] is absent and this unbiased estimator has infinite variance; [F4] therefore rules out describing its second-moment efficiency as finite.

Rare event importance sampling and multilevel splitting — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Gaussian barrier under the prescribed exponential tilt

Example

Facts & Assumptions

Verification

Two-stage queue overflow and a redundant split at equal work

Example

Facts & Assumptions

Verification

A pilot with no rare-event hit returns failure

Example

Facts & Assumptions

Verification

Correct level marginals do not justify a dependent product

Statement refuted

Facts & Assumptions

Counterexample

A zero-particle prefix does not prove a zero event probability

Example

Facts & Assumptions

Verification

A finite grid can miss a continuous-time crossing

Example

Facts & Assumptions

Verification

An unbiased importance-sampling weight can have infinite second moment

Example

Facts & Assumptions

Verification

Sources