$x=y$.

-   There is exactly one index $i\in I$ such that $y_i=0$ and $f(y)\le f(x)$ holds.

-   There are at least two different indices $j,\ell\in I$ such that $y_j=0$ and $y_\ell=0$ and $f(y)\le f(x)$ holds.

The only possibility for the event ($C_1$) to hold is if $x=y$. Therefore, $$\label{eq:casea}
{\ensuremath{\operatorname{E}}}[g(x)-g(y)\mid (C_1)]=0.$$

Next, suppose the event ($C_3$) holds. By linearity of expectation, we have $${\ensuremath{\operatorname{E}}}[g(x)-g(y)\mid (C_3)]=\sum_{i=1}^n
{\ensuremath{\operatorname{E}}}[g(x_i)-g(y_i)\mid (C_3)].$$

On the one hand, the event ($C_3$) implies that there are (at least) two indices $j$ and $\ell$ in $\{1,\dots,n\}$ for which $x_j=x_\ell=1$ and $y_j=y_\ell=1$. Since $g_j\ge 1$ and $g_\ell\ge 1$, we have $$\sum_{i\in I}{\ensuremath{\operatorname{E}}}[g(x_i)-g(y_i)\mid (C_3)]\ge 2.$$

On the other hand, if $i\in\{1,\dots,n\}\setminus I$ then $${\ensuremath{\operatorname{E}}}[g(x_i)-g(y_i)\mid (C_3)]=-g_i{\ensuremath{\mathrm{Pr}}}[y_1=0\mid(C_3)]\ge -\frac{g_i}{n},$$ since the condition ($C_3$) does not increase the probability of $1/n$ that the $y_i=0$. Therefore, since the $g_i$’s are at most two, we have $$\label{eq:casec}
{\ensuremath{\operatorname{E}}}[g(x)-g(y)\mid (C_3)]\ge 2-\frac{1}{n}\sum_{i\notin I}g_i\ge 0.$$

Therefore, by the law of total expectation and by (\[eq:accepted\]), (\[eq:casea\]) and (\[eq:casec\]), we have $$\label{eq:exactone}
{\ensuremath{\operatorname{E}}}[\Delta(x)]\ge{\ensuremath{\operatorname{E}}}[g(x)-g(y)\mid (C_2)]\,{\ensuremath{\mathrm{Pr}}}[(C_2)]$$ and can focus on the event ($C_2$).

Suppose that ($C_2$) holds. For every $i\in I$, we distinguish two events:

-   The $i$-th bit is the only one-bit in $x$ that flips, none of the zero-bits at the 