# ランダムウォーク ## 定義 ランダムウォーク(random walk)とは、対象が一連のステップで無作為に選ばれた方向へ移動していく確率過程である。最も単純な形は整数直線上の 1 次元ウォークで、各ステップごとに確率 `p` で +1、確率 `1-p` で -1 に移動する。`p=1/2` の場合を偏りのない(unbiased)ウォーク、`p≠1/2` の場合を偏りのある(biased)ウォークと呼ぶ。破産問題(Gambler's Ruin)は、賭博者の資金の時間変化を境界(0 と目標額 `T`)を持つ 1 次元ランダムウォークとしてモデル化したものであり、公平な賭けでは目標到達確率は `n/T`(`n`: 初期資金)、偏った賭けでは `w_n=(r^n-1)/(r^T-1)`(`r:=q/p`)になる(定理20.1.1)。この 1 次元の定式化は、頂点集合が有限個の状態(整数値)であり、各頂点から隣接頂点への遷移確率が固定された有向グラフ上のウォークとみなすこともでき、20.2 節で扱われる一般の有向グラフ上のランダムウォークの特殊ケースになっている。有向グラフ上のランダムウォークでは、各ステップで現在の頂点 `x` から出る辺 `⟨x→y⟩` を割り当てられた確率(典型的には一様に `1/outdeg(x)`)に従って選び、次の頂点へ移動する。十分に長いランダムウォークにおける各頂点の訪問確率は、後述の[[定常分布]]に近づいていく場合がある。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] §20.1, §20.2.2) 破産問題の勝利確率 `w_n=(r^n-1)/(r^T-1)`(定理20.1.1)は、2 つの独立した証明技法で導かれる。1 つはパスカルによる「賭けを公正にするようチップの価値を `r^k` で再定義する」という確率論的な発想(§20.1.1)、もう 1 つは全確率の規則から線形漸化式 `w_n=p·w_{n+1}+q·w_{n-1}` を立て、母関数法で解く代数的な標準手法(§20.1.2)である。異なる道具立てから同一の閉形式へ到達することは、線形漸化式が「特別な着想を要求しない methodical な代替手段」(本文の表現)であることを示す。さらに `p<1/2` の場合の上界 `(1/r)^(T-n)`(系20.1.2)は初期資金 `n` ではなく目標利益 `T-n` のみに依存する形をしており、この構造が「初期資金をいくら増やしても勝率がほぼ変わらない」という直観に反する結論(わずかな不利さが破滅的に効く)を生む。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] §20.1.1-§20.1.3) ## 横断的知見 - 現時点では [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] のみが本概念のソースであり、複数ソースの突き合わせによる横断的知見はまだ蓄積されていない。今後、確率過程・グラフアルゴリズムを扱う別ソースを ingest した際に追記する。 ## 未解決の問い - 本章は 1 次元(破産問題)と有向グラフ上のランダムウォークの 2 例のみを扱う。物理学のブラウン運動・気体拡散のモデルとして言及される多次元(2 次元以上)のランダムウォークは、本書の範囲外として名前だけ挙げられ詳細は扱われない(§20 冒頭)。多次元ランダムウォークの復帰確率(recurrence)などの性質は、本 vault の他ソースで扱われているか未確認。 - 有限だが非常に大きい状態空間(Web グラフのような数兆頂点規模)でのランダムウォークの収束速度(mixing time)は本章では触れられていない。定常分布への収束が「十分に長い」ウォークで起こるとされるのみで、収束に要するステップ数の評価は演習問題にも本文にも登場しない。 ## 関連 - 概念: [[定常分布]] / [[PageRank]] / [[有向グラフ]] / [[漸化式]] / [[期待値]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 20 §20.1-§20.2.