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

• 白髪 丈晴

• 山内 由紀子

• 来嶋 秀治

• 山下 雅史

書誌事項

タイトル別名

• Deterministic Random Walks for Irrational Transition Probabilities

抄録

ランダムウォークの脱乱択化とは，決定的な過程によってランダムウォークを模倣する試みであり，ロータールーターモデルと呼ばれるモデルが提案されている．グラフ上の頂点をトークンがランダムに隣接点へ移動するランダムウォークに対して，ロータールーターモデルでは，グラフの各頂点上にあらかじめ隣接点の順番を決め，その順番に従ってトークンを移動させる．従来のロータールーターモデルは有理数の遷移確率しか模倣することが出来なかったが，本稿では無理数の遷移確率をもつランダムウォークも模倣出来る新しいロータールーターモデルを提案する．さらに，ランダムウォークにおけるトークンの期待配置と提案モデルにおけるトークンの配置の誤差の上下界の解析を与える．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.

収録刊行物

• 研究報告アルゴリズム（AL）

  研究報告アルゴリズム（AL） 2012 (2), 1-7, 2012-10-26

詳細情報

• CRID: 1573668927658186240
• NII論文ID: 110009465409
• NII書誌ID: AN1009593X
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles