2026-03-11T03:49:22Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00086133 2025-01-21T17:48:19Z 1164:2592:6670:6899

無理数遷移確率ランダムウォークの脱乱択化 Deterministic Random Walks for Irrational Transition Probabilities 白髪, 丈晴 山内, 由紀子 来嶋, 秀治 山下, 雅史 Takeharu, Shiraga Yukiko, Yamauchi Shuji, Kijima Masafumi, Yamashita ランダムウォークの脱乱択化とは，決定的な過程によってランダムウォークを模倣する試みであり，ロータールーターモデルと呼ばれるモデルが提案されている．グラフ上の頂点をトークンがランダムに隣接点へ移動するランダムウォークに対して，ロータールーターモデルでは，グラフの各頂点上にあらかじめ隣接点の順番を決め，その順番に従ってトークンを移動させる．従来のロータールーターモデルは有理数の遷移確率しか模倣することが出来なかったが，本稿では無理数の遷移確率をもつランダムウォークも模倣出来る新しいロータールーターモデルを提案する．さらに，ランダムウォークにおけるトークンの期待配置と提案モデルにおけるトークンの配置の誤差の上下界の解析を与える． The rotor-router model, a.k.a. the deterministic random walk, is a deterministic process possibly emulating a random walk. In a random walk, tokens move to adjacent vertices at random. In the classical rotor-router model, every vertex launches tokens into adjacent vertices according do a prescribed order defined for each vertex, thus the rotor-router model cannot handle irrational transition probabilities. In this paper, we devise a new model, which can handle irrational transition probabilities. Then, we analyze the difference between the number of tokens in our rotor-router model and the expected number of tokens in a random walk. 情報処理学会 2012-10-26 jpn technical report https://ipsj.ixsq.nii.ac.jp/records/86133 AN1009593X 研究報告アルゴリズム（AL） 2012-AL-142 2 1 7 https://ipsj.ixsq.nii.ac.jp/record/86133/files/IPSJ-AL12142002.pdf application/pdf 173.7 kB 2014-10-26