Expected bit-query cost of unknown-count BBHT search

In a round with stage size $M_{\mathrm{\ell }}$, there is one direct test, at most $M_{\mathrm{\ell }}$ iterate queries by [F4], and one candidate verification. Thus the round makes at most $M_{\mathrm{\ell }}+2\le (3\mathrm{/}2{)}^{\mathrm{\ell }}+3$ bit queries.

Now let $0<a<3\mathrm{/}4$ and let $L$ be the first stage with $M_L\ge 4\mathrm{/}\sqrt{a}$, which exists because $(3\mathrm{/}2{)}^{\mathrm{\ell }}\to \mathrm{\infty }$. Minimality gives $(3\mathrm{/}2{)}^{L-1}<4\mathrm{/}\sqrt{a}$ and $M_L\le (3\mathrm{/}2{)}^L+1<6\mathrm{/}\sqrt{a}+1\le 7\mathrm{/}\sqrt{a}\mathrm{.}$ Also $(3\mathrm{/}2{)}^m\ge 1+m\mathrm{/}2$ by induction, so the threshold is reached by $m=\lceil 8\mathrm{/}\sqrt{a}\rceil$; thus $L=O(1\mathrm{/}\sqrt{a})$. The absorptions of the additive constants use [F7].

First suppose $a\ge 3\mathrm{/}4$. Each round succeeds at least on its direct uniform sample, with probability at least $3\mathrm{/}4$ by [F1]. The probability of reaching round $\mathrm{\ell }$ is at most $(1\mathrm{/}4{)}^{\mathrm{\ell }-1}$. Hence the expected total query count over any finite number of rounds is bounded by ${\sum }_{\mathrm{\ell }\ge 1}(1\mathrm{/}4{)}^{\mathrm{\ell }-1}((3\mathrm{/}2{)}^{\mathrm{\ell }}+3),$ a convergent geometric series because $(3\mathrm{/}2)\mathrm{/}4=3\mathrm{/}8<1$. It is an absolute constant, hence $O(1\mathrm{/}\sqrt{a})$ by [F7].

Before stage $L$, bound every reach probability by $1$. The geometric sum of $(3\mathrm{/}2{)}^{\mathrm{\ell }}$ over $\mathrm{\ell }<L$ is at most $3(3\mathrm{/}2{)}^{L-1}<12\mathrm{/}\sqrt{a}$, while the additive $3$ per round contributes $3(L-1)=O(1\mathrm{/}\sqrt{a})$ by step 1.2. Thus the early-stage expected query count is $O(1\mathrm{/}\sqrt{a})$.

At every stage $\mathrm{\ell }\ge L$, [F2] bounds the conditional failure probability by $5\mathrm{/}8$. Therefore the probability of reaching $L+k$ is at most $(5\mathrm{/}8{)}^k$. Since $M_{L+k}\le (3\mathrm{/}2{)}^k{M}_L+1,$ the tail expected query count is at most ${\sum }_{k\ge 0}(5\mathrm{/}8{)}^k((3\mathrm{/}2{)}^k{M}_L+3),$ which is $16M_L+8=O(1\mathrm{/}\sqrt{a})$ because $(5\mathrm{/}8)(3\mathrm{/}2)=15\mathrm{/}16<1$, $M_L\le 7\mathrm{/}\sqrt{a}$ by step 1.2, and $8=O(1\mathrm{/}\sqrt{a})$ by [F7].

Any finite $M$-step execution prefix can begin at most $M$ rounds because each attempted round starts with a direct sample query; if the prefix ends inside a round, its query count is bounded by that completed round's bound in step 1.1. Summing the reach-probability-weighted round bounds through the prefix is therefore at most the full sums in steps 1.2 and 2.2–2.3, uniformly in $M$. The supremum over finite prefixes in [F5] is bounded by those convergent geometric sums. [F3] gives almost-sure termination for $t>0$; the expected bound is for bit queries only, with other coordinates separate by [F8]. Since $1\mathrm{/}\sqrt{a}=\sqrt{N\mathrm{/}t}$, the expected bit-query cost is $O(\sqrt{N\mathrm{/}t})$. If $t=0$, every round issues a direct sample query and continues, so a finite prefix after $R$ completed rounds has expected query count at least $R$; the supremum is infinite.