$x^{(0)}\in\{0,1\}^n$ uniformly at random

In this section, we analyze the (1+1) Evolutionary Algorithm ((1+1) EA) for pseudo-Boolean functions (Algorithm \[alg:oneoneea\]). This algorithm follows the neighborhood structure imposed by the hypercube on $\{0,1\}^n$ where two points are adjacent if they differ by exactly one bit, that is, if their Hamming distance is one. The (1+1) EA successively attempts to improve the so-far best search point by randomly sampling candidates over $\{0,1\}^n$ according to probabilities decreasing with the distance to the current optimum.

The *optimization time* of the (1+1) EA on a function $f$ is the random variable $T$ that denotes the first point in time $t\in\mathbb{N}$ such that $f(x^{(t)})$ is minimal.

One elementary linear pseudo-Boolean function for which the optimization time (1+1) EA has been analyzed (e.g., in [@Muehlenbein1992] and [@DrosteJW02]) is the function ${\textsc{OneMax}\xspace}\colon\{0,1\}^n\to\mathbb{N}$. This function simply counts the number of one-bits in $x$, that is, $$\label{eq:onemax}
{\textsc{OneMax}\xspace}(x):=|x|_1=\sum_{i=1}^n x_i.$$ Unlike indicated by the name of this function, we are interested in the time the (1+1) EA needs to find its minimum. Thus, in the selection step (Step 4) of each iteration, the (1+1) EA accepts the candidate solution $y^{(t)}$ if and only if the number of bits equal to $1$ 