  Sourav Chatterjee, Persi Diaconis, Allan Sly and Lingfu Zhang, prompted by a
question of Ramis Movassagh, renewed the study of a process proposed in the
early 1980s by Jean Bourgain. A state vector $v \in \mathbb R^n$, labeled with
the vertices of a connected graph, $G$, changes in discrete time steps
following the simple rule that at each step a random edge $(i,j)$ is picked and
$v_i$ and $v_j$ are both replaced by their average $(v_i+v_j)/2$. It is easy to
see that the value associated with each vertex converges to $1/n$. The question
was how quickly will $v$ be $\epsilon$-close to uniform in the $L^{1}$ norm in
the case of the complete graph, $K_{n}$, when $v$ is initialized as a standard
basis vector that takes the value 1 on one coordinate, and zeros everywhere
else. They have established a sharp cutoff of $\frac{1}{2\log 2}n\log n +
O(n\sqrt{\log n})$. Our main result is to prove, that
$\frac{(1-\epsilon)}{2\log2}n\log n-O(n)$ is a general lower bound for all
connected graphs on $n$ nodes. We also get sharp magnitude of $t_{\epsilon,1}$
for several important families of graphs, including star, expander, dumbbell,
and cycle. In order to establish our results we make several observations about
the process, such as the worst case initialization is always a standard basis
vector. Our results add to the body of work of Aldous, Aldous and Lanoue,
Quattropani and Sau, Cao, Olshevsky and Tsitsiklis, and others. The renewed
interest is due to an analogy to a question related to the Google's supremacy
circuit. For the proof of our main theorem we employ a concept that we call
'augmented entropy function' which may find independent interest in the
computer science and probability theory communities.
