Theorem 6.1 (corrected) — $R_M$ is an $(\epsilon,\delta)$-approximator for $M \ge \frac12\epsilon^{-2}n^2\mathrm{rank}^{-2}(A)\ln(2/\delta)\kappa_f^2(A)$

Let $A \in \mathbb{R}^{n\times n}$ be a nonzero symmetric positive semi-definite matrix, and let $\kappa_f(A)$ be the ratio between its largest and smallest nonzero eigenvalue. Let $\epsilon > 0$ and $0 < \delta < 1$. Let $R_M = \frac1M\sum_{i=1}^M z_i^TAz_i$ be a normalized Rayleigh-quotient trace estimator of $A$: $z_1, \ldots, z_M$ are independent random vectors with $z_i^Tz_i = n$ and $\mathrm{E}(z_i^TAz_i) = \mathrm{trace}(A)$. If

then $R_M$ is an $(\epsilon,\delta)$-approximator of $\mathrm{trace}(A)$, that is,

The bound holds for every estimator in the class at once — Hutchinson's, the unit vector estimator, and any other normalized one — and needs no assumption on the distribution of the $z_i$ beyond normalization and unbiasedness. Its price is the factor $\kappa_f^2(A)$, so it is informative for well-conditioned matrices.

Formalization Note The paper prints the threshold as $M \ge \frac12\epsilon^{-2}n^{-2}\mathrm{rank}^2(A)\ln(2/\delta)\kappa_f^2(A)$ (Theorem 6.1 and Table I); its proof on p. 8:10 ends with $M \ge \ln(2/\delta)\,n^2\kappa_f^2(A)/(2\,\mathrm{rank}^2(A)\epsilon^2)$, with the exponents of $n$ and $\mathrm{rank}(A)$ swapped. The printed version is false: for $n = 2$, $A = e_1e_1^T$, $z = \sqrt2\,e_k$ with $k$ uniform on $\{1,2\}$, and $\epsilon = \delta = 1/2$, it admits $M = 1$, while $R_1 \in \{0, 2\}$ is never within $1/2$ of $\mathrm{trace}(A) = 1$. The statement here is the one the proof establishes. The probabilistic model is a general probability space $(\Omega,P)$ with IsNormalizedRayleighSample P A z (measurable, mutually independent, $z_i^Tz_i = n$ almost surely, unbiased for this $A$); the hypotheses are satisfiable (Rademacher vectors, or $\sqrt n\,e_k$ with $k$ uniform). The assumptions $A \ne 0$ and $M \ge 1$ are implicit on the page ($\kappa_f$ and $1/M$ must make sense).