マルコフ連鎖混合時間

確率論において、マルコフ連鎖の混合時間とは、マルコフ連鎖が定常状態分布に「近づく」までの時間のことである。

より正確には、マルコフ連鎖に関する基本的な結果として、有限状態の既約非周期連鎖は一意の定常分布πを持ち 、初期状態に関係なく、tが無限大に近づく につれて連鎖の時間t分布はπに収束します。混合時間とは、この考え方のいくつかの異なる形式化のいずれかを指します。つまり、時間t分布がほぼπになるまでtはどれくらい大きくなければならないかということです。1つの形式化である全変動距離混合時間は、確率測度の全変動距離が小さくなるような最小のtとして定義されます。

${\displaystyle t_{\operatorname {mix} }(\varepsilon )=\min \left\{t\geq 0:\max _{x\in S}{\Big [}\max _{A\subseteq S}\left|\Pr(X_{t}\in A\mid X_{0}=x)-\pi (A)\right|{\Big ]}\leq \varepsilon \right\}.}$

別の選択をする${\displaystyle \varepsilon }$、 に限って${\displaystyle \varepsilon <1/2}$混合時間は定数係数までしか変更できません（${\displaystyle \varepsilon }$）そのため、しばしば修正する${\displaystyle \varepsilon =1/4}$そして単に書く${\displaystyle t_{\mathrm {mix} }}$。

これは、デイブ・ベイヤーとパーシー・ディアコニス（1992 ）が、通常の52枚のカードデッキを混ぜるのに必要なリフルシャッフルの回数は7回であることを証明した意味である。数学理論は、チェーンの根底にある構造のサイズに応じて混合時間がどのように変化するかに焦点を当てている。 ${\displaystyle n}$カードデッキの場合、必要なリフルシャッフルの回数は、${\displaystyle 1.5\log _{2}n}$最も発展した理論は、与えられたグラフの彩色数などの#P完全アルゴリズム的計数問題に対するランダム化アルゴリズムに関するものである。${\displaystyle n}$頂点グラフ。このような問題は、色の数が十分に多い場合、マルコフ連鎖モンテカルロ法を使用して解決でき、混合時間は次のようにしか増加しないことを示すことができます。${\displaystyle n\log(n)}$（ジェラム 1995 ）。この例とシャッフル例は、混合時間が多項式的に速く増加するという高速混合特性を持っています。${\displaystyle \log }$（連鎖の状態数）。高速混合を証明するためのツールには、コンダクタンスに基づく議論や結合法などがあります。マルコフ連鎖モンテカルロ法のより広範な使用においては、シミュレーション結果の厳密な正当化には混合時間の理論的な上限が必要となりますが、多くの興味深い実用例は、そのような理論的分析に抵抗してきました。

• 混合（数学）混合の正式な定義については、以下を参照してください。

• Aldous, David; Fill, Jim、「グラフ上の可逆マルコフ連鎖とランダムウォーク」 、 2004年9月21日にオリジナルからアーカイブ済み。
• Bayer, Dave ; Diaconis, Persi (1992)、「ダブテールシャッフルをたどってその隠れ家へ」（PDF）、『応用確率年報』、2（2）：294–313、doi：10.1214/aoap/1177005705、JSTOR 2959752、MR 1161056  。
• Jerrum, Mark (1995)、「低次数グラフのk彩色数を推定するための非常にシンプルなアルゴリズム」、 Random Structures & Algorithms、7 (2): 157–165、doi : 10.1002/rsa.3240070205、MR 1369061 。
• レヴィン、デイビッド A.、ペレス、ユヴァル、ウィルマー、エリザベス L. (2009)、マルコフ連鎖と混合時間、プロビデンス、ロードアイランド：アメリカ数学会、ISBN 978-0-8218-4739-8MR 2466937​ 。
• シンクレア、アリスター（1993）、「乱数生成と計数のためのアルゴリズム：マルコフ連鎖アプローチ」、理論計算機科学の進歩、Birkhäuser Boston, Inc.、ボストン、マサチューセッツ州、doi：10.1007/978-1-4612-0323-0、ISBN 0-8176-3658-7MR 1201590​ 。