$A$ are nonnegative, and because the choice $(i^*, j^*) \in \E(A)$ implies that $a_{j^* i^*} \geq{\eta}$.]{} Consequently, $$\sum_{j \in S^{+}} w_{i^* j} \geq \eta \sum_{j \in
S^{+}} a_{j^*j} = \eta\, C_{j^*}^{+}. \label{wlowerbound2}$$ [Combining Eqs. (\[wsubset2\]) and]{} (\[wlowerbound2\]), and recalling [the assumption]{} $C_{j^*}^+ \geq
1/2$, the [result]{} follows. An illustration of this argument can be found in Figure \[cdef\][(c)]{}.

A Bound on Convergence Time {#convergtime}
---------------------------

With the preliminaries on doubly stochastic matrices in place, we [can now proceed to derive]{} bounds on the decrease of $V(x(k))$ in between iterations. We will first somewhat relax our connectivity assumptions. In particular, we consider the following relaxation of Assumption \[connectivity\].

\[weakconnect\] Given an integer $k\ge 0$, suppose that the components of $x(kB)$ have been reordered so that they are in nonincreasing order. We assume that for every $d\in\{1,\ldots,n-1\}$, we either have $x_d(kB)=x_{d+1}(kB)$, or there exist some time $t\in\{kB,\ldots,(k+1)B-1\}$ and some $i\in\{1,\ldots,d\}$, $j\in\{d+1,\ldots,n\}$ such that $(i,j)$ or $(j,i)$ belongs to $\E(A(t))$.

\[as2implas3\] Assumption \[connectivity\] implies Assumption \[weakconnect\], [with the same value of $B$.]{}

If Assumption \[weakconnect\] does not hold, then $$\Big(N,\E({A}(kB)) \bigcup \E(A(kB+1)){\bigcup} \cdots \bigcup
\E(A((k+1)B-1))\Big)$$ is disconnected, which violates Assumption 2.

For our convergence time results, we will use the weaker Assumption \[weakconnect\], 