{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:46:35Z","timestamp":1787319995222,"version":"build-2736575974"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Random walks are frequently used in randomized algorithms. We study a derandomized variant of a random walk on graphs called the rotor-router model. In this model, instead of distributing tokens randomly, each vertex serves its neighbors in a fixed deterministic order. For most setups, both processes behave in a remarkably similar way: Starting with the same initial configuration, the number of tokens in the rotor-router model deviates only slightly from the expected number of tokens on the corresponding vertex in the random walk model. The maximal difference over all vertices and all times is called single vertex discrepancy. Cooper and Spencer [ Combin. Probab. Comput., 15 (2006), pp. 815--822] showed that on $\\mathbb{Z}^d$, the single vertex discrepancy is only a constant $c_d$. Other authors also determined the precise value of $c_d$ for $d=1,2$. All of these results, however, assume that initially all tokens are only placed on one partition of the bipartite graph $\\mathbb{Z}^d$. We show that this assumption is crucial by proving that, otherwise, the single vertex discrepancy can become arbitrarily large. For all dimensions $d\\geqslant1$ and arbitrary discrepancies $\\ell\\geqslant0$, we construct configurations that reach a discrepancy of at least $\\ell$.<\/jats:p>","DOI":"10.1137\/17m1131088","type":"journal-article","created":{"date-parts":[[2018,10,18]],"date-time":"2018-10-18T11:15:27Z","timestamp":1539861327000},"page":"2441-2452","source":"Crossref","is-referenced-by-count":0,"title":["Unbounded Discrepancy of Deterministic Random Walks on Grids"],"prefix":"10.1137","volume":"32","author":[{"given":"Tobias","family":"Friedrich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maximilian","family":"Katzmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anton","family":"Krohmer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,10,18]]},"reference":[{"key":"atypb1","first-page":"218","author":"Aleliunas R.","year":"1979","journal-title":"New York"},{"key":"atypb2","first-page":"423","author":"Bampas E.","year":"2009","journal-title":"Heidelberg"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(97)00015-X"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20314"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.04.018"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007565"},{"key":"atypb7","unstructured":"D. Dereniowski, A. Kosowski, D. Paja\u0327k, and P. Uzna\u0144ski,\n                      Bounds on the cover time of parallel rotor walks\n                      , in Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science, 2014, pp. 263-275."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009589"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/2650185"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102408341"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/100799216"},{"key":"atypb13","first-page":"212","author":"Friedrich T.","year":"2015","journal-title":"Japan"},{"key":"atypb14","doi-asserted-by":"crossref","first-page":"167","DOI":"10.37236\/439","volume":"17","author":"Friedrich T.","year":"2010","journal-title":"Electron. J. Combin."},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"S. Kijima, K. Koga, and K. Makino,\n                      Deterministic random walks on finite graphs\n                      , in 9th Meeting on Analytic Algorithmics and Combinatorics, 2012, pp. 16-25.","DOI":"10.1137\/1.9781611973020.3"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"R. Klasing, A. Kosowski, D. Paja\u0327k, and T. Sauerwald,\n                      The multi-agent rotor-router on the ring: A deterministic alternative to parallel random walks\n                      , in Proceedings of the 32nd ACM Symposium on Principles of Distributed Computing, 2013, pp. 365-374.","DOI":"10.1145\/2484239.2484260"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF02984814"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"A. Kosowski and D. Paja\u0327k,\n                      Does adding more agents make a difference? A case study of cover time for the rotor-router\n                      , in 41st International Colloquium on Automata, Languages, and Programming, 2014, pp. 544-555.","DOI":"10.1007\/978-3-662-43951-7_46"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"G. Lawler and V. Limic,\n                      Random Walk: A Modern Introduction\n                      , Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 2010.","DOI":"10.1017\/CBO9780511750854"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"T. Nipkow, L. C. Paulson, and M. Wenzel,\n                      Isabelle\/HOL: A Proof Assistant for Higher-Order Logic\n                      , Lecture Notes in Comput. Sci. 2283, Springer-Verlag, Berlin, Heidelberg, 2002.","DOI":"10.1007\/3-540-45949-9"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.77.5079"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.2307\/2308012"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/70.795795"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1030-9"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1131088","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:53:43Z","timestamp":1787316823000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1131088"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1131088"],"URL":"https:\/\/doi.org\/10.1137\/17m1131088","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}