 Randomized symmetric finite-difference derivative estimator

Let $Z_i$ be independent Rademacher random variables and observe $Y_i=g(x_0+h{Z}_i)+{ϵ}_i$, where the noises are independent of the $Z_i$ and of one another, with zero mean and variance ${\sigma }^2$. Assume the baseline $g(x_0)$ is known exactly and $|g^{\prime \prime }|\le M$ on the sampled interval. The estimatoruses function values on both sides of $x_0$. A first-order Taylor expansion givesThe average remainder therefore has squared magnitude at most $M^2{h}^2/4$, while the independent zero-mean noise contribution has variance ${\sigma }^2/(N{h}^2)$. Their cross term vanishes after conditioning on the sample directions, provingThe noise assumptions and exact baseline belong to this bound. Correlated or biased errors, or an independently estimated baseline, require their own error calculation.