ランダムウォーク

数学において、ランダムウォークは酔っぱらいの散歩とも呼ばれ、ある数学的空間上での一連のランダムなステップからなる経路を記述する確率過程です。

ランダムウォークの基本的な例としては、0 から始まり、各ステップで等しい確率で +1 または -1 に移動する整数直線上のランダムウォークが挙げられます。その他の例としては、液体または気体中を移動する分子の描く経路 (ブラウン運動を参照)、餌を探す動物の探索経路、変動する株価、ギャンブラーの財務状況などがあります。ランダムウォークは、工学や、生態学、心理学、コンピューターサイエンス、物理学、化学、生物学、経済学、社会学など多くの科学分野に応用されています。ランダムウォークという用語は、 1905 年にカール・ピアソンによって初めて導入されました。 ^[1]${\displaystyle \mathbb {Z} }$

ランダムウォークの実現はモンテカルロシミュレーションによって得られる。^[2]

よく知られているランダムウォークモデルは、規則格子上のランダムウォークであり、各ステップで位置が何らかの確率分布に従って別のサイトへジャンプする。単純なランダムウォークでは、位置は格子の隣接サイトへのみジャンプでき、格子パスを形成する。局所有限格子上の単純な対称ランダムウォークでは、位置が各隣接サイトへジャンプする確率は同じである。最もよく研​​究されている例は、 d次元整数格子（超立方格子と呼ばれることもある）上のランダムウォークである。^[3]${\displaystyle \mathbb {Z} ^{d}}$

状態空間が有限次元に制限されている場合、ランダムウォークモデルは単純な境界付き対称ランダムウォークと呼ばれ、境界状態とコーナー状態では動きが制限されるため、遷移確率は状態の位置に依存します。^[4]

ランダム ウォークの基本的な例としては、整数直線上のランダム ウォークが挙げられます。これは 0 から始まり、各ステップで等しい確率で +1 または -1 に移動します。 ${\displaystyle \mathbb {Z} }$

このウォークは次のように説明できます。数直線上のゼロにマーカーを置き、公平なコインを投げます。表が出たら、マーカーは 1 単位右に移動します。裏が出たら、マーカーは 1 単位左に移動します。5 回投げた後、マーカーは -5、-3、-1、1、3、5 のいずれかにある可能性があります。5 回投げて、表が 3 回、裏が 2 回 (順序は問いません) になると、マーカーは 1 に止まります。1 に止まる方法は 10 通り (表が 3 回、裏が 2 回)、-1 に止まる方法は 10 通り (裏が 3 回、表が 2 回)、3 に止まる方法は 5 通り (表が 4 回、裏が 1 回)、-3 に止まる方法は 5 通り (裏が 4 回、表が 1 回)、5 に止まる方法は 1 通り (表が 5 回)、-5 に止まる方法は 1 通り (裏が 5 回) あります。 5 回投げた場合の可能な結果については、下の図を参照してください。

このウォークを正式に定義するには、独立したランダム変数（各変数は 1 または −1 で、どちらの値になる確率も 50%）を取り、 およびと設定します。この数列は上の単純ランダムウォークと呼ばれます。 この数列（−1 と 1 のシーケンスの合計）は、ウォークの各部分の長さが 1 である場合に、歩行された正味の距離を示します。の期待値は 0 です。つまり、コインを投げる回数が増えるにつれて、すべてのコイン投げの平均は 0 に近づきます。 これは、期待値の有限加法性によって決まります。 ${\displaystyle Z_{1},Z_{2},\dots }$${\displaystyle S_{0}=0}$${\textstyle S_{n}=\sum _{j=1}^{n}Z_{j}.}$ ${\displaystyle \{S_{n}\}}$${\displaystyle \mathbb {Z} }$ ${\displaystyle E(S_{n})}$${\displaystyle S_{n}}$$${\displaystyle E(S_{n})=\sum _{j=1}^{n}E(Z_{j})=0.}$$

ランダム変数の独立性と という事実を使用した同様の計算により、次のことがわかります。 ${\displaystyle E(Z_{n}^{2})=1}$$${\displaystyle E(S_{n}^{2})=\sum _{i=1}^{n}E(Z_{i}^{2})+2\sum _{1\leq i<j\leq n}E(Z_{i}Z_{j})=n.}$$

これは、nステップ後の予想される並進距離が のオーダーになるはずであることを示唆している。実際、^[5]${\displaystyle E(|S_{n}|)\,\!}$ ${\displaystyle {\sqrt {n}}}$ $${\displaystyle \lim _{n\to \infty }{\frac {E(|S_{n}|)}{\sqrt {n}}}={\sqrt {\frac {2}{\pi }}}.}$$

ランダムウォークが永遠に歩き続けることを許された場合、境界線を何回横切るかという質問に答えるために、単純なランダムウォークはすべてのポイントを無限回横切ります。この結果には、レベルクロッシング現象、再発、ギャンブラーの破滅など、多くの名前があります。最後の名前の理由は次のとおりです。限られた金額のギャンブラーは、無限の金額の銀行と公平なゲームをプレイすると、最終的には負けます。ギャンブラーのお金はランダムウォークを実行し、ある時点でゼロになり、ゲームは終了します。 ${\displaystyle \mathbb {Z} }$

aとb が正の整数である場合、0 から始まる 1 次元の単純ランダム ウォークが最初にbまたは − aに到達するまでの期待ステップ数はabです。このウォークが− aに到達する前にb に到達する確率は であり、これは単純ランダム ウォークがマルチンゲールであるという事実から導き出されます。そして、これらの期待値と到達確率は、一般的な 1 次元ランダム ウォークのマルコフ連鎖で 計算できます。${\displaystyle a/(a+b)}$${\displaystyle O(a+b)}$

上で述べた結果のいくつかは、パスカルの三角形の特性から導くことができます。各ステップが +1 または −1 であるnステップの異なるウォークの数は2 ⁿです。単純なランダムウォークでは、これらのウォークのそれぞれが等しく発生する可能性があります。S n_が数kに等しいためには、ウォーク内の +1 の数が −1 の数をkだけ上回ることが必要かつ十分です。したがって、ウォークのnステップ中に +1 が ( n  +  k )/2 回出現する必要があるため、を満たすウォークの数は、n要素セット^{[6]から (} n  +  k )/2 要素を選択する方法の数に等しくなります。これに意味を持たせるには、 n  +  k が偶数であることが必要であり、これはnとk が両方とも偶数か両方とも奇数であることを意味します。したがって、の確率は に等しくなります。パスカルの三角形の要素を階乗で表し、スターリングの公式を使用することで、 の大きな値に対してこれらの確率の良好な推定値を得ることができます。 ${\displaystyle S_{n}=k}$${\textstyle n \choose (n+k)/2}$${\displaystyle S_{n}=k}$${\textstyle 2^{-n}{n \choose (n+k)/2}}$${\displaystyle n}$

簡潔にするためにスペースを+ に限定すると、ランダムウォークが 5 回投げて任意の数字に到達する方法の数は、{0,5,0,4,0,1} と表すことができます。 ${\displaystyle \mathbb {Z} }$

パスカルの三角形とのこの関係は、 nの値が小さい場合に実証されます。ゼロ回転では、ゼロに留まる可能性しかありません。ただし、1 回転では、-1 に着地する可能性が 1 回、または 1 に着地する可能性が 1 回あります。2 回転では、1 にあるマーカーは 2 に移動するか、ゼロに戻る可能性があります。-1 にあるマーカーは、-2 に移動するか、ゼロに戻る可能性があります。したがって、-2 に着地する可能性が 1 回、ゼロに着地する可能性が 2 回、2 に着地する可能性が 1 回あります。

中心極限定理と反復対数の法則は、上の単純ランダムウォークの挙動の重要な側面を説明します。特に、前者は、n が増加するにつれて、確率 (各行の数字に比例) が正規分布に近づくことを意味します。 ${\displaystyle \mathbb {Z} }$

正確に言うと、 を知り、スターリングの公式を 使うと、${\textstyle \mathbb {P} (X_{n}=k)=2^{-n}{\binom {n}{(n+k)/2}}}$

$${\displaystyle {\log \mathbb {P} (X_{n}=k)}=n\left[\left({1+{\frac {k}{n}}+{\frac {1}{2n}}}\right)\log \left(1+{\frac {k}{n}}\right)+\left({1-{\frac {k}{n}}+{\frac {1}{2n}}}\right)\log \left(1-{\frac {k}{n}}\right)\right]+\log {\frac {\sqrt {2}}{\sqrt {\pi }}}+o(1).}$$

を固定してスケーリングし、が消えるときの展開を用いると、次のようになる。 ${\textstyle k=\lfloor {\sqrt {n}}x\rfloor }$${\textstyle x}$${\textstyle \log(1+{k}/{n})=k/n-k^{2}/2n^{2}+\dots }$${\textstyle k/n}$

$${\displaystyle {\mathbb {P} \left({\frac {X_{n}}{n}}={\frac {\lfloor {\sqrt {n}}x\rfloor }{\sqrt {n}}}\right)}={\frac {1}{\sqrt {n}}}{\frac {1}{2{\sqrt {\pi }}}}e^{-{x^{2}}}(1+o(1)).}$$

極限をとると（そして がスケーリンググリッドの間隔に対応することを観察すると）、ガウス密度 が見つかります。実際、密度 を持つ絶対連続ランダム変数の場合、が成り立ち、 は無限小間隔に対応します。 ${\textstyle {1}/{\sqrt {n}}}$${\textstyle f(x)={\frac {1}{2{\sqrt {\pi }}}}e^{-{x^{2}}}}$${\textstyle X}$${\textstyle f_{X}}$${\textstyle \mathbb {P} \left(X\in [x,x+dx)\right)=f_{X}(x)dx}$${\textstyle dx}$

直接的な一般化として、結晶格子（有限グラフ上の無限重アーベル被覆グラフ）上のランダムウォークを考えることができる。実際に、この設定では中心極限定理と大偏差定理を確立することが可能である。^{[7] [8]}

1次元ランダムウォークは、状態空間が整数で与えられるマルコフ連鎖として見ることもできる。を満たすある数pに対して、遷移確率（状態iから状態jに移動する確率P _i,j）は次のように与えられる。 ${\displaystyle i=0,\pm 1,\pm 2,\dots .}$${\displaystyle \,0<p<1}$$${\displaystyle \,P_{i,i+1}=p=1-P_{i,i-1}.}$$

異種ランダムウォークは、各タイムステップでローカルジャンプ確率を決定する乱数を抽出し、次に実際のジャンプ方向を決定する乱数を抽出します。主な問題は、ジャンプ後にさまざまなサイトのそれぞれに留まる確率と、が非常に大きい 場合のこの確率の限界です。${\displaystyle t}$${\displaystyle t}$

高次元では、ランダムに歩いた点の集合は興味深い幾何学的特性を持ちます。実際、離散フラクタル、つまり大規模で確率的自己相似性を示す集合が得られます。小規模では、歩行が実行されるグリッドから生じる「ギザギザ」を観察できます。ランダム ウォークの軌跡は、歩行がポイントに到着したタイミングを無視した集合として考えられた、訪問したポイントのコレクションです。1 次元では、軌跡は単に、歩行が達成した最小の高さと最大の高さの間のすべてのポイントです (平均すると、両方とも のオーダーです)。 ${\displaystyle {\sqrt {n}}}$

2 次元の場合を視覚化するには、人が街中をランダムに歩いているところを想像します。街は事実上無限で、歩道が四角い格子状に並んでいます。交差点ごとに、人は 4 つの可能なルート (最初に通ってきたルートを含む) のうちの 1 つをランダムに選択します。正式には、これは整数座標を持つ平面上のすべての点の集合上のランダム ウォークです。

人が歩行の出発点に戻れるかどうかという疑問に対する答えは、上で議論したレベルクロッシング問題の 2 次元版です。1921 年にジョージ ポリアは、2 次元のランダム ウォークでは人がほぼ確実に戻ることを証明しましたが、3 次元以上では次元数が増えるにつれて原点に戻る確率は低下します。3 次元では、その確率は約 34% に低下します。^[9]数学者角谷静夫は、この結果について次の引用で言及したことで知られています。「酔っ払った男は家に帰る道を見つけるが、酔った鳥は永遠に迷うかもしれない」。^[10]

再発確率は一般にはであり、これは生成関数^[11]またはポアソン過程^[12]によって導くことができる。${\displaystyle p=1-\left({\frac {1}{\pi ^{d}}}\int _{[-\pi ,\pi ]^{d}}{\frac {\prod _{i=1}^{d}d\theta _{i}}{1-{\frac {1}{d}}\sum _{i=1}^{d}\cos \theta _{i}}}\right)^{-1}}$

ポリアもこの質問の別のバリエーションとして、「2 人の人が同じ出発点を離れた場合、再び会うことはあるだろうか？」というものがあります。 ^[13] 2 人の位置の差 (2 つの独立したランダム ウォーク) も単純なランダム ウォークであることが示されており、2 次元ウォークではほぼ確実に再び会うことができますが、3 次元以上では次元の数に応じて確率は低下します。ポール エルデシュとサミュエル ジェームズ テイラーは 1960 年に、4 次元以下では、任意の 2 点から出発する 2 つの独立したランダム ウォークはほぼ確実に無限に交差しますが、5 次元を超えると、ほぼ確実に交差する回数は有限であることを示しました。^[14]

2次元ランダムウォークのステップ数が増加するにつれての漸近関数はレイリー分布で与えられる。確率分布は原点からの半径の関数であり、ステップ長は各ステップで一定である。ここで、ステップ長は1と仮定し、Nはステップの総数、rは原点からの半径である。^[15]

$${\displaystyle P(r)={\frac {2r}{N}}e^{-r^{2}/N}}$$

ウィーナー過程は、流体内で拡散する微粒子の物理現象であるブラウン運動に似た動作をする確率過程です。(ウィーナー過程は「ブラウン運動」と呼ばれることもありますが、厳密に言えば、これはモデルとモデル化される現象の混同です。)

ウィーナー過程は、次元 1 におけるランダム ウォークのスケーリング限界です。つまり、ステップが非常に小さいランダム ウォークがある場合、ウィーナー過程 (および、それほど正確ではありませんが、ブラウン運動) への近似値が存在するということです。より正確には、ステップ サイズが ε の場合、ウィーナー長Lを近似するには、長さL /ε ²のウォークを実行する必要があります。ステップ サイズが 0 に近づくにつれて (ステップ数は比例して増加します)、ランダム ウォークは適切な意味でウィーナー過程に収束します。正式には、B が最大位相を持つ長さLのすべてのパスの空間であり、Mがノルム位相を持つB上の測度の空間である場合、収束は空間Mにあります。同様に、複数の次元におけるウィーナー過程は、同じ数の次元におけるランダム ウォークのスケーリング限界です。

ランダム ウォークは離散フラクタル (1、2、... の整数次元を持つ関数) ですが、ウィーナー過程の軌跡は真のフラクタルであり、両者の間にはつながりがあります。たとえば、半径rにステップ長を掛けた円に達するまでランダム ウォークを続けます。実行するステップの平均数はr ²です。^{[引用が必要]}この事実は、ウィーナー過程のウォークがハウスドルフ次元 2のフラクタルであるという事実の離散バージョンです。 ^{[引用が必要]}

2次元では、同じランダムウォークの軌道の境界にある点の平均数はr ^{4/3です。これは、ウィーナー過程の軌道の境界が4/3次元のフラクタルであるという事実に対応しており、これは}マンデルブロがシミュレーションを使用して予測した事実ですが、2000年にローラー、シュラム、ヴェルナーによって証明されました。^[16]

ウィーナー過程には、ランダムウォークにはない多くの対称性があります。たとえば、ウィーナー過程のウォークは回転に対して不変ですが、ランダムウォークは回転に対して不変ではありません。これは、基礎となるグリッドが回転に対して不変ではないためです (ランダムウォークは 90 度の回転に対して不変ですが、ウィーナー過程は、たとえば 17 度の回転に対しても不変です)。つまり、多くの場合、ランダムウォークの問題は、ウィーナー過程に翻訳し、そこで問題を解決してから、元に戻すと簡単に解決できます。一方、ランダムウォークの離散的な性質により、ランダムウォークで簡単に解決できる問題もあります。

ランダム ウォークとウィーナー過程は結合することができ、つまり、同じ確率空間上で従属的に表現され、非常に近いものになります。最も単純な結合はスコロホッド埋め込みですが、コムロス-メジャー-トゥスナディ近似定理などのより正確な結合も存在します。

ランダム ウォークのウィーナー過程への収束は、中心極限定理とドンスカー定理によって制御されます。t = 0 で既知の固定位置にある粒子の場合 、中心極限定理によれば、ランダム ウォークの多数の独立したステップの後、歩行者の位置は総分散の正規分布に従って分布します。

$${\displaystyle \sigma ^{2}={\frac {t}{\delta t}}\,\varepsilon ^{2},}$$

ここで、tはランダム ウォークの開始からの経過時間、はランダム ウォークのステップのサイズ、は連続する 2 つのステップ間の経過時間です。 ${\displaystyle \varepsilon }$${\displaystyle \delta t}$

これは、ウィーナー過程を制御する拡散方程式のグリーン関数に対応しており、多数のステップを経るとランダムウォークがウィーナー過程に収束することを示唆しています。

3D では、拡散方程式の グリーン関数に対応する分散は次のようになります。$${\displaystyle \sigma ^{2}=6\,D\,t.}$$

この量をランダム ウォーカーの位置に関連付けられた分散と等しくすることで、多数のステップの後にランダム ウォークが収束する漸近ウィーナー過程について考慮される等価拡散係数が得られます (3D でのみ有効)。 $${\displaystyle D={\frac {\varepsilon ^{2}}{6\delta t}}}$$

上記の分散の 2 つの式は、3D でランダム ウォークの両端を結ぶベクトルに関連付けられた分布に対応します。各コンポーネント、またはに関連付けられた分散は、この値の 3 分の 1 にすぎません (依然として 3D)。 ${\displaystyle {\vec {R}}}$${\displaystyle R_{x}}$${\displaystyle R_{y}}$${\displaystyle R_{z}}$

2Dの場合: ^[17]

$${\displaystyle D={\frac {\varepsilon ^{2}}{4\delta t}}.}$$

1Dの場合: ^[18]

$${\displaystyle D={\frac {\varepsilon ^{2}}{2\delta t}}.}$$

正規分布に従って変化するステップ サイズを持つランダム ウォークは、金融市場などの現実世界の時系列データのモデルとして使用されます。

ここで、ステップ サイズは、0 ≤  z  ≤ 1 が均一に分布する乱数 である逆累積正規分布であり、μ と σ はそれぞれ正規分布の平均と標準偏差です。${\displaystyle \Phi ^{-1}(z,\mu ,\sigma )}$

μ がゼロでない場合、ランダム ウォークは線形傾向に沿って変化します。v _{s が}ランダム ウォークの開始値である場合、nステップ後の期待値は v _s + n μになります。

μ がゼロに等しい特殊なケースでは、nステップ後、変換距離の確率分布はN (0, n σ ² ) で与えられます。ここで、N () は正規分布の表記、nはステップ数、σ は上記の逆累積正規分布から得られます。

証明: ガウスランダムウォークは、平均がゼロの逆累積正規分布からの X _iと元の逆累積正規分布の σ という、独立した同一分布のランダム変数のシーケンスの合計と考えることができます。

${\displaystyle Z=\sum _{i=0}^{n}{X_{i}},}$

しかし、2つの独立した正規分布するランダム変数の和の分布Z = X + Y は、次のように与えられます （こちらを参照）。 $${\displaystyle {\mathcal {N}}(\mu _{X}+\mu _{Y},\sigma _{X}^{2}+\sigma _{Y}^{2})}$$

この場合、μ _X = μ _Y = 0かつσ ² _X = σ ² _Y = σ ²である ため、帰納法により、nステップ について 次式が得られます。平均がゼロで分散が有限である分布 (必ずしも正規分布である必要はありません) に従って分布するステップの場合、nステップ後の二乗平均平方根平行移動距離は次式になります ( Bienaymé の恒等式を参照)。 $${\displaystyle {\mathcal {N}}(0,2\sigma ^{2})}$$${\displaystyle Z\sim {\mathcal {N}}(0,n\sigma ^{2}).}$

${\displaystyle {\sqrt {Var(S_{n})}}={\sqrt {E[S_{n}^{2}]}}=\sigma {\sqrt {n}}.}$

しかし、ガウスランダムウォークの場合、これはnステップ後の移動距離の分布の標準偏差に過ぎません。したがって、μ がゼロで、二乗平均平方根 (RMS) 移動距離が 1 標準偏差である場合、nステップ後の RMS 移動距離が の間になる確率は 68.27% です。同様に、 nステップ後の移動距離が の間になる確率は 50% です。 ${\displaystyle \pm \sigma {\sqrt {n}}}$${\displaystyle \pm 0.6745\sigma {\sqrt {n}}}$

単一のランダムウォーカーが訪れる異なるサイトの数は、正方格子や立方格子、フラクタルについて広く研究されてきた。^{[19] [20]}この量は、トラッピングや運動反応の問題の解析に役立つ。また、振動状態密度、^{[21] [22]}拡散反応プロセス^[23] や生態学における個体群の拡散にも関連している。^{[24] [25]}${\displaystyle S(t)}$

ガウスランダムウォークの二乗誤差距離に関する情報率、すなわちその二次率歪み関数は、 ^[26] でパラメータ的に与えられ、 ここで である。したがって、ビット未満のバイナリコードを使用してエンコードし、 未満の期待平均二乗誤差でそれを復元することは不可能である。一方、任意の に対して、十分に大きい と 個以下の異なる要素を持つバイナリコードが存在し、このコードからの復元の期待平均二乗誤差は最大でも である。 $${\displaystyle R(D_{\theta })={\frac {1}{2}}\int _{0}^{1}\max\{0,\log _{2}\left(S(\varphi )/\theta \right)\}\,d\varphi ,}$$ $${\displaystyle D_{\theta }=\int _{0}^{1}\min\{S(\varphi ),\theta \}\,d\varphi ,}$$${\displaystyle S(\varphi )=\left(2\sin(\pi \varphi /2)\right)^{-2}}$${\displaystyle {\{Z_{n}\}_{n=1}^{N}}}$${\displaystyle NR(D_{\theta })}$ ${\displaystyle D_{\theta }}$${\displaystyle \varepsilon >0}$${\displaystyle N\in \mathbb {N} }$${\displaystyle 2^{NR(D_{\theta })}}$${\displaystyle {\{Z_{n}\}_{n=1}^{N}}}$${\displaystyle D_{\theta }-\varepsilon }$

前述のように、何らかのランダムウォークで説明しようと試みられてきた自然現象の範囲は広く、特に物理学^{[27] [28]}や化学^[29] 、材料科学^{[30] [31] 、生物学[32] [ 33} ] の分野でその傾向が顕著である。^[34]ランダムウォークの具体的な応用例は以下の通りである。

• 金融経済学では、ランダムウォーク仮説は株価やその他の要因をモデル化するために使用されています。^[35]実証研究では、特に短期および長期の相関関係において、この理論モデルからの逸脱がいくつか見つかりました。株価を参照してください。
• 集団遺伝学では、ランダムウォークは遺伝的浮動の統計的性質を記述する。
• 物理学では、ランダム ウォークは、液体や気体中の分子のランダムな 動きなど、物理的なブラウン運動や拡散の簡略化されたモデルとして使用されます。たとえば、拡散限界凝集を参照してください。また、物理学では、ランダム ウォークといくつかの自己相互作用ウォークは、量子場の理論で役割を果たします。
• 半導体製造では、ランダム ウォークは、より小さなノードでの熱処理の効果を分析するために使用されます。これは、重要な製造ステップ中のドーパント、欠陥、不純物などの拡散を理解するために適用されます。ランダム ウォーク処理は、化学蒸着プロセス中の反応物、生成物、プラズマの拡散を研究するためにも使用されます。連続拡散は、CVD リアクター内のマクロ スケールでのガスの流れを研究するために使用されてきました。ただし、寸法が小さくなり、複雑さが増したため、ランダム ウォークで処理せざるを得なくなりました。これにより、半導体製造における分子レベル以下の確率過程の正確な分析が可能になります。
• 数理生態学では、ランダムウォークは個々の動物の動きを記述したり、生物拡散のプロセスを経験的にサポートしたり、時には個体群動態をモデル化したりするために使用されます。
• 高分子物理学では、ランダムウォークは理想的な鎖を記述する。これはポリマーを研究するための最も単純なモデルである。^[36]
• 他の数学の分野では、ランダムウォークはラプラス方程式の解を計算したり、調和測度を推定したり、解析学や組合せ論におけるさまざまな構成に使用されます。
• コンピュータサイエンスでは、ランダムウォークはWebのサイズを推定するために使用されます。^[37]
• 画像セグメンテーションでは、ランダムウォークを使用して各ピクセルに関連付けるラベル（つまり、「オブジェクト」または「背景」）を決定します。^{[38]このアルゴリズムは通常、}ランダムウォーカーセグメンテーションアルゴリズムと呼ばれます。

• 脳の研究では、ランダム ウォークと強化ランダム ウォークを使用して、脳内のニューロン発火のカスケードをモデル化します。
• 視覚科学では、眼球運動はランダムウォークのように振る舞う傾向がある。^[39]一部の研究者によると、一般的な固定眼球運動もランダムウォークでうまく説明できるという。^[40]
• 心理学では、ランダムウォークは意思決定に必要な時間と特定の意思決定が行われる確率の関係を正確に説明します。^[41]
• ランダムウォークは、たとえばインターネットからランダムにページを選択するなど、未知または非常に大きい状態空間からサンプリングするために使用できます。^[要出典]コンピューターサイエンスでは、この方法はマルコフ連鎖モンテカルロ(MCMC)として知られています。

• ワイヤレス ネットワークでは、ランダム ウォークを使用してノードの移動をモデル化します。^{[引用が必要]}
• 運動性細菌は偏ったランダムウォークを行う。^[42]
• 物理学では、ランダムウォークはフェルミ推定法の基礎となっている。^[要出典]
• ウェブ上では、Twitterのウェブサイトはランダムウォークを使用して誰をフォローすべきかを提案している^[43]
• Dave BayerとPersi Diaconis は、7 回のリフル シャッフルで1 組のトランプを混ぜるのに十分であることを証明しました(詳細はシャッフルの項を参照)。この結果は、対称群上のランダム ウォークに関する記述に変換され、彼らはこれを証明しました。この証明では、フーリエ解析による群構造が重要な役割を果たしています。

純粋なランダムウォークに似ているが、単純な構造をより一般化できる確率過程のいくつかの型が考えられてきた。純粋な構造は、独立かつ同一に分布するランダム変数によって定義されるステップによって特徴付けられる。ランダムウォークは、グラフ、整数、実数直線、平面または高次元ベクトル空間、曲面または高次元リーマン多様体、および群などのさまざまな空間上で発生する可能性がある。ランダムな時間にステップを踏むランダムウォークを定義することも可能であり、その場合、位置X
_tすべての時間t ∈ [0, +∞)に対して定義される必要があります。ランダムウォークの特定のケースまたは限界には、レヴィ飛行モデルやブラウン運動などの拡散モデルが含まれます。

根が0である可能性のある無限グラフG上の長さkのランダム ウォークは、 および が の近傍から一様にランダムに選択された頂点であるようなランダム変数を持つ確率過程です。この場合、数は、vから始まる長さkのランダム ウォークがwで終了する確率です。特に、G が根が0であるグラフの場合、は - ステップのランダム ウォークが0に戻る確率です。 ${\displaystyle X_{1},X_{2},\dots ,X_{k}}$${\displaystyle X_{1}=0}$${\displaystyle {X_{i+1}}}$${\displaystyle X_{i}}$${\displaystyle p_{v,w,k}(G)}$${\displaystyle p_{0,0,2k}}$${\displaystyle 2k}$

前の高次元のセクションの類推に基づいて、都市が完全な正方形のグリッドではなくなったと仮定します。ある人物が特定の交差点に到着すると、彼はさまざまな利用可能な道路を同じ確率で選択します。したがって、交差点に 7 つの出口がある場合、人物は各出口に 7 分の 1 の確率で向かいます。これはグラフ上のランダム ウォークです。この人物は家にたどり着くでしょうか。かなり穏やかな条件下では、答えは依然として「はい」であることがわかります。^[44]しかし、グラフによっては、「2 人の人物は再び会うでしょうか」という別の質問に対する答えは、彼らがほぼ確実に無限に会うというものではない可能性があります。^[45]

人がほぼ確実に自宅にたどり着く場合の例として、すべてのブロックの長さがaとb の間にある場合が挙げられます(ここで、aとbは任意の 2 つの有限の正の数)。グラフが平面であるとは想定していないことに注意してください。つまり、都市にはトンネルや橋が含まれている可能性があります。この結果を証明する 1 つの方法は、電気ネットワークへの接続を使用することです。都市の地図を取り、すべてのブロックに 1オームの 抵抗器を配置します。次に、「ポイントと無限の間の抵抗」を測定します。言い換えると、ある数Rを選択し、電気ネットワーク内でポイントからRよりも大きい距離にあるすべてのポイントを取り、それらを配線します。これで有限の電気ネットワークになり、ポイントから配線されたポイントまでの抵抗を測定できます。R を無限大まで取ります。この極限は、ポイントと無限の間の抵抗と呼ばれます。次の式が真であることがわかります (基本的な証明は Doyle と Snell の本にあります)。

定理:グラフが過渡的であるのは、点と無限大の間の抵抗が有限である場合のみです。グラフが接続されている場合は、どの点を選択するかは重要ではありません。

言い換えれば、過渡的なシステムでは、任意の点から無限大に到達するには有限の抵抗を克服するだけで済みます。再帰的なシステムでは、任意の点から無限大までの抵抗は無限大です。

この一時性と再発性の特徴付けは非常に有用であり、具体的には、距離が制限された平面上に描かれた都市のケースを分析することができます。

グラフ上のランダム ウォークは、マルコフ連鎖の非常に特殊なケースです。一般的なマルコフ連鎖とは異なり、グラフ上のランダム ウォークは、時間対称性または可逆性と呼ばれる特性を備えています。大まかに言えば、詳細バランスの原理とも呼ばれるこの特性は、特定のパスを一方向または他方向に通過する確率が、非常に単純な関係にあることを意味します (グラフが正則である場合、それらは単に等しい)。この特性は重要な結果をもたらします。

1980 年代以降、グラフの特性とランダム ウォークを結び付ける研究が盛んに行われてきました。上記の電気ネットワークとの結びつきに加え、等周不等式(詳細はこちらを参照)、ソボレフ不等式やポアンカレ不等式などの関数不等式、ラプラス方程式の解の特性との重要な結びつきがあります。この研究の大部分は、有限生成群のケーリー グラフに焦点が当てられていました。多くの場合、これらの離散的な結果は多様体やリー群に引き継がれるか、多様体やリー群から導出されます。

ランダムグラフ、特にエルデシュ・レーニモデルの文脈では、ランダムウォーカーのいくつかの特性に対する解析結果が得られています。これには、ウォーカーの最初の^[46]ヒット時間と最後のヒット時間^[47]の分布が含まれます。最初のヒット時間は、ウォーカーがグラフの以前に訪れた場所に初めて足を踏み入れた時間によって与えられ、最後のヒット時間は、ウォーカーが以前に訪れた場所を再訪せずに追加の動きを実行できない最初の時間に対応します。

グラフ上のランダムウォークに関する参考文献としては、Aldous と Fill のオンライン ブックがお勧めです。グループについては、Woess の本を参照してください。遷移カーネル自体がランダムである場合 (環境 に基づく)、ランダムウォークは「ランダム環境内のランダムウォーク」と呼ばれます。ランダムウォークの法則に のランダム性が含まれる場合、その法則は焼きなまし法則と呼ばれます。一方、 が固定されていると見なされる場合、その法則は焼き入れ法則と呼ばれます。Hughes の本、Revesz の本、または Zeitouni の講義ノートを参照してください。 ${\displaystyle p(x,y)}$${\displaystyle \omega }$${\displaystyle \omega }$${\displaystyle \omega }$

不確実性（エントロピー）を局所的に最大化するのと同じ確率ですべての可能なエッジを選択することを考えることができます。また、これをグローバルに行うこともできます。最大エントロピーランダムウォーク（MERW）では、すべてのパスが等確率になるようにします。言い換えると、2つの頂点ごとに、指定された長さの各パスが等確率になるようにします。^[48]このランダムウォークは、はるかに強力な局所化特性を持っています。

各ステップが複雑な方法で過去に依存するランダム パスの興味深いモデルが多数あります。いずれも、通常のランダム ウォークよりも解析的に解決するのが複雑ですが、ランダム ウォーカーのあらゆるモデルの動作はコンピューターを使用して取得できます。例:

• 自己回避歩行[ ^49]

上の長さnの自己回避歩行は、原点から始まり、 内の隣接するサイト間でのみ遷移し、サイトを再訪することはなく、そのようなすべてのパスの中から一様に選択されるランダムな n ステップのパスです。2 次元では、自己トラッピングのため、典型的な自己回避歩行は非常に短いですが、^{[50]高次元ではすべての境界を超えて大きくなります。このモデルは}、ポリマー物理学でよく使用されています(1960 年代以降)。 ${\displaystyle \mathbb {Z} ^{d}}$${\displaystyle \mathbb {Z} ^{d}}$

• ループ消去ランダムウォーク。^{[51] [52]}
• 強化ランダムウォーク^[53]
• 探索プロセス。^[要出典]
• マルチエージェントランダムウォーク^[54]

エントロピー率を最大化するために選択されたランダム ウォークは、はるかに強力なローカリゼーション プロパティを備えています。

ランダムウォークとは、ある時点における移動方向が次の時点における移動方向と相関関係にある場合の運動である。動物の動きをモデル化するのに使用される。 ^{[55] [56]}

• 分岐ランダムウォーク
• ブラウン運動
• 反復対数の法則
• レヴィ飛行
• レヴィの飛行採餌仮説
• ループ消去ランダムウォーク
• 最大エントロピーランダムウォーク
• 自己回避歩行
• 単位根

• Aldous, David ; Fill, James Allen (2002). グラフ上の可逆マルコフ連鎖とランダムウォーク。2019年2月27日時点のオリジナルよりアーカイブ。
• Doyle, Peter G.; Snell, J. Laurie (1984).ランダムウォークと電気ネットワーク. Carus Mathematical Monographs. 第22巻.アメリカ数学協会. arXiv : math.PR/0001057 . ISBN 978-0-88385-024-4. MR  0920811.
• フェラー、ウィリアム（1968）「確率論とその応用入門（第1巻）」ISBN 0-471-25708-7 
• ヒューズ、バリー D. (1996)、「ランダムウォークとランダム環境」、オックスフォード大学出版局。ISBN 0-19-853789-1 
• ノリス、ジェームズ（1998）、マルコフ連鎖、ケンブリッジ大学出版局。ISBN 0-521-63396-6 
• Pólya G. (1921)、「Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfault im Strassennetz」 2016 年 3 月 4 日にウェイバック マシンにアーカイブ、Mathematische Annalen、84(1–2):149–160、1921 年 3 月。
• Révész, Pal (2013)、「ランダムおよび非ランダム環境におけるランダムウォーク（第3版）」、World Scientific Pub Co. ISBN 978-981-4447-50-8 
• 砂田俊一(2012)。位相結晶学：離散幾何学解析の観点から。応用数学科学の概説とチュートリアル。第6巻。Springer。ISBN 978-4-431-54177-6。
• Weiss G.ランダムウォークの側面と応用、North-Holland、1994 年。
• Woess, Wolfgang (2000)、「無限グラフと群上のランダムウォーク」、ケンブリッジ数学論文集 138、ケンブリッジ大学出版局。ISBN 0-521-55292-3 

• Pólya のランダム ウォーク定数
• Java アプレットのランダムウォーク 2007 年 8 月 31 日アーカイブWayback Machineで
• 量子ランダムウォーク
• ガウスランダムウォーク推定器
• 最大エントロピーランダムウォークを用いた電子伝導モデル Wolfram デモンストレーション プロジェクト