カバー時間

数学では、有限マルコフ連鎖のカバータイムとは、与えられた開始状態から、すべての状態に到達する最初のステップまで、連鎖がたどるステップ数です。これは、マルコフ連鎖と開始状態の選択に依存する確率変数です。連結無向グラフのカバータイムとは、グラフ上でランダムウォークを行うマルコフ連鎖のカバータイムであり、各ステップで1つの頂点からその頂点の均一にランダムな隣接点へと移動します。^{[ 1 ]}

グラフのカバー時間は、 st連結性の複雑さ、代数的グラフ理論、エキスパンダーグラフの研究、トークンリングコンピュータネットワーク技術のモデリングなど、理論計算機科学の応用分野で広く研究されてきた。 ^{[ 1 ]}

確率論における古典的な問題であるクーポン収集者問題は、完全グラフの期待被覆時間の結果として解釈できる。${\displaystyle K_{n}}$は${\displaystyle n\ln n(1+o(1))}$他のすべての${\displaystyle n}$-頂点グラフの場合、期待されるカバー時間は少なくともこの式と同じくらい大きい。^{[ 2 ]}任意の${\displaystyle n}$-頂点規則拡張グラフには期待カバー時間もあります${\displaystyle \Theta (n\log n)}$任意の開始頂点から、より一般的には任意の正則グラフの被覆時間は$${\displaystyle O\left({\frac {n\log n}{1-\lambda _{2}}}\right),}$$どこ$\displaystyle \lambda _{2}}$は、グラフの2番目に大きい固有値であり、最大の固有値が1になるように正規化されています。 ^{[ 1 ]}任意の${\displaystyle n}$-頂点グラフでは、任意の開始頂点からカバー時間は最大で$${\displaystyle \left({\frac {4}{27}}+o(1)\right)n^{3},}$$そして、期待被覆時間がこれほど大きいグラフが存在する。^{[ 3 ]}平面グラフでは、期待被覆時間は${\displaystyle \Omega (n\log ^{2}n)}$そして${\displaystyle O(n^{2})}$[ ^{4 ]​}

• 到達時間、一連の状態に初めて到達するまでのステップ数