is only missing those $d$ for which $y_d=y_{d+1}$.

We next establish a bound on [the]{} variance decrease that plays [a]{} key role in our convergence analysis.

\[lboundvar\] Let Assumptions \[weights\] and \[weakconnect\] hold, and suppose that $V(kB)>0$. Then, $$\frac{V(kB)-V((k+1)B)}{V(kB)} \geq \frac{\eta}{2 n^2}\qquad
\hbox{for all }k.$$

[Without loss of generality, we assume that the components of $x(kB)$ have been sorted in nonincreasing order.]{} By Lemma \[vardiff\], we have $$V(kB) -
V((k+1)B) \geq \frac{\eta}{2}\, \sum_{i=1}^{n-1} (x_{i}(kB) -
x_{i+1}(kB))^2.$$ This implies that $$\frac{V(kB)-V((k+1)B)}{V(kB)}\ge\frac{\eta}{2} \,
\frac{\sum_{i=1}^{n-1} (x_{i}(kB) - x_{i+1}(kB))^2}{\sum_{i=1}^n
(x_i(kB)-\bar{x}(kB))^2}.$$ Observe that the right-hand side does not change when we add a constant to every $x_i(kB)$. We can therefore assume, without loss of generality, that $\bar{x}(kB)=0$, [so that]{} $$\frac{V(kB)-V((k+1)B)}{V(kB)} \geq \frac{\eta}{2}\,
\min_{{x_1\ge x_2\ge \cdots\ge x_n \atop \sum_i x_i=0}}
\frac{\sum_{i=1}^{n-1} (x_{i} - x_{i+1})^2}{\sum_{i=1}^n x_i^2}.$$ Note that the right-hand side is unchanged if we multiply each $x_i$ by the same constant. Therefore, we can assume, without loss of generality, that $\sum_{i=1}^n x_i^2=1$, [so that]{} $$\label{eq:vv}
\frac{V(kB)-V((k+1)B)}{V(kB)} \geq \frac{\eta}{2}\, \min_{{x_1\ge
x_2\ge \cdots\ge x_n  \atop \sum_i x_i=0, \ \sum_i x_i^2 = 1}}
~~\sum_{i=1}^{n-1} (x_{i} - x_{i+1})^2.$$ The requirement $\sum_i x_i^2 = 1$ implies that the average value of $x_i^2$ is $1/n$, which implies that there exists some $j$ 