arXiv:1704.04538 · v3
A Simple Randomized Estimator for Harmonic Numbers and Logarithms
摘要
Scanning a list of $x$ distinct numbers in uniformly random order for its maximum replaces the running maximum $H_x$ times on average, where $H_x$ is the $x$th harmonic number. Run backwards, this gives an estimator: the replacement count of a random list is an unbiased Monte Carlo estimate of $H_x$, and since $H_x = \ln x + γ+ O(1/x)$, a corrected estimate of $\ln x$. We give the exact variance of the count, an error decomposition with sample-size rules, and an exact sampler of the count using $H_x$ integer draws on average instead of a scan of length $x$. Coupling two counts estimates $\ln(a/b)$ without $γ$, and a binary range reduction then bounds the standard error by $\sqrt{\ln 2/n}$ for every $x$ at fewer than $1.7$ draws per repetition on average. A classical deterministic series on the same reduction reaches the rounding floor with sixteen terms in the reported experiments, quantifying the gap between the two approaches. The purpose is pedagogical: the analysis of an algorithm becomes an estimator of the quantity that analysis produces, with exact variances, finite-sample error bounds, reproducible experiments, and machine-checked algorithm contracts and moment identities. The ingredients are classical; the contribution is their assembly.
作者备注：v3: substantially revised and extended third version; title changed from "A Simple Randomized Algorithm to Compute Harmonic Numbers and Logarithms". 22 pages, 4 figures, 7 tables. Code, data, and Dafny proofs at https://github.com/alidasdan/randomized-harmonic-logarithms