\frac{1}{n} \sum_{j=1}^n
x_j(0).$$

This is a minor modification of known results in [@T84; @TBA86; @JLM03; @BHOT05], where the convergence of each $x_i(k)$ to the same value is established under weaker versions of Assumptions \[weights\] and \[connectivity\]. The fact that the limit is the average of the entries of the vector $x(0)$ follows from the fact that multiplication of a vector by a doubly stochastic matrix preserves the average of the vector’s components.

Recent research has focused on methods of choosing weights $a_{ij}(k)$ that satisfy Assumptions \[weights\] and \[connectivity\], and minimize the convergence time of the resulting averaging algorithm (see [@XB04] for the case of static graphs, see [@OSM04] and [@BFT05] for the case of symmetric weights, i.e., weights satisfying $a_{ij}(k)=a_{ji}(k)$, and also see [@C06; @boyd]). For static graphs, some recent results on optimal time-invariant algorithms may be found in [@OT06].

Convergence time \[convtimesection\]
====================================

In this section, we give an analysis of the convergence time of averaging algorithms of the form (\[noquant\]). Our goal is to obtain tight estimates of the convergence time, under Assumptions \[weights\] and \[connectivity\].

As a convergence measure, we use the “sample variance” of a vector $x \in \R^n$, defined as $$V(x) = \sum_{i=1}^n (x_i - 