A token located at some vertex v of a connected, undirected graph G on n vertices is said to be
taking a "random walk" on G if, whenever it is instructed to move, it moves with equal probability to any of
the neighbors of v. The authors consider the following problem: Suppose that two tokens are placed on G, and
at each tick of the clock a certain demon decides which of them is to make the next move. The demon is trying
to keep the tokens apart as long as possible. What is the expected time M before they meet?
The problem arises in the study of self-stabilizing systems, a topic of recent interest in distributed computing.
Since previous upper bounds for M were exponential in n, the issue was to obtain a polynomial bound.
The authors use a novel potential function argument to show that in the worst case $M = (4/27+o(1))n^3$.
%0 Journal Article
%1 coppersmith1993collisions
%A Coppersmith, Don
%A Tetali, Prasad
%A Winkler, Peter
%D 1993
%I Society for Industrial & Applied Mathematics (SIAM)
%J SIAM J. Discrete Math.
%K bounds coalescent_time hitting_time meeting_time potential_theory random_walks_on_graphs
%N 3
%P 363--374
%R 10.1137/0406029
%T Collisions Among Random Walks on a Graph
%U http://dx.doi.org/10.1137/0406029
%V 6
%X A token located at some vertex v of a connected, undirected graph G on n vertices is said to be
taking a "random walk" on G if, whenever it is instructed to move, it moves with equal probability to any of
the neighbors of v. The authors consider the following problem: Suppose that two tokens are placed on G, and
at each tick of the clock a certain demon decides which of them is to make the next move. The demon is trying
to keep the tokens apart as long as possible. What is the expected time M before they meet?
The problem arises in the study of self-stabilizing systems, a topic of recent interest in distributed computing.
Since previous upper bounds for M were exponential in n, the issue was to obtain a polynomial bound.
The authors use a novel potential function argument to show that in the worst case $M = (4/27+o(1))n^3$.
@article{coppersmith1993collisions,
abstract = {A token located at some vertex v of a connected, undirected graph G on n vertices is said to be
taking a "random walk" on G if, whenever it is instructed to move, it moves with equal probability to any of
the neighbors of v. The authors consider the following problem: Suppose that two tokens are placed on G, and
at each tick of the clock a certain demon decides which of them is to make the next move. The demon is trying
to keep the tokens apart as long as possible. What is the expected time M before they meet?
The problem arises in the study of self-stabilizing systems, a topic of recent interest in distributed computing.
Since previous upper bounds for M were exponential in n, the issue was to obtain a polynomial bound.
The authors use a novel potential function argument to show that in the worst case $M = (4/27+o(1))n^3$.},
added-at = {2016-03-15T23:42:20.000+0100},
author = {Coppersmith, Don and Tetali, Prasad and Winkler, Peter},
biburl = {https://www.bibsonomy.org/bibtex/20c00d8aa7d375a8e8590bbda3a747a44/peter.ralph},
doi = {10.1137/0406029},
interhash = {64459609c6b97740d8ee207bd118219a},
intrahash = {0c00d8aa7d375a8e8590bbda3a747a44},
journal = {{SIAM} J. Discrete Math.},
keywords = {bounds coalescent_time hitting_time meeting_time potential_theory random_walks_on_graphs},
month = aug,
number = 3,
pages = {363--374},
publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})},
timestamp = {2016-03-15T23:42:20.000+0100},
title = {Collisions Among Random Walks on a Graph},
url = {http://dx.doi.org/10.1137/0406029},
volume = 6,
year = 1993
}