\bar{x} )^2,$$ where $\bar{x}$ is the average of the entries of $x$: $$\bar{x} = \frac{1}{n} \sum_{i=1}^n x_i.$$

Let $x(k)$ denote the vector of node values at time $k$ \[i.e., the vector of iterates generated by algorithm (\[noquant\]) at time $k$\]. We are interested in providing an upper bound on the number of iterations it takes for the “sample variance” $V(x(k))$ to decrease to a small fraction of its initial value $V(x(0))$. We first establish some technical preliminaries that will be key in the subsequent analysis. In particular, in the next subsection, we explore several implications of the double stochasticity assumption on the weight matrix $A(k)$.

Preliminaries on Doubly Stochastic Matrices
-------------------------------------------

We begin by analyzing how the sample variance $V(x)$ changes when the vector $x$ is multiplied by a doubly stochastic matrix $A$. The next lemma shows that $V(Ax) \leq V(x)$. Thus, under Assumption \[weights\], the sample variance $V(x(k))$ is nonincreasing in $k$, and $V(x(k))$ can be used as a Lyapunov function.

\[vl\] Let $A$ be a doubly stochastic matrix. Then,[^5] for all $x \in \R^n$, $$V(Ax) = V(x) - \sum_{i<j} w_{ij} (x_i - x_j)^2,$$ where $w_{ij}$ is the $(i,j)$-th entry of the matrix $A^T A$.

Let ${\bf 1}$ denote 