Assumption \[connectivity\] implies Assumption \[weakconnect\]. In view of this, the convergence time bound of Theorem \[uqbound\] holds for any $n$ and any sequence of weights satisfying Assumptions \[weights\] and \[connectivity\]. In the next subsection, we show that this bound is tight when the stronger Assumption \[connectivity\] holds.

Tightness
---------

The next shows that the convergence time bound of Theorem \[uqbound\] is tight under Assumption \[connectivity\].

\[unquanttight\] [There exist constants $c$ and $n_0$ with the following property. For any $n\geq n_0$,]{} nonnegative integer $B$, $\eta < 1/2$, and $\epsilon < 1$, there exist a sequence of weight matrices $A(k)$ satisfying Assumptions \[weights\] and \[connectivity\], and an initial value $x(0)$ such that [if]{} $V(k)/V(0) \leq \epsilon$, [then]{} $$k \geq {c}\, \frac{n^2}{\eta}\, B \log \frac{1}{\epsilon}.$$

Let $P$ be the circulant shift operator defined by $P e_i = e_{i+1}$, $P e_n = e_1$, where $e_i$ is a unit vector with the $i$-th entry equal to 1, and all other entries equal to 0. Consider the symmetric circulant matrix defined by $$A = (1 - 2 \eta) I + \eta P + \eta P^{-1}.$$ Let $A({k})=A$, when ${k}$ is a multiple of $B$, and $A({k})=I$ otherwise. Note that this sequence satisfies Assumptions 1 and 2.

