MEETING TIMES OF RANDOM WALKS ON GRAPHS
Date
1994-02-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We derive techniques for proving exact values or bounds on the
meeting time. These techniques are used to prove two upper bounds
on the meeting time of an arbitrary number of random walks in any
connected undirected graph. Both bounds express the meeting time
of several random walks in terms of the meeting times of fewer
random walks. One of the bounds is tight on rings, the other is a
generalization of a bound suggested by Tetali and Winkler. The
techniques yield exact expressions for the meeting times on rings and for
two or three random walks in hitting-time-symmetric graphs. Additional
results include case study of various meeting time games on rings,
several counterexamples to "natural" conjectures concerning meeting
times, and partial characterization of hitting-time-symmetric graphs.
Description
Keywords
Computer Science