無理数遷移確率ランダムウォークの脱乱択化

• Item type: SIG Technical Reports(1)
• 公開日: 2012-10-26
• タイトル: 無理数遷移確率ランダムウォークの脱乱択化
• タイトル / 言語: en
• タイトル: Deterministic Random Walks for Irrational Transition Probabilities
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 九州大学
• 著者所属: 九州大学
• 著者所属: 九州大学
• 著者所属: 九州大学
• 著者所属(英): en
• 著者所属(英): Kyushu University
• 著者所属(英): en
• 著者所属(英): Kyushu University
• 著者所属(英): en
• 著者所属(英): Kyushu University
• 著者所属(英): en
• 著者所属(英): Kyushu University
• 著者名: 白髪, 丈晴; 山内, 由紀子; 来嶋, 秀治; 山下, 雅史
• 著者名(英): Takeharu, Shiraga; Yukiko, Yamauchi; Shuji, Kijima; Masafumi, Yamashita
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ランダムウォークの脱乱択化とは，決定的な過程によってランダムウォークを模倣する試みであり，ロータールーターモデルと呼ばれるモデルが提案されている．グラフ上の頂点をトークンがランダムに隣接点へ移動するランダムウォークに対して，ロータールーターモデルでは，グラフの各頂点上にあらかじめ隣接点の順番を決め，その順番に従ってトークンを移動させる．従来のロータールーターモデルは有理数の遷移確率しか模倣することが出来なかったが，本稿では無理数の遷移確率をもつランダムウォークも模倣出来る新しいロータールーターモデルを提案する．さらに，ランダムウォークにおけるトークンの期待配置と提案モデルにおけるトークンの配置の誤差の上下界の解析を与える．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2012-AL-142, 号 2, p. 1-7, 発行日 2012-10-26
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会