MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Cooper, Joshua
Doerr, Benjamin
Spencer, Joel
Tardos, Gábor		dblp
dblp
dblp
dblp
Not MPG Author(s):
Cooper, Joshua
Spencer, Joel
Tardos, Gábor
Editor(s):
Raman, Rajeev
Sedgewick, Robert
Stallmann, Matthias F.		dblp
dblp
dblp
Not MPII Editor(s):
Raman, Rajeev
Sedgewick, Robert
Stallmann, Matthias F.
BibTeX cite key*:
DoerrANALCO06
Title, Booktitle
Title*:
Deterministic Random Walks
Booktitle*:
Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments and the Third Workshop on Analytic Algorithmics and Combinatorics (ALENEX'06 / ANALCO'06)
Event, URLs
Conference URL::
Downloading URL:
http://www.siam.org/meetings/analco06/proceedings06/017jcooper.pdf
Event Address*:
Miami, FL, USA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
9 March 2007
Event End Date:
9 March 2007
Publisher
Name*:
SIAM
URL:
Address*:
Philadelphia, PA, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
185-197
Year*:
2006
VG Wort Pages:
23
ISBN/ISSN:
0898716101
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Jim Propp’s P-machine, also known as ‘rotor router model’ is a simple deterministic process that simulates random walk on a graph. Instead of distributing chips
to randomly chosen neighbors, it serves the neighbors in a fixed order.
We investigate how well this process simulates a random walk. For the graph being the infinite path, we show that, independent of the starting configuration, at each time and on each vertex, the number of chips on this vertex deviates from the expected number of chips in the random walk model by at most a constant c1, which is approximately 2.29. For intervals of length L, this improves to a difference of O(log L) (instead of 2.29L), for the L2 average of a contiguous set of intervals even to O(√log L). It seems plausible that similar results hold for higher-dimensional grids Zd instead of the path Z.
HyperLinks / References / URLs:
http://www.siam.org/meetings/analco06/proceedings06/proceedings06.php
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{DoerrANALCO06,
AUTHOR = {Cooper, Joshua and Doerr, Benjamin and Spencer, Joel and Tardos, G{\'a}bor},
 EDITOR = {Raman, Rajeev and Sedgewick, Robert and Stallmann, Matthias F.},
 TITLE = {Deterministic Random Walks},
 BOOKTITLE = {Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments and the Third Workshop on Analytic Algorithmics and Combinatorics (ALENEX'06 / ANALCO'06)},
 PUBLISHER = {SIAM},
 YEAR = {2006},
 PAGES = {185--197},
 ADDRESS = {Miami, FL, USA},
 ISBN = {0898716101},
}

Entry last modified by Christine Kiesel, 05/02/2007
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Mathias Bader		Created
03/09/2007 11:54:51
Revisions
5.
4.
3.
2.
1.		Editor(s)
Christine Kiesel
Uwe Brahm
Mathias Bader
Christine Kiesel
Christine Kiesel		Edit Dates
02.05.2007 18:09:09
2007-04-26 18:52:02
13.03.2007 11:21:25
12.03.2007 13:37:55
12.03.2007 13:36:19