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) exact | 3.3977e-06; 100,000 draws per batch |
| proposal mean batch estimates (x 1e-6) rel.sd theory | |
| mu | 0.0 0.000 0.000 0.000 0.000 0.000 542.5 |
| mu | 2.0 3.717 3.518 3.660 3.344 3.617 13.7 |
| mu | 4.5 3.358 3.351 3.391 3.381 3.435 2.3 |
| mu | 6.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/p | 294,319; sqrt-law (pi/4)/sqrt(p) = 426 |
| proposal mu | 2.0: P(draw lands in event) = 0.006 |
| proposal mu | 4.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
- Chapter 1 · The Square-Root Wall: a Classical Simulation of Amplitude Amplification and the Lower Bound for Unstructured Search
- Chapter 2 · Annealing, Restarts and the Metropolis Rule: Classical Recipes for Escaping Local Optima
- Chapter 3 · The Burden of Proof for a Speedup: Time to Solution, Scaling Laws and Dequantisation
- Chapter 5 · Shared Structure: Spectral Fingerprints, Exhaustive Mappings and the Typicality of Combinations
- Chapter 6 · A Pipeline for Ramanujan-Style Conjectures: Abundant Generation, Exhaustive Refutation and Exact Bounds
- Chapter 7 · Following the Natural Joints and Reasoning to Hypotheses: Cook Ding, Shen Kuo, Peirce and Hardy
- Chapter 8 · Closing the Empirical Loop: Standard Operating Templates and Checker Specification