Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
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

BibTeX cite key*:

CDoerrST2007

Title

Title*:

Deterministic random walks on the integers

Journal

Journal Title*:

European Journal of Combinatorics
Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Elsevier
Publisher's URL:


Publisher's
Address:

Amsterdam, The Netherlands
ISSN:

0195-6698

Vol, No, pp, Date

Volume*:

28
Number:

8

Publishing Date:

2007

Pages*:

2072-2090
Number of
VG Pages:


Page Start:

2072
Page End:

2090

Sequence Number:


DOI:

10.1016/j.ejc.2007.04.018

Note, Abstract, ©

Note:


(LaTeX) Abstract:

Jim Propp’s P-machine, also known as the ‘rotor router model’, is a simple deterministic process that simulates a 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(logL), for the L2 average of a contiguous set of intervals even to . All these bounds are tight.

URL for the Abstract:

http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WDY-4NKXWD5-1&_user=43521&_coverDate=04%2F29%2F2007&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000004638&_version=1&_urlVersion=0&_userid=43521&md5=77c591d5c071a241639d1586f96b4b11

Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

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:

@ARTICLE{CDoerrST2007,
AUTHOR = {Cooper, Joshua and Doerr, Benjamin and Spencer, Joel and Tardos, G{\'a}bor},
 TITLE = {Deterministic random walks on the integers},
 JOURNAL = {European Journal of Combinatorics},
 PUBLISHER = {Elsevier},
 YEAR = {2007},
 NUMBER = {8},
 VOLUME = {28},
 PAGES = {2072--2090},
 ADDRESS = {Amsterdam, The Netherlands},
 ISBN = {0195-6698},
 DOI = {10.1016/j.ejc.2007.04.018},
}

Entry last modified by Anja Becker, 02/28/2008
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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)
Christine Kiesel		Created
06/26/2007 13:49:06
Revisions
4.
3.
2.
1.
0.		Editor(s)
Anja Becker
Anja Becker
Benjamin Doerr
Uwe Brahm
Uwe Brahm		Edit Dates
22.02.2008 11:42:22
08.02.2008 13:43:30
01/19/2008 06:50:45 PM
2007-07-18 14:40:23
26.06.2007 14:19:00