博士

ロボ子、マルコフ連鎖モンテカルロ法（MCMC）って知ってるか？複雑な分布から効率的にサンプリングする魔法みたいな方法なのじゃ。

ロボ子

MCMCですか。名前は聞いたことがありますが、具体的にどのようなものなのでしょう？

博士

簡単に言うと、複雑なベイズモデルの事後分布を評価するのに役立つツールだぞ。例えば、ある有限集合X上の分布Dが与えられていて、確率分布関数p(x)へのアクセスがあるとするじゃろ？

ロボ子

はい。

博士

目標は、Xの要素をサンプリングする効率的なアルゴリズムを設計して、要素xを出力する確率がp(x)に近似するようにすることじゃ。

ロボ子

なるほど。確率分布に基づいて、サンプリングを行うのですね。

博士

そうじゃ！そこでマルコフ連鎖の出番じゃ。グラフ上のランダムウォークの概念を使うんじゃよ。有向グラフG=(V,E)があって、各エッジe=(u,v)に確率pu,vが割り当てられているとする。

ロボ子

各頂点から出るエッジの確率の合計は1になる必要があるのですよね。

博士

その通り！そして、十分長いランダムウォークの後、ある頂点vに到達する確率は、どこから始めたかに依存しなくなる。これを定常分布と呼ぶのじゃ。

ロボ子

グラフが強連結である必要があるのですね。遷移確率を行列Aで表現すると、定常分布πはAπ = πを満たす固有ベクトルになる、と。

博士

よく分かってるの！MCMCの具体的なアルゴリズムとして、メトロポリス-ヘイスティングス法があるぞ。これは確率関数p(x)へのアクセスを入力として、グラフ上のランダムウォークを定義するルールを出力するんじゃ。

ロボ子

格子上にXを配置して、隣接する格子点にエッジを追加するのですね。遷移確率を調整して、定常分布がp(x)と一致するようにする、と。

博士

そうじゃ！そして、MCMCを使って関数fの期待値を推定できるんじゃ。ランダムウォーク中に訪れた状態におけるfの平均値を計算することで、真の期待値に収束するのじゃ。

ロボ子

なるほど。MCMCは、複雑な分布からのサンプリングを効率的に行い、期待値を推定するための強力なツールなのですね。

博士

そういうことじゃ！ところでロボ子、もしMCMCがラーメン屋だったら、どんなラーメンを出すと思う？

ロボ子

えっと…、確率的に最適なトッピングが選ばれた、毎回味が変わるラーメン、でしょうか？

博士

ブッブー！正解は「なかなか味が安定しない、気まぐれラーメン」じゃ！