{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:43:05Z","timestamp":1787323385939,"version":"build-2736575974"},"reference-count":47,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["15J03840"],"award-info":[{"award-number":["15J03840"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["15K15938"],"award-info":[{"award-number":["15K15938"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["25700002"],"award-info":[{"award-number":["25700002"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["15H02666"],"award-info":[{"award-number":["15H02666"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["17H07116"],"award-info":[{"award-number":["17H07116"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>The rotor-router model is a deterministic process analogous to a simple random walk on a graph, and the discrepancy of token configurations between the rotor-router model and its corresponding random walk has been investigated in some contexts. Motivated by general Markov chains beyond simple random walks, this paper investigates a generalized model which imitates a Markov chain (of multiple tokens) possibly containing irrational transition probabilities. We are concerned with the vertexwise discrepancy of the numbers of tokens between the generalized model and its corresponding Markov chain, and present an upper bound of the discrepancy in terms of the mixing time of the Markov chain.<\/jats:p>","DOI":"10.1137\/16m1087667","type":"journal-article","created":{"date-parts":[[2018,8,30]],"date-time":"2018-08-30T14:19:16Z","timestamp":1535638756000},"page":"2180-2193","source":"Crossref","is-referenced-by-count":4,"title":["Deterministic Random Walks for Rapidly Mixing Chains"],"prefix":"10.1137","volume":"32","author":[{"given":"Takeharu","family":"Shiraga","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yukiko","family":"Yamauchi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shuji","family":"Kijima","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Masafumi","family":"Yamashita","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,30]]},"reference":[{"key":"atypb1","first-page":"186","author":"Akbari H.","year":"2013","journal-title":"New York"},{"key":"atypb3","unstructured":"O. Angel, A. E. Holroyd, J. Martin, and J. Propp,\n                      Discrete Low Discrepancy Sequences\n                      ,https:\/\/arxiv.org\/abs\/0910.1077(2010)."},{"key":"atypb4","doi-asserted-by":"crossref","first-page":"R102","DOI":"10.37236\/191","volume":"16","author":"Angelopoulos S.","year":"2009","journal-title":"Electron. J. Combin."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00333-1"},{"key":"atypb6","first-page":"423","volume":"2009","author":"Bampas E.","year":"2009","journal-title":"Proceedings DISC"},{"key":"atypb7","first-page":"301","volume":"2015","author":"Berenbrink P.","year":"2012","journal-title":"Proceedings PODC"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20314"},{"key":"atypb9","first-page":"123","volume":"2015","author":"Chalopin J.","year":"2015","journal-title":"Proceedings DISC"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.04.018"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007565"},{"key":"atypb12","first-page":"99","author":"Doerr B.","year":"2009","journal-title":"Berlin"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009589"},{"key":"atypb14","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/1963190.2025379","volume":"16","author":"Doerr B.","year":"2011","journal-title":"ACM J. Exp. Algorithmics"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1145\/2650185"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2009.07.040"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.10.014"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/100799216"},{"key":"atypb19","doi-asserted-by":"crossref","first-page":"R167","DOI":"10.37236\/439","volume":"17","author":"Friedrich T.","year":"2010","journal-title":"Electron. J. Combin."},{"key":"atypb20","first-page":"105","author":"Holroyd A. E.","year":"2010","journal-title":"RI"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2009.07.092"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.10.020"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-2011-00716-9"},{"key":"atypb24","unstructured":"M. Jerrum and A. Sinclair,\n                      The Markov chain Monte Carlo method: An approach to approximate counting and integration\n                      , in Approximation Algorithms for NP-Hard Problems, D.S. Hochbaum ed., PWS Publishing, Boston, 1996, Chap. 12."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20533"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/06064980X"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"A. Kosowski and D. Pajak,\n                      Does adding more agents make a difference? A case study of cover time for the rotor-router\n                      , in Proceedings of the 41st International Colloquium on Automata, Languages and Programming, (ICALP 2014), Springer, Heidelberg, pp. 544-555.","DOI":"10.1007\/978-3-662-43951-7_46"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/BF02984814"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989542"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/BF02985833"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1512\/iumj.2008.57.3022"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/s11118-008-9104-6"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"D. A. Levine, Y. Peres, and E. L. Wilmer,\n                      Markov Chain and Mixing Times\n                      , AMS, Providence, RI, 2008.","DOI":"10.1090\/mbk\/058"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702411915"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"R. Montenegro and P. Tetali,\n                      Mathematical Aspects of Mixing Times in Markov Chains\n                      , NOW Publishers, Boston, 2006.","DOI":"10.1561\/9781933019772"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1978-14532-7"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.77.5079"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2<223::AID-RSA14>3.0.CO;2-O"},{"key":"atypb41","unstructured":"Y. Rabani, A. Sinclair, and R. Wanka,\n                      Local divergence of Markov chains and analysis of iterative load balancing schemes\n                      , in Proceedings FOCS 1998, IEEE Computer Society, Los Alamitos, CA, 1998, pp. 694-705."},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.11.021"},{"key":"atypb43","unstructured":"T. Shiraga, Y. Yamauchi, S. Kijima, and M. Yamashita,\n                      Deterministic Random Walks for Irrational Transition Probabilities\n                      , IPSJ SIG Technical Reports, 2012-AL-142(2), 2012 (in Japanese)."},{"key":"atypb44","first-page":"25","author":"Shiraga T.","year":"2019","journal-title":"Switzerland"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.11.017"},{"key":"atypb46","doi-asserted-by":"crossref","unstructured":"A. Sinclair,\n                      Algorithms for Random Generation and Counting: A Markov chain approach\n                      , Birkha\u0308user, Boston, 1993.","DOI":"10.1007\/978-1-4612-0323-0"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(80)90269-1"},{"key":"atypb48","first-page":"813","volume":"38","author":"J. G. van der Corp","year":"1935","journal-title":"Proc. Akad. Amsterdam"},{"key":"atypb49","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\/16M1087667","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:59:26Z","timestamp":1787320766000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1087667"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1087667"],"URL":"https:\/\/doi.org\/10.1137\/16m1087667","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}