標準ランダムウォーク

ネットワーク上の隣接する頂点に等確率で遷移していくランダムウォークのことを標準ランダムウォークという。

頂点数 $n$ 、辺数 $m$ の任意の単純グラフの場合、到達時間と全訪問時間の期待値が $O(nm)$ に抑えられる。