TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck pass

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.

Gaussian tail tilting is logarithmically efficient but not bounded-relative-error

Statement

Assume AC. Let $P = N (0, 1)$ , $A_{a} = [a, \infty)$ , $p_{a} = P (A_{a}) = \overset{ˉ}{Φ} (a)$ , and $Q_{a} = N (a, 1)$ , for $a > 0$ . Let $Z_{a} = 1_{A_{a}} (X) d P / d Q_{a} (X)$ for $X \sim Q_{a}$ , and let ${\hat{p}}_{a, n}$ be the average of $n$ IID copies. Then $E_{Q_{a}} [Z_{a}] = p_{a}, E_{Q_{a}} [Z_{a}^{2}] = e^{a^{2}} \overset{ˉ}{Φ} (2 a) .$ As $a \to \infty$ , ${\hat{p}}_{a, n}$ is logarithmically efficient, while its one-sample relative error grows asymptotically as $(π / 2)^{1 / 4} \sqrt{a}$ . In particular this tilt is not bounded-relative-error.

Facts & Assumptions

Given: The standard-normal density and tail, the event $A_{a}$ , the proposal $Q_{a}$ , and $a > 0$ .

[A1]

The Axiom of Choice: AC is inherited through Standard normal and normal laws; no further choice is used.

[F1]

Standard normal and normal laws: $N (0, 1)$ has density $ϕ (x) = e^{- x^{2} / 2} / \sqrt{2 π}$ , and $N (a, 1)$ is its translate by $a$ .

[F2]

Standard-normal Mills bounds and logarithmic tail asymptotics: $\overset{ˉ}{Φ} (x) \sim ϕ (x) / x$ and $\log \overset{ˉ}{Φ} (x) \sim - x^{2} / 2$ for $x \to \infty$ .

[F3]

Rare-event efficiency and work criteria: Relative error is $\sqrt{Var (Z_{a})} / p_{a}$ , and logarithmic efficiency is determined by $\log E [Z_{a}^{2}] / \log (p_{a}^{2})$ .

[F4]

Ordinary importance sampling is unbiased: Under the event-support and integrability hypotheses, the ordinary importance-sampling mean equals $p_{a}$ .

[F5]

Ordinary importance sampling has finite variance and a CLT under a weighted second moment: A finite weighted second moment gives $Var (Z_{a}) = E [Z_{a}^{2}] - p_{a}^{2}$ .

[F6]

Unbiasedness and exact variance of the IID Monte Carlo mean: For $n$ IID square-integrable contributions, the sample mean has mean $p_{a}$ and variance $Var (Z_{a}) / n$ .

Proof

1.1A1F1F4givenalgebra

For every $x \in R$ , the density ratio is $ϕ (x) / ϕ (x - a) = \exp (- a x + a^{2} / 2)$ . The proposal has positive density on $A_{a}$ , and $0 \leq Z_{a} \leq e^{- a^{2} / 2}$ on $A_{a}$ , so the event-support and integrability hypotheses of [F4] hold. Hence $E_{Q_{a}} Z_{a} = p_{a}$ .

1.2F1givenalgebra

Direct integration gives $E_{Q_{a}} Z_{a}^{2} = \int_{a}^{\infty} e^{- 2 a x + a^{2}} ϕ (x - a) d x .$ With $y = x - a$ , the integrand becomes $e^{- 2 a y - a^{2}} ϕ (y) = e^{a^{2}} ϕ (y + 2 a)$ ; the integral is $e^{a^{2}} \overset{ˉ}{Φ} (2 a)$ , which is finite for every $a > 0$ .

2.1F2F3F6step 1.2givenalgebra

For the average of $n \geq 1$ IID contributions, [F6] gives $E [{\hat{p}}_{a, n}^{2}] = p_{a}^{2} + \frac{E [Z_{a}^{2}] - p_{a}^{2}}{n}, p_{a}^{2} \leq E [{\hat{p}}_{a, n}^{2}] \leq p_{a}^{2} + E [Z_{a}^{2}] .$ By [F2], $\log p_{a}^{2} = - a^{2} + o (a^{2})$ and $\log E [Z_{a}^{2}] = a^{2} + \log \overset{ˉ}{Φ} (2 a) = - a^{2} + o (a^{2})$ . Therefore also $\log (p_{a}^{2} + E [Z_{a}^{2}]) = - a^{2} + o (a^{2})$ . The two bounds squeeze $\log E [{\hat{p}}_{a, n}^{2}] = - a^{2} + o (a^{2})$ , while $2 \log p_{a} = - a^{2} + o (a^{2})$ . By [F3], the logarithmic-efficiency ratio tends to $1$ .

3.1F2F4F5step 1.2algebra∎

Mills' equivalent in [F2] yields $\frac{E Z_{a}^{2}}{p_{a}^{2}} \sim \frac{e^{a^{2}} ϕ (2 a) / (2 a)}{(ϕ (a) / a)^{2}} = \sqrt{π / 2} a .$ Using [F4] and [F5], $RE ({\hat{p}}_{a, 1})^{2} = E Z_{a}^{2} / p_{a}^{2} - 1 \sim \sqrt{π / 2} a$ ; taking square roots gives the stated divergence.

Depends on

Used by

Gaussian barrier under the prescribed exponential tilt Example

Dependency tree · two levels

30 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

Gino Biondini, An Introduction to Rare Event Simulation and Importance Sampling, Handbook of Statistics 33, Chapter 2, ``3.1–3.4, 8 (standard reference, not scraped)
Patrick Laub, Algorithms for Rare Event Estimation, Short Course, Lecture 1 Part 2, Exponential Tilting (standard reference, not scraped)
NIST Digital Library of Mathematical Functions, `7.12(i), Equation (7.12.1) (standard reference, not scraped)