What does Quantum-Inspired Search and Verified Conjectures conclude, in numbers, about “Amplifying Samples by Value: Importance Sampling and Upper Confidence Bounds”?

Answer: Classical statistics has two mature ways of amplifying samples by value. Importance sampling switches to a distribution aimed at the target and corrects with weights: in estimating a normal tail probability, a shift of 4.5 cuts the relative standard deviation of a single draw from 542.5 to 2.3, while too small or too large a shift spoils the gain. The multi-armed bandit learns while sampling: with ten directions and two thousand checks, epsilon-greedy has a regret of 77.9, UCB1 188.0 and even allocation 300.0. Both depend on knowledge of value; prior knowledge and the speed of learning are the real sources of amplification.

Scope of the numbers: Parameters are illustrative and all calculations are generated by the book's programs. Marked boxes separate published evidence, runnable Python calculations (20 programs), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 2.3, 4.5, 542.5

A. P(Z > 4.5) exact3.3977e-06; 100,000 draws per batch
proposal mean batch estimates (x 1e-6) rel.sd theory
mu0.0 0.000 0.000 0.000 0.000 0.000 542.5
mu2.0 3.717 3.518 3.660 3.344 3.617 13.7
mu4.5 3.358 3.351 3.391 3.381 3.435 2.3
mu6.5 3.459 3.286 3.407 3.350 3.287 6.0
B. draws to see one marked item, marked fraction p = exact
classical 1/p294,319; sqrt-law (pi/4)/sqrt(p) = 426
proposal mu2.0: P(draw lands in event) = 0.006
proposal mu4.5: P(draw lands in event) = 0.500
Show the full program
# Chapter 4. p41: importance sampling as classical "amplification".
# Target: the rare-event probability P(Z > 4.5), Z standard normal,
# exact value 0.5 * erfc(4.5 / sqrt 2). Plain Monte Carlo with 100,000
# draws almost never sees the event. Drawing from a shifted normal
# N(mu, 1) and reweighting by exp(-mu x + mu^2 / 2) is unbiased for any
# mu; a well-placed mu concentrates the draws where the value is, a
# badly placed one is worse than doing nothing. Part B compares the draw
# counts with the square-root law for amplitude amplification of a marked
# fraction p (a calculation of query counts only, no hardware). Seeded.
import math
import random
import statistics

A, DRAWS, BATCHES = 4.5, 100000, 5


def q(z):
    return 0.5 * math.erfc(z / math.sqrt(2))


def rel_sd(mu, p):
    # second moment of the weighted indicator: exp(mu^2) Q(A + mu)
    return math.sqrt(math.exp(mu * mu) * q(A + mu) - p * p) / p


def estimate(rng, mu):
    vals = []
    for _ in range(DRAWS):
        x = rng.gauss(mu, 1.0)
        vals.append(math.exp(-mu * x + mu * mu / 2) if x > A else 0.0)
    return statistics.fmean(vals), statistics.pstdev(vals)


if __name__ == "__main__":
    exact = q(A)
    print("A. P(Z > 4.5) exact = {:.4e}; {:,} draws per batch".format(
        exact, DRAWS))
    print("   proposal mean   batch estimates (x 1e-6)     rel.sd theory")
    rng = random.Random(20261120)
    for mu in (0.0, 2.0, 4.5, 6.5):
        ests = [estimate(rng, mu)[0] for _ in range(BATCHES)]
        cells = " ".join("{:6.3f}".format(e * 1e6) for e in ests)
        print("   mu = {:<4}      {}   {:>10.1f}".format(
            mu, cells, rel_sd(mu, exact)))
    print("B. draws to see one marked item, marked fraction p = exact")
    p = exact
    print("   classical 1/p = {:,.0f}; sqrt-law (pi/4)/sqrt(p) = {:,.0f}"
          .format(1 / p, math.pi / 4 / math.sqrt(p)))
    for mu in (2.0, 4.5):
        print("   proposal mu = {}: P(draw lands in event) = {:.3f}".format(
            mu, q(A - mu)))

Single source and citation

Fan, Y. (2026). Quantum-Inspired Combinatorial Search, Abductive Intuition and Computationally Verified Breakthrough Monograph Engineering (Version 1.0.0), Chapter 4: Amplifying Samples by Value: Importance Sampling and Upper Confidence Bounds. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-364 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026364,
  author    = {Fan, Yafu},
  title     = {Quantum-Inspired Combinatorial Search, Abductive Intuition and Computationally Verified Breakthrough Monograph Engineering},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book