Proof of Theorem [thm:Main0]. As mentioned previously, \((1^n,1^n)\) is the Maximin optimum or Nash Equilibrium of \(f\). Note that \((1,\lambda)\)-EA initialises the search point uniformly at random.

Let us denote the number of \(1\)-bits of search point at iteration \(t\) by \(Z_t\). Let \(M_t=2n-Z_t\). Next, to show the runtime’s lower bound, we define the first hitting time \(T_{\varepsilon}:=\inf \{t>0 \mid M_t\leq \varepsilon n\}\) for any \(\varepsilon \in [0,1)\). Note that \(Z_0\) are subject to Binomial distribution \(\text{Bin}(2n,1/2)\). We compute the probability of \(M_0\leq (1-\eta) n\) for any \(\eta \in (0,1)\).

\[\begin{align} \Pr \left(M_0\leq (1-\eta) n \right) = \Pr \left(2n-Z_0 \leq (1-\eta) n \right) &= \Pr \left( Z_0 \geq (1+\eta) n \right) \nonumber \\ \intertext{By using Chernoff's bound on Z_0 \sim \text{Bin}(2n,1/2), we have} &\leq \exp \left(-\frac{n \eta^2}{2+\eta} \right) = e^{-\Omega(n)}. \label{eq:initThmNeg} \end{align}\tag{1}\] This means that the initial search point \(Z_0\) satisfies \(M_0>(1-\eta)n\) with probability \(1-e^{-\Omega(n)}\) for any \(\eta \in (0,1)\) or with high probability for sufficiently large \(n\). We satisfy one of the assumptions of Theorem 1 with high probability.

Next, we denote \(x_t, y_t\) by the binary bitstring for the leftmost part and rightmost part of the original bitstring and \(X_t, Y_t\) by the numbers of \(1\)-bits of \(x, y\) respectively at iteration \(t\). Suppose the numbers of \(1\)-bits of \(\lambda\) offspring from \(x, y\) respectively at iteration \(t\) are denoted by \[\begin{align} (X_t^{(1)},Y_t^{(1)}), (X_t^{(2)},Y_t^{(2)}), \cdots ,(X_t^{(\lambda)},Y_t^{(\lambda)}). \end{align}\] Based on the bitwise mutation operator, we have, for \(i\in [\lambda]\), \[X_t^{(i)} \sim \text{Bin}(n-X_t,\frac{\chi}{n})-\text{Bin}(X_t,\frac{\chi}{n}) \text{ and } Y_t^{(i)} \sim \text{Bin}(n-Y_t,\frac{\chi}{n})-\text{Bin}(Y_t,\frac{\chi}{n}). \label{eq:mutant}\tag{2}\]

If the search point \(z_t=(x_t,y_t)\) satisfies \(X_t<Y_t\), then \(f(z_t)=0\). \((1,\lambda)\)-EA continues the random walk on the search space of fitness \(0\) until it finds the point of fitness \(1\). Next, we show the following claim:

Under the worst case scenario, this random walk firstly leads to \((X_t,Y_t)=(\frac{n}{2}, \frac{n}{2})\) in polynomial runtime rather than \((X_t,Y_t)=(n,n)\) within exponentially large iterations.

Suppose the \((1,\lambda)\)-EA is unlucky and samples all the offspring of fitness \(0\), then the algorithm will choose one of the offspring uniformly at random. In this case, the search point will be only driven by the mutation operator. So we compute the drift \[\begin{align} \mathrm{E}_t\mathord{\left(X_t-X_{t+1}\right)}=(n-2X_t)\frac{\chi}{n} \text{ and } \mathrm{E}_t\mathord{\left(Y_t-Y_{t+1}\right)}=(n-2Y_t)\frac{\chi}{n}. \end{align}\] Firstly, we consider the hitting time to \((X_t,Y_t)=(n/2,n/2)\). Without loss of generality, if \(X_t\leq \frac{n}{2}\) (or \(Y_t\leq \frac{n}{2}\)), then the additive drift theorem implies that the algorithm will reach \((n/2,n/2)\) with the potential function \(M_t=\frac{n}{2}-X_t\) (or \(M_t=\frac{n}{2}-Y_t\)). If \(X_t \geq \frac{n}{2}\) (or \(Y_t\geq \frac{n}{2}\)), by taking \(M_t:=X_t-\frac{n}{2}\) (or \(M_t:=Y_t-\frac{n}{2}\)) as the potential function, we can obtain the same result. Now, if we consider the hitting time to \((X_t,Y_t)=(n,n)\) with the uniform initialisation of the search point (shown in Eq. 1 ), then we can only obtain the negative drift before reaching the optimum. Moreover, since it is a random walk, and each of the offspring is of the same fitness \(0\), then we satisfy condition (2) in Theorem 1. Using Theorem 1, we can conclude that this random walk hits \((X_t,Y_t)=(n,n)\) with an exponentially large runtime.

Now, we assume that before reaching the optimum \((1^n,1^n)\), \(X_t\geq Y_t\) and \(\varepsilon n<M_t <n/4\) and \(Y_t\geq n/2\). We define the number of offspring such that \(\Delta_t^{(i)}:=X_t^{(i)}-Y_t^{(i)}\geq 0\) by \(N\): \[\begin{align} N:=|\{i \in [\lambda]\}\mid \Delta_t^{(i)}\geq 0\}|. \end{align}\] We can see that for each \(i\in [\lambda]\), \[\begin{align} \Pr\left( \Delta_t^{(i)}\geq 0 \right) \geq (1-\frac{\chi}{n})^{2n} \geq \frac{1}{2e^{2\chi}}:=q_{N^*}. \end{align}\] where we define \(N^* \sim \text{Bin}(\lambda,q_{N^*})\). Then, we can see \(N\) stochastic dominates \(N^*\) (i.e. \(N^* \succcurlyeq N\)) since \(N \sim \text{Bin}(\lambda, \Pr\left( \Delta_t^{(i)}\geq 0 \right))\) where \(\Pr\left( \Delta_t^{(i)}\geq 0 \right) \geq q_{N^*}\). By using stochastic dominance, we obtain: for any \(\delta \in (0,1)\), \[\begin{align} \Pr \left(N\leq (1-\delta) \lambda q_{N^*} \right) &\leq \Pr \left(N^*\leq (1-\delta) \lambda q_{N^*} \right) \\ &= \Pr \left(N^*\leq (1-\delta) \mathrm{E}\mathord{\left(N^*\right)} \right) \\ \intertext{Using Chernoff's bound gives} &\leq \exp \left(- \mathrm{E}\mathord{\left(N^*\right)} \delta /2 \right) = e^{-\Omega(\lambda)}. \end{align}\] Note that \(\Delta_t^{(i)}\geq 0\) means that we have \(f(z_t^{(i)})=1\) and the above concentration means that when sampling \(\lambda\) offspring, there are at least \((1-\delta)\lambda /2e^{2\chi}\) offspring of fitness \(1\) with probability \(1-e^{-\Omega (\lambda)}\). Then, for any \(j \in \mathbb{N}_0\), using the law of total probability gives \[\begin{align} \mathrm{Pr}_{t}\left(|M_t-M_{t+1}|\geq j \right) &= \mathrm{Pr}_{t}\left(|M_t-M_{t+1}|\geq j \mid N\geq \frac{\lambda}{4e^{2\chi}}\right)\cdot \Pr( N\geq \frac{\lambda}{4e^{2\chi}})\\ &\quad + \mathrm{Pr}_{t}\left(|M_t-M_{t+1}|\geq j \mid N\leq \frac{\lambda}{4e^{2\chi}}\right) \cdot \Pr ( N\leq \frac{\lambda}{4e^{2\chi}}) \\ \intertext{Using\Pr( N\geq \frac{\lambda}{4e^{2\chi}})\leq 1 and \Pr ( N\leq \frac{\lambda}{4e^{2\chi}}) \leq e^{-\Omega (\lambda)} gives} &\leq \mathrm{Pr}_{t}\left(|M_t-M_{t+1}|\geq j \mid N\geq \frac{\lambda}{4e^{2\chi}}\right)+ e^{-\Omega (\lambda)} \\ \intertext{Recall that X_t^{(i)},Y_t^{(i)} denote the number of 1 bits of i-th offspring for x,y individual respectively (for i \in [\lambda]). Let us denote the difference between Hamming distance to the optimum for each i-th offspring (i.e 2n-X_t-Y_t-(2n-X_t^{(i)}-Y_t^{(i)})=(X_t^{(i)}-X_t)+(Y_t^{(i)}-Y_t)) by Z_t^{(i)}:=(X_t^{(i)}+Y_t^{(i)})-X_t-Y_t and the event \{|M_t-M_{t+1}|\geq j\} by E_j. We also denote the event \{\text{k-th offspring is selected}\} by F_k. Using the law of total probability for conditional probability gives} &= \sum_{k=1}^{\lambda} \Pr \left(E_j \mid N\geq \frac{\lambda}{4e^{2\chi}}, F_k \right) \Pr \left(F_k \mid N\geq \frac{\lambda}{4e^{2\chi}} \right) + e^{-\Omega (\lambda)} \\ \intertext{When conditioning on F_k, the event E_j becomes |Z_t^{(k)}|\geq j. Thus, we have} &= \sum_{k=1}^{\lambda} \Pr \left(|Z_t^{(k)}|\geq j \mid N\geq \frac{\lambda}{4e^{2\chi}}, F_k\right)\Pr \left(F_k \mid N\geq \frac{\lambda}{4e^{2\chi}} \right) + e^{-\Omega (\lambda)} \\ \intertext{We can upper bound probability of |Z_t^{(k)}|\geq j by only considering flipping j bits among 2n-bitstring. Thus, } &\leq \sum_{k=1}^{\lambda} \binom{n}{j} (\frac{\chi}{n})^j \Pr\left(F_k \mid N\geq \frac{\lambda}{4e^{2\chi}} \right) + e^{-\Omega (\lambda)} \\ \intertext{Using \binom{n}{j} \leq \frac{n^j}{j!}, j!\geq 2^jand \chi \in (0,1] gives} &\leq \sum_{k=1}^{\lambda} \frac{1}{2^j} \Pr\left(F_k \mid N\geq \frac{\lambda}{4e^{2\chi}} \right) + e^{-\Omega (\lambda)} \intertext{Recall that we denote N to the number of offspring of fitness 1 (i.e.\Delta_t^{(i)} \geq 0) and F_k denotes the event that k-th offspring will be selected. As mentioned, when the algorithm comes across a tie, we select the offspring uniformly at random among those offspring of fitness 1. Thus, we can get} &\leq \lambda \cdot \frac{1}{2^j}\cdot \frac{1}{N} +e^{-\Omega(\lambda)} \\ \intertext{Also, note that we condition on the event that N \geq \lambda / 4e^{2\chi}.} &\leq \frac{4e^{2\chi}}{2^j}+ e^{-\Omega (\lambda)} \leq \frac{8e^{2\chi}}{2^j}. \end{align}\] Now, we satisfy condition (2) in Theorem 1 with \(r=8e^{2\chi}=o(n/\log n)\) and \(\eta=1\).

Finally, we compute the negative drift for \(M_t\). Recall the assumptions: before reaching the optimum \((1^n,1^n)\), \(X_t\geq Y_t\) and \(\varepsilon n<M_t <n/4\) and \(Y_t\geq n/2\). It is possible for \((1,\lambda)\)-EA to produce a search point which is allowed to move to \(4\) directions in \(|x|-|y|\) plane (see Figure 1) only if the search point is of fitness \(1\) (or below the diagonal in Figure 1).

Next, we compute the drift. Then we can compute the following: \[\begin{align} \mathrm{E}_t\mathord{\left(M_t-M_{t+1}\right)} &=\mathrm{E}_t\mathord{\left(X_t-X_{t+1}\right)} + \mathrm{E}_t\mathord{\left(Y_t-Y_{t+1}\right)} \\ \intertext{ Recall that X_t^{(i)},Y_t^{(i)} denote the number of 1 bits of i-th offspring for x,y individual respectively (for i \in [\lambda]). Recall that Z_t^{(i)}:=(X_t^{(i)}+Y_t^{(i)})-X_t-Y_t and that the event \{\text{k-th offspring is selected}\} by F_k. Using law of total expectation gives } &= \sum_{k=1}^{\lambda}\mathrm{E}\mathord{\left(M_t-M_{t+1} \mid F_k\right)} \Pr \left(F_k \right) \\ &= \sum_{k=1}^{\lambda}\mathrm{E}\mathord{\left(Z_t^{(k)}\right)}\Pr \left(F_k \right) \\ \intertext{Recall the bitwise mutation operator in Eq.~\ref{eq:mutant}. Each Z_t^{(k)} is independently and identically distributed.} &= \mathrm{E}\mathord{\left(Z_t^{(k)}\right)} \sum_{k=1}^{\lambda}\Pr \left(F_k \right) \intertext{Note that \sum_{k=1}^{\lambda}\Pr \left(F_k \right)=1. We can prove it by dividing it into two cases. Firstly, if N\geq 1, then the probability of each offspring of fitness 1 being selected is 1/N and the probability of each offspring of fitness 0 being selected is 0 if N\geq 1. Thus, if we sort all the offspring of fitness 1 in the first N offspring and the offspring of fitness 0 in the rest \lambda-N places (See Fig.~\ref{fig:Thmthree}), then \sum_{k=1}^{\lambda}\Pr \left(F_k \right)=\sum_{k=1}^N 1/N=1. Secondly, if N=0, then \sum_{k=1}^{\lambda}\Pr \left(F_k \right)=\sum_{k=1}^{\lambda}\frac{1}{\lambda}=1.} &= \mathrm{E}\mathord{\left(Z_t^{(k)}\right)} \\ \intertext{To simplify the calculation, we underestimate the negative drift along x-axis by neglecting the backwards negative drift and only considering the forward positive drift towards x=1^n. Moreover, we overestimate the positive drift along the y-axis by taking all the possible samples (even the search point above the diagonal and thus of fitness 0) into account. } &\leq (n-X_t)\frac{\chi}{n} + (n-2Y_t) \frac{\chi}{n} \\ &=M_t \frac{\chi}{n} - Y_t\frac{\chi}{n} \leq \frac{1}{4} - \frac{1}{2} = \frac{-1}{4}<0. \end{align}\] Now, we satisfy all the conditions of Theorem 1. Then, we apply Theorem 1 on \(M_t\) to derive the following: there exists a constant \(c>0\) such that \[\begin{align} \Pr\left( T_{\varepsilon} \leq e^{cn} \right) \leq e^{-cn}. \end{align}\] 0◻ ◻

Proof of Lemma [lem:AvgCharacteristic1].

• If \(|x^{(1)}|\geq |x^{(2)}|\), then we rewrite the fitness in terms of sum indicator functions: \[\begin{align} f(x^{(1)}):= g(x^{(1)},y)= \mathbb{1}_{\{x^{(1)}\geq y \}} \end{align}\] Notice that if \(|x^{(2)}|\geq |y|\), then \(|x^{(1)}|\geq |x^{(2)}| \geq |y|\). Then we have the event inclusion: \[\begin{align} \{|x^{(2)}|\geq |y| \} &\subseteq \{|x^{(1)}| \geq |y|\} \\ \intertext{This implies that} \mathbb{1}_{\{|x^{(2)}|\geq |y| \}} & \leq \mathbb{1}_{\{|x^{(1)}| \geq |y|\}} \\ \intertext{Then, we have} f(x^{(2)})= \mathbb{1}_{\{|x^{(2)}|\geq |y| \}} & \leq \mathbb{1}_{\{x^{(1)}\geq y \}}=f(x^{(1)}). \end{align}\]

• If \(|y^{(1)}|\geq |y^{(2)}|\), then we rewrite the fitness in terms of sum indicator functions: \[\begin{align} h(y^{(1)}):=g(x,y^{(1)})= \mathbb{1}_{\{x \geq y^{(1)} \}} \end{align}\] Notice that if \(|x|\geq |y^{(1)}|\), then \(|x|\geq |y^{(1)}| \geq |y^{(2)}|\). Then we have the event inclusion: \[\begin{align} \{|x|\geq |y^{(1)}| \} &\subseteq \{|x| \geq |y^{(2)}|\} \\ \intertext{This implies that} \mathbb{1}_{\{|x|\geq |y^{(1)}| \}} & \leq \mathbb{1}_{\{|x| \geq |y^{(2)}|\}} \\ \intertext{Then, we have} h(y^{(1)}) = \mathbb{1}_{\{|x|\geq |y^{(1)}| \}} & \geq \mathbb{1}_{\{|x| \geq |y^{(2)}|\}} = h(y^{(2)}). \end{align}\]

0◻ ◻

Proof of Lemma [lem:phase1]. In odd iterations \(t=1,3, \dots,\) Algorithm 3 updates \(y\) and in even iterations \(t=2,4, \dots,\) Algorithm 3 updates \(x\).

If we have \(Y_{2t}>X_{2t}\) in iteration \(2t\), then the next search point does not cross the diagonal if \(Y_{2t+1}>X_{2t+1}\) or \(X_{2t+2} \geq Y_{2t+2}\) in one cycle. And if \(Y_{2t+1}+c \leq X_{2t+1}\) or \(X_{2t+2}+c \leq Y_{2t+2}\), then the search point lies outside the \(c\)-tube during the consecutive steps. Thus, a successful cycle in Definition 5 breaks. Note that a successful cycle in Definition 5 breaks is equivalent to the event that either the search point escapes from the \(c\)-tube or does not cross the diagonal during the cycle. Then, we use the union bound to give an upper bound of the probability that a cycle fails to be successful. Before that, we provide a more precise union bound as follows. Given events \(A,B,E\), \[\begin{align} \Pr \left(A \cup B \mid E \right) &=\Pr\left(A \mid E \right) + \Pr \left(B \setminus A \mid E \right) \nonumber \\ &\leq \Pr\left(A \mid E \right) + \Pr \left(B \mid E, A^c \right) \Pr \left(A^c \mid E \right) \nonumber \\ &\leq \Pr\left(A \mid E \right) + \Pr \left(B \mid E, A^c \right) \label{eq:unionbound} \end{align}\tag{3}\] Next, we denote the following events. \[\begin{align} E_0:&=\{Y_{2t}>X_{2t} \cap D_{2t}<c\} \\ E_1:&=\{X_{2t+1}\geq Y_{2t+1} \} \\ E_2:&=\{Y_{2t+2} > X_{2t+2} \} \\ F_1:&=\{D_{2t+1}\geq c\} \\ F_2:&=\{D_{2t+2}\geq c\} \end{align}\] Note that we have a successful cycle in iteration \(2t\) if and only if \(E_1\cap E_2\cap F_1^c \cap F_2^c\) holds. \[\begin{align} &\Pr \left(\text{A cycle fails to be successful at iteration 2t} \right) \nonumber \\ = & \Pr \left(E_1^c \cup E_2^c\cup F_1 \cup F_2 \mid E_0 \right) \nonumber \\ \intertext{Using the union bound gives} \leq & \Pr \left(E_1^c \cup E_2^c \mid E_0 \right)+ \Pr \left(F_1 \cup F_2 \mid E_0 \right)\nonumber \\ \intertext{Using Eq~(\ref{eq:unionbound}) gives} \leq& \Pr \left(E_1^c \mid E_0 \right) + \Pr \left(E_2^c \mid E_0, E_1 \right) \nonumber\\ &\quad + \Pr \left(F_1 \mid E_0 \right) + \Pr \left(F_2 \mid E_0, F_1^c \right) \nonumber\\ \intertext{Using the conditions (1)-(3) gives} \leq & 2p_c + 2p_e \label{eq:cycle} \end{align}\tag{4}\] Next, we consider \(\tau\) consecutive cycles. We define the failure event \(F_t\) as the algorithm has an unsuccessful cycle in iteration \(t\). By using the union bound and Eq (4 ), we have \[\begin{align} &\Pr \left(\exists t \in [\tau] \text{ s.t. }F_t \text{ occurs during \tau consecutive cycles} \right) \\ \leq& 2\tau (p_c+p_e) \end{align}\] So, we can derive that \[\begin{align} &\Pr \left(\text{The algorithm has \tau consecutive successful cycles} \right) \\ \geq& 1 - 2\tau (p_c+p_e). \end{align}\] A similar analysis holds for the case that \((X_{2t+1},Y_{2t+1})\) in iteration \(2t+1\).

0◻ ◻

Proof of Lemma [lem:binomial]. Consider the Binomial Theorem: \[\begin{align} \left(p+ (1-p) \right)^n &= \sum_{k=0}^n \binom{n}{k}p(1-p)^{n-k} \nonumber \\ &= \sum_{k=0}^{\left\lfloor n/2\right\rfloor} \binom{n}{2k}p^{2k}(1-p)^{n-2k} \nonumber \\ &\quad + \sum_{k=0}^{\left\lfloor n/2\right\rfloor-1} \binom{n}{2k+1}p^{2k+1}(1-p)^{n-(2k+1)} \label{eq:binomial1} \end{align}\tag{5}\] And \[\begin{align} \left(p- (1-p) \right)^n &= \sum_{k=0}^n \binom{n}{k}p \left(-(1-p)\right)^{n-k} \nonumber \\ &= \sum_{k=0}^{\left\lfloor n/2\right\rfloor} \binom{n}{2k}p^{2k}(1-p)^{n-2k} \nonumber \\ &\quad - \sum_{k=0}^{\left\lfloor n/2\right\rfloor-1} \binom{n}{2k+1}p^{2k+1}(1-p)^{n-(2k+1)} \label{eq:binomial2} \end{align}\tag{6}\] Now, we add Equations 5 and 6 to obtain: \[\begin{align} \Pr\left(\text{Z is even} \right) &= \sum_{k=0}^{\left\lfloor n/2\right\rfloor} \binom{n}{2k}p^{2k}(1-p)^{n-2k}\\ &= \frac{1}{2} \left(1^n + (2p-1)^n \right). \end{align}\] 0◻ ◻

Proof of Lemma [lem:crossD0]. If \(\chi=O(1)\), then \[\begin{align} \Pr\left(\text{No offspring of x_t is identical to x_t}\right) &= \left(1-(1-\frac{\chi}{n})^n \right)^{\lambda} \\ \intertext{Here, we use (1-\frac{\chi}{n})^n \geq e^{-\chi}(1-\frac{\chi^2}{n}) and taking n large enough such that (1-\frac{\chi^2}{n}) \geq \frac{1}{2} gives } & \leq (1-\frac{e^{-\chi}}{2})^{\lambda} \\ \intertext{Note that 1-\frac{e^{-\chi}}{2} is a constant in (0,1) so that we obtain the exponentially small tail in \lambda. } & \leq e^{-\Omega(\lambda)}. \end{align}\] Then there exists \(k, \ell>0\) s.t. \(x_t^{k}=x_t\) and \(y_t^{\ell}=y_t\) w.h.p. respectively.

Moreover, note that \(\Pr(X_t^{(1)}>X_t^{(\lambda)})=1-\Pr(X_t^{(1)}\leq X_t^{(\lambda)})= 1- \Pr(X_t^{(1)}=X_t^{(\lambda)})\). Then we can bound the following first (denote the number of 1-bits of original \(x_t\) by \(X_t\)): \[\begin{align} \Pr\left(X_t^{(i)}=X_t\right) &= \sum_{k=0}^{\min \{n-X_t, X_t\}}\binom{n-X_t}{k} (\frac{\chi}{n})^k \\ &\quad \times \binom{X_t}{k}(\frac{\chi}{n})^k (1-\frac{\chi}{n})^{n-2k}\\ \intertext{Using \binom{n_1}{k_1}\binom{n_2}{k_2} \leq \binom{n_1+n_2}{k_1+k_2}gives} & \leq \sum_{k=0}^{\min \{n-X_t, X_t\}}\binom{n}{2k} (\frac{\chi}{n})^{2k} \cdot (1-\frac{\chi}{n})^{n-2k} \\ \intertext{Note that \min \{n-X_t, X_t\} \leq \frac{n}{2}} & \leq \sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n}{2k} (\frac{\chi}{n})^{2k} \cdot (1-\frac{\chi}{n})^{n-2k} \\ \intertext{Consider a binomial random variable Z\sim Bin(n,\frac{\chi}{n}) and we consider the probability that Z is even. Then, we have} & = \Pr\left(\text{Z is even} \right) \\ \intertext{Using Lemma~\ref{lem:binomial} with p=\frac{\chi}{n} gives} &=\frac{1}{2}+\frac{1}{2}\cdot (1-\frac{2\chi}{n})^n \\ &\leq \frac{1}{2} + \frac{1}{2e^{2\chi}} \end{align}\] Since \(\chi>0\) is some constant, so \(\frac{1}{2} + \frac{1}{2e^{2\chi}}=c<1\) is also constant. Given that there exists \(k>0\) s.t. \(x_t^{(k)}=x_t\) w.h.p., we have \[\begin{align} \Pr(X_t^{(1)}=X_t^{(\lambda)}) &\leq \Pr(\text{\forall j \in [\lambda], } X_t^{(j)}=X_t ) \\ &\quad \times (1-e^{-\Omega(\lambda)})+ e^{-\Omega(\lambda)})\cdot 1 \\ &\leq c^{\lambda} (1-e^{-\Omega(\lambda)})+ e^{-\Omega(\lambda)} \\ &= e^{-\Omega(\lambda)} . \end{align}\] Then, \(X_t^{(1)}>X_t^{(\lambda)}\) w.h.p and so is \(Y_t^{(1)}>Y_t^{(\lambda)}\). Then we have \(\lambda\) offspring cross the diagonal w.h.p if \(X_t^{(\lambda)}\leq Y_t^{(1)}\). 0◻ ◻

Proof of Lemma [lem:MGF1]. Compute for any \(\eta> 0\) by using MGFs of binomial random variables: \[\begin{align} M_U(\eta)&= E[e^{\eta U}] \\ &= E[e^{\eta (V_1-V_2)}] \\ \intertext{Using the independence of V_1 and V_2 gives} &= E[e^{\eta V_1}]E[e^{ -\eta V_2}] \\ &= M_{V_1}(\eta) M_{V_2}(-\eta) \\ \intertext{Using the MGF of Binomial random variable gives} &=\left(1-\frac{\chi}{n}+\frac{\chi}{n}e^{\eta} \right)^{n-s} \left(1-\frac{\chi}{n}+\frac{\chi}{n}e^{-\eta} \right)^{s} \\ &= \left(1+\frac{\chi(e^{\eta}-1)}{n} \right)^{n-s}\left(1+\frac{\chi(e^{-\eta}-1)}{n} \right)^{s} \\ \intertext{Using 1+\frac{x}{n} \leq e^{x/n} for all |x|<n gives the following.} &\leq \exp \left(\frac{n-s}{n}\chi(e^{\eta}-1)+\frac{s}{n}\chi(e^{-\eta}-1) \right)\\ &=\exp \left(\chi(e^{\eta}-1)+\frac{s}{n}\chi(e^{-\eta}-e^{\eta}) \right) \\ \intertext{Note that e^{-\eta}-e^{\eta} <0 for any \eta>0.} &\leq \exp \left(\chi(e^{\eta}-1)\right) \end{align}\] 0◻ ◻

Proof of Lemma [lem:MaxPoisson]. We apply Lemma [lem:MGF1] and Markov’s inequality for the concentration. For any \(s \geq 0\) and \(\lambda \geq 1\), \[\begin{align} \Pr \left(U \geq s \right)=\Pr \left(e^{\eta U } \geq e^{\eta s} \right) &\leq E [e^{\eta U } ]e^{-\eta s} \\ \intertext{Taking E [e^{\eta U } ] \leq \exp \left(\chi(e^{\eta}-1)\right) and \eta:=\ln \ln \lambda gives} &\leq e^{\chi (\ln \lambda -1)} e^{- s\ln \ln \lambda } \\ &\leq e^{-\chi} \lambda ^{\chi} e^{- s\ln \ln \lambda } \end{align}\] For the second part, we notice that \[\begin{align} \Pr \left(U \geq s \right)=\Pr \left(e^{\eta U } \geq e^{\eta s} \right) &\leq E [e^{\eta U } ]e^{-\eta s} \\ &\leq e^{-\chi} e^{\chi e^{\eta}-s\eta} \\ \intertext{Note that h(\eta):=\chi e^{\eta}-s\eta attains its minimum at \eta=\ln (\frac{s}{\chi}) by differentiation. So setting \eta:=\ln (\frac{s}{\chi}) gives } &\leq e^{-\chi}e^{-s \left(\ln (\frac{s}{\chi})-1 \right)} \\ \intertext{s\geq e^2 \chi gives \ln (\frac{s}{\chi})-1\geq 1. Then, we have} &\leq e^{-\chi}e^{-s}. \end{align}\] 0◻ ◻

Proof of Lemma [lem:crossD1]. Let us divide the analysis into two cases. Assume \(t\) is even and \(Y_t>X_t\) first. The only way the search point can cross the diagonal is to cross horizontally. Assume now we are in iteration \(t\) such that we mutate and select the new \(X_{t+1}\). By using Lemma [lem:crossD0], we conclude that if \(t\) is even, then \(\Pr \left( \exists k \in [\lambda] , x_t^{k}=x_t\right) \geq 1-e^{-\Omega(\lambda)}\) and \(\Pr \left( \max_{i \in [\lambda]}X_t^i >\min_{i \in [\lambda]}X_t^i\right) \geq 1-e^{-\Omega(\lambda)}\). Then, we first compute the probability that \(E\) does not occur under the case that we have both \(F_1:=\{\exists k \in [\lambda] , x_t^{k}=x_t\}\) and \(F_2:=\{\max_{i \in [\lambda]}X_t^i >\min_{i \in [\lambda]}X_t^i \}\) hold. \[\begin{align} \Pr \left(E_t^c \mid F_1 \cap F_2 \right) &= \Pr \left( X_t^{(1)} <Y_t\right) \\ &= \Pr \left( \max_{i \in [\lambda]}X_t^i <Y_t\right) \\ \intertext{We define for i \in [\lambda] for x_t-bitstring, a random variable W_{i,-} to be the number of 1-bits that the mutation operator flips into 0-bits and another the random variable W_{i,+} to be the number of 0-bits that the mutation operator flips into 1-bits. Then, we define the change in 1-bits W_i=W_{i,+}-W_{i,-} is subject to the distribution\text{Bin}(n-X_t,\frac{\chi}{n})-\text{Bin}(X_t,\frac{\chi}{n}). After the mutation in Algorithm~\ref{alg:ocoea2}, we have \lambdaoffspring at iteration t+1: X_t^{i}=X_t+W_i. So we have} \Pr \left(E_t^c \mid F_1 \cap F_2 \right)&=\Pr \left(\max_{i \in [\lambda]}W_i<Y_t-X_t \right) \\ &= \prod_{i \in [\lambda]}\Pr \left(W_i<D_t \right) \\ &=\prod_{i \in [\lambda]} \left(1-\Pr \left(W_i \geq D_t \right) \right) \\ \intertext{ We consider the event that we only flip 0-bit in x_t. We modify the probability pessimistically by assuming we flip exactlyD_tbits in 0-bit of x_t. In particular, \Pr \left(W_i \geq D_t \right) \geq \Pr \left(W_{i,+}=D_t \right). Let D_t=Y_t-X_t. Then, we have } &\leq \left(1- \binom{n-X_t}{D_t} \left(\frac{\chi}{n} \right)^{D_t} \right.\\ & \left. \quad \quad \times \left(1-\frac{\chi}{n} \right)^{n-D_t} \right)^{\lambda} \\ \intertext{Using \binom{n-X_t}{D_t}\geq \frac{(n-X_t)^{D_t}}{D_t^{D_t}} and n-X_t \geq \varepsilon n gives} & \leq \left(1- \frac{(n-X_t)^{D_t}}{D_t^{D_t}} \left(\frac{\chi}{n} \right)^{D_t} \right. \\ &\left. \quad \quad \times \left(1-\frac{\chi}{n} \right)^{n-D_t} \right)^{\lambda} \\ &\leq \left(1- \left( \frac{\chi \varepsilon}{D_t} \right)^{D_t}\left(1-\frac{\chi}{n} \right)^{n-D_t} \right)^{\lambda} \\ \intertext{Using (1-\frac{x}{n})^n \geq e^{-x}(1-\frac{x^2}{n}) and 1-\frac{x^2}{n}\geq \frac{1}{2} for sufficiently large n gives} &\leq \left(1-\left( \frac{\chi \varepsilon}{D_t} \right)^{D_t} e^{-\chi \frac{n-D_t}{n}}\frac{1}{2}\right)^{\lambda} \\ \intertext{Recall that D_t\leq c \leq n. Thus, \frac{n-D_t}{n}\leq 1for sufficiently large n.} &\leq \left(1-\frac{\frac{1}{2}e^{-\chi}}{\left( \frac{D_t}{\varepsilon \chi}\right)^{D_t}}\right)^{\lambda} \\ \intertext{Using (1-\frac{x}{n})^n \leq e^{-x} gives} &\leq \exp \left(-\frac{1}{2e^{\chi}} \frac{\lambda}{\left( \frac{D_t}{\varepsilon \chi}\right)^{D_t}} \right) \\ \intertext{If \left(\frac{D_t}{\varepsilon \chi} \right)^{D_t} \leq \frac{\lambda}{ \ln \lambda}, this gives } &\leq \exp \left(-\frac{1}{2e^{\chi}} \frac{\lambda}{\lambda / \ln \lambda} \right) \\ &=\left(\frac{1}{\lambda} \right)^{\frac{1}{2e^{\chi}}} \end{align}\]

So we would like to check the range of \(D_t\) which satisfies \(\left(\frac{D_t}{\varepsilon \chi} \right)^{D_t} \leq \frac{\lambda}{ \ln \lambda}\). It is known that the Lambert function \(W(x)=\ln x - \ln \ln x +o(1)\) [30], [31]. We can derive \(W(x) \leq \ln (x)\), and thus we have \[\begin{align} \frac{ \ln \left(\frac{\lambda}{ \ln \lambda} \right)}{W \left(\frac{ \ln \left(\frac{\lambda}{ \ln \lambda} \right)}{\varepsilon \chi}\right)} &\geq \frac{ \ln \left(\frac{\lambda}{ \ln \lambda} \right)}{ \ln\left(\frac{ \ln \left(\frac{\lambda}{ \ln \lambda} \right)}{\varepsilon \chi}\right)} \\ &= \frac{\ln \lambda - \ln \ln \lambda}{\ln \ln \left(\frac{\lambda}{\ln \lambda} \right) +\ln (\frac{1}{\varepsilon \chi}) } \\ &= \frac{\ln \lambda - \ln \ln \lambda}{\ln \ln \lambda - \ln \ln \ln \lambda +\ln (\frac{1}{\varepsilon \chi}) } \\ &\geq c = \frac{\kappa \ln \lambda }{\ln \ln \lambda} \\ \intertext{for any constant \kappa \in (0,1).} \end{align}\] So \(D_t \leq c\) implies that \(D_t \leq \frac{ \ln \left(\frac{\lambda}{ \ln \lambda} \right)}{W \left(\frac{ \ln \left(\frac{\lambda}{ \ln \lambda} \right)}{\varepsilon \chi}\right)}\). Next, if \(D_t \leq \frac{ \ln \left(\frac{\lambda}{ \ln \lambda} \right)}{W \left(\frac{ \ln \left(\frac{\lambda}{ \ln \lambda} \right)}{\varepsilon \chi}\right)}\), then by definition of \(W\) function (\(e^{W(x)}=\frac{x}{W(x)}\)), we have

\[\begin{align} \frac{D_t}{\varepsilon \chi} &\leq \frac{\frac{ \ln \left(\frac{\lambda}{ \ln \lambda} \right)}{\varepsilon \chi}}{ W \left(\frac{ \ln \left(\frac{\lambda}{ \ln \lambda} \right)}{\varepsilon \chi}\right)} \\ &= \exp \left( W\left( \frac{ \ln \left(\frac{\lambda}{ \ln \lambda} \right)}{\varepsilon \chi} \right) \right) \\ \intertext{Taking \ln gives} \ln \left(\frac{D_t}{\varepsilon \chi} \right) & \leq W\left( \frac{ \ln \left(\frac{\lambda}{ \ln \lambda} \right)}{\varepsilon \chi} \right) \\ \intertext{Considering y\leq W(x) is the solution to the inequality ye^y\leq x and using x=\frac{ \ln \left(\frac{\lambda}{ \ln \lambda} \right)}{\varepsilon \chi}, y=\ln \left(\frac{D_t}{\varepsilon \chi} \right) give} \ln \left(\frac{D_t}{\varepsilon \chi} \right) e^{\ln \left(\frac{D_t}{\varepsilon \chi} \right)} & \leq \frac{\ln \left(\frac{\lambda}{ \ln \lambda} \right)}{\varepsilon \chi} \\ \intertext{Taking exponent on both sides and rearranging the expression give} \left(\frac{D_t}{\varepsilon \chi} \right)^{D_t} &\leq \frac{\lambda}{ \ln \lambda} . \end{align}\] Now, we combine the probability of \(E_t\) under the case that we have both \(F_1=\{\exists k \in [\lambda] , x_t^{k}=x_t\}\) and \(F_2=\{\max_{i \in [\lambda]}X_t^i >\min_{i \in [\lambda]}X_t^i \}\) hold with Lemma [lem:crossD0] to give the overall probability of \(E_t\). Using the law of total probability gives: \[\begin{align} \Pr\left(E_t^c \right) & = \Pr\left(E_t^c \mid F_1 \cap F_2 \right) \Pr \left(F_1 \cap F_2 \right) \\ & \quad +\Pr\left(E_t^c \mid F_1^c \cup F_2^c \right) \Pr \left(F_1^c \cup F_2^c \right) \\ &\leq \left(\frac{1}{\lambda} \right)^{\frac{1}{2e^{\chi}}} +\Pr \left(F_1^c \cup F_2^c \right) \\ \intertext{Using Union bound and Lemma~\ref{lem:crossD0} gives} &\leq \left(\frac{1}{\lambda} \right)^{\frac{1}{2e^{\chi}}} + 2 e^{-\Omega(\lambda)} \\ \intertext{For sufficiently large \lambda, we have 2 e^{-\Omega(\lambda)} \leq \left(\frac{1}{\lambda} \right)^{\frac{1}{2e^{\chi}}} . So, this leads to} &\leq 2\left(\frac{1}{\lambda} \right)^{\frac{1}{2e^{\chi}}} \end{align}\] 0◻ ◻

Proof of Lemma [lem:crossD2]. A similar statement works for \(\Delta Y_t^i\). In this proof, we deal with the case \(\Delta X_t^i\). We assume \(t\) is even and \(X_t<Y_t\). Statement (A) follows immediately from Lemma [lem:crossD1] because any constant \(\kappa\in(\chi,(1+\chi)/2)\subset (0,1)\) for \(\chi \in (0,1)\).

Next, we deal with the second inequality. To estimate \(K\), we use Lemma [lem:MaxPoisson]. We denote the number of \(1\)-bits that \(i\)-th offspring increases by \(U_i\) for \(i \in [\lambda]\). Lemma [lem:MaxPoisson] implies that for all \(i \in [\lambda]\), \[\begin{align} \Pr \left(U_i \geq D_t +c \right) &\leq e^{-\chi} \lambda ^{\chi}e^{-(c+D_t) \ln \ln \lambda} \\ &=e^{-\chi}\lambda^{\chi-\kappa}e^{-D_t \ln \ln \lambda}:=q_k. \end{align}\] We can consider such sampling with at least \((D_t+c)\)-jump as \(\lambda\) independent trials, and thus \(K\) is stochastic dominated by a binomial distributed random variable \(Bin(\lambda,q_K) \sim K^*\). So \[\begin{align} E[K^*]=\lambda q_K &=e^{-\chi}\lambda^{1+\chi-\kappa}e^{-D_t \ln \ln \lambda}\\ \intertext{Using D_t\leq \frac{\kappa \ln \lambda}{\ln \ln \lambda} gives} &\geq e^{-\chi} \lambda^{1+\chi -2\kappa} \end{align}\] We can apply the Chernoff’s bound to get for any \(\delta_1 \in (0,1)\), \[\begin{align} &\Pr \left(K > (1+\delta_1) E[K^*] \right) \\ \intertext{Using the definition of stochastic dominance (K^*\succcurlyeq K) gives} \leq &\Pr \left(K^* > (1+\delta_1) E[K^*] \right) \\ \intertext{Using Chernoff's bound gives} \leq& e^{-E[K^*]\delta_1^2 /3} \\ \intertext{Using the lower bound for \mathrm{E}\mathord{\left(K^*\right)} gives} \leq &e^{\frac{e^{-\chi} \lambda^{1+\chi -2\kappa}\delta_1^2}{3}}=\exp(-\lambda \Omega(1)) \end{align}\] where \(1+\chi-2\kappa>0\) directly follows from \(\kappa \in (\chi,\frac{1+\chi}{2})\).

To estimate \(M\), we note that \[\begin{align} \Pr \left( \Delta X_t^i \geq D_t\right) &\geq \binom{n-X_t}{D_t} (\frac{\chi}{n})^{D_t}(1-\frac{\chi}{n})^{n-D_t} \\ \intertext{Using \binom{n-X_t}{D_t}\geq \frac{(n-X_t)^{D_t}}{D_t^{D_t}} and n-X_t \geq \varepsilon n gives} &\geq \frac{(n-X_t)^{D_t}}{D_t^{D_t}} \left(\frac{\chi}{n} \right)^{D_t} (1-\frac{\chi}{n})^{n-D_t} \\ \intertext{Using n-X_t \geq \varepsilon n gives} &\geq \frac{(\varepsilon n)^{D_t}}{D_t^{D_t}} \left(\frac{\chi}{n} \right)^{D_t} (1-\frac{\chi}{n})^{n-D_t} \\ \intertext{Using (1-\frac{x}{n})^n \geq e^{-x}(1-\frac{x^2}{n}) and 1-\frac{x^2}{n}\geq \frac{1}{2} for sufficiently large n gives} &\geq \frac{1}{2e^{\chi}} \left(\frac{\varepsilon \chi}{D_t} \right)^{D_t}:=q_M \end{align}\] \(M\) is stochastic dominated the random variable \(M^* = Bin(\lambda, q_M)\) So we have \[\begin{align} E[M^*]&=\lambda q_M \\ \intertext{D_t \leq c implies that } &\geq \frac{1}{2e^{\chi}} \lambda \left(\frac{\varepsilon \chi}{c} \right)^c \\ \intertext{Note that c=\frac{\kappa \ln \lambda}{\ln \ln \lambda} and thus \left(\frac{\varepsilon \chi}{c} \right)^c= \frac{1}{e^{\frac{\kappa \ln \lambda}{\ln \ln \lambda}\ln \left(\frac{\kappa \ln \lambda}{\varepsilon \chi \ln \ln \lambda} \right) } } \geq \lambda^{-\kappa} . Then, we have} &\geq \frac{\lambda^{1-\kappa}}{2e^{\chi}} \end{align}\] where \(\kappa<1\) follows from \(\kappa \in (\chi,\frac{1+\chi}{2})\). By using Chernoff’s bound on \(M^*\) and \(M^*\preccurlyeq M\), we have for any \(\delta_2 \in (0,1)\), \[\begin{align} \Pr \left( M \leq (1-\delta_2) \lambda q_M \right) &\leq \Pr \left(M^* \leq (1-\delta_2) \lambda q_M \right) \\ &\leq e^{-E[M^*]\delta_2^2 /2} \\ \intertext{Using the lower bound for \mathrm{E}\mathord{\left(M^*\right)} gives} &\leq e^{-\lambda^{1-\kappa}\delta_2^2 /2e^{\chi}} \end{align}\] Now, we have for any \(\delta_1, \delta_2 \in (0,1)\), \[\begin{align} \Pr \left( K> (1+\delta_1) \lambda q_K \right) &\leq e^{\frac{e^{-\chi} \lambda^{1+\chi -2\kappa}\delta_1^2}{3}} \\ \Pr \left( M \leq (1-\delta_2) \lambda q_M \right) &\leq e^{-\lambda^{1-\kappa}\delta_2^2 /2e^{\chi}}. \end{align}\] We then use the union bound to prove that either of \(F_1=\{ K> (1+\delta_1) \lambda q_K\}\) and \(F_2=\{M \leq (1-\delta_2) \lambda q_M\}\) occurs with exponentially small probability in \(\lambda\): \[\begin{align} \Pr \left(F_1 \cup F_2 \right) \leq e^{\frac{e^{-\chi} \lambda^{1+\chi -2\kappa}\delta_1^2}{3}}+ e^{-\lambda^{1-\kappa}\delta_2^2 /2e^{\chi}}. \end{align}\] So we can prove that \[\begin{align} \Pr \left(\frac{K}{M} \leq \frac{1+\delta_1}{1-\delta_2} \frac{q_K \lambda}{q_M \lambda} \right) &\geq \Pr \left(F_1^c \cap F_2^c \right) \\ & = 1 -\Pr \left(F_1 \cup F_2 \right) \\ &\geq 1 - e^{\frac{e^{-\chi} \lambda^{1+\chi -2\kappa}\delta_1^2}{3}} \\ &\quad \quad - e^{-\lambda^{1-\kappa}\delta_2^2 /2e^{\chi}} \\ &=1-e^{-\Omega (\lambda)} \end{align}\] Finally, we want to bound the ratio \(\frac{q_K}{q_M}\) in a small quantity. Note that \[\begin{align} \frac{q_K}{q_M} &\leq \frac{e^{-\chi}\lambda^{\chi-\kappa}e^{-D_t \ln \ln \lambda}}{\frac{1}{2e^{\chi}} \left(\frac{\varepsilon \chi}{D_t} \right)^{D_t}} \\ &= 2 \lambda^{\chi-\kappa} \frac{1}{e^{D_t \ln \ln \lambda} \left(\frac{\varepsilon \chi}{D_t} \right)^{D_t}} \\ \intertext{Note that for y \in [1,c], \phi(y):=e^{y \ln \ln \lambda} \left(\frac{\varepsilon \chi}{y} \right)^{y} attains its minimum at 1 or c from extreme value theorem and the fact that \phi'(y)<0 for y \in [1,c]. So \phi(D_t) \geq \min \{\phi(1),\phi(c)\}. We can see \phi(1)=e^{\ln \ln \lambda} and \phi(c)=\lambda^{\kappa} \cdot (\frac{\varepsilon \chi}{c})^c \geq \lambda^{\kappa} \cdot \lambda^{-\kappa}=1. Then, \phi(D_t) \geq 1.} &\leq 2 \lambda^{\chi-\kappa}. \end{align}\] In overall, for any \(\chi \in (0,1)\), \(\kappa \in (\chi,\frac{\chi+1}{2}), \delta_1, \delta_2 \in (0,1)\), we derive \[\begin{align} \Pr \left(\frac{K}{M} \leq 2\frac{1+\delta_1}{1-\delta_2} \left(\frac{1}{\lambda} \right)^{\kappa -\chi} \right) \geq 1- e^{-\Omega(\lambda)}. \end{align}\] Note that \(\frac{1+\delta_1}{1-\delta_2}= 1 + \frac{\delta_1+\delta_2}{1-\delta_2}= 1+ \delta\) where \(\delta:=\frac{\delta_1+\delta_2}{1-\delta_2} >0\). The second case follows from a similar analysis and we complete the proof. 0◻ ◻

Proof of Lemma [lem:crossD3]. In this proof, we assume that \(Y_t>X_t\) and a similar analysis is applied to the case \(Y_t\leq X_t\). Let us choose \(c\) in Lemma [lem:crossD2]. For any \(\chi \in (0,1)\) and \(c\) ( \(c= \frac{\kappa \ln \lambda}{\ln \ln \lambda}\) where any constant \(\kappa \in (\chi, \frac{1+\chi}{2})\)), we have

• \(\delta_1,\delta_2 \in (0,1)\)

where \(\Delta X_t^i\) denotes the change of number of \(1\)-bit in \(i\)-th offspring of \(x_t\), and \[\begin{align} K:&=\{\text{\# of samples/offspring s.t. \Delta X_t^i \geq D_t+ c}\}\\ M:&=\{\text{\# of samples/offspring s.t. \Delta X_t^i \geq D_t}\}. \end{align}\]

Given that \(D_t \in [1,c)\), some of the offspring may escape from the lower boundary \((Y_t=X_t-c)\) of the tube, while there is only a small probability that the algorithm selects such escaping offspring. By using Lemma [lem:crossD2], we have \[\begin{align} &\Pr \left(D_{t+1}>c \mid D_t<c \right) \\ =&\Pr \left(|X_{t+1}-Y_{t+1}|>c \mid D_t<c \right) \\ \intertext{Let E=\{\lambda offspring cross the diagonal\} and we use Law of total probability} =&\Pr \left(\Delta X_t-D_t>c \mid D_t<c, E \right) \Pr (E \mid D_t<c) \\ & + \Pr \left(D_t-\Delta X_t>c \mid D_t<c, E^c\right) \Pr(E^c \mid D_t<c) \\ \intertext{Using definition of conditional probability and the condition of c from Lemma~\ref{lem:crossD2} gives} \leq & \Pr \left(\Delta X_t-D_t>c \mid D_t<c \right) \\ & + 2\Pr \left(D_t-\Delta X_t>c \mid D_t<c, E^c\right) \left(\frac{1}{\lambda} \right)^{\frac{1}{2e^{\chi}}} \\ \leq & \Pr \left(\Delta X_t>D_t+c \mid D_t<c \right) + 2\cdot \left(\frac{1}{\lambda} \right)^{\frac{1}{2e^{\chi}}} \\ \intertext{We define K:=\{\text{\# of samples/offspring s.t. \Delta X_t^i \geq D_t+c}\}, \newline M:=\{\text{\# of samples/offspring s.t. \Delta X_t^i \geq D_t}\}. The algorithm assigns the fitness 1 to M offspring in this case including those crossing outside the tube (denote their number by K). Since their fitness is the same, the next search point will be selected uniformly at random from M. Using the second condition in Lemma~\ref{lem:crossD2} the and Law of total probability again, we have for any constant \delta_1,\delta_2 \in (0,1),} \leq & \Pr \left(\Delta X_t>D_t+c \mid D_t<c, \frac{K}{M}< 2\frac{1+\delta_1}{1-\delta_2} \left(\frac{1}{\lambda} \right)^{\kappa -\chi} \right) \\ &\quad \times \Pr \left( \frac{K}{M} <2\frac{1+\delta_1}{1-\delta_2} \left(\frac{1}{\lambda} \right)^{\kappa -\chi} \right) \\ & + \Pr \left(\Delta X_t>D_t+c \mid D_t<c, \frac{K}{M}\geq 2\frac{1+\delta_1}{1-\delta_2} \left(\frac{1}{\lambda} \right)^{\kappa -\chi} \right) \\ &\quad \times \Pr \left( \frac{K}{M} \geq 2\frac{1+\delta_1}{1-\delta_2} \left(\frac{1}{\lambda} \right)^{\kappa -\chi} \right) \\ & + 2\cdot \left(\frac{1}{\lambda} \right)^{\frac{1}{2e^{\chi}}} \\ \intertext{Using (B) in Lemma~\ref{lem:crossD2} gives} \leq & 2\frac{1+\delta_1}{1-\delta_2} \left(\frac{1}{\lambda} \right)^{\kappa -\chi}\cdot 1 + \Pr \left( \frac{K}{M} \geq 2\frac{1+\delta_1}{1-\delta_2} \left(\frac{1}{\lambda} \right)^{\kappa -\chi} \right) \\ &+ 2\left(\frac{1}{\lambda} \right)^{\frac{1}{2e^{\chi}}} \\ \leq &2\frac{1+\delta_1}{1-\delta_2} \left(\frac{1}{\lambda} \right)^{\kappa -\chi}+ e^{-\Omega(\lambda)}+ 2\left(\frac{1}{\lambda} \right)^{\frac{1}{2e^{\chi}}} \\ \intertext{Taking \delta_1=\delta_2=\frac{1}{2} gives} \leq & 6 \left(\frac{1}{\lambda} \right)^{\min\{\kappa-\chi, \frac{1}{2e^{\chi}} \}}+ \left(\frac{1}{\lambda} \right)^{\min\{\kappa-\chi, \frac{1}{2e^{\chi}} \}}+ 2 \left(\frac{1}{\lambda} \right)^{\min\{\kappa-\chi, \frac{1}{2e^{\chi}} \}} \\ \intertext{Notice that \kappa \in (\chi,\frac{\chi+1}{2}) and thus \kappa-\chi \in (0,\frac{1-\chi}{2}). It is known that e^x \geq 1+x for all x\in \mathbb{R}. In our case, we derive \frac{1-\chi}{2} \leq \frac{1}{2e^\chi} for any \chi \in (0,1). Then, \min\{\kappa-\chi, \frac{1}{2e^{\chi}} \}=\kappa-\chi. Then, we derive} \leq & 9 \left(\frac{1}{\lambda} \right)^{\kappa-\chi} \\ \intertext{We introduce another variable \gamma:=\kappa-\chi and we complete the proof.} =&9 \left(\frac{1}{\lambda} \right)^{\gamma}. \end{align}\] 0◻ ◻

Proof of Lemma [lem:crossD4]. We use Lemma [lem:crossD3] can conclude that with probability at most \(9 \left(\frac{1}{\lambda} \right)^{\gamma }\) where constant \(\gamma \in (0,\frac{1-\chi}{2})\), the search point deviates from \(c\)-tube where \(c\) in Lemma [lem:crossD2]. By Lemma [lem:crossD1], the offspring crosses the diagonal with probability at least \(1-\left(\frac{1}{\lambda} \right)^{\frac{1}{2e^{\chi}}}\). So we have shown the first part and second parts directly from the fact that at each iteration, when the search point stays within the tube, either \(X_{t+1}-X_t\geq 1\) or \(Y_{t+1}-Y_t \geq 1\) with probability at least \(1-9 \left(\frac{1}{\lambda} \right)^{\gamma }-\left(\frac{1}{\lambda} \right)^{\frac{1}{2e^{\chi}}}=1-O(\frac{1}{\lambda ^\gamma})\). By taking \(\gamma:= \frac{1-\chi}{4}\) (and thus in Lemma [lem:crossD3], \(\kappa=\frac{1+3\chi}{4}\)), We conclude that either \(X_{t+1}-X_t\geq 1\) or \(Y_{t+1}-Y_t \geq 1\) with high probability i.e. with probability \(1-O(\frac{1}{\lambda ^{(1-\chi)/4}})\). Finally, by taking sufficiently large \(\lambda\) s.t. \(1-O(\frac{1}{\lambda ^{(1-\chi)/4}}) \geq \frac{1}{2}\), it yields the positive constant drift \(\frac{1}{2}\) for \(H_t\). 0◻ ◻

Proof of Theorem [thm:Main]. Assume Algorithm 3 starts from \((X_0,Y_0)=(0,0)\), \(t\) is even if \(X_t<Y_t\) and \(t\) is odd if \(X_t \geq Y_t\). We use \(H_t=2n-X_t-Y_t\) as our potential function. We define \(D_t=|X_t-Y_t|\) as the distance function away from the diagonal in \(|x|_1\)-\(|y|_1\) plane. We define \(T:=\inf \{t>0 \mid H_t \leq \delta n\}\) for any constant \(\delta \in (0,1)\). Then we want to show \(\mathrm{E}\mathord{\left(T\right)}\leq 2(2-\delta)n\). Note that \(c\) defined in Lemma [lem:crossD4] and \[\begin{align} T:&=\inf \{t>0 \mid H_t \leq \delta n\} \\ &\leq \inf \{t>0 \mid D_t<c \wedge H_t \leq \delta n\}. \\ \intertext{We replace \delta with 3\varepsilon where \varepsilon \in (0,1/3) and c=\frac{1+3\chi}{4 \ln \ln \lambda} \ln \lambda.} &= \inf \{t>0 \mid D_t<c \wedge H_t \leq 3\varepsilon n\}:= T_{c,3\varepsilon}. \end{align}\] If \(D_t <c\), without loss of generality assume \(X_t\geq Y_t\), then \(D_t <c\) implies that \(n-Y_t\geq n-X_t, X_t-Y_t<c\) and moreover \(H_t>3\varepsilon n\) implies that \(n-X_t>3\varepsilon n-n+Y_t>3\varepsilon n-n+X_t-c\). This is equivalent to \(n-X_t>\frac{3\varepsilon n-c}{2}\). Thus, if \(D_t <c\) and \(H_t>3\varepsilon n\), then \[\begin{align} n-X_t > \frac{3\varepsilon n-c}{2} &\And n-Y_t > \frac{3\varepsilon n-c}{2}. \\ \intertext{ In Lemma~\ref{lem:crossD4}, we assume c= \frac{\frac{1+3\chi}{4} \ln \lambda}{\ln \ln \lambda}=O(\ln\lambda)=o(n) where the last equality follows from the assumption in this paper \lambda=\text{poly}(n). For sufficiently large n, we have for any \varepsilon \in (0,1/3),} n-X_t > \varepsilon n &\And n-Y_t > \varepsilon n . \end{align}\] Now, we meet the conditions of Lemma [lem:crossD4]. Under this setting, by Lemma [lem:crossD4], \(\mathrm{E}_t\mathord{\left(H_{t}-H_{t+1}\right)} \geq 1/2\). By additive drift theorem [25], \[\begin{align} \mathrm{E}\mathord{\left(T\right)} \leq \mathrm{E}\mathord{\left(T_{c,3\varepsilon}\right)}\leq \frac{2n-3\varepsilon n}{1/2} = \frac{(2-3\varepsilon)n}{ 1/2} = 2(2-\delta)n. \end{align}\] Now, consider the failure event that a cycle (consecutive steps) fails to be successful at some iteration \(t\). We want to use Lemma [lem:phase1] to restart the analysis if such a failure occurs. To clarify our argument, recall from Definition 7 that a cycle is two consecutive generations of the algorithm. A cycle can be successful (see Definition 7). We call \(T_c\) such cycles a \(T_c\)-cycle phase, and we have a failure in a \(T_c\)-cycle phase if any of the \(T_c\) cycles is unsuccessful. Note that the event that a successful cycle in Definition 5 breaks is equivalent to the event that either the search point escapes from the \(c\)-tube or does not cross the diagonal during the cycle. By Lemma [lem:crossD1], the probability that the search point does not cross the diagonal is at most \(p_c = 2(\frac{1}{\lambda})^{1/2e^{\chi}}\). By Lemma [lem:crossD3], the probability that the search point lies outside the \(c\)-tube where \(c\) defined in Lemma [lem:crossD3] is at most \(p_e=9 (\frac{1}{\lambda})^{(1-\chi)/4}\). By Lemma [lem:phase1], we have \[\begin{align} &\Pr \left(\text{The algorithm has T_c consecutive successful cycles} \right) \\ \geq& 1 - 2T_c (p_c+p_e) \\ \intertext{Substituting p_c = 2(\frac{1}{\lambda})^{1/2e^{\chi}} and p_e=9 (\frac{1}{\lambda})^{(1-\chi)/4} gives} \geq & 1 -2T_c \left(2(\frac{1}{\lambda})^{1/2e^{\chi}}+ 9 (\frac{1}{\lambda})^{(1-\chi)/4} \right) \\ \intertext{Recall that e^{-\chi} \geq \frac{1-\chi}{2} \geq \frac{1-\chi}{4} for \chi \in (0,1). Then, we have} \geq & 1 - 2T_c \cdot 11 (\frac{1}{\lambda})^{(1-\chi)/4} \\ \intertext{Picking T_c=4(2-\delta)n and \lambda \geq (264(2-\delta)n)^{4/(1-\chi)} gives} \geq & 1- 4(2-\delta)n \cdot 22 \cdot \frac{1}{264(2-\delta)n} = \frac{2}{3}. \end{align}\] This means that the algorithm has \(4(2-\delta)n\) successful consecutive cycles with probability at least \(\frac{2}{3}\). If the algorithm fails to have such a successful consecutive cycles, then we restart the algorithm. In a successful phase, the algorithm finds a \(\delta\)-approximation in expected time \(2(2-\delta)n\) generations. By Markov’s inequality, within \(4(2-\delta)n\) generations with probability at least \(1/2\) (otherwise we consider this a failure). By taking a union bound on the failure events (i.e. an unsuccessful \(T_c\)-cycle phase or the algorithm does not find the \(\delta\)-approximation within the end of the phase, the algorithm finds the \(\delta\)-approximation in a phase of length \(T_c\) cycles with probability \(p \geq 1-1/3-1/2=1/6\). Hence, we multiply a factor of \(6\) to obtain the overall expected runtime is at most \(4 (2-\delta)n/p \leq 24(2-\delta)n\).

Notice that we only compute the number of generations so far. To obtain the algorithm’s runtime (number of function evaluations), we need to multiply \(\lambda\) for each iteration. So we end up with the expected runtime of Algorithm 3 is \(4 \lambda (2-\delta)n\) for \(\lambda = \Omega(n^{\frac{4}{1-\chi}})\). 0◻ ◻