Simon recovery succeeds with probability at least 1-delta

If $d=0$, the unique nonzero element of ${\mathbb{F}}_2^1$ is $1$, so the budgeted algorithm returns the correct mask with zero queries. The rank process has already reached its target rank zero.

Suppose $d\ge 1$. For each finite horizon $R$, use the finite $R$-round experiment of [F1] and let $Q_R$ count the samples actually taken before reaching rank $d$, capped at $R$. Decompose $Q_R={\sum }_{k<d}{V}_{k,R}$, where $V_{k,R}$ counts the trials spent at rank $k$ and is zero if that rank is not reached within the prefix. Condition on each finite history at the first time rank $k$ is reached, with $r\le R$ rounds remaining. If $r=0$, its remaining contribution is zero; if $r\ge 1$, the rank-growth theorem [F2] gives expected truncated wait at most $2$ on that continuation. If rank $k$ is not reached, the contribution is zero. Summing over these disjoint first-arrival histories gives $\mathbb{E}[V_{k,R}]\le 2$ for every $k<d$, hence $\mathbb{E}[Q_R]\le 2d$. Since $Q_R$ is the query count on the finite $R$-round prefix, [F3] gives expected query cost at most $2d$.

Let $A_R$ be the event, in the finite $R$-round experiment, that the rank is still below $d$ after all $R$ samples. On $A_R$ the process has used all $R$ queries, so $Q_R=R$ and $R\mathrm{Pr}(A_R)\le \mathbb{E}[Q_R]\le 2d$. Therefore $\mathrm{Pr}(T>R):=\mathrm{Pr}(A_R)\le 2d\mathrm{/}R$ for every $R\ge 1$, which tends to zero. This tail argument uses only finite-prefix events and expectations.

In the finite $M$-sample experiment, failure is the event $A_M$ that rank remains below $d$ after all $M$ samples. On $A_M$, $Q_M=M$, so $\mathrm{Pr}(\text{FAIL})\le \mathrm{Pr}(Q_M\ge M)$. The variable $Q_M$ is nonnegative and bounded, and Markov's inequality [F7] gives $\mathrm{Pr}(\text{FAIL})\le \mathbb{E}[Q_M]\mathrm{/}M\le 2d\mathrm{/}M\le \delta$.

For $d\ge 1$, let $A_R$ be as in step 2.1, with $A_0$ the whole zero-round experiment. By consistency of finite-prefix probabilities, extending the $(t-1)$-round experiment to $t$ rounds partitions $A_{t-1}$ into histories that first reach rank $d$ at round $t$ and histories in $A_t$. Define the mass at $T=t$ to be $\mathrm{Pr}(A_{t-1})-\mathrm{Pr}(A_t)$; these masses are nonnegative. Their partial sums telescope to $1-\mathrm{Pr}(A_R)$, and step 2.1 makes the residual mass at infinity zero. The resulting countable masses sum to one. For $d=0$, step 1.1 gives $T=0$. Thus the process terminates almost surely without assuming a measure on infinite histories.

If rank $d$ is reached, all collected rows are independent and lie in $s^{\perp }$ by [F1]–[F2]. The recovery routine therefore returns $s$ by [F5]. Combining this with step 2.2 proves success probability at least $1-\delta$. The finite cap makes at most $M$ sampling rounds. In each round, reducing an incoming row against at most $d$ pivot rows and clearing a new pivot from at most $d-1$ rows requires $O(n^2)$ bit operations; so basis maintenance costs $O(M{n}^2)$. The final reduction costs $O(n^3)$ by [F5]. To compute $M$, the algorithm multiplies binary integers of total length $O(B+\log n)$ and performs long division on integers of at most that length; the schoolbook multiplication, comparisons, shifts, and long division each use $O((B+\log n{)}^2)$ bit operations. These counts use the finite-alphabet Turing-machine convention [F9], giving the stated postprocessing bound.