有限グラフ上のランダムウォークの脱乱択化

• 来嶋 秀治

• 古賀 健太郎

• 牧野 和久

書誌事項

タイトル別名

• Deterministic Random Walks on Finite Graphs

抄録

Propp 機械，あるいは rotor-router モデルは，ランダムウォークを模倣する決定的過程である．ランダムウォークにおいては，グラフ上をトークンがランダムに巡回するのに対し，Propp 機械においては，各頂点上の router があらかじめ定められた隣接点の順番に従って，トークンを隣接点に発射する．本稿では，有限グラフ上の Propp 機械に着目し，ランダムウォークモデルにおけるトークンの期待配置と Propp 機械におけるトークンの配置の誤差の上下界を見積もる．より正確には，任意のグラフに対し，単一頂点誤差が O(mn) であることを示す．ただし，m は枝数，n は頂点数を表す．下界としは，単一頂点誤差が Ω(m) となるようなグラフと配置を与える．Propp machine, also known as the rotor-router model, is a deterministic process which may emulate a random walk on a graph. In the process, tokens on each node are launched one by one to the neighboring nodes served in a prescribed order, instead of random choice. In this paper, we focus on finite graphs and investigate the difference between the number of tokens in the Propp machine and the expected number of tokens in a random walk. We show that for any initial configuration, at any time, the difference is bounded by O(mn) when the corresponding random walk is lazy and reversible, where n denotes the number of nodes and m denotes the number of edges. We also show a lower bound Ω(m) of the difference by providing graphs and initial configurations such that the difference on any node at any time (> 0) is Ω(m).

収録刊行物

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

  研究報告アルゴリズム（AL） 2011 (5), 1-8, 2011-05-09

詳細情報

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