positions larger than $i$ flips, and $f(y)\le f(x)$ holds.

-   The $i$-th bit is the only one-bit in $x$ that flips, at least one of the zero-bits at the positions larger than $i$ that flips, and $f(y)\le f(x)$ holds.

We substitute the right side in (\[eq:exactone\]) and obtain $$\label{eq:ab}
{\ensuremath{\operatorname{E}}}[\Delta(x)]\ge\sum_{i\in I}{\ensuremath{\operatorname{E}}}[\Delta(x)\mid (A_i)]\,{\ensuremath{\mathrm{Pr}}}[(A_i)]+{\ensuremath{\operatorname{E}}}[\Delta(x)\mid (B_i)]\,{\ensuremath{\mathrm{Pr}}}[(B_i)]$$

Let $i\in I$ and suppose that the condition $(A_i)$ holds. Then we have $y_i=0$ and $y_j=x_j$ for all $j>i$. For a lower bound on ${\ensuremath{\operatorname{E}}}[\Delta(x)\mid (A_i)]$, we may suppose that $x_j=0$ for all $j<i$ and that every flip of a bit with index $j<i$ is accepted. Therefore, since $i\le n$ $${\ensuremath{\operatorname{E}}}[\Delta(x)\mid (A_i)]\ge 1+\frac{i}{n}-\sum_{j=1}^{i-1}\frac{1}{n}\Big(1+\frac{j}{n}\Big)=1+\frac{1}{n}-\frac{i(i-1)}{2n^2}\ge 1-\frac{i-3}{2n}.$$ and thus ${\ensuremath{\operatorname{E}}}[\Delta(x)\mid (A_i)]$ is positive. Furthermore, ${\ensuremath{\mathrm{Pr}}}[(A_i)]\ge\frac{1}{n}\big(1-\frac{1}{n}\big)^{n-1}$ which is the probability that only the $i$-th bit flips. Hence, $$\label{eq:ai}
{\ensuremath{\operatorname{E}}}[\Delta(x)\mid (A_i)]\,{\ensuremath{\mathrm{Pr}}}[(A_i)]\ge \frac{1}{n}\Big(1-\frac{1}{n}\Big)^{n-1}\Big(1-\frac{i-3}{2n}\Big).$$

Next, suppose that condition $(B_i)$ holds. Then we have $y_i=0$ and $y_\ell=1$ for all $\ell\in I\setminus\{i\}$, and there exists a $j>i$ with $j\notin I$ such that $y_j=1$. In order to satisfy $f(y)\le f(x)$, $w_j=w_i$ has to hold. This implies $x_\ell=y_\ell$ for all $\ell\in\{1,\dots,n\}\setminus\{i,j\}$. To see this, recall that the $w_i$’s are monotone and we condition on the event that the $i$-th bit is the only bit that flips from one 