2次元単純ランダムウォーク(2DSRW)の被覆時間
- 千葉大学の阿部圭宏さんにネタを頂きました.
- 2DSRWが $n\times n$ のサイズの格子の点を全て訪問するまでのステップ数はいくらか? という問題.
- ここでは$n$ を $n=50$ としていて境界は周期境界.
- STOPは一時停止, RESTARTは再開, REDOは最初から開始.
- 緑のバーをドラッグ&ドロップでRWのスピードを変更できる.
- 最初は全ての点が白. 一度訪問すると黒く塗られ訪問される毎に黒$\to$赤$\to$黄$\to$白となる.
- 全ての点が一度黒になるとStep to Coverのカウントが止まる. ただその後もRWは動く.
- 全ての点を最初に訪問するまでにかかったステップ数を $T_n$ とすると,
\begin{align*}
\lim_{n\to\infty}\dfrac{T_n}{(n\log n)^2}=\dfrac{4}{\pi}, \quad \text{ in probability},
\end{align*}
であることがDembo, Peres, Rosen, Zeitouniによって示されている.
- $n=50$ の場合,
\begin{align*}
T_{50} \sim \dfrac{4(50\log 50)^2}{\pi} \sim 48713.9030515277,
\end{align*}
となっている.