Dyadic positive-mean estimator under an L2 bound

The intervals $[0,1),[1,2),\dots ,[2^{k-1},2^k)$ are disjoint and cover $[0,2^k)$. Write $h_{\mathrm{\ell }}$ for the scaled band output in [F1], $q_{\mathrm{\ell }}=\mathbb{E}[h_{\mathrm{\ell }}]$, and $T=\mathbb{E}[h{\mathbf{1}}_{h\ge 2^k}]$. By [F7] and finite-sum additivity, $\mathbb{E}[h]=q_0+{\sum }_{\mathrm{\ell }=1}^k{2}^{\mathrm{\ell }}{q}_{\mathrm{\ell }}+T\mathrm{.}$ Since $h\ge 2^k$ on the tail, $0\le T\le 2^{-k}\mathbb{E}[h^2]=s^2\mathrm{/}{2}^k\le a{s}^2$.

By [F2]–[F3], the $\mathrm{\ell }$th estimate has error at most $2\pi \sqrt{q_{\mathrm{\ell }}(1-q_{\mathrm{\ell }})}\mathrm{/}M+{\pi }^2\mathrm{/}{M}^2$ except with probability $1\mathrm{/}[10(k+1)]$. A union bound over $k+1$ bands makes all estimates satisfy these bounds with probability at least $9\mathrm{/}10$. On that event, the deterministic estimation error is at most $\frac{2\pi }{M}{\sum }_{\mathrm{\ell }=0}^k{2}^{\mathrm{\ell }}\sqrt{q_{\mathrm{\ell }}}+\frac{{\pi }^2}{M^2}{\sum }_{\mathrm{\ell }=0}^k{2}^{\mathrm{\ell }}+T\mathrm{.}$

The least-dyadic choice in [F1] gives $1000\sqrt{k}\mathrm{/}a\le M<2000\sqrt{k}\mathrm{/}a$, since this positive threshold exceeds $2000$. Each binned call has $O(1+\ln (k+1))$ median repetitions. In repeated controlled-$Q$ access it has $M-1=O(\sqrt{k}\mathrm{/}a)$ controlled-Grover calls per repetition by [F1]–[F3]; each includes one supplied state reflection. There are $k+1$ bins. The outer $R_1$ repetitions are $O(1+\ln (1\mathrm{/}{\rho }_1))$ because [F10] makes $U_1\le \ln (1\mathrm{/}{\rho }_1)+1\mathrm{/}4$. Each repetition prepares one fresh state in either access mode. Therefore the total state-copy count is $O(k\ln (k+1)(1+\ln (1\mathrm{/}{\rho }_1)))$, and in repeated access the total reflection count is $O(a^{-1}{k}^{3\mathrm{/}2}\ln (k+1)(1+\ln (1\mathrm{/}{\rho }_1)))$. In supplied-power access each repetition instead makes $m$ power queries, whose actual declared prices are summed; no reflection expansion is assumed.

By [F11], the general expectations in the Hölder application [F6] equal their finite weighted-sum values in [F7]. For the lowest band, [F6] with $X=h$ and $Y={\mathbf{1}}_{h<1}$ gives $q_0=\mathbb{E}[h{\mathbf{1}}_{h<1}]\le s$, since $\mathbb{E}[Y^2]=\mathrm{Pr}(h<1)\le 1$ by [F7]; hence $\sqrt{q_0}\le \sqrt{s}\le 1+s$. For $\mathrm{\ell }\ge 1$, $h\ge 2^{\mathrm{\ell }-1}$ on its band, so $(2^{\mathrm{\ell }}\sqrt{q_{\mathrm{\ell }}}{)}^2=2^{\mathrm{\ell }}\mathbb{E}[h{\mathbf{1}}_{\mathrm{b}\mathrm{a}\mathrm{n}\mathrm{d}}]\le 2\mathbb{E}[h^2{\mathbf{1}}_{\mathrm{b}\mathrm{a}\mathrm{n}\mathrm{d}}]$. Finite Cauchy–Schwarz on the $k$ band terms gives ${\sum }_{\mathrm{\ell }=1}^k{2}^{\mathrm{\ell }}\sqrt{q_{\mathrm{\ell }}}\le \sqrt{2k}s$, because the bands are disjoint. Thus ${\sum }_{\mathrm{\ell }=0}^k{2}^{\mathrm{\ell }}\sqrt{q_{\mathrm{\ell }}}\le (1+\sqrt{2k})(1+s)$.

The parameter choice in [F1] gives $M^2{a}^2\ge {10}^{6}k$ with $Ma\ge 0$, so [F9] implies $M\ge 1000\sqrt{k}\mathrm{/}a$; also $k\ge 2$ because $2a<1$, and minimality gives $2^{k-1}a<1$, hence $2^k<2\mathrm{/}a$. Thus $1+\sqrt{2k}\le (1+\sqrt{2})\sqrt{k}$. By [F9], $2\pi (1+\sqrt{2})\mathrm{/}1000<176\mathrm{/}7000<0.026$ and $4{\pi }^2\mathrm{/}({10}^{6}k)<0.00004$. Thus the first error term in step 1.2 is less than $0.026a(1+s)$, and the second less than $0.00004a$. Together with $T\le a{s}^2$ from step 1.1, their sum is at most $a(1+s{)}^2$, since $0.026(1+s)+0.00004+s^2\le (1+s{)}^2$ for $s\ge 0$.

A single binned execution succeeds with probability at least $9\mathrm{/}10$ by step 1.2, hence at least $4\mathrm{/}5$, and has the stated error by step 3.1. For its median over $R_1$ independent executions, a failure requires at least half the runs to fail; their failure probability is at most $1\mathrm{/}5$, so the deviation from its mean is at least $3R_1\mathrm{/}10$. By [F4] and the chosen $R_1\ge 2\ln (1\mathrm{/}{\rho }_1)\mathrm{/}(3\mathrm{/}10{)}^2$, this probability is at most $\exp (-2R_1(3\mathrm{/}10{)}^2)\le {\rho }_1$: the algorithm uses $R_1\ge \lceil 2U_1\mathrm{/}(3\mathrm{/}10{)}^2\rceil +1$ and [F10] gives $U_1\ge \ln (1\mathrm{/}{\rho }_1)$. This proves the confidence claim.

The reflection count is an oracle coordinate only. By [F5], sampler preparation/inverse, controlled access, data loading, band comparison, value arithmetic, and rotation compilation are additional declared costs.