%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 }