Proof. If the mutation flips \(k\) bits of which \(i\) are zero-bits and the offspring is accepted, then the number of zero-bits decreases by \(i\) and increases by \((k-i)\), hence \[Y_{t+1}=y-i+(k-i)=y+k-2i,\] so \(Y_t-Y_{t+1}=2i-k\) on \(A\) and \(0\) otherwise. Thus \(Y_t-Y_{t+1}=(2I-K)\mathbf{1}_A\). Taking the conditional expectation given \(Y_t=y\) yields the claim. ◻

Proof. A detailed proof is given in 8.2. ◻

Proof. See 8.3. ◻

Proof. (1) By [prop:pre:drift95convergence], there exists \(c(\chi)>0\) such that uniformly in \(\alpha\in[0,1]\), \[\abs{\Delta(\lfloor \alpha n\rfloor)-D_\chi(\alpha)}\le \frac{c(\chi)}{n}.\] Choose \(n_0\) such that \(c(\chi)/n_0\le \varepsilon\). Then for all \(n\ge n_0\) and all \(\alpha\in[a,b]\), \[\Delta(\lfloor \alpha n\rfloor)\le D_\chi(\alpha)+\frac{c(\chi)}{n} \le -2\varepsilon+\varepsilon=-\varepsilon.\] and hence \(\E{Y_{t+1}-Y_t\mid Y_t=\lfloor \alpha n\rfloor}=-\Delta(\lfloor \alpha n\rfloor)\ge \varepsilon\).

(2) Let \(K_n\sim\mathrm{Bin}(n,\chi/n)\) be the mutation size. In one generation the number of zero-bits changes by at most the number of flipped bits, hence \[\abs{Y_{t+1}-Y_t}\le K_n.\] Therefore for any state \(y\) and any \(j\in\mathbb{N}_0\), \[\Prob{\abs{Y_{t+1}-Y_t}\ge j\mid Y_t=y}\le \Prob{K_n\ge j}.\] For \(j\ge 1\) we apply Markov’s inequality to \(e^{tK_n}\) with a parameter \(t>0\): \[\Prob{K_n\ge j} = \Prob{e^{tK_n}\ge e^{tj}} \le \frac{\E{e^{tK_n}}}{e^{tj}}.\] Since \(K_n\sim\mathrm{Bin}(n,\chi/n)\), \[\E{e^{tK_n}} =\Bigl(1-\frac{\chi}{n}+\frac{\chi}{n}e^t\Bigr)^n \le e^{\chi(e^t-1)}.\] Choosing \(t=\ln 2\) gives \(\E{e^{tK_n}}\le e^\chi\), hence for all \(j\ge 1\), \[\Prob{\abs{Y_{t+1}-Y_t}\ge j\mid Y_t=y}\le \frac{e^\chi}{2^j}.\] For \(j=0\) the bound holds as well since \(e^\chi\ge 1\). ◻

Proof. A proof is given in 8.4. ◻

Proof. Fix a generation \(t\) and write \(W\mathrel{\vcenter{:}}= W^{(t)}\). Conditional on \(K=k\), the set \(F\subseteq[n]\) of flipped positions is a uniformly random \(k\)-subset of \([n]\). Conditional on \((K=k,I=i)\), the set \(G\subseteq F\) of flipped zero-bits is a uniformly random \(i\)-subset of \(F\). The acceptance event \(A\) is determined by \[\sum_{j\in G} W_j \ge \sum_{j\in F\setminus G} W_j.\] By permutation-invariance of \(W\), the distribution of the weights that end up with flipped bits depends only on \(\abs{F}=k\), and conditional on \((K=k,I=i)\) the partition \((G,F\setminus G)\) is uniform among all partitions of \(F\) into parts of size \(i\) and \(k-i\). Consequently, the conditional probability is a function of \((k,i)\) only. ◻

Proof. Condition on \((K=k,I=i)\) in some fixed generation and let \(F\) be the set of flipped positions and \(G\subseteq F\) the set of improving flips. Set \[S\mathrel{\vcenter{:}}=\sum_{j\in G} W^{(t)}_j,\qquad T\mathrel{\vcenter{:}}=\sum_{j\in F\setminus G} W^{(t)}_j.\] Since weights are strictly positive we have \(S+T>0\) and acceptance is the event \(A=\{S\ge T\}\). Define \(R\mathrel{\vcenter{:}}= S/(S+T)\in[0,1]\), so \(A=\{R\ge1/2\}\).

By permutation-invariance and the fact that conditional on \((K=k,I=i)\) the set \(G\) is a uniform \(i\)-subset of \(F\), \[\E{R\mid K=k,I=i}=\frac{i}{k}.\] For the upper bound in ?? , apply Markov’s inequality to the nonnegative random variable \(R\): \[p_A(k,i)=\Prob{R\ge 1/2}\le \frac{\E{R}}{1/2}=\frac{2i}{k}.\] For the lower bound, note that \(R\le 1\) on \(A\) and \(R\le 1/2\) on \(\lnot A\), hence \[\E{R}\le 1\cdot \Prob{A} + \frac{1}{2}\cdot\Prob{\lnot A}\le\frac{1}{2}+\frac{1}{2}\,\Prob{A},\] which rearranges to \(\Prob{A}\ge 2\E{R}-1 = 2i/k-1\). Combining these bounds with \(0\le p_A(k,i)\le 1\) yields ?? .

Finally, let \(i = 1\) and assume \(k \ge 3\). If the offspring is accepted, then the single improving weight is at least the sum of the remaining \(k - 1\) weights, that is, \[W_j \ge \sum_{\ell \in F \setminus \{j\}} W_\ell.\] Moreover, at most one index in \(F\) can satisfy this inequality. Indeed, if distinct \(j,j'\in F\) both satisfied it, then since \(k\ge 3\) and all weights are positive, we would have \[W_j\ge W_{j'} + \sum_{\ell \in F\setminus\{j,j'\}} W_\ell > W_{j'}\qquad\text{and}\qquad W_{j'}\ge W_{j} + \sum_{\ell \in F\setminus\{j,j'\}} W_\ell > W_{j},\] a contradiction. Hence there is at most one position in \(F\) whose weight is at least the sum of all other weights. By permutation-invariance, each position is distinguished with probability at most \(1/k\) which proves ?? . ◻

Proof. Fix \(k,i\). If \(2i-k<0\) then 3 gives \(p_A(k,i)\le \widetilde{p}_A(k,i)\), hence \((2i-k)p_A(k,i)\ge (2i-k)\widetilde{p}_A(k,i)\). If \(2i-k>0\) then 3 gives \(p_A(k,i)\ge \widetilde{p}_A(k,i)\), hence the same inequality holds. In the remaining case \(2i-k=0\), the corresponding term in the drift expansion vanishes, hence the inequality holds trivially. Multiplying the inequality \((2i-k)p_A(k,i)\ge (2i-k)\widetilde{p}_A(k,i)\) by the nonnegative factor \(e^{-\chi}\chi^k/k!\,\binom{k}{i}\alpha^i(1-\alpha)^{k-i}\) and summing over all \(i\in\{0,\dots,k\}\) and \(k\ge 0\) yields \(D_\chi(\alpha)\ge \widetilde{D}_\chi(\alpha)\). ◻

Proof. Analogously to [prop:pre:right95derivative] and its proof in 8.3, we may compute the right derivative of \(\widetilde{D}_\chi\) at \(0\) as \[\partial_+\widetilde{D}_\chi(0) =\sum_{k = 1}^\infty e^{-\chi}\frac{\chi^k}{k!}\,k(2-k)\,\widetilde{p}_A(k,1).\] By definition, \(\widetilde{p}_A(1,1)=1\), and \(\widetilde{p}_A(k,1)=1/k\) for all \(k\ge 3\), while the term \(\widetilde{p}_A(2,1)\) for \(k=2\) is multiplied with \(2-k=0\). Hence \[\begin{align} \partial_+\widetilde{D}_\chi(0) &= \sum_{k = 1}^\infty e^{-\chi}\frac{\chi^k}{k!}\,(2-k) \\ &= \sum_{k = 0}^\infty e^{-\chi}\frac{\chi^k}{k!}\,(2-k)-2e^{-\chi}. \end{align}\] Since \(\sum_{k = 0}^\infty p_k(\chi)=1\) and \(\sum_{k=0}^\infty k\,p_k(\chi)=\chi\) for \(p_k(\chi)=e^{-\chi}\chi^k/k!\), the full sum equals \(2-\chi\), and thus \(\partial_+\widetilde{D}_\chi(0)=2-\chi-2e^{-\chi}\).

For the root statement, consider \(g(\chi)=2-\chi-2e^{-\chi}\). Then \(g(0)=0\), \(g'(\chi)=-1+2e^{-\chi}\) with \(g'(0)=1\), and \(g''(\chi)=-2e^{-\chi}<0\), so \(g\) is strictly concave and increases initially, but satisfies \(g(\chi)\to-\infty\) as \(\chi\to\infty\). Hence \(g\) has exactly one positive root \(\chi_0\), and the sign change is as claimed. ◻

Proof. Fix \(\chi\in(0,\chi_0)\). For all \(k\ge 5\) we have \[\frac{p_{k+1}(\chi)}{p_k(\chi)}=\frac{\chi}{k+1}\le \frac{\chi}{6}.\] Telescoping yields \[\label{eq:add:pois95tail95geom} p_k(\chi)\le p_{5}(\chi)\Bigl(\frac{\chi}{6}\Bigr)^{k-5}\quad\text{for all }k\ge 5.\tag{5}\]

For \(k\ge 2\), differentiating \(b_{k,i}\) twice yields the standard second-difference identity \[\label{eq:add:second95deriv95diff} \widetilde{H}''_k(\alpha) = k(k-1)\sum_{i=0}^{k-2}\bigl(\widetilde{h}_k(i+2)-2\widetilde{h}_k(i+1)+\widetilde{h}_k(i)\bigr)\,b_{k-2,i}(\alpha).\tag{6}\] Moreover, we claim that for all \(k\ge 5\) and \(0\le i \le k - 2\) we have \[\label{eq:add:second95diff95bound} \abs{\widetilde{h}_k(i+2)-2\widetilde{h}_k(i+1)+\widetilde{h}_k(i)}\le 2.\tag{7}\] For \(k =5,6\), 7 is checked directly. For \(k\ge 7\), by the definition of \(\widetilde{p}_A(k,i)\), the function \(i\mapsto \widetilde{h}_k(i)\) is piecewise quadratic, with breakpoints only at \(i\in\{0,1,\lfloor k/2\rfloor,\lceil k/2\rceil\}\). Hence every window \((i,i+1,i+2)\) that does not meet a breakpoint lies entirely in one quadratic branch, and one checks that in this case we have \[\abs{\widetilde{h}_k(i+2)-2\widetilde{h}_k(i+1)+\widetilde{h}_k(i)}=\frac{8}{k}\le 2.\] For the finitely many windows \((i,i+1,i+2)\) that cross a breakpoint, a case distinction on the breakpoints and direct computations using the definition of \(\widetilde{h}_k\) show that the relevant second differences have absolute value at most \(2\).

Inserting 7 into 6 and using \(\sum_{i=0}^{k-2} b_{k-2,i}(\alpha)=1\) gives \[\label{eq:add:Hpp95bound95k} \abs{\widetilde{H}''_k(\alpha)}\le 2k(k-1)\quad\text{for all }k\ge 2.\tag{8}\]

Combining 5 and 8 yields \[\begin{align} \abs*{\sum_{k=5}^{\infty} p_k(\chi)\,\widetilde{H}''_k(\alpha)} &\le 2\,p_5(\chi)\sum_{k=5}^{\infty} k(k-1)\Bigl(\frac{\chi}{6}\Bigr)^{k-5} \\ &= 2\,p_5(\chi)\sum_{j=0}^{\infty} (j+5)(j+4)\Bigl(\frac{\chi}{6}\Bigr)^{j}. \end{align}\] The series has nonnegative coefficients and is therefore increasing in \(\chi\) for \(\chi\in(0,6)\). Since \(\chi_0<8/5<6\), it is bounded by its value at \(\chi=8/5\), i.e.with \(r\mathrel{\vcenter{:}}= \frac{8}{30}=\frac{4}{15}\). Thus we may take \[c \mathrel{\vcenter{:}}= 2\sum_{j=0}^{\infty} (j+5)(j+4)\,r^{j} = \frac{86760}{1331}\approx 65.184.\] ◻

Proof. We have \(\widetilde{D}_\chi(\alpha)=\sum_{k=0}^\infty p_k(\chi)\widetilde{H}_k(\alpha)\), hence \[\widetilde{D}_\chi''(\alpha)=\sum_{k=0}^\infty p_k(\chi)\,\widetilde{H}_k''(\alpha).\] For \(k=0,1\) we have \(\widetilde{H}_k''(\alpha)=0\). For \(k=2,3,4\), a direct computation from the definition of \(\widetilde{p}_A\) yields \[\widetilde{H}_2(\alpha)=2\alpha^2,\qquad \widetilde{H}_3(\alpha)=\alpha^3+3\alpha^2-\alpha,\qquad \widetilde{H}_4(\alpha)=2\alpha^4-2\alpha^3+6\alpha^2-2\alpha,\] and therefore \[\widetilde{H}_2''(\alpha)=4,\qquad \widetilde{H}_3''(\alpha)=6\alpha+6\ge 6,\qquad \widetilde{H}_4''(\alpha)=24\left(\alpha - \frac{1}{4}\right)^2 + \frac{21}{2} \ge \frac{21}{2}.\] Using 6 (with tail starting at \(k=5\)) we obtain, for all \(\alpha\in[0,1]\), \[\begin{align} \widetilde{D}_\chi''(\alpha) &= \sum_{k=2}^{4} p_k(\chi)\widetilde{H}_k''(\alpha) \;+\; \sum_{k=5}^{\infty} p_k(\chi)\widetilde{H}_k''(\alpha) \\ &\ge 4p_2(\chi)+6p_3(\chi)+\frac{21}{2}p_4(\chi) \;-\; c\,p_5(\chi). \end{align}\]

Since \(p_k(\chi)=e^{-\chi}\chi^k/k!\), the right-hand side equals \(e^{-\chi}Q(\chi)\) with \[Q(\chi)=2\chi^2+\chi^3+\frac{21}{48}\chi^4-\frac{c}{120}\chi^5 =2\chi^2+\chi^3+\frac{7}{16}\chi^4-\frac{723}{1331}\chi^5,\] where we used \(c=\frac{86760}{1331}\) from 6. We claim that \(Q(\chi)>0\) for all \(\chi\in(0,8/5]\), and hence in particular for all \(\chi\in(0,\chi_0)\).

Indeed, write \[Q(\chi) = \chi^2\bigl(2 + \chi R(\chi)\bigr), \qquad R(\chi)\mathrel{\vcenter{:}}= 1 + \frac{7}{16}\chi - \frac{723}{1331}\chi^2.\] The function \(R\) is a concave quadratic, so its minimum on \([0,8/5]\) is attained at one of the endpoints. Moreover, \[R(0) = 1\qquad\text{and}\qquad R(8/5)=\frac{20591}{66550}>0.\] Hence \(R(\chi)>0\) for all \(\chi\in[0,8/5]\), and therefore \[Q(\chi) = \chi^2(2+\chi R(\chi))>0\qquad\text{for all }\chi\in(0,8/5).\]

Consequently, \(\widetilde{D}_\chi''(\alpha)\ge e^{-\chi}Q(\chi)>0\) for all \(\alpha\in[0,1]\) and \(\chi\in(0,\chi_0)\), which proves convexity. ◻

Proof. By 7, the function \(\widetilde{D}_\chi\) is convex on \([0,1]\) and satisfies \(\widetilde{D}_\chi(0)=0\). Hence \(\widetilde{D}_\chi(\alpha)\ge \alpha\,\partial_+\widetilde{D}_\chi(0)\) for all \(\alpha\in[0,1]\). The derivative is given by 5, and \(g(\chi)>0\) for \(\chi\in(0,\chi_0)\) by definition of \(\chi_0\). ◻

Proof. Fix \(\chi\in(0,\chi_0)\) and write \(g(\chi)\mathrel{\vcenter{:}}= 2-\chi-2e^{-\chi}>0\). By combining 4 and 1, we have for all \(\alpha\in[0,1]\), \[\label{eq:add:global95positivity} D_\chi(\alpha)\ge g(\chi)\alpha.\tag{9}\] By [prop:pre:drift95convergence], there exists a constant \(c(\chi)>0\) such that, uniformly in \(\alpha\in[0,1]\), \[\label{eq:add:drift95convergence} \abs*{\Delta(\lfloor \alpha n\rfloor)-D_\chi(\alpha)}\le \frac{c(\chi)}{n}.\tag{10}\] Let \[y_0\mathrel{\vcenter{:}}= \left\lceil \frac{2c(\chi)}{g(\chi)}\right\rceil.\] Then for all \(y\ge y_0\), setting \(\alpha=y/n\) and using 9 and 10 yields \[\label{eq:add:mult95drift95lower} \Delta(y)\ge g(\chi)\frac{y}{n}-\frac{c(\chi)}{n}\ge\frac{g(\chi)}{2n}\,y.\tag{11}\]

Define the stopping time \(T_{y_0}\mathrel{\vcenter{:}}= \min\{t\ge 0 : Y_t\le y_0\}\) and the shifted process \[Z_t \mathrel{\vcenter{:}}= \max\{Y_t-y_0,0\}.\] Then \(Z_t\in\{0,1,\dots,n-y_0\}\) and \(T_{y_0}=\min\{t\ge 0: Z_t=0\}\). Moreover, for all \(s\ge 1\), \[\E{Z_t-Z_{t+1}\mid Z_t=s} = \Delta(s+y_0) \ge \frac{g(\chi)}{2n}(s+y_0) \ge \frac{g(\chi)}{2n}\,s,\] where we used 11 . Hence 1 applies to \((Z_t)_{t\ge 0}\) and yields \(T_{y_0}=\Oh{n\log n}\) a.a.s. In particular, the exponential tail bound in 1 implies \[\label{eq:add:runtime95y0} \E{T_{y_0}} = \Oh{n\log n}.\tag{12}\]

To cover the remaining states \(\{1,\dots,y_0\}\) we invoke 2. Its assumptions are satisfied since weights are strictly positive almost surely and the multiplicative drift lower bound 11 holds for all \(y\ge y_0\). Consequently, for all \(n\) sufficiently large, \[\label{eq:add:endgame95exp} \sup_{1\le y\le y_0}\E{T\mid Y_0=y}=\Oh{n},\tag{13}\] and \[\label{eq:add:endgame95tail} \sup_{1\le y\le y_0}\Prob{T>n\log n\mid Y_0=y}=\oh{1}.\tag{14}\]

We now combine the two parts. Recall \(T=\min\{t\ge 0:Y_t=0\}\) and \(T_{y_0}=\min\{t\ge 0:Y_t\le y_0\}\). At time \(T_{y_0}\) we have \(Y_{T_{y_0}}\in\{0,1,\dots,y_0\}\). Since \((Y_t)_{t\ge 0}\) is a time-homogeneous Markov chain, conditioning on \(Y_{T_{y_0}}\) yields \[\begin{align} \E{T} = \E{T_{y_0}} + \E{\E{T-T_{y_0}\mid Y_{T_{y_0}}}} &\le \E{T_{y_0}} + \sup_{1\le y\le y_0}\E{T\mid Y_0=y} \\ &= \Oh{n\log n}, \end{align}\] where we used 12 and 13 .

Moreover, conditioning on \(Y_{T_{y_0}}\) and using 14 gives \[\Prob{T-T_{y_0}>n\log n} \le \sup_{1\le y\le y_0}\Prob{T>n\log n\mid Y_0=y} = \oh{1}.\] Together with \(T_{y_0}=\Oh{n\log n}\) a.a.s., a union bound implies \(T=\Oh{n\log n}\) a.a.s. ◻

Proof. Fix \(k\ge 1\) and condition on the event that mutation flips exactly \(k\) positions, among which exactly \(i\) positions are currently zero-bits. Let \(S\) be this set of flipped positions. In DBV, the weight vector in the current generation is a uniformly random permutation of distinct weights, hence the relative order of weights on \(S\) is uniform over all \(k!\) permutations. In particular, the position in \(S\) carrying the maximum weight is uniformly random over the \(k\) elements of \(S\). The offspring is accepted if and only if this maximum-weight flipped position is a \(0\to 1\) flip, which holds with probability \(i/k\). ◻

Proof. The proof is a direct computation and is deferred to 8.5. ◻

Proof. Fix \(\chi>0\) and write \(B(\chi)\mathrel{\vcenter{:}}= 2-2\chi-2e^{-\chi}\). Then 16 reads \[D_\chi(\alpha)=\alpha\bigl(A(\chi)-\alpha B(\chi)\bigr).\] For all \(\chi>0\) we have \(B(\chi)<0\), so the map \(\alpha\mapsto A(\chi)-\alpha B(\chi)\) is strictly increasing on \([0,1]\). If \(A(\chi)>0\) (i.e.\(\chi<\chi_\mathrm{dbv}\)), then \(A(\chi)-\alpha B(\chi)\ge A(\chi)>0\) for all \(\alpha\in[0,1]\), and thus \(D_\chi(\alpha)>0\) for all \(\alpha\in(0,1]\).

If \(A(\chi)<0\) (i.e.\(\chi>\chi_\mathrm{dbv}\)), then the increasing function \(\alpha\mapsto A(\chi)-\alpha B(\chi)\) has a unique root \[\alpha^*(\chi)=\frac{A(\chi)}{B(\chi)}=\frac{2-\chi-2e^{-\chi}}{2-2\chi-2e^{-\chi}}.\] Since both \(A(\chi)\) and \(B(\chi)\) are negative, we have \(\alpha^*(\chi)>0\). Moreover \(\alpha^*(\chi)<1\) is equivalent to \(A(\chi)>B(\chi)\), i.e.\(\chi>0\). Thus \(\alpha^*(\chi)\in(0,1)\) and the sign change of \(A(\chi)-\alpha B(\chi)\) yields the stated sign pattern for \(D_\chi(\alpha)\) on \((0,1]\).

For \(\chi\to\infty\), since \(e^{-\chi}\to 0\), we have \(\alpha^*(\chi)\to (2-\chi)/(2-2\chi)=\frac{1}{2}\). ◻

Proof. The proof is a direct computation and is deferred to 8.6. ◻

Proof. Recall \(\alpha=y/n\) and \(r_n(\chi)=(1-\chi/n)^n\). From 17 , \[\Delta(y)=\frac{n}{n-1}\,\alpha\Bigl(\bigl(2-\chi-2r_n(\chi)-\tfrac{\chi}{n}\bigr) -\alpha\bigl(2-2\chi-2r_n(\chi)\bigr)\Bigr).\] For fixed \(\chi>0\) we have \(r_n(\chi)\to e^{-\chi}\) as \(n\to\infty\), hence \[2-2\chi-2r_n(\chi)\to 2-2\chi-2e^{-\chi}<0.\] Therefore, for all sufficiently large \(n\) we have \(2-2\chi-2r_n(\chi)<0\), and thus \[-\alpha\bigl(2-2\chi-2r_n(\chi)\bigr)\ge 0.\] Consequently, \[\Delta(y)\ge \frac{n}{n-1}\,\alpha\bigl(2-\chi-2r_n(\chi)-\tfrac{\chi}{n}\bigr) \ge \alpha\bigl(2-\chi-2r_n(\chi)-\tfrac{\chi}{n}\bigr).\]

Moreover, \(r_n(\chi)\le e^{-\chi}\) implies \(2-\chi-2r_n(\chi)\ge 2-\chi-2e^{-\chi}\). Choose \(n_0\) such that \(\chi/n\le (2-\chi-2e^{-\chi})/2\) for all \(n\ge n_0\). Then for \(n\ge n_0\), \[\Delta(y)\ge \alpha\,\frac{2-\chi-2e^{-\chi}}{2} =\frac{2-\chi-2e^{-\chi}}{2n}\,y.\] ◻

Proof. By 15 and 18 , we may write \[\alpha^*(\chi) = \frac{a}{b},\qquad\alpha_n^*(\chi) = \frac{a_n}{b_n},\] where \[a \mathrel{\vcenter{:}}= 2 - \chi - 2e^{-\chi},\qquad b \mathrel{\vcenter{:}}= 2 - 2\chi - 2e^{-\chi},\] and \[a_n \mathrel{\vcenter{:}}= 2 - \chi - 2(1-\chi/n)^n-\chi/n,\qquad b_n \mathrel{\vcenter{:}}= 2 - 2\chi - 2(1 - \chi/n)^n.\] By [@doerr2019probabilistic], for all \(n\ge \chi\), \[\left(1-\frac{\chi}{n}\right)^n \le e^{-\chi}\le \left(1-\frac{\chi}{n}\right)^{n-\chi},\] which implies, for fixed \(\chi\), \[\Big(1-\frac{\chi}{n}\Big)^n = e^{-\chi} + \Oh{1/n}.\] Therefore \[\label{eq:dbv:num95denom95diff} a_n - a = \Oh{1/n}\qquad\text{and}\qquad b_n - b = \Oh{1/n}.\tag{19}\] Since \(\chi > \chi_{\mathrm{dbv}}\), we have \(a = 2 - \chi - 2e^{-\chi}<0\) and hence \(b = a - \chi < 0\). As \(b_n \to b\) for \(n\to \infty\), we have \(\abs{b_n}\ge \abs{b}/2\) for sufficiently large \(n\). Finally, \[\alpha_n^*(\chi) - \alpha^*(\chi) = \frac{a_n}{b_n} - \frac{a}{b} = \frac{(a_n - a)b - a(b_n - b)}{bb_n}.\] Using 19 and the fact that \(bb_n\) is bounded away from zero for all sufficiently large \(n\), it follows that \(\alpha_n^*(\chi) = \alpha^*(\chi) \pm \Oh{1/n}\). ◻

Proof. Case \(0<\chi<\chi_\mathrm{dbv}\). Fix \(\chi\in(0,\chi_\mathrm{dbv})\). By 3, for all sufficiently large \(n\), \[\E{Y_t-Y_{t+1}\mid Y_t=y}=\Delta(y)\ge \frac{A(\chi)}{2n}\,y \quad\text{for all }y\in\{1,\dots,n\}.\] Thus 1 applies with \(\delta=A(\chi)/(2n)>0\) and \(s_{\min}=1\). This yields \(T=\Oh{n\log n}\) a.a.s.and \(\E{T}=\Oh{n\log n}\).

Case \(\chi>\chi_\mathrm{dbv}\). Fix \(\chi>\chi_\mathrm{dbv}\) and let \(\alpha^*(\chi)\) be as in 15 . Since the drift is positive for all \(\alpha > \alpha^*(\chi)\), the \((1+1)\text{-EA}\) reaches distance \(\alpha > \alpha^*(\chi)\) in time \(\Oh{n}\).

So let us consider constants \(0<a<b<\alpha^*(\chi)\) and show that it takes exponential time to reach distance \(an\) from the optimum. By 2, we have \(D_\chi(\alpha)<0\) for all \(\alpha\in(0,\alpha^*(\chi))\). Hence, choosing \(0<a<b<\alpha^*(\chi)\), continuity yields some \(\varepsilon>0\) such that \[\label{eq:dbv:neg95interval} D_\chi(\alpha)\le -2\varepsilon\quad\text{for all }\alpha\in[a,b].\tag{20}\] Applying 1 yields that, for all sufficiently large \(n\), the hypotheses of 2 hold for \((Y_t)_{t\ge 0}\) on the interval \([a_n,b_n]\) with \(a_n\mathrel{\vcenter{:}}=\lfloor an\rfloor\) and \(b_n\mathrel{\vcenter{:}}=\lfloor bn\rfloor\). Indeed, condition (1) holds with \(\varepsilon\) as above, and condition (2) holds with \(\delta=1\) and \(r(\ell)=e^\chi\), where \(\ell\mathrel{\vcenter{:}}= b_n - a_n\). Define the hitting time \(T^*\mathrel{\vcenter{:}}= \min\SetBuilder{t\ge 0}{Y_t\le a_n}\). Then 2 implies that there exists a constant \(c^*>0\) such that \[\Prob{T^* \le 2^{c^*\ell/r(\ell)} \mid Y_0\ge b_n} = 2^{-\Om{\ell/r(\ell)}} = 2^{-\Om{n}},\] for all sufficiently large \(n\), where we used \(r(\ell)=e^\chi\le\Oh{1}\) and \(\ell \le (b-a)n\le\Oh{n}\). Equivalently, with probability \(1-2^{-\Om{n}}\) we have \(T^*\ge 2^{\Om{n}}\) on the event \(\{Y_0\ge b_n\}\). Since the runtime \(T\) satisfies \(T\ge T^*\), the same lower bound holds for \(T\).

Under u.a.r.initialisation we have \(Y_0\sim\mathrm{Bin}(n,1/2)\), and since \(b<1/2\) is fixed, a Chernoff bound yields \(\Prob{Y_0\ge b_n}=1-e^{-\Om{n}}\). Therefore \(T=2^{\Om{n}}\) a.a.s. Moreover, \[\E{T}\ge \E{T\mid Y_0\ge b_n}\Prob{Y_0\ge b_n}\ge 2^{\Om{n}}(1-e^{-\Om{n}})=2^{\Om{n}}.\] ◻

Proof. A full derivation is given in 8.7. ◻

Proof. We compute \(\partial_+D_\chi(0)\) via [prop:pre:right95derivative] and then analyse \(g(\chi)\) using a Bessel-function representation. The full argument (including uniqueness of the root and the sign change) is given in 8.8. ◻

Proof. Fix \(\chi > 0\). By 8 we have \(D_\chi(\alpha)/\alpha\to g(\chi)\) as \(\alpha\to 0^+\). By the definition of the limit, there exists \(\alpha^*>0\) such that for all \(\alpha\in(0,\alpha^*)\), \[\abs*{\frac{D_\chi(\alpha)}{\alpha}-g(\chi)}\le \frac{1}{2}\abs{g(\chi)}.\] If \(g(\chi)>0\), then \(D_\chi(\alpha)/\alpha\ge g(\chi)-\frac{1}{2} g(\chi)=\frac{1}{2} g(\chi)\) and hence \(D_\chi(\alpha)\ge \frac{1}{2}\alpha\,g(\chi)>0\) for all \(\alpha\in(0,\alpha^*)\). If \(g(\chi)<0\), then \(D_\chi(\alpha)/\alpha\le g(\chi)+\frac{1}{2}\abs{g(\chi)} = g(\chi)-\frac{1}{2} g(\chi)=\frac{1}{2} g(\chi)\) and hence \(D_\chi(\alpha)\le \frac{1}{2}\alpha\,g(\chi)<0\) for all \(\alpha\in(0,\alpha^*)\).

Finally, 8 gives \(g(\chi)>0\) for \(\chi\in(0,\chi_\mathrm{unif})\) and \(g(\chi)<0\) for \(\chi\in(\chi_\mathrm{unif},\infty)\), which completes the proof. ◻

Proof. For fixed \(\chi>0\) and all \(k\ge 10\) we have \[\frac{p_{k+1}(\chi)}{p_k(\chi)}=\frac{\chi}{k+1}\le \frac{\chi}{11}.\] Telescoping this inequality yields \[\label{eq:unif:pois95tail95geom} p_k(\chi)\le p_{10}(\chi)\Bigl(\frac{\chi}{11}\Bigr)^{k-10}\quad\text{for all }k\ge 10.\tag{21}\]

For \(k\ge 2\) and through the identity \(b'_{k,i}(\alpha)=k\bigl(b_{k-1,i-1}(\alpha)-b_{k-1,i}(\alpha)\bigr)\) the second derivative of \(H_k\) yields \[\label{eq:unif:second95deriv95diff} H''_k(\alpha) = k(k-1)\sum_{i=0}^{k-2}\bigl(h_k(i+2)-2h_k(i+1)+h_k(i)\bigr)\,b_{k-2,i}(\alpha).\tag{22}\]

Fix \(k\ge 10\) and \(0\le i\le k-2\) and let \(q_1\mathrel{\vcenter{:}}= p_A(k,i+1)-p_A(k,i)\) and \(q_2\mathrel{\vcenter{:}}= p_A(k,i+2)-p_A(k,i+1)\). Then \(0\le q_1,q_2\le 1\) and \(\abs{q_2-q_1}\le 1\). A direct computation gives \[h_k(i+2)-2h_k(i+1)+h_k(i)=(2i-k)(q_2-q_1)+4q_2,\] hence, using \(\abs{2i-k}\le k\), \[\abs{(2i-k)(q_2-q_1)+4q_2}\le k+4\le \frac{7}{5}k.\] Inserting into 22 and using \(\sum_{i=0}^{k-2} b_{k-2,i}(\alpha)=1\) yields \[\label{eq:unif:second95deriv95bound95k} \abs{H''_k(\alpha)}\le \frac{7}{5}k^3 \quad\text{for all }k\ge 10.\tag{23}\]

Combining 21 and 23 yields \[\begin{align} \abs*{\sum_{k=10}^{\infty} p_k(\chi)H''_k(\alpha)} \le \sum_{k=10}^{\infty} p_k(\chi)\,\abs*{H''_k(\alpha)} &\le \frac{7}{5}\,p_{10}(\chi)\sum_{k=10}^{\infty} k^3\Bigl(\frac{\chi}{11}\Bigr)^{k-10} \\ &= \frac{7}{5}\,p_{10}(\chi)\sum_{j=0}^{\infty} (j+10)^3\Bigl(\frac{\chi}{11}\Bigr)^{j}. \end{align}\] The series on the right hand side has strictly positive coefficients and is therefore increasing in \(\chi\) for \(\chi\in(0,11)\). Since \(\chi_\mathrm{unif}<14/5<11\), we may bound it for all \(\chi\in(0,\chi_\mathrm{unif})\) by its value at \(\chi=14/5\). Evaluating the resulting closed form at \(\chi=14/5\) gives \[\sum_{j=0}^{\infty} (j+10)^3\Bigl(\frac{14}{55}\Bigr)^{j}\approx 1503.725,\] hence the bound holds with \(c\mathrel{\vcenter{:}}= \frac{7}{5}\,1504\). ◻

Proof. By [prop:unif:irwin95hall] we have \(p_A(k,i)=F_k(i)\) for integers \(0\le i\le k\), where \(F_k\) denotes the Irwin–Hall cdf. In particular, \(p_A(k,i)\) is independent of \(\alpha\) and \(\chi\). Recalling the definition \[H_k(\alpha)=\sum_{i=0}^{k} h_k(i)\,b_{k,i}(\alpha), \quad h_k(i)=(2i-k)p_A(k,i),\] it follows that each \(H_k\) is a polynomial in \(\alpha\) of degree at most \(k\), and hence \(H_k''\) is a polynomial of degree at most \(k-2\). Moreover, differentiating the identity \[D(\chi,\alpha)=\sum_{k=0}^{\infty} p_k(\chi)\,H_k(\alpha)\] twice with respect to \(\alpha\) yields \[\label{eq:unif:D95second95derivative95series} \frac{\partial^2}{\partial\alpha^2}D(\chi,\alpha) =\sum_{k=0}^{\infty} p_k(\chi)\,H_k''(\alpha).\tag{24}\]

By 9 there exists a constant \(c>0\) such that for all \(\chi\in(0,\chi_\mathrm{unif})\), \[\abs*{\sum_{k=10}^{\infty} p_k(\chi)\,H_k''(\alpha)}\le c\,p_{10}(\chi) \quad\text{for all }\alpha\in[0,1].\] Consequently, for all \((\alpha,\chi)\in[0,1]\times(0,\chi_\mathrm{unif})\), \[\label{eq:unif:D95second95derivative95split} \frac{\partial^2}{\partial\alpha^2}D(\chi,\alpha) \ge \sum_{k=0}^{9} p_k(\chi)\,H_k''(\alpha)-c\,p_{10}(\chi).\tag{25}\]

For each \(0\le k\le 9\) choose constants \(m_k\) such that \[m_k \le H_k''(\alpha)\quad\text{for all }\alpha\in[0,1],\] and set \(m_{10}\mathrel{\vcenter{:}}= -c\). Using \(p_k(\chi)=e^{-\chi}\chi^k/k!\), inequality 25 implies \[\frac{\partial^2}{\partial\alpha^2}D(\chi,\alpha) \ge e^{-\chi}\sum_{k=0}^{10} m_k\frac{\chi^k}{k!} = e^{-\chi}P(\chi),\] where we define the polynomial \[P(\chi)\mathrel{\vcenter{:}}= \sum_{k=0}^{10} m_k\frac{\chi^k}{k!}.\]

It remains to show \(P(\chi)\ge 0\) for all \(\chi\in(0,\chi_\mathrm{unif})\). We proceed by a computer-assisted verification. First, we compute valid constants \(m_k\) for \(0\le k\le 9\) and take \(m_{10}=-c\), where \(c\) is the tail constant from 9. Second, on the interval \([0,14/5]\supseteq(0,\chi_\mathrm{unif})\) we verify \(P(0)=0\) and \(P(14/5)>0\), and we exclude any further real roots of \(P\) in \([0,14/5]\). Hence \(P(\chi)\ge 0\) for all \(\chi\in(0,\chi_\mathrm{unif})\). The full verification (choice of \(m_k\) and root exclusion for \(P\) on \([0,14/5]\)) is documented in a reproducible script, available on our Zenodo repository [@hasebe_2026_19232932].

Therefore \(e^{-\chi}P(\chi)\ge 0\) on \((0,\chi_\mathrm{unif})\), and the claimed inequality follows. In particular, for each fixed \(\chi\in(0,\chi_\mathrm{unif})\) we have \(D''_\chi(\alpha)\ge 0\) for all \(\alpha\in[0,1]\), so \(\alpha\mapsto D_\chi(\alpha)\) is convex on \([0,1]\). ◻

Proof. Fix \(\chi\in(0,\chi_\mathrm{unif})\). By 10, the function \(\alpha\mapsto D_\chi(\alpha)\) is convex on \([0,1]\). Hence it lies above its tangent at every point and at \(\alpha=0\) we have \[\label{eq:unif:supporting95line95at950} D_\chi(\alpha)\ge D_\chi(0)+\alpha\,\partial_+ D_\chi(0)\quad\text{for all }\alpha\in[0,1].\tag{26}\] At \(\alpha=0\) the algorithm is at the optimum, so no offspring will be accepted and therefore \(D_\chi(0)=0\). Moreover, by 8 we have \(\partial_+D_\chi(0)=g(\chi)\), and \(g(\chi)>0\) for \(\chi\in(0,\chi_\mathrm{unif})\). Substituting these facts into 26 yields \(D_\chi(\alpha)\ge \alpha\,g(\chi)> 0\) for all \(\alpha\in(0,1]\). ◻

Proof. Case \(0<\chi<\chi_\mathrm{unif}\). Fix \(\chi \in (0,\chi_\mathrm{unif})\). By 6 we have for all \(\alpha\in[0,1]\), \[\label{eq:unif:global95positivity} D_\chi(\alpha)\ge g(\chi)\alpha, \quad\text{where }g(\chi)>0.\tag{27}\] By [prop:pre:drift95convergence], there exists a constant \(c(\chi)>0\) such that, uniformly in \(\alpha\in[0,1]\), \[\label{eq:unif:drift95convergence} \abs*{\Delta(\lfloor \alpha n\rfloor)-D_\chi(\alpha)}\le \frac{c(\chi)}{n}.\tag{28}\] Let \(y_0\mathrel{\vcenter{:}}= \bigl\lceil 2c(\chi)/g(\chi)\bigr\rceil\). Then for all \(y\ge y_0\), using 27 and 28 we obtain \[\label{eq:unif:mult95drift95lower} \Delta(y)\ge g(\chi)\frac{y}{n}-\frac{c(\chi)}{n}\ge\frac{g(\chi)}{2n}\,y.\tag{29}\]

Define the runtime \(T_{y_0}\mathrel{\vcenter{:}}= \min\SetBuilder{t\ge 0}{Y_t\le y_0}\) and the shifted process \[Z_t \mathrel{\vcenter{:}}= \max\{Y_t-y_0,0\}.\] Then \(Z_t\in\{0,1,\dots,n-y_0\}\) and \(T_{y_0}=\min\SetBuilder{t\ge 0}{Z_t=0}\). Moreover, for all \(s\ge 1\), \[\E{Z_t-Z_{t+1}\mid Z_t=s} = \Delta(s+y_0) \ge \frac{g(\chi)}{2n}(s+y_0) \ge \frac{g(\chi)}{2n}\,s,\] where we used 29 . Hence 1 applies to \((Z_t)_{t\ge 0}\) and yields \(T_{y_0}=\Oh{n\log n}\) a.a.s. Since 1 provides an exponential upper tail, it also implies \[\label{eq:unif:runtime95y0} \E{T_{y_0}} = \Oh{n\log n}.\tag{30}\]

To cover the remaining states \(\{1,\dots,y_0\}\) we invoke 2. Its assumptions are satisfied since all weights are positive almost surely and the multiplicative drift lower bound 29 holds for all \(y\ge y_0\). Consequently, for all \(n\) sufficiently large, \[\label{eq:unif:endgame95exp} \sup_{1\le y\le y_0}\E{T\mid Y_0=y}=\Oh{n},\tag{31}\] and for every fixed \(y\in\{1,\dots,y_0\}\), \[\label{eq:unif:endgame95tail} \Prob{T>n\log n\mid Y_0=y}=\oh{1}.\tag{32}\]

We now combine the two parts. Recall \(T\mathrel{\vcenter{:}}=\min\SetBuilder{t\ge 0}{Y_t=0}\) and \(T_{y_0}\mathrel{\vcenter{:}}=\min\SetBuilder{t\ge 0}{Y_t\le y_0}\). At time \(T_{y_0}\) we have \(Y_{T_{y_0}}\in\{0,1,\dots,y_0\}\). Since \((Y_t)_{t\ge 0}\) is a time-homogeneous Markov chain, conditioning on \(Y_{T_{y_0}}\) yields \[\begin{align} \E{T} = \E{T_{y_0}} + \E{\E{T-T_{y_0}\mid Y_{T_{y_0}}}} &\le \E{T_{y_0}} + \sup_{1\le y\le y_0}\E{T\mid Y_0=y}\\ &= \Oh{n\log n}, \end{align}\] where we used 30 and 31 .

Moreover, conditioning on \(Y_{T_{y_0}}\) and using 32 gives \[\Prob{T-T_{y_0}>n\log n} \le \sup_{1\le y\le y_0}\Prob{T>n\log n\mid Y_0=y} = \oh{1}.\] Together with \(T_{y_0}=\Oh{n\log n}\) a.a.s., a union bound implies \(T=\Oh{n\log n}\) a.a.s.

Case \(\chi > \chi_\mathrm{unif}\). Fix \(\chi>\chi_\mathrm{unif}\). By 5 and continuity of \(\alpha\mapsto D_\chi(\alpha)\), there exists \(\alpha^*>0\) such that \(D_\chi(\alpha)<0\) for all \(\alpha\in(0,\alpha^*]\). Choose constants \(0<a<b\le \alpha^*\). Then \(\max_{\alpha\in[a,b]}D_\chi(\alpha)<0\), and hence we may assume that \[D_\chi(\alpha)\le -2\varepsilon \quad\text{for all }\alpha\in[a,b].\] Applying 1 yields that, for all sufficiently large \(n\), the hypotheses of 2 hold for \((Y_t)_{t\ge 0}\) on the interval \([a_n,b_n]\) with \(a_n\mathrel{\vcenter{:}}=\lfloor an\rfloor\) and \(b_n\mathrel{\vcenter{:}}=\lfloor bn\rfloor\). Indeed, condition (1) holds with \(\varepsilon\) as above, and condition (2) holds with \(\delta=1\) and \(r(\ell)=e^\chi\), where \(\ell\mathrel{\vcenter{:}}= b_n - a_n\). Define the hitting time \(T^*\mathrel{\vcenter{:}}= \min\SetBuilder{t\ge 0}{Y_t\le a_n}\). Then 2 implies that there exists a constant \(c^*>0\) such that \[\Prob{T^*\le 2^{c^*\ell/r(\ell)}\mid Y_0\ge b_n} = 2^{-\Om{\ell/r(\ell)}} = 2^{-\Om{n}},\] for all sufficiently large \(n\), where we used \(r(\ell)=e^\chi\le\Oh{1}\) and \(\ell \le (b - a)n\le\Oh{n}\). Hence with probability \(1-2^{-\Om{n}}\) we have \(T^*\ge 2^{\Om{n}}\) on the event \(\{Y_0\ge b_n\}\). Since reaching the optimum \(Y_t=0\) implies reaching \(Y_t\le a_n\), the runtime \(T\) satisfies \(T\ge T^*\) on \(\{Y_0\ge b_n\}\).

Under uniform random initialisation, \(Y_0\sim\mathrm{Bin}(n,1/2)\), and for any fixed \(b<1/2\) a Chernoff bound gives \(\Prob{Y_0\ge b_n}=1-e^{-\Om{n}}\). Therefore \(T=2^{\Om{n}}\) a.a.s. Moreover, \[\E{T}\ge \Prob{Y_0\ge b_n}\,\E{T\mid Y_0\ge b_n} \ge (1-e^{-\Om{n}})\,2^{\Om{n}} = 2^{\Om{n}},\] so the runtime is exponential in expectation as well. ◻

Proof. Fix \(\chi\in(0,\infty)\) and \(\alpha\in[0,1]\), and set \(y\mathrel{\vcenter{:}}= y(\alpha)=\lfloor \alpha n\rfloor\). Condition on the event \(Y_t=y\). Recall that \(K\sim\mathrm{Bin}(n,\chi/n)\) denotes the number of flipped bits. We define a pair \((K,I_\mathrm{Hyp})\) as follows: first draw \(K\), and conditional on \(K=k\) draw \(I_\mathrm{Hyp}\sim\mathrm{Hyp}(n,y,k)\), i.e.\(I_\mathrm{Hyp}\) is the number of flipped zero-bits when \(Y_t=y\). Likewise, let \((K,I_\mathrm{Bin})\) be such that conditional on \(K=k\) we have \(I_\mathrm{Bin}\sim\mathrm{Bin}(k,\alpha)\).

Moreover, by [prop:pre:explicit95drift] we have \[\Delta(y)=\E{(2I_\mathrm{Hyp}-K)\mathbf{1}_A\mid Y_t=y}.\] Recall from 3 that, conditional on \(Y_t=y\), we have \[\Delta(y) = \sum_{k = 0}^n\Prob{K=k}\sum_{i = 0}^{\Min{k}{y}} (2i-k)\,p_A(k,i)\,\Prob{I = i\mid(Y_t=y,K=k)}\] Since \(\Prob{I=i\mid (Y_t=y,K=k)}=0\) for all \(i>\Min{k}{y}\), we may equivalently write \[\label{eq:app:delta95double95sum95hyp} \Delta(y) = \sum_{k = 0}^n \Prob{K = k}\sum_{i = 0}^k (2i - k)\,p_A(k,i)\,\Prob{I = i\mid (Y_t = y,K=k)}\tag{33}\] We start by approximating \(\mathrm{Hyp}(n,y,k)\) by \(\mathrm{Bin}(k,\alpha)\). For \(k\ge 1\) and \(i\in\{0,1,\dots,k\}\) define \[h_k(i)\mathrel{\vcenter{:}}= (2i-k)\,p_A(k,i).\] Then \(\abs{h_k(i)/k}\le 1\) for all \(k,i\), since \(\abs{2i-k}\le k\) and \(p_A(k,i)\in[0,1]\).

We first bound the total variation distance between the two laws of \(I\) for fixed \(k\). Couple \(k\) draws without replacement from \(\{1,\dots,n\}\) (yielding \(\mathrm{Hyp}(n,y,k)\)) with \(k\) i.i.d.uniform draws from \(\{1,\dots,n\}\) (yielding \(\mathrm{Bin}(k,y/n)\)). If no collision occurs among the i.i.d.draws, then both sampling procedures select the same set of bits, hence the two counts coincide. By [@levinMarkovChainsMixing] and a union bound over collisions, \[\label{eq:app:tv95hyp95bin95yn} \norm{\mathrm{Hyp}(n,y,k)-\mathrm{Bin}(k,y/n)}_{\mathrm{TV}} \le \Prob{\{\text{a collision occurs}\}} \le \binom{k}{2}\frac{1}{n}.\tag{34}\] Next, we couple \(\mathrm{Bin}(k,y/n)\) and \(\mathrm{Bin}(k,\alpha)\) by coupling the \(k\) underlying Bernoulli trials one-by-one. Since \(\norm{\mathrm{Bernoulli}(p)-\mathrm{Bernoulli}(q)}_{\mathrm{TV}}=\abs{p-q}\) and total variation satisfies the triangle inequality ([@levinMarkovChainsMixing]), this yields the standard product bound \[\label{eq:app:tv95bin95bin95alpha} \norm{\mathrm{Bin}(k,y/n)-\mathrm{Bin}(k,\alpha)}_{\mathrm{TV}} \le k\,\abs{y/n-\alpha} \le \frac{k}{n},\tag{35}\] where we used \(\abs{\lfloor \alpha n\rfloor/n-\alpha}\le 1/n\). Combining 34 and 35 via the triangle inequality gives, for every \(1\le k\le n\), \[\label{eq:app:tv95hyp95bin95alpha} \norm{\mathrm{Hyp}(n,y,k)-\mathrm{Bin}(k,\alpha)}_{\mathrm{TV}} \le \binom{k}{2}\frac{1}{n}+\frac{k}{n}.\tag{36}\]

We now bound the effect of this approximation on the inner sum. By [@levinMarkovChainsMixing] and \(\abs{h_k(i)/k}\le 1\), \[\abs*{\E*{\frac{h_k(I_\mathrm{Hyp})}{k}}-\E*{\frac{h_k(I_\mathrm{Bin})}{k}}}\le 2\,\norm{\mathrm{Hyp}(n,y,k)-\mathrm{Bin}(k,\alpha)}_{\mathrm{TV}}.\] Multiplying by \(k\) and using 36 yields, for \(1\le k\le n\), \[\label{eq:app:inner95error} \abs{\E{h_k(I_\mathrm{Hyp})}-\E{h_k(I_\mathrm{Bin})}} \le 2k\Bigl(\binom{k}{2}\frac{1}{n}+\frac{k}{n}\Bigr) = \frac{k^3+k^2}{n}.\tag{37}\] For \(k=0\) both sides equal \(0\), so 37 holds for all \(0\le k\le n\).

Define the “intermediate” drift \(D_\chi^{(n)}\) where only the law of \(I\) is approximated by a binomial: \[\label{eq:app:drift95binI95def} D^{(n)}_\chi(\alpha) \mathrel{\vcenter{:}}= \sum_{k=0}^{n}\Prob{K=k}\sum_{i=0}^{k}(2i-k)\,p_A(k,i)\,\Prob{\mathrm{Bin}(k,\alpha)=i}.\tag{38}\]

With this coupling, the inner sum in 33 equals \(\E{h_k(I_\mathrm{Hyp})\mid K=k}\). Hence, by the law of total expectation, \[\Delta(y)=\E{h_K(I_\mathrm{Hyp})}.\] Similarly, by 38 and the definition of \((K,I_\mathrm{Bin})\) we have \[D^{(n)}_\chi(\alpha)=\E{h_K(I_\mathrm{Bin})}.\] Averaging 37 over \(K\sim\mathrm{Bin}(n,\chi/n)\) gives \[\label{eq:app:error95replace95I} \abs{\Delta(y)-D^{(n)}_\chi(\alpha)} \le \frac{1}{n}\E{K^3+K^2}.\tag{39}\] Using falling factorials \((x)_r\mathrel{\vcenter{:}}= x(x-1)\cdots(x-r+1)\), we have the identities \[K^2=(K)_2+K \quad\text{and}\quad K^3=(K)_3+3(K)_2+K.\] Hence \(\E{K^3+K^2}=\E{(K)_3}+4\E{(K)_2}+2\E{K}\). Moreover, \[\E{(K)_3}=(n)_3\Bigl(\frac{\chi}{n}\Bigr)^3 \le \chi^3,\quad \E{(K)_2}=(n)_2\Bigl(\frac{\chi}{n}\Bigr)^2 \le \chi^2,\quad \E{K}=\chi.\] Inserting into 39 yields \[\label{eq:app:error95replace95I95final} \abs{\Delta(y)-D^{(n)}_\chi(\alpha)} \le \frac{\chi^3+4\chi^2+2\chi}{n}.\tag{40}\]

We now approximate \(K\sim\mathrm{Bin}(n,\chi/n)\) by \(\mathrm{Poi}(\chi)\). For \(k\ge 1\) define \[g_\alpha(k)\mathrel{\vcenter{:}}= \frac{1}{k}\sum_{i=0}^{k}(2i-k)\,p_A(k,i)\,\Prob{\mathrm{Bin}(k,\alpha)=i}, \quad g_\alpha(0)\mathrel{\vcenter{:}}= 0.\] Then \(\abs{g_\alpha(k)}\le 1\) for all \(k\), since \(\abs{2i-k}\le k\) and \(p_A(k,i)\le 1\). By construction, \[D^{(n)}_\chi(\alpha)=\E{K\,g_\alpha(K)} \quad\text{for } K\sim\mathrm{Bin}(n,\chi/n),\] and \[D_\chi(\alpha)=\E{K\,g_\alpha(K)} \quad\text{for } K\sim\mathrm{Poi}(\chi),\] where \(D_\chi(\alpha)=D(\chi,\alpha)\) is defined in 4 .

Let \(K_n\sim\mathrm{Bin}(n,\chi/n)\) and \(K_\mathrm{Poi}\sim\mathrm{Poi}(\chi)\). Since \(\E{K_n}=\E{K_\mathrm{Poi}}=\chi>0\), we may size-bias both distributions. By [@arratiaSizeBiasOne2018], for any bounded measurable \(g\) and any non-negative \(K\) with mean \(\chi>0\), \[\E{K\,g(K)}=\chi\,\E{g(K^*)}.\] Moreover, by [@arratiaSizeBiasOne2018] we have the explicit size-biased laws \[K_n^*\overset{d}{=}1+\mathrm{Bin}(n-1,\chi/n) \quad\text{and}\quad K_\mathrm{Poi}^*\overset{d}{=}1+\mathrm{Poi}(\chi).\] Applying these identities with \(g=g_\alpha\) gives \[\begin{align} \abs{D^{(n)}_\chi(\alpha)-D_\chi(\alpha)} &= \abs{\E{K_n\,g_\alpha(K_n)}-\E{K_\mathrm{Poi}\,g_\alpha(K_\mathrm{Poi})}} \\ &= \chi\,\abs{\E{g_\alpha(1+K_{n-1})}-\E{g_\alpha(1+K_\mathrm{Poi})}}, \end{align}\] where \(K_{n-1}\sim\mathrm{Bin}(n-1,\chi/n)\). By [@levinMarkovChainsMixing] and \(\abs{g_\alpha(k)}\le 1\) we obtain \[\label{eq:app:error95replace95K95tv} \abs{D^{(n)}_\chi(\alpha)-D_\chi(\alpha)} \le 2\chi\,\norm{\mathrm{Bin}(n-1,\chi/n)-\mathrm{Poi}(\chi)}_{\mathrm{TV}}.\tag{41}\]

To bound this total variation distance, we use the triangle inequality ([@levinMarkovChainsMixing]). First, couple \(\mathrm{Bin}(n-1,\chi/n)\) and \(\mathrm{Bin}(n,\chi/n)\) by writing \(K_n=K_{n-1}+X_n\) with \(X_n\sim\mathrm{Bernoulli}(\chi/n)\) and independent. Then [@levinMarkovChainsMixing] yields \[\norm{\mathrm{Bin}(n-1,\chi/n)-\mathrm{Bin}(n,\chi/n)}_{\mathrm{TV}} \le \Prob{K_{n-1}\neq K_n} = \Prob{X_n=1} = \frac{\chi}{n}.\] Second, by the Poisson approximation bound in [@rossFundamentalsSteinsMethod2011], \[\norm{\mathrm{Bin}(n,\chi/n)-\mathrm{Poi}(\chi)}_{\mathrm{TV}} \le \frac{\chi^2}{n}.\] Combining, we get \[\norm{\mathrm{Bin}(n-1,\chi/n)-\mathrm{Poi}(\chi)}_{\mathrm{TV}} \le \frac{\chi}{n}+\frac{\chi^2}{n}.\] Inserting into 41 yields \[\label{eq:app:error95replace95K95final} \abs{D^{(n)}_\chi(\alpha)-D_\chi(\alpha)} \le \frac{2\chi^3+2\chi^2}{n}.\tag{42}\]

Finally, we combine the two approximation errors. By the triangle inequality, \[\abs{\Delta(y)-D_\chi(\alpha)} \le \abs{\Delta(y)-D^{(n)}_\chi(\alpha)} + \abs{D^{(n)}_\chi(\alpha)-D_\chi(\alpha)}.\] Combining 40 and 42 gives \[\abs{\Delta(\lfloor \alpha n\rfloor)-D_\chi(\alpha)} \le \frac{3\chi^3+6\chi^2+2\chi}{n}.\] The bound is uniform in \(\alpha\in[0,1]\) since the estimates above depend on \(\alpha\) only through \(\abs{\lfloor \alpha n\rfloor/n-\alpha}\le 1/n\). In particular, for every fixed \(\alpha\in[0,1]\) we have \(\Delta(\lfloor \alpha n\rfloor)\to D_\chi(\alpha)\) as \(n\to\infty\). ◻

Proof. Recall that \(D_\chi(\alpha)=D(\chi,\alpha)\) is defined by conditioning on \(K\sim\mathrm{Poi}(\chi)\) and \(I\mid(K=k)\sim\mathrm{Bin}(k,\alpha)\), hence \[\label{eq:app:Dchi95double95sum} D_\chi(\alpha) = \sum_{k=0}^{\infty} e^{-\chi}\frac{\chi^k}{k!}\sum_{i=0}^{k} (2i-k)\,p_A(k,i)\binom{k}{i}\alpha^i(1-\alpha)^{k-i}.\tag{43}\] For fixed \(k\), let \(I\sim\mathrm{Bin}(k,\alpha)\) and write the inner sum as \[S_k(\alpha)\mathrel{\vcenter{:}}= \sum_{i=0}^{k} (2i-k)\,p_A(k,i)\binom{k}{i}\alpha^i(1-\alpha)^{k-i} = \E{(2I-k)\,p_A(k,I)}.\]

We expand \(S_k(\alpha)\) at \(\alpha=0\) and bound the remainder uniformly in \(\alpha\in[0,1]\). If \(I=0\), then all flipped bits are one-bits, so the offspring cannot be accepted because all weights are non-negative and hence \(p_A(k,0)=0\) for all \(k\ge 1\). Moreover, for \(k=0\) the factor \(2i-k\) is \(0\). Thus the \(i=0\) term never contributes.

For the \(i=1\) term we have \[(2-k)\,p_A(k,1)\binom{k}{1}\alpha(1-\alpha)^{k-1} = k(2-k)\,p_A(k,1)\,\alpha + R_{k,1}(\alpha),\] where \[R_{k,1}(\alpha) = k(2-k)\,p_A(k,1)\,\alpha\bigl((1-\alpha)^{k-1}-1\bigr).\] Since \(p_A(k,1)\in[0,1]\) and \(1-(1-\alpha)^{k-1}\le (k-1)\alpha\) for \(\alpha\in[0,1]\), we obtain \[\label{eq:app:i95eq95one95bound} \abs{R_{k,1}(\alpha)} \le k\abs{2-k}\,\alpha\bigl(1-(1-\alpha)^{k-1}\bigr) \le k^2\alpha\,(k-1)\alpha \le k^3\alpha^2.\tag{44}\]

For the contribution of indices \(i\ge 2\), using \(\abs{2i-k}\le k\) and \(p_A(k,i)\in[0,1]\) yields \[\abs*{\sum_{i=2}^{k} (2i-k)\,p_A(k,i)\binom{k}{i}\alpha^i(1-\alpha)^{k-i}} \le k\,\Prob{I\ge 2}.\] To bound this tail probability, note that \(I\ge 2\) implies that there exists a pair of distinct trials that both succeed. By a union bound over the \(\binom{k}{2}\) pairs, \[\label{eq:app:i95ge95two95bound} \Prob{\mathrm{Bin}(k,\alpha)\ge 2} \le \binom{k}{2}\alpha^2 \le \frac{k^2}{2}\alpha^2,\tag{45}\] and therefore the \(i\ge 2\) contribution is bounded (in absolute value) by \(\frac{1}{2}k^3\alpha^2\).

Combining the 44 and 45 we conclude that for all \(k\ge 0\) and all \(\alpha\in[0,1]\), \[\label{eq:app:inner95expansion95fixed95k95new} S_k(\alpha) = k(2-k)\,p_A(k,1)\,\alpha + R_k(\alpha), \quad \abs{R_k(\alpha)}\le \frac{3}{2}\,k^3\alpha^2.\tag{46}\]

Insert 46 into 43 . Writing \(K\sim\mathrm{Poi}(\chi)\) and observing that the term for \(k=i=0\) vanishes due to the factor \(2i-k=0\), we obtain \[D_\chi(\alpha) = \alpha\sum_{k=1}^{\infty} e^{-\chi}\frac{\chi^k}{k!}\,k(2-k)\,p_A(k,1) +\sum_{k=1}^{\infty} e^{-\chi}\frac{\chi^k}{k!}\,R_k(\alpha).\] Using \(\abs{R_k(\alpha)}\le \frac{3}{2}k^3\alpha^2\) and the finiteness of the third moment of a Poisson random variable, \[\abs*{\sum_{k=0}^{\infty} e^{-\chi}\frac{\chi^k}{k!}\,R_k(\alpha)} \le \frac{3}{2}\alpha^2 \sum_{k=0}^{\infty} e^{-\chi}\frac{\chi^k}{k!}\,k^3 = \frac{3}{2}\alpha^2\,\E{K^3} = \Oh{\alpha^2},\] where the hidden constant depends only on \(\chi\) via \(\E{K^3}\). Hence \[\label{eq:app:Dchi95expansion} D_\chi(\alpha) = \alpha\sum_{k=1}^{\infty} e^{-\chi}\frac{\chi^k}{k!}\,k(2-k)\,p_A(k,1) + \Oh{\alpha^2}.\tag{47}\]

Finally, \(D_\chi(0)=0\), so dividing 47 by \(\alpha\) yields \[\frac{D_\chi(\alpha)-D_\chi(0)}{\alpha} = \sum_{k=1}^{\infty} e^{-\chi}\frac{\chi^k}{k!}\,k(2-k)\,p_A(k,1) + \Oh{\alpha}.\] Letting \(\alpha\to 0^+\) gives the claimed formula for \(\partial_+ D_\chi(0)\). ◻

Proof. Write \(p\mathrel{\vcenter{:}}=\chi/n\). Fix \(n\) sufficiently large such that \(n\ge n_0\) and \(p\le 1/2\). In particular, \[\label{eq:endgame:qn95lower} (1-p)^{n-1}\ge e^{-2p(n-1)}\ge e^{-2\chi}.\tag{48}\] We prove (1) and (2) for such \(n\).

For \(y\ge 1\), let \(E_y\) be the event that mutation flips exactly one bit and this bit is one of the \(y\) zero-bits. If \(Y_t=y\), then \[\label{eq:endgame:PyEy} \Prob{E_y\mid Y_t=y}=y\,p(1-p)^{n-1}.\tag{49}\] On \(E_y\) the offspring flips one \(0\to 1\) bit and no other bit. Since weights are assumed to be positive almost surely, this strictly increases fitness, so the offspring is accepted and \(Y_{t+1}=y-1\).

Consequently, starting from a state \(y\le y_0\), if in each accepted generation \(t\) until reaching \(0\) the corresponding event \(E_{Y_t}\) occurs, then \(Y_t\) decreases by \(1\) each time and the optimum is reached after at most \(y\) accepted generations. We refer to this outcome as a lucky strike.

Let \(A\) denote the acceptance event and let \(I\) be the number of flipped zero-bits. If \(I=0\), then only \(1\to 0\) flips occur fitness can only decrease, hence acceptance is impossible. Therefore \(A\subseteq\{I\ge 1\}\) and, for \(Y_t=y\), \[\label{eq:endgame:acceptance95upper95bound} \Prob{A\mid Y_t=y}\le \Prob{I\ge 1\mid Y_t=y}\le \E{I\mid Y_t=y}=y\,p.\tag{50}\] Combining 49 and 50 gives, for all \(y\ge 1\), \[\label{eq:endgame:Ey95given95accept} \Prob{E_y\mid A,\,Y_t=y} \ge \frac{y\,p(1-p)^{n-1}}{y\,p} =(1-p)^{n-1}.\tag{51}\] Now fix any \(y\in\{1,\dots,y_0\}\). Consider the successive accepted generations starting from a generation \(t\) when \(Y_t=y\), and stop if either the process reaches \(0\) or we encounter the first accepted generation \(t'\) in which \(E_{Y_{t'}}\) does not occur. At each accepted generation \(t\) before reaching \(0\), the current value of \(Y_t\) lies in \(\{1,\dots,y_0\}\), and by 51 the conditional probability that the accepted generation is of type \(E_{Y_t}\) is at least \((1-p)^{n-1}\). Iterating this bound over at most \(y_0\) accepted generations yields that the probability of a lucky strike is at least \[\label{eq:endgame:lucky95strike95prob} \Prob{\{\text{lucky strike}\}\mid Y_t=y}\ge \bigl((1-p)^{n-1}\bigr)^{y_0}\ge e^{-2\chi y_0},\tag{52}\] where the last inequality follows from 48 .

Assume \(Y_0\in\{1,\dots,y_0\}\). We proceed as follows. Whenever the process is in \(\{1,\dots,y_0\}\), we start an attempt and watch accepted generations until either a lucky strike occurs (success) or the first accepted generation \(t\) occurs in which \(E_{Y_t}\) does not occur (failure). If an attempt fails and the new state is still in \(\{1,\dots,y_0\}\), we start a new attempt immediately. If instead the attempt fails and the new state is \(>y_0\), we wait until the first time the process returns to \(\{1,\dots,y_0\}\) and then start the next attempt there.

By 52 , each time we start an attempt from a state in \(\{1,\dots,y_0\}\), the conditional probability of success is at least \(e^{-2\chi y_0}=:p_{\mathrm{ls}}>0\). Let \(N\) be the number of attempts until the first success. Then for all \(m\ge 0\), \[\Prob{N>m}\le (1-p_{\mathrm{ls}})^m,\] since each attempt succeeds with conditional probability at least \(p_{\mathrm{ls}}\), and hence \[\label{eq:endgame:EN} \E{N}=\sum_{m\ge 0}\Prob{N>m}\le \frac{1}{p_{\mathrm{ls}}}\le\Oh{1}.\tag{53}\]

For \(Y_t\ge 1\), an accepted generation occurs whenever \(E_{Y_t}\) occurs, hence \[\Prob{A\mid Y_t\ge 1}\ge \Prob{E_{Y_t}\mid Y_t\ge 1}\ge p(1-p)^{n-1}.\] Therefore the expected waiting time (in generations) until the next accepted generation is at most \[\frac{1}{p(1-p)^{n-1}}=\frac{n}{\chi}\,\frac{1}{(1-p)^{n-1}}\le\Oh{n},\] using 48 . Since an attempt involves at most \(y_0\) accepted generations before it either succeeds or fails, the expected number of generations spent in \(\{1,\dots,y_0\}\) during an attempt is \(\Oh{n}\).

If an attempt fails in generation \(t\) by leaving \(\{1,\dots,y_0\}\), let \(Z\) be the value of \(Y_{t + 1}\) (i.e. immediately after an attempt fails). Let \(K\sim\mathrm{Bin}(n,p)\) be the mutation size in that generation, so \(\E{K}=\chi\) and \(\E{K^2}=\chi(1-p)+\chi^2\le \chi+\chi^2\). Fix \(y\in\{1,\dots,y_0\}\). Conditional on \(K=k\), acceptance implies that at least one of the \(k\) flipped positions is a zero-bit, hence \[\Prob{A\mid K=k,\,Y_t=y}\le \Prob{I\ge 1\mid K=k,\,Y_t=y}\le k\,\frac{y}{n}.\] Thus, \[\E{K\mathbf{1}_A\mid Y_t=y}\le \sum_{k=0}^n k\,\Prob{K=k}\,k\,\frac{y}{n}=\frac{y}{n}\E{K^2}.\] On the other hand, \(E_y\subseteq A\) implies \(\Prob{A\mid Y_t=y}\ge \Prob{E_y\mid Y_t=y}=\frac{y}{n}\chi(1-p)^{n-1}\). Using \(\E{K\mid A,\,Y_t=y}=\E{K\mathbf{1}_A\mid Y_t=y}/\Prob{A\mid Y_t=y}\), we obtain \[\label{eq:endgame:EK95given95accept} \E{K\mid A,\,Y_t=y} \le \frac{\E{K^2}}{\chi(1-p)^{n-1}} \le \frac{\chi+\chi^2}{\chi(1-p)^{n-1}} \le\Oh{1},\tag{54}\] where the last bound uses 48 . At generation \(t\), where we fail an attempt, we must have \(Y_t\le y_0\) and the state can increase by at most \(K\) in one step, hence \(Z\le y_0+K\) and therefore \(\E{Z}\le\Oh{1}\).

Now apply the multiplicative drift theorem [@doerrMultiplicativeDriftAnalysis2012] under the assumption \(\Delta(y)\ge (c/n)y\) for \(y\ge y_0\). For all \(z\ge y_0\) this yields an expected return time to \(\{0,1,\dots,y_0\}\) of at most \[\frac{n}{c}\Bigl(1+\ln(z/y_0)\Bigr).\] Conditioning on \(Z\) and using Jensen’s inequality (since \(\ln\) is concave) and \(\E{Z}\le\Oh{1}\) we obtain a return time of \[\frac{n}{c}\Bigl(1+\E{\ln(Z/y_0)}\Bigr) \le \frac{n}{c}\Bigl(1+\ln(\E{Z}/y_0)\Bigr) \le\Oh{n},\] in expectation and a.a.s. Hence the expected number of generations per attempt (including a possible excursion above \(y_0\) and the return) is \(\Oh{n}\).

In summary, starting from any \(y\in\{1,\dots,y_0\}\), the runtime is the sum of the durations of \(N\) attempts, hence by 53 , \[\sup_{1\le y\le y_0}\E{T\mid Y_0=y}\le\Oh{n},\] which proves (1). For (2), Markov’s inequality yields for fixed \(y\in\{1,\dots,y_0\}\), \[\Prob{T>n\log n\mid Y_0=y}\le \frac{\E{T\mid Y_0=y}}{n\log n}\le\Oh*{\frac{1}{\log n}}=\oh{1},\] which concludes the proof. ◻

Proof. Recall that for DBV we have \(p_A(k,i)=i/k\) for all \(k\ge 1\) and \(0\le i\le k\). By definition of the continuous drift approximation (see 4 ), \[D(\chi,\alpha) =\sum_{k=0}^\infty e^{-\chi}\frac{\chi^k}{k!} \sum_{i=0}^k (2i-k)\,p_A(k,i)\,\Prob{I=i\mid K=k},\] where \(K\sim\mathrm{Poi}(\chi)\) and \(I\mid(K=k)\sim\mathrm{Bin}(k,\alpha)\). For \(k=0\), recall that we set \(p_A(0,0)=0\) hence the \(k=0\) term vanishes. This corresponds to the case the parent and offspring are identical, in which case the drift is trivially zero.

For \(k\ge 1\), using \(p_A(k,i)=i/k\) we obtain \[\sum_{i=0}^k (2i-k)\,p_A(k,i)\,\Prob{I=i\mid K=k} =\E{(2I-k)I/k\mid K=k}.\] For \(I\sim\mathrm{Bin}(k,\alpha)\) we have \(\E{I}=k\alpha\) and \[\E{I^2}=k\alpha(1-\alpha)+k^2\alpha^2.\] Thus, for every \(k\ge 1\), \[\begin{align} \E{(2I-k)I/k\mid K=k} &=\frac{1}{k}\Bigl(2\E{I^2\mid K=k}-k\E{I\mid K=k}\Bigr) \\ &=\frac{1}{k}\Bigl(2\bigl(k\alpha(1-\alpha)+k^2\alpha^2\bigr)-k^2\alpha\Bigr) \\ &=2\alpha(1-\alpha)+k(2\alpha^2-\alpha). \end{align}\]

Summing over \(k\ge 1\) yields \[\begin{align} D(\chi,\alpha) &=2\alpha(1-\alpha)\sum_{k=1}^\infty e^{-\chi}\frac{\chi^k}{k!} +(2\alpha^2-\alpha)\sum_{k=1}^\infty k\,e^{-\chi}\frac{\chi^k}{k!} \\ &=2\alpha(1-\alpha)\bigl(1-e^{-\chi}\bigr)+(2\alpha^2-\alpha)\chi, \end{align}\] since \(\sum_{k\ge 1} e^{-\chi}\chi^k/k!=\Prob{\mathrm{Poi}(\chi)\ge 1}=1-e^{-\chi}\) and \(\sum_{k\ge 1} k\,e^{-\chi}\chi^k/k!=\E{\mathrm{Poi}(\chi)}=\chi\).

Finally, expand and regroup: \[\begin{align} D(\chi,\alpha) &=2\alpha(1-e^{-\chi})-2\alpha^2(1-e^{-\chi})+2\chi\alpha^2-\chi\alpha \\ &=\alpha\bigl(2-\chi-2e^{-\chi}\bigr)-\alpha^2\bigl(2-2\chi-2e^{-\chi}\bigr) \\ &=\alpha\Bigl(\bigl(2-\chi-2e^{-\chi}\bigr)-\alpha\bigl(2-2\chi-2e^{-\chi}\bigr)\Bigr), \end{align}\] which is 16 . ◻

Proof. Set \(p\mathrel{\vcenter{:}}= \chi/n\) and let \(K_n\sim\mathrm{Bin}(n,p)\) be the number of flipped bits in one mutation step. Recall \(\alpha\mathrel{\vcenter{:}}= y/n\) and \(r_n(\chi)\mathrel{\vcenter{:}}= \Prob{K_n=0}=(1-p)^n=(1-\chi/n)^n\).

If \(K_n=0\), then the offspring equals the parent and the drift is trivially zero.

Assume now that \(K_n=k\ge 1\). Conditional on \(Y_t=y\) and \(K_n=k\), the number \(I\) of flipped zero-bits satisfies \(I\sim\mathrm{Hyp}(n,y,k)\). For DBV, conditional on \((K_n=k,I=i)\), the offspring is accepted with probability \(i/k\) ([prop:dbv:acceptance]). Hence \[\E{Y_t-Y_{t+1}\mid Y_t=y,\,K_n=k} = \E{(2I-k)\,I/k} = \frac{1}{k}\Bigl(2\E{I^2}-k\E{I}\Bigr).\] For \(I\sim\mathrm{Hyp}(n,y,k)\) we have \(\E{I}=k\alpha\) and \[\Var{I}=k\alpha(1-\alpha)\frac{n-k}{n-1}, \quad \E{I^2}=\Var{I}+(\E{I})^2.\] Substituting yields, for \(k\ge 1\), \[\E{Y_t-Y_{t+1}\mid Y_t=y,\,K_n=k} = \frac{2}{n-1}\,\alpha(1-\alpha)(n-k) + k\,\alpha(2\alpha-1).\]

Taking expectations over \(K_n\) and using \(\E{K_n}=\chi\), we obtain \[\label{eq:dbv:disc95intermediate} \Delta(y) = \frac{2}{n-1}\,\alpha(1-\alpha)\,\E{(n-K_n)\mathbf{1}_{\{K_n\ge 1\}}} + \alpha(2\alpha-1)\,\E{K_n}.\tag{55}\] Finally, \[\E{(n-K_n)\mathbf{1}_{\{K_n\ge 1\}}} = n\Prob{K_n\ge 1}-\E{K_n} = n(1-r_n(\chi))-\chi,\] so 55 becomes \[\label{eq:dbv:disc95almost} \Delta(y) = \frac{2}{n-1}\,\alpha(1-\alpha)\bigl(n(1-r_n(\chi))-\chi\bigr) + \chi\,\alpha(2\alpha-1).\tag{56}\]

It remains to rewrite 56 into the factorised form 17 . Expanding 56 and regrouping the coefficients of \(\alpha\) and \(\alpha^2\) gives \[\Delta(y) = \alpha\Bigl(\frac{2\bigl(n(1-r_n(\chi))-\chi\bigr)}{n-1}-\chi\Bigr) + \alpha^2\Bigl(2\chi-\frac{2\bigl(n(1-r_n(\chi))-\chi\bigr)}{n-1}\Bigr).\] After rewriting and factoring out \(\frac{n}{n-1}\alpha\) we get \[\Delta(y) = \frac{n}{n-1}\,\alpha\Bigl(\bigl(2-\chi-2r_n(\chi)-\tfrac{\chi}{n}\bigr) -\alpha\bigl(2-2\chi-2r_n(\chi)\bigr)\Bigr),\] which is exactly 17 . ◻

Proof. Fix integers \(k\ge 0\) and \(0\le i\le k\) and condition on the event \((K=k,I=i)\). In the selection step, the offspring is accepted iff the total weight gained from the \(i\) flipped zero-bits exceeds the total weight lost from the \(k-i\) flipped one-bits. Since the weights are i.i.d.\(\mathrm{Unif}(0,1)\), we may represent the \(k\) flipped weights by i.i.d.random variables \(U_1,\dots,U_k\sim\mathrm{Unif}(0,1)\) such that \[p_A(k,i) = \Prob{ \sum_{j=1}^{i} U_j\ge\sum_{j=i+1}^{k} U_j }.\]

For \(1\le j\le k-i\) define \(V_j\mathrel{\vcenter{:}}= 1-U_{i+j}\). Then \(V_1,\dots,V_{k-i}\) are i.i.d.\(\mathrm{Unif}(0,1)\) and independent of \(U_1,\dots,U_i\). Substituting \(U_{i+j}=1-V_j\) yields \[p_A(k,i) = \Prob{ \sum_{j=1}^{i} U_j + \sum_{j=1}^{k-i} V_j \ge k-i }.\] The \(k\) summands on the left-hand side are i.i.d.\(\mathrm{Unif}(0,1)\), hence their sum has the Irwin–Hall distribution with parameter \(k\). Let \(S_k\mathrel{\vcenter{:}}= \sum_{j=1}^k W_j\) with \(W_1,\dots,W_k\overset{\mathrm{i.i.d.}}{\sim}\mathrm{Unif}(0,1)\), and let \(F_k(x)\mathrel{\vcenter{:}}= \Prob{S_k\le x}\). Then \[p_A(k,i)=\Prob{S_k\ge k-i}=1-F_k(k-i).\] By symmetry \(S_k\overset{d}{=}k-S_k\) and continuity of the distribution, we have \(F_k(x)=1-F_k(k-x)\) for all \(x\in[0,k]\) (also noted in 3). Thus \(1-F_k(k-i)=F_k(i)\) and therefore \(p_A(k,i)=F_k(i)\). Evaluating the Irwin–Hall cdf at the integer \(x=i\) yields the claimed closed form. ◻

Proof. By [prop:pre:right95derivative] we have, for all \(\chi>0\), \[\partial_+ D_\chi(0) = \sum_{k=0}^\infty e^{-\chi}\frac{\chi^k}{k!}\,k(2-k)\,p_A(k,1).\] In the uniform weights model, [prop:unif:irwin95hall] yields \(p_A(k,1)=1/k!\) for all \(k\ge 1\) (and the term \(k=0\) vanishes due to the factor \(k(2-k)\)). Hence \[\label{eq:unif:g95series} g(\chi) = \sum_{k=0}^\infty e^{-\chi}\frac{\chi^k}{(k!)^2}\,k(2-k).\tag{57}\]

We use modified Bessel functions of the first kind, \[I_a(x)\mathrel{\vcenter{:}}= \sum_{m=0}^\infty \frac{1}{m!\,\Gamma(m+a+1)}\Bigl(\frac{x}{2}\Bigr)^{2m+a}, \quad a\in\mathbb{Z}.\] Set \(x\mathrel{\vcenter{:}}= 2\sqrt{\chi}\). One checks (by comparing coefficients) that \[\label{eq:unif:bessel95identity} \sum_{k=0}^\infty \frac{k(2-k)}{(k!)^2}\chi^k = xI_1(x) - \frac{x^2}{4}I_0(x).\tag{58}\] Since \(I_0(x)>0\) for all \(x>0\), we can factor \[\label{eq:unif:root95equivalence} xI_1(x) - \frac{x^2}{4}I_0(x) = \frac{x^2}{4}I_0(x)\Bigl(\frac{4I_1(x)}{xI_0(x)}-1\Bigr).\tag{59}\] Consequently, for \(\chi>0\) we have \(g(\chi)=0\) if and only if \[\label{eq:unif:root95equation} \frac{4I_1(x)}{xI_0(x)}=1, \quad x=2\sqrt{\chi},\tag{60}\] since the factor \(\frac{x^2}{4}I_0(x)\) in 59 is strictly positive.

We now address the root and its uniqueness. Let \(v_0(x)\mathrel{\vcenter{:}}= x\,\frac{I_0(x)}{I_1(x)}\) as in [@bariczGeneralizedBesselFunctions2010]. By [@bariczGeneralizedBesselFunctions2010], the function \(v_0\in(0,\infty)\) is strictly increasing on \((0,\infty)\). Therefore the function \[h(x)\mathrel{\vcenter{:}}= \frac{4I_1(x)}{xI_0(x)}=\frac{4}{v_0(x)}\] is strictly decreasing on \((0,\infty)\).

From the series expansions of \(I_0\) and \(I_1\) we have \[I_0(x)=1+\Oh{x^2} \quad\text{and}\quad I_1(x)=\frac{x}{2}+\Oh{x^3},\] and thus \[h(x)=\frac{4I_1(x)}{xI_0(x)} = 2+\Oh{x^2}>1,\] for sufficiently small \(x>0\). On the other hand, by comparing the integral representations of \(I_0\) and \(I_1\) [@NIST:DLMF] one obtains \[\frac{4I_1(x)}{xI_0(x)} < \frac{4}{x} < 1 \quad\text{for all } x>4.\] Since \(h\) is continuous and strictly decreasing on \((0,\infty)\), 60 has a unique solution \(x_0\in(0,5)\), and hence \(\chi_\mathrm{unif}\mathrel{\vcenter{:}}= x_0^2/4\) is the unique strictly positive root of \(g\).

By 59 , the sign of \(g(\chi)\) for \(\chi>0\) agrees with the sign of \(h(x)-1\) at \(x=2\sqrt{\chi}\), since the remaining factors are strictly positive. As \(h\) is strictly decreasing and crosses \(1\) exactly once at \(x_0\), we obtain \(h(x)>1\) for \(x<x_0\) and \(h(x)<1\) for \(x>x_0\). Equivalently, \(g(\chi)>0\) for \(\chi\in(0,\chi_\mathrm{unif})\) and \(g(\chi)<0\) for \(\chi\in(\chi_\mathrm{unif},\infty)\).

Numerically, \(x_0\approx 3.325\,\) and thus \(\chi_\mathrm{unif}=x_0^2/4\approx 2.76531\). ◻