2016/02/24 by Takeharu Shiraga, Shiraga, Takeharu
Decision Sciences · Mathematics · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Probability and Risk Models #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1602.07729
openalex publication_date 2016/02/24 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
The deterministic random walk is a deterministic process analogous to a\nrandom walk. While there are some results on the cover time of the rotor-router\nmodel, which is a deterministic random walk corresponding to a simple random\nwalk, nothing is known about the cover time of deterministic random walks\nemulating general transition probabilities. This paper is concerned with the\nSRT-router model with multiple tokens, which is a deterministic process coping\nwith general transition probabilities possibly containing irrational numbers.\nFor the model, we give an upper bound of the cover time, which is the first\nresult on the cover time of deterministic random walks for general transition\nprobabilities. Our upper bound also improves the existing bounds for the\nrotor-router model in some cases.\n