Proof. We only prove the first part of the theorem because the second part follows immediately from the first when choosing \(t = \ceil{(\ln(\expect{X_0 \cdot \indic{T > 0}} / x_{\min}) + \gamma) / \delta}\) and estimating \((1 - \delta)^t \leq \exp(-\delta t)\).

Let \((Y_t)_{t \in \mathbb{N}} \mathrel{\vcenter{:}}= (X_t \cdot \indic{t < T})_{t \in \mathbb{N}}\) for convenience, and let \(t \in [0 .. t']\). The inequality to show follows by noting that the event \(\set{T > t}\) is by the definition of \(T\) equivalent to the event \(\set{Y_t \geq x_{\min}}\). Making a case distinction with respect to the event \(\set{\cap_{s \in [0 .. t]} A_t}\), we obtain \[\begin{align} \prob{T > t} & = \prob{Y_t \geq x_{\min}} \\ & = \prob{Y_t \geq x_{\min}\land \cup_{s \in [0 .. t']} \overline{A_s}} + \prob{Y_t \geq x_{\min}\land \cap_{s \in [0 .. t']} A_s} . \end{align}\] In the remainder of the proof, we bound the second probability from above. To this end, our proof follows the conventional one, as given, for example, by LenglerS18DriftRevisited?, noting that only events until time \(t\) are relevant.

Note that since the event \(\set{Y_t \geq x_{\min}\land \cap_{s \in [0 .. t']} A_s}\) is an intersection and since \(x_{\min}> 0\) by assumption, the event is equivalent to \(\set{Y_t \cdot \indic{\cap_{u \in [0 .. t']} A_u} \geq x_{\min}}\). For the convenience of notation, let \((Z_s)_{s \in \mathbb{N}} \mathrel{\vcenter{:}}= (Y_s \cdot \indic{\cap_{u \in [0 .. t']} A_u})_{s \in \mathbb{N}}\). By rearranging 1 , we obtain \(\expect{Z_{t + 1} \filt{t}} \leq (1 - \delta) \expect{Z_t \filt{t}}\), and thus by the tower rule \(\expect{Z_{t + 1}} \leq (1 - \delta) \expect{Z_t}\). Iterating this argument, we obtain \(\expect{Z_t} \leq (1 - \delta)^t \expect{Z_0}\). Noting that \(Z\) is a nonnegative random process, Markov’s inequality yields \(\prob{Z_t \geq x_{\min}} \leq \frac{\expect{Z_t}}{x_{\min}}\). Applying the bound on \(\expect{Z_t}\) shows the first inequality. The second inequality follows by regarding a superset of the events of either term, thus concluding the proof. 0◻ ◻

Proof. For the sake of brevity, let \(Q\) denote the left-hand side of 5 .

We partition the domain \([m \rho^+]\) of \(q\) into \(m\) subsets, defining for all \(k \in [m]\) that \(D_k = [(k - 1) \rho^+ + 1 .. k \rho^+]\), noting that \(\bigcup_{k \in [m]} D_k = [m \rho^+]\). We then show the lower bound of \(\frac{M^2}{2 m}\) for another, easier sum that is contained in \(Q\) and only considers those terms where the two factors of \(q\) have common indices in one of the sets of our partition \(D\) above.

To this end, we first double each product of \(q\) in \(Q\) except those with identical indices, and we observe that due to the commutativity of multiplication, we have \[\begin{align} & 2 \sum\nolimits_{d \in [0 .. \rho]} \sum\nolimits_{i \in [m \rho^+ - d]} q(i) q(i + d) - \sum\nolimits_{i \in [m \rho^+]} q(i)^2 \\ & = \sum\nolimits_{i \in [m \rho^+]} \sum\nolimits_{j \in [m \rho^+]} q(i) q(j) \cdot \indic{\abs{i - j} \leq \rho} . \end{align}\] Solving for \(Q\) implies that \[\label{eq:probabilityShiftingLowerBound:intermediateResult} Q \geq \frac{1}{2} \sum\nolimits_{i \in [m \rho^+]} \sum\nolimits_{j \in [m \rho^+]} q(i) q(j) \cdot \indic{\abs{i - j} \leq \rho} .\tag{12}\] The remaining part of the proof deals with bounding the outer sum on the right-hand side from below.

As mentioned before, we derive another sum that only considers products of \(q\) whose indices share a set in the partition \(D\). Consequently, as indices in the same set of \(D\) are at most \(\rho\) apart and since each product of values of \(q\) is non-negative, due to the non-negativity of \(q\), we obtain \[\begin{align} & \sum\nolimits_{i \in [m \rho^+]} \sum\nolimits_{j \in [m \rho^+]} q(i) q(j) \cdot \indic{\abs{i - j} \leq \rho} \\ & \quad \geq \sum\nolimits_{k \in [m]} \sum\nolimits_{i \in D_k} \sum\nolimits_{j \in D_k} q(i) q(j) . \end{align}\]

In order to simplify the right-hand side above further, for all \(k \in [m]\), let \(m_k = \sum_{i \in D_k} q(i)\). Using this definition and rearranging the sums, since the indices are independent of each other, we obtain \[\begin{align} \sum\nolimits_{k \in [m]} \sum\nolimits_{i \in D_k} \sum\nolimits_{j \in D_k} q(i) q(j) & = \sum\nolimits_{k \in [m]} \sum\nolimits_{i \in D_k} q(i) \sum\nolimits_{j \in D_k} q(j) \\ & = \sum\nolimits_{k \in [m]} m_k^2 . \end{align}\]

By the Cauchy–Schwarz inequality, we furthermore see that \[\sum\nolimits_{k \in [m]} m_k^2 \geq \frac{1}{m} \bigl(\sum\nolimits_{k \in [m]} m_k\bigr)^2 .\]

The proof then follows by recalling that 12 requires a factor of \(\frac{1}{2}\) as well as that the statement assumes that \(\sum_{i \in [m \rho^+]} q(i) = M\), which, since \(D\) is a partition, is equivalent to \(\sum_{k \in [m]} m_k = M\). 0◻ ◻

Proof. We consider the interval \(I \mathrel{\vcenter{:}}= \bigl[\floor{\expect{\sumOfSampleValues{t'}{1}{i} \freq{t'}{}{}} - 2 \sigma} + 1 .. \ceil{\expect{\sumOfSampleValues{t'}{1}{i} \freq{t'}{}{}} + 2 \sigma} - 1\bigr]\) and then apply [lem:probabilityShiftingLowerBound]. First, note that by the assumption on the bounds of \(I\), we have \(I \subseteq [0 .. (n - 1) (r - 1)]\).

For each \(d \in [0 .. \Delta]\), let \(I_{-d} = \bigl[\floor{\expect{\sumOfSampleValues{t'}{1}{i} \freq{t'}{}{}} - 2 \sigma} + 1 .. \ceil{\expect{\sumOfSampleValues{t'}{1}{i} \freq{t'}{}{}} + 2 \sigma} - 1 - d\bigr] \subseteq I\). By the definition of the quantities from 2 , we see that \[\begin{align} & \prob[\big]{\differenceOfSampleValues{t'}{i} \in [0 .. \Delta]} \\ & \quad \geq \sum\nolimits_{d \in [0 .. \Delta]} \sum\nolimits_{v \in I_{-d}} \prob{\sumOfSampleValues{t'}{1}{i} = v \freq{t'}{}{}} \prob{\sumOfSampleValues{t'}{2}{i} = v + d \freq{t'}{}{}} . \end{align}\] Note that for each \(d \in [0 .. \Delta]\), we can shift the index \(v\) of the second sum such that it ranges over the interval at least \([4 \sigma - 1 - d]\), which is non-empty by the assumption on \(\sigma\). Hence, applying [lem:probabilityShiftingLowerBound] with \(\rho = \Delta\) and \(m = \floor{(4 \sigma - 1) / \max \set{1, \Delta}} \geq 1\), and noting that \(\sumOfSampleValues{t'}{1}{i}\) and \(\sumOfSampleValues{t'}{2}{i}\) follow the same distribution, we obtain \[\begin{align} \prob[\big]{\differenceOfSampleValues{t'}{i} \in [\Delta]} \geq \frac{\prob{\sumOfSampleValues{t'}{1}{i} \in I \freq{t'}{}{}}^2}{2 \floor{(4 \sigma - 1) / \max \set{1, \Delta}}} \geq \frac{\prob{\sumOfSampleValues{t'}{1}{i} \in I \freq{t'}{}{}}^2 \cdot \max \set{1, \Delta}}{2 (4 \sigma - 1)} . \end{align}\] Performing the following estimations and applying Cheybshev’s inequality, accounting for rounding, yields \[\begin{align} \prob[\big]{\sumOfSampleValues{t'}{1}{i} \in I \freq{t'}{}{}} & \geq 1 - \prob[\Big]{\abs[\big]{\sumOfSampleValues{t'}{1}{i} - \expect{\sumOfSampleValues{t'}{1}{i} \freq{t'}{}{}}} \geq 2 \sigma \freq{t'}{}{}} \\ & \geq 1 - \frac{1}{4} = \frac{3}{4} , \end{align}\] which concludes the proof. 0◻ ◻

Proof. Note that \(\sumOfSampleValues{t'}{1}{i}\) and \(\sumOfSampleValues{t'}{2}{i}\) follow the same distribution, which is why it is sufficient to focus on one of them. To this end, let \(S\) denote a random variable that follows the same distribution as both \(\sumOfSampleValues{t'}{1}{i}\) and \(\sumOfSampleValues{t'}{2}{i}\).

Since the components of \(\sample{t'}{1}{}\) are independent and thus uncorrelated, it follows that \(\var{S \freq{t'}{}{}} = \sum_{k \in [n] \smallsetminus \set{i}} \var{\sample{t'}{1}{k} \freq{t'}{}{}}\).

Let \(k \in [n] \smallsetminus \set{i}\). We use \(\var{\sample{t'}{1}{k} \freq{t'}{}{}} = \expect{(\sample{t'}{1}{k} - \expect{\sample{t'}{1}{k} \freq{t'}{}{}})^2 \freq{t'}{}{}}\). To this end, note that by the definition of \(j^\star\), we have \(\expect{\sample{t'}{1}{k} \freq{t'}{}{}} \geq j^\star\). Thus, the distance \(\abs{\sample{t'}{1}{k} - \expect{\sample{t'}{1}{k} \freq{t'}{}{}}}\) of each outcome of \(\sample{t'}{1}{k}\) for values in \([j^\star.. r - 1]\) is at most \(r - 1 - j^\star\). Consequently, we estimate \(\var{\sample{t'}{1}{k} \freq{t'}{}{}} \leq (r - 1 - j^\star)^2\). We conclude the proof by noting that we consider in total \(n - 1\) positions, that is, values for \(k\). 0◻ ◻

Proof. The overall aim is to bound the probability \(\prob{B}\) of a biased step at position \(i\), where we drop the index \(i\) for convenience. We let \(G\) be the event that a large step occurs at position \(i\), i. e., one sample has a value of at least \(\ell_{\kappa+2}\) and the other one a value less than \(\ell_{\kappa+1}\) in position \(i\). By the assumptions of the lemma, we have \(\prob{G} \ge \mu_i^{(t)}(S_{\kappa+2})(1-\mu_i^{(t)}(S_{\kappa+1})) \ge c_{\mathrm{drift}}\mu_i^{(t)}(S_{\kappa+1})(1-\mu_i^{(t)}(S_{\kappa+1}))\). On \(G\), a biased step occurs if \(\card{\differenceOfSampleValues{t'}{i}} < 5(r-1-\ell_\kappa)/9 - 1 \le \ell_{\kappa+2} - \ell_{\kappa}\), where the \(-1\) is an estimate on the rounding of the \(\ell_\kappa\). We set \(\Delta\) smaller than \(5(r-1-\ell_\kappa)/9 - 1\) by choosing \(\Delta = (r-1-\ell_\kappa)/2\) (using \(\ell_k \le r-10\)) in Lemma [lem:biasedStepLowerBound] and also satisfy \((\Delta + 2) / 4 \le \sigma\) by choosing \(\sigma\) large enough. The lemma now bounds the probability of a biased step at position \(i\) as \[\begin{align} \prob{B} & \ge \prob{G} \prob[\big]{\differenceOfSampleValues{t'}{i} \in [0 .. \Delta]} \ge c_{\mathrm{drift}}\cdot \mu_i^{(t)}(S_{\kappa+1})(1-\mu_i^{(t)}(S_{\kappa+1})) \frac{9 \max \set{1, \Delta}}{32 (4 \sigma - 1)} \\ & \ge \frac{9c_{\mathrm{drift}}\cdot \mu_i^{(t)}(S_{\kappa+1})(1-\mu_i^{(t)}(S_{\kappa+1})) \max \set{1, (r-1-\ell_\kappa)/2}}{32 (4 \sigma - 1)} . \end{align}\] Bounding \(\sigma\) via Lemma [lem:varianceUpperBound] with \(j^\star=\ell_k\), noting that there is no probability mass in \([0..\ell_\kappa-1]\), we have \[\prob{B} \ge \frac{9c_{\mathrm{drift}}\cdot \mu_i^{(t)}(S_{\kappa+1})(1-\mu_i^{(t)}(S_{\kappa+1})) \max \set{1, (r-1-\ell_\kappa)/2}}{32 \Biggl(4 \sqrt{(n - 1) (r - 1 - \ell_\kappa)^2 } - 1\Biggr)} \eqqcolon D_i^{(t')}(\kappa)\] The considered biased step will increase a frequency for one of the values in \(S_{\kappa+2}\) of the values in \([0..r-1]\setminus S_{\kappa+1} = [0,\dots,\ell_{\kappa+1}-1]\). Hence, \[\expect{\mu_i^{(t'+1)}(S_{\kappa+2}) - \mu_i^{(t')}(S_{\kappa+2})\freq{t'}{}{}} \geq \frac{D_i^{(t')}(\kappa) }{K} .\]

The same bound holds for \(\expect{\mu_i^{(t'+1)}(S_{\kappa+1}) - \mu_i^{(t')}(S_{\kappa+1})\freq{t'}{}{}}\) since the considered steps, which sample a value of at least \(\ell_{\kappa+2}\) and a value smaller than \(\ell_{\kappa+1}\), increase both \(\mu_i^{(t')}(S_{\kappa+1})\) and \(\mu_i^{(t')}(S_{\kappa+2})\) at the same time but decrease \((1-\mu_i^{(t')}(S_{\kappa+1}))\). 0◻ ◻

Proof. We aim to apply 1 to \((P'_t)_{t \in \mathbb{N}} \mathrel{\vcenter{:}}= (P_{U_t})_{t \in \mathbb{N}}\). To this end, we only consider a restriction of \(P'\) until it deviates from \(P'_0\) by at least \(\alpha P'_0\), noting that the statement is identical for the original process and for its restriction.

Let \(V = \inf \set{t \in \mathbb{N}P'_t \notin \bigl((1 - \alpha) P'_0, (1 + \alpha) P'_0\bigr)}\), and for all \(t \in \mathbb{N}\), let \(X_t = P'_t \cdot \indic{t < V} + P'_S \cdot \indic{t \geq V}\) be the restriction of \(P'\) that we are interested in, that is, the stopped process of \(P'\). Note that since \(P'\) is a martingale by assumption, we see that \(X\) is a martingale with respect to the natural filtration of \((\freq{t}{}{})_{t \in \mathbb{N}}\).

We aim to apply 1 to \(X\), choosing \(\varepsilon = \alpha P'_0\). Since the update of the \(r\)-cGA changes a frequency by at most \(\frac{1}{K}\), it follows for 1 that \(b = \frac{1}{K}\). It remains to estimate for all \(t \in \mathbb{N}\) the value \(\hat{v}_t\).

Let \(t \in \mathbb{N}\). We derive \(\var{X_{t + 1} - X_t \freq{t}{i}{}}\) via a case distinction with respect to how \(t\) compares to \(V\).

Case \(\boldsymbol{t < V}\). Since the frequencies in \(X\) are not cut off by the update, we substitute \(\freq{t + 1}{i}{j} = \freq{t}{i}{j} + \frac{1}{K} (\indic{x_i = j} - \indic{y_i = j})\). Using that the two indicator functions per update are independent and thus uncorrelated, we obtain \[\begin{align} \var{X_{t + 1} - X_t \freq{t}{i}{}} & \leq \var*{\frac{1}{K}(\indic{\selectedSample{t}{1}{i} = j} - \indic{\selectedSample{t}{2}{i} = j})} \\ & = \frac{1}{K^2}\bigl(\var{\indic{\selectedSample{t}{1}{i} = j} \freq{t}{i}{}} + \var{\indic{\selectedSample{t}{2}{i} = j} \freq{t}{i}{}}\bigr) \\ & = \frac{2}{K^2} \freq{t}{i}{j} (1 - \freq{t}{i}{j}) \\ & \leq \frac{2}{K^2} \min \set{\freq{t}{i}{j}, 1 - \freq{t}{i}{j}}. \end{align}\] Since we consider a \(t\) such that \(\freq{t}{i}{j} \in \bigl[(1 - \alpha) P'_0, (1 + \alpha) P'_0\bigr]\), we have \(\var{X_{t + 1} - X_t \freq{t}{i}{}} \leq \frac{2}{K^2} \beta\).

Case \(\boldsymbol{t \geq V}\). Since \(X\) no longer changes once \(t \geq V\), it follows that \(\var{X_{t + 1} - X_t \freq{t}{i}{}} = 0\).

Concluding the first case. Combining the two cases, we see for all \(t \in \mathbb{N}\) that \(\hat{v}_t \leq t \frac{2}{K^2} \beta\). Applying 1 yields for all \(t \in \mathbb{N}\) that \[\prob[\big]{\exists s \in [0 .. t]\colon \abs*{P'_s - P'_0} \geq \alpha P'_0 P'_0} \leq 2 \exp\mathopen{}\mathclose{\left(-\frac{(\alpha P'_0)^2}{2 \cdot 2 t \beta / K^2 + 2 \alpha P'_0 / (3 K)}}\right) .\] Simplifying the exponent on the right-hand side yields \[-\frac{(\alpha P'_0)^2}{2 \cdot 2 t \beta / K^2 + 2 \alpha P'_0 / (3 K)} \leq -\frac{3 (\alpha P'_0 K)^2}{4 \cdot \max \{6 t \beta, \alpha P'_0 K\}} ,\] which concludes the proof, as the statement is the same for \(P'\) and for \(X\). 0◻ ◻

Proof. We aim at applying [thm:rcgaNeutralConcentration] to \((P_t)_{t \in \mathbb{N}} \mathrel{\vcenter{:}}= \bigl(\mu_{i \mid \randomWalkStoppingTime{i}{t'}[]}^{(t' + t)}(S_{\nu})\bigr)_{t \in \mathbb{N}}\) with \(\alpha = \frac{1}{\kappa^*}\), that is, choosing in the theorem \(J = S_{\nu}\). Note that by the definition of \(\randomWalkStoppingTime{i}{t'}[]\), we only consider random-walk steps in \(P\). Hence, \(P\) is a martingale. That is, [thm:rcgaNeutralConcentration] is directly applicable. This leaves us only with discussing the exponent in the probability bound in the following.

For \(\beta\), we see that our assumption \(\kappa^* \ge 2\) implies \(\alpha \le 1/2\), so we have \(\frac{1}{2} P_0 \le \beta \le \frac{3}{2}P_0\) for any value of \(P_0\).

From the definition of \(t_{\mathrm{stop}}\) and the bound on \(\beta\), we have \(6 t_{\mathrm{stop}}\beta \ge 3 t_{\mathrm{stop}} P_0 \geq 3c_{\mathrm{stop}} K \sqrt{n} (\ln n) P_0 \ge \alpha K P_0\) for sufficiently large \(n\). Thus, we get for the exponent of [thm:rcgaNeutralConcentration] that \[\begin{align} -\frac{3 (\alpha P_0 K)^2}{4 \cdot \max \{6 t_{\mathrm{stop}}\beta, \alpha P_0 K\}} & = -\frac{3 \alpha^2 P_0^2 K^2}{24 t_{\mathrm{stop}}\beta} \le -\frac{3 \alpha^2 P_0^2 K^2}{24c_{\mathrm{stop}} K\sqrt{n}(\ln n)(3/2)P_0} \\ & = -\frac{\alpha^2 P_0 K}{12c_{\mathrm{stop}}\sqrt{n}\ln n}. \end{align}\] We substitute \(K\) and recall that \(P_0 \geq \frac{\eulerE[-3]}{r}\) and \(\alpha = \frac{1}{\kappa^*} = \tfrac{1}{\lceil \log_{3/2}(r-1)\rceil} \ge \tfrac{1}{1.6\log_{3/2}(r-1)}\ge \frac{1}{4\ln r}\), where the first inequality holds for \(r\ge 3\). Hence, we obtain an upper bound for the exponent of \(-\frac{c^*\ln n}{192\eulerE[3]c_{\mathrm{stop}}} \le -\frac{c^*\ln n}{3857c_{\mathrm{stop}}}\), which concludes the proof. 0◻ ◻

Proof. We derive a lower bound \(p_i\ge (1-b\delta )p\) that holds for all \(i\le t\) with high probability and then apply the usual Chernoff bounds on independent trials with this pessimistic bound on their success probability.

If \(p_i\ge (1-b \delta)p\) for all \(i\le t\), then by standard Chernoff bounds with success probability \((1-b \delta)p\) and expectation \(t(1-b \delta)p\), we have \[\begin{align} \prob{Z_t\le (1-\delta) tp} & \le \prob{Z_t \le (1-b \delta)(1-(1-b)\delta)tp} \\ & \le \exp(-(1-b\delta)(1-b)^2\delta^2 tp / 2) \end{align}\]

We now study the event that \(p_i \ge (1-b\delta) p\) for all \(i\le t\). We note that our bound \(\frac{\rho p+\eta S_i}{\rho+\eta i}\) on \(p_i\) becomes smallest for \(i=t\), pessimistically assuming \(Z_i \le ip\) (otherwise we already have \(p_i \ge p\)). If \(Z_t\ge (1-\delta)tp\), then \[p_i \ge \frac{\rho p+\eta (1-\delta) tp}{\rho +\eta t} = \mathopen{}\mathclose{\left(1-\frac{\delta \eta t}{\rho+\eta t}}\right) p \ge (1-b\delta) p ,\] where the last inequality follows from our assumption \(\tfrac{\eta t}{\rho+\eta t}\le b\). Hence, by a union bound over \(t\) values, the probability that there is an \(i\le t\) where \(p_i< (1-b\delta)p\) is at most \(t\exp(-(1-b\delta)(1-b)^2\delta^2 tp / 2)\). Otherwise, the Chernoff bound for \(Z_t\) applies, whose failure probability has already been subsumed in the union bound. Hence, the total failure probability is still bounded as before. 0◻ ◻

Proof. The proof essentially analyzes how biased steps add probability mass to either \(K_\nu\) or \(S_{\nu+1}\). In particular, we consider only biased steps that increase a frequency in \(S_\nu\). Typically, only a tiny fraction of the steps in the considered time interval is biased, so it is crucial to bound the total number of biased steps.

First, we filter the biased steps given by 8 from iteration \(t'\) onward, namely, \((\biasedStoppingTime{i}{t'}[t])_{t \in \mathbb{N}}\), to consider only those where a frequency in \(S_\nu\) is increased. To this end, let \((U^i_{t', t})_{t \in \mathbb{N}}\) be defined as \(U^i_{t', 0} = \biasedStoppingTime{i}{t'}[0] = t'\) and, for all \(t \in \mathbb{N}_{\geq 1}\), that \(U^i_{t', t} = \inf\set{\biasedStoppingTime{i}{t'}[s] > U^i_{t', t - 1} s \in \mathbb{N}\land \Delta^{(\biasedStoppingTime{i}{t'}[s])}_i(S_\nu) > 0}\). Since we aim to restrict the amount of such biased steps, let \(B_t = \max\set{t'' \in \mathbb{N}U^i_{t', t''} \leq t' + t}\) be the number of these steps in the time interval \([t',t'+t]\) and \(B=B_{t_{\mathrm{stop}}}\) be the number in the whole time interval considered. We claim that \(B\le \mathopen{}\mathclose{\left(1+\tfrac{1}{\kappa^*}}\right)K\) holds with high probability, and we postpone the proof for later.

We aim at applying [thm:success-upper-parts] to the biased steps that increase a frequency in \(S_{\nu + 1}\), considering all biased steps that increase a frequency in \(S_\nu\), that is, using 9 , to \[(\indic{\Delta^{(U^i_{t', t})}_i(S_{\nu + 1}) > 0})_{t \in [B]} \eqqcolon (X_t)_{t \in [B]} .\] To this end, we choose \(\eta = \frac{1}{K}\), \(\rho = (1+\frac{1}{\kappa^*}) \mu_{i}^{(t')}(S_\nu)\), and recall \(p = \frac{1-1/\kappa^*}{1+1/\kappa^*} \frac{\mu_{i }^{(t')}(S_{\nu + 1})}{\mu_{i}^{(t')}(S_\nu)}\). We note that \(\rho p = (1-\frac{1}{\kappa^*} ) \mu_{i}^{(t')}(S_{\nu + 1})\), and we recall that \(\biasedStoppingTime{i}{t'}[0] = t'\) by definition.

In order to apply [thm:success-upper-parts], we show for all \(t \in [B]\) that 11 holds. Using the same notation of \(Z\) from [thm:success-upper-parts], by the definition of \(X\), which only considers points in time where we increase a frequency in \(S_\nu\), we obtain for all \(t \in [0 .. B]\) that \[\label{lem:adequate-biased-growth:actual-update-probability} \prob{X_{t + 1} = 1 Z_{t + 1}, U^i_{t', t}} = \frac{\mu_{i}^{(t' + U^i_{t', t})}(S_{\nu + 1})}{\mu_{i}^{(t' + U^i_{t', t})}(S_\nu)} .\tag{13}\] We bound 13 in the following from below by bounding the numerator and denominator separately.

Bounding the numerator from below. The contribution to the probability mass in \(S_{\nu + 1}\) does not only consist of the increase via biased steps but also of the updates via (typically much more frequent) random-walk steps, which can decrease the probability mass. We account for the decrease via random-walk steps by [lem:contribution-random-walk-steps-kappastar]. Since we assume that \(\mu^{(t')}_i(S_{\nu + 1}) \ge (1-1/\kappa^*)^{3\kappa^*-3}/r \geq \frac{\eulerE[-3]}{r}\) and that \(t_{\mathrm{stop}}\leq c_{\mathrm{stop}} K \sqrt{n} \ln n\), [lem:contribution-random-walk-steps-kappastar] is applicable and yields that genetic drift contributes to the frequencies in \(S_{\nu + 1}\) at least a value of \(-\frac{1}{\kappa^*} \mu_{i \mid \randomWalkStoppingTime{i}{t'}[]}^{(t')}(S_{\nu + 1})\) with probability at least \(1 - 2 n^{-c^*/ (3857 c_{\mathrm{stop}})}\).

Since the biased steps cannot decrease the frequencies in \(S_{\nu + 1}\), and since \(U^i_{t', 0} = \biasedStoppingTime{i}{t'}[0]\), we get for all \(t \in [0 .. t_{\mathrm{stop}}]\) with probability at least \(1 - 2 n^{-c^*/ (3857 c_{\mathrm{stop}})}\) that \[\mu_{i}^{(t' + U^i_{t', t})}(S_{\nu + 1}) \geq \mathopen{}\mathclose{\left(1-\frac{1}{\kappa^*}}\right) \mu_{i \mid U^i_{t'}}^{(t')}(S_{\nu + 1}) + \frac{Z_{t + 1}}{K} = \rho p + \eta Z_{t + 1} .\]

Bounding the numerator from above. Similarly to the previous case, the probability mass in \(S_\nu\) is updated via random-walk steps and increased via biased steps. By applying [lem:contribution-random-walk-steps-kappastar], we obtain that the increase via random-walk steps is at most \(\frac{1}{\kappa^*}\) of the starting value, with probability at least \(1 - 2 n^{-c^*/ (3857 c_{\mathrm{stop}})}\).

Moreover, each biased update in \(S_\nu\) increases the probability mass by \(\frac{1}{K}\). Thus, for all \(t \in [0 .. t_{\mathrm{stop}}]\), we have \[\mu_{i}^{(t' + U^i_{t', t})}(S_\nu) \leq \mathopen{}\mathclose{\left(1+\frac{1}{\kappa^*}}\right) \mu_{i \mid U^i_{t'}}^{(t')}(S_\nu) + \frac{t + 1}{K} = \rho + \eta (t + 1) .\]

Bounding the ratio of mass at time \(t\). The two inequalities above show that 11 is satisfied. Recalling that we are aiming at a statement holding for all time steps \(t'+t\in[t'..t'+t_{\mathrm{stop}}]\), we distinguish two cases according to the number \(B_t\) of biased steps increasing \(S_{\nu}\) in that time interval.

Case 1: \(B_t\ge (1-1/\kappa^*)^{3(\kappa^*-1)} \frac{K}{\kappa^* r}\). In this case, \(B_t\) is so large that [thm:success-upper-parts] yields sufficient concentration for the probability mass moved into \(S_{\nu+1}\).

Using the notation from [thm:success-upper-parts], we choose \(\delta = \frac{1}{\kappa^*}\) as well as \(b = 1-\frac{1}{2\eulerE[3]r}\), noting that, due to our assumptions \(B_t \le B \leq (1+\frac{1}{\kappa^*})K\) and \(\mu_{i}^{(t')}(S_\nu) \ge (1-1/\kappa^*)^{3\kappa^*-3}/r \geq \frac{\eulerE[-3]}{r}\), we obtain \[b = 1 - \frac{1}{2 \eulerE[3] r } \geq 1 - \frac{1}{1 + \eulerE[3] r} \ge 1 - \frac{1}{1 + \eta B_t/\rho} = \frac{\eta B_t}{\rho + \eta B_t} .\]

Hence, by applying [thm:success-upper-parts], we have that \(Z_{B_t + 1} \leq (1 - \delta) B_t p = (1-\frac{1}{\kappa^*}) B_tp\) only occurs with probability at most \[\begin{align} B_t \exp\mathopen{}\mathclose{\left(-\frac{1}{2} (1 - b \delta) (1 - b)^2 \delta^2 B_t p}\right) & = B_t \exp\mathopen{}\mathclose{\left(- \bigOmega*{\frac{\delta^2 B_t p}{r^2 }}}\right) \\ & = B_t \exp\mathopen{}\mathclose{\left(- \bigOmega*{\frac{\delta^2 K p}{r^3\ln r }}}\right) \end{align}\] by our assumption \(B_t\ge (1-1/\kappa^*)^{3(\kappa^*-1)} \frac{K}{\kappa^* r} = \Omega(K/(r\ln r))\). Further using that \(r=O(n^{1/6-\varepsilon})\), \(K=\Omega(\sqrt{n})\), \(B_t=\mathrm{poly}(n)\), and \(\delta=\Omega(1/\!\ln n)\), the bound on the failure probability is at most \(\exp(-\Omega(n^{\varepsilon/2}p))\).

Concluding under the current assumptions. Under the likely event \(Z_{B_t + 1} \geq (1 - \delta) B_t p\), we now relate the final probability masses in \(S_{\nu+1}\) and \(S_\nu\) to each other to prove the statement of the theorem. The event states that at least \((1-1/\kappa^*)B_t p\) of the \(B_t\) specific biased steps in the interval \([t'..t'+t]\) add probability mass to \(S_{\nu+1}\). We assume this to happen and pessimistically let all other biased steps increase the mass of \(S_{\nu}\). Hence, we have at time \(t\) that \[\mu_{i}^{(t'+t)}(S_{\nu + 1}) \geq \mathopen{}\mathclose{\left(1-\frac{1}{\kappa^*}}\right) \mu_{i}^{(t')}(S_{\nu + 1}) + \frac{(1-1/\kappa^*)B_t p}{K}\] and \[\mu_{i}^{(t'+t)}(S_{\nu}) \leq \mathopen{}\mathclose{\left(1+\frac{1}{\kappa^*}}\right) \mu_{i}^{(t')}(S_{\nu}) + \frac{B_t(1-(1-1/\kappa^*))}{K} \leq \mathopen{}\mathclose{\left(1+\frac{1}{\kappa^*}}\right) \mu_{i}^{(t')}(S_{\nu}) + \frac{B_t}{K}.\] Recalling that \(p = \frac{(1-\frac{1}{\kappa^*}) \mu_{i}^{(t')}(S_{\nu + 1})}{(1+\frac{1}{\kappa^*}) \mu_{i}^{(t')}(S_{\nu})}\), combining the two inequalities, we obtain \[\frac{\mu_{i}^{(t'+t)}(S_{\nu + 1})}{ \mu_{i}^{(t'+t)}(S_{\nu})} \ge \frac{p (1+1/\kappa^*) \mu_{i}^{(t')}(S_{\nu}) +p(1-1/\kappa^*)B_t/K}{(1+1/\kappa^*) \mu_{i}^{(t')}(S_{\nu}) + B_t/K} \ge p(1-1/\kappa^*).\] Again substituting \(p\) in the last bound and noting that \(\frac{1-1/\kappa^*}{1+1/\kappa^*}\ge (1-\frac{1}{\kappa^*})^2\), we finally have \[\frac{\mu_{i}^{(t'+t)}(S_{\nu + 1})}{ \mu_{i}^{(t'+t)}(S_{\nu})} \ge \mathopen{}\mathclose{\left(1-\frac{1}{\kappa^*}}\right)^3 \cdot \frac{\mu_{i}^{(t')}(S_{\nu + 1})}{ \mu_{i}^{(t')}(S_{\nu})}\] with the claimed probability, recalling that we still need to bound the probability of \(B\) not being too large, which we do at the end of this proof.

Case 2: \(B_t < (1-1/\kappa^*)^{3(\kappa^*-1)}\). Here the number of steps is so small that Theorem [thm:success-upper-parts] does not provide strong enough concentration. However, then the few biased steps cannot significantly change the ratio of masses in \(S_\nu\) and \(S_{\nu+1}\). We pessimistically assume that all the \(S_\nu\)-increasing biased steps in the time interval \([t'..t'+t]\) increase \(S_\nu\setminus S_{\nu+1}\). Similarly to the above but without applying Theorem [thm:success-upper-parts], we have \[\begin{align} \frac{\mu_{i}^{(t'+t)}(S_{\nu + 1})}{ \mu_{i}^{(t'+t)}(S_{\nu})} & \ge \frac{p (1+1/\kappa^*) \mu_{i}^{(t')}(S_{\nu}) }{(1+1/\kappa^*) \mu_{i}^{(t')}(S_{\nu}) + B_t/K} \ge \frac{p \mu_{i}^{(t')}(S_{\nu}) }{\mu_{i}^{(t')}(S_{\nu}) + B_t/K} \\ & \ge \frac{p \mu_{i}^{(t')}(S_{\nu}) }{\mu_{i}^{(t')}(S_{\nu}) + (1-1/\kappa^*)^{3\kappa^*-3}/(\kappa^* r)} \\ & \ge \frac{p (1-1/\kappa^*)^{3\kappa^*-3}/r}{ (1-1/\kappa^*)^{3\kappa^*-3}/r + (1-1/\kappa^*)^{3\kappa^*-3}/(\kappa^* r) } \ge \mathopen{}\mathclose{\left(1-\frac{1}{\kappa^*}}\right) p . \end{align}\] using the prerequisite \(\mu_i^{(t')}(S_\nu)\ge (1-1/\kappa^*)^{3\kappa^*-3}/r\) from the lemma.

Bounding the total number of biased steps. We are still left with the claim that \(B\le \mathopen{}\mathclose{\left(1+\frac{1}{\kappa^*}}\right)K\) with high probability. This is actually a consequence of the fact that we have bounded the number of random-walk steps with high probability. First, note that \(\mu_i^{(t')}(K_{\psi})\le 1\), \(\mu_i^{(t'+t_{\mathrm{stop}})}(K_{\psi})= 0\) by definition of \(t_{\mathrm{stop}}\), and that each biased step decreases the probability mass in \(K_{\psi}\) by \(1/K\). Hence, the number of biased steps in the time interval \([t'..t'+t_{\mathrm{stop}}]\) is bounded by \(\mu_i^{(t'+t_{\mathrm{stop}})}(K_{\psi}) - \mu_i^{(t')}(K_{\psi}) \le K\), plus \(K\) times the accumulated increase of probability mass in \(K_{\psi}\) due to random-walk steps. We recall the application of [lem:contribution-random-walk-steps-kappastar] above and obtain that genetic drift increases the probability mass in \(K_\psi\) by at most \(\frac{1}{\kappa^*} \mu_i^{t'} (K_{\psi}) \le \frac{1}{\kappa^*}\) in the time interval \([t'..t'+t_{\mathrm{stop}}]\), with the high probability \(1-2n^{-c^*/(3857c_{\mathrm{stop}})}\) stated above. Hence, there are at most \(K(1+1/\kappa^*)\) biased steps with the stated probability. Adding this probability to the failure probability of the statement and taking a union bound over the at most \(t_{\mathrm{stop}}\) steps considered concludes the proof. 0◻ ◻

Proof. We make a case distinction with respect to \(r\). If \(r\) is constant, we apply the known result by AdakW25?, which is better than our runtime bound for such values of \(r\). Hence, in the following, we assume that \(r = \smallOmega{1}\).

Recalling 3 and as mentioned before, we split the analysis into \(\kappa^* = \ceil{\log_{3/2}(r - 1)}\) consecutive phases for each position \(i \in [n]\). At the beginning of phase \(\kappa \in [0 .. \kappa^* - 1]\), all probability mass at position \(i\) is in frequencies for values in \(S_\kappa\) and none of the other frequencies, and the probability mass in \(K_\kappa\) is positive. Phase \(\kappa\) stops once all probability mass from \(K_\kappa\) is removed. We note that a phase \(\kappa' \in [\kappa + 1 .. \kappa^* - 1]\) is skipped if for all \(\psi \in [\kappa + 1 .. \kappa']\), the frequency mass in \(K_{\psi}\) is (also) \(0\) at the end of phase \(\kappa\).

We assume first that the assumptions of [lem:driftBound] are met during an entire phase. Via the multiplicative drift theorem ([thm:multiplicative-drift-concentration-with-failure]), we show that each phase (for each position) lasts with high probability at most order \(K \sqrt{n} \ln n\) iterations. Since each position is optimized in parallel, a union bound over all positions yields that a single phase for all positions also only takes at most order \(K \sqrt{n} \ln n\) iterations. Since we have \(\kappa^* = \bigO{\log r}\), the total runtime is with high probability at most \(\bigO{K \sqrt{n} \log(n) \log(r)}\). Afterward, we show via [lem:adequate-biased-growth] that the assumptions of [lem:driftBound] hold for each phase and each position, thus concluding the proof.

We note that [lem:driftBound] only works for phases \(\kappa \in [0 .. \kappa^* - 1]\) where \(\ell_\kappa \leq r - 10\), which excludes constantly many phases toward the end. For these phases, we apply the result by Adak and Witt (2) directly, noting that we only consider a constant amount of frequencies with positive mass, all of which have at the beginning of each remaining phase at least a constant value. Although this does not imply that all these frequencies share their mass uniformly at the beginning of a phase, the result from 2 is still applicable, since scaling the initial value of all involved frequencies by a constant factor does not affect the results asymptotically by more than a constant factor. This implies that we have the same bound for all phases.

Bounding the runtime for each phase for each position. Consider position \(i \in [n]\) and phase \(\kappa \in [0 .. \kappa^* - 1]\). Let \(c^*\in \mathbb{R}_{> 0}\) be a sufficiently large constant, and let \(t' \in \mathbb{N}\) be the random iteration in which phase \(\kappa\) starts for position \(i\). Assume that the assumptions of [lem:driftBound] are met for the first \(c^* K \sqrt{n} \ln n\) iterations of the phase or until the phase ends. To this end, let \(\mathcal{A}_{t'}\) denote the event that the assumptions of [lem:driftBound] hold for the first \(c^* K \sqrt{n} \ln n\) iterations of the phase. We note that we show at the end of this proof that \(\prob{\mathcal{A}_{t'}} = \bigO{n^{-3}}\). Moreover, assume that the probability mass in \(S_{\kappa + 1}\) is at least some constant throughout this time.

We consider the random process \((X_t)_{t \in \mathbb{N}} \mathrel{\vcenter{:}}= (1 - \mu_i^{(t' + t)}(S_{\kappa+1}))_{t \in \mathbb{N}}\). Let \(c_1, c_2 \in \mathbb{R}_{> 3}\) be sufficiently large constants, and let \(x_{\min}= \frac{1}{K}\). Then by [lem:driftBound], including the fact that we consider the setting where we actually observe drift, we obtain for all \(t \in \mathbb{N}\) before the phase ends that \[\expect{(X_t - X_{t + 1}) \cdot \indic{t < T \land \mathcal{A}_{t'}} \freq{t}{}{}} \geq c^*\frac{1}{K \sqrt{n}} X_t \cdot \indic{t < T} \prob{\mathcal{A}_{t'} \freq{t}{}{}} .\] By an application of the second statement of [thm:multiplicative-drift-concentration-with-failure] with \(\gamma = c_2 \ln n\), noting that \(X_0 \leq 1\) and thus \(\expect{X_0 \cdot \indic{t < T}} / x_{\min}\leq K = \mathrm{poly}(n)\), we obtain that with probability at least \(1 - n^{-c_2} - \bigO{n^{-3}}\), phase \(\kappa\) for position \(i\) ends in at most \(c_1 K \sqrt{n} \ln n\) iterations. Via a union bound over all \(n\) positions, phase \(\kappa\) ends for all positions with probability at least \(1 - n^{1 - c_2} - \bigO{n^{-2}}\) during the same number of iterations.

Showing that the assumptions for [lem:driftBound] are met. Consider a position \(i \in [n]\) and a phase \(\kappa \in [0 .. \kappa^* - 2]\). Let \(t' \in \mathbb{N}\) denote the first (random) iteration of phase \(\kappa\) for position \(i\), and for a sufficiently large constant \(c_{\mathrm{stop}}\in \mathbb{R}_{> 0}\), let \(t_{\mathrm{stop}}= c_{\mathrm{stop}} K \sqrt{n}\) denote an upper bound on the length of this phase (that holds with high probability). Then \(\mu_i^{(t')}(S_\kappa)=1\) and \(\mu_i^{(t')}(K_\kappa) > 0\) hold by the definition of a phase. Assuming that \(\mu^{(t')}_i(S_{\nu}) \ge (1-1/\kappa^*)^{3\kappa^*-3}/r\) also holds, which we prove below, [lem:adequate-biased-growth] yields that for a sufficiently large constants \(c^*\in \mathbb{R}_{> 3}\), with probability at least \(1 - 3 t_{\mathrm{stop}} n^{-c^*/ (3857 c_{\mathrm{stop}})}\), for the \(c_{\mathrm{stop}} K \sqrt{n} \ln n\) iterations following \(t'\), the ratio of cumulative probability mass in the upper frequencies is roughly the same as it is in the previous phase.

Applying [lem:adequate-biased-growth] iteratively, assuming its conditions to be met for now, we obtain for all \(\nu \in [\kappa + 1 .. \kappa^* - 1]\) and all \(t \in [t' .. t' + t_{\mathrm{stop}}]\), that \[\frac{\mu_{i}^{(t' + t)}(S_{\nu + 1})}{\mu_{i}^{(t' + t)}(S_\nu)} \geq \mathopen{}\mathclose{\left(1 - \frac{1}{\kappa^*}}\right)^{3 (\kappa^* - 1)} \frac{\mu_{i}^{(0)}(S_{\nu + 1})}{\mu_{i}^{(0)}(S_\nu)}\] with probability at least \(1 - 3 \kappa^* t_{\mathrm{stop}} n^{-c^*/ (3857 c_{\mathrm{stop}})}\).

Note that since in iteration \(0\), all frequencies are initialized to \(\frac{1}{r}\), and by 3 , we see that \(\mu_{i}^{(0)}(S_{\nu + 1}) / \mu_{i}^{(0)}(S_\nu)\) is bounded from below by \[\frac{r - 1 - \ell_{\nu + 1}}{r - 1 - \ell_\nu} = \frac{\ceil*{\mathopen{}\mathclose{\left(\frac{2}{3}}\right)^{\nu + 1} (r - 1)}}{\ceil*{\mathopen{}\mathclose{\left(\frac{2}{3}}\right)^\nu (r - 1)}} \geq \frac{\mathopen{}\mathclose{\left(\frac{2}{3}}\right)^{\nu + 1} (r - 1)}{\mathopen{}\mathclose{\left(\frac{2}{3}}\right)^\nu (r - 1) + 1} \geq \frac{2}{5} .\] Thus, \(\mu_{i}^{(t' + t_{\mathrm{stop}})}(S_{\nu + 1}) / \mu_{i}^{(t' + t_{\mathrm{stop}})}(S_\nu) \geq \frac{2}{5}\). This shows that the non-trivial assumption in [lem:driftBound] including the constant \(c_{\mathrm{drift}}\) is met.

It remains to show that the assumption \(\mu^{(t')}_i(S_{\nu}) \ge (1-1/\kappa^*)^{3\kappa^*-3}/r\) from [lem:adequate-biased-growth] is satisfied. This follows inductively from an application of [lem:adequate-biased-growth] for all preceding phases. The base case is satisfied since all frequencies are initialized with \(\frac{1}{r}\) by the definition of the \(r\)-cGA. The other cases follow from [lem:contribution-random-walk-steps-kappastar], using the induction hypothesis for the lower bound on the probability mass in \(S_\nu\), since \((1 - 1/\kappa^*)^{3(\kappa^* - 1)} \geq \eulerE[-3]\). Thus, since probability mass in \(S_\nu\) can never decrease due to biased steps, with probability at least \(1 - 2 \kappa^* n^{-c^*/ (3857 c_{\mathrm{stop}})}\), each phase reduces the probability mass in \(S_\nu\) by at most a \(1/\kappa^*\)-fraction. This proves this claim.

Concluding. We are left with adding up all the failure probabilities of all the cases discussed above. The bound of the multiplicative drift theorem holds per phase (and for all positions) with probability at least \(1 - n^{1 - c_2} - \bigO{n^{-2}}\). Since we have at most \(\kappa^*\) phases, the probability of one phase taking longer is at most \(\kappa^* (n^{1 - c_2} + \bigO{n^{-2}}) = \bigO{\frac{1}{n}}\), since \(c_2\) is sufficiently large and since \(\kappa^* = \bigO{\log n}\).

The failure probability of applying [lem:adequate-biased-growth] is per phase and per position at most \(3 \kappa^* t_{\mathrm{stop}} n^{-c^*/ (3857 c_{\mathrm{stop}})}\). A union bound over all at most \(\kappa^*\) phases and all \(n\) positions yields, since \(c^*\) is sufficiently large and since \(t_{\mathrm{stop}}= \mathrm{poly}(n)\), a total failure probability of \(\bigO{n^{-3}}\). Note that this failure probability also accounts for \(q\) in the application of [thm:multiplicative-drift-concentration-with-failure].

Last, the application of [lem:contribution-random-walk-steps-kappastar] adds a failure probability of at most \(2 \kappa^* n^{-c^*/ (3857 c_{\mathrm{stop}})}\) for each phase and each position. Similar to the previous paragraph, this adds up to a total failure probability of \(\bigO{\frac{1}{n}}\).

Adding up these three total failure probabilities concludes the proof. 0◻ ◻