規格化をしていない確率分布関数からサンプリングをする方法だ。

この方法では、初期のパターンiを決め、そこからqを使って連続的にパターンを生成していく。そうやって生成されたパターンはpに従っている、というものだ。

例えば、初期パターンを1000として、パターン番号iを0としよう。

このパターンiに何か操作して、別なパターンjに確率的に変化する規則Tを決める。

例えばパターン1000の0番目と1番目を交換すれば0100になるし、2番目と3番目を交換すれば、1000のままとなる。

ここまでをまとめると、

1.規則Tに従ってバターンiからパターンjを決める

だ。

次に、iの次のパターンjが決まったら、本当にjに遷移させるかを以下の手順で判定する。

2.規格化していない確率q(i)とq(j)を計算する。

3.もし、q(i)q(j)なら、q(j)/q(j)の確率でj、そうでなければiのままとする。

以上の1から4手続きを繰り返すことで、連続的にパターンを作っていくことができる。このように生成されたパターンは、p(i)に従う分布になるのだ。すごい。

確かにこの手続きなら、qが大きいパターンで留まりやすいし、qが小さいバターンにはなかなかならない感じはするね。

でも、規格化していないqだけを使ってpの分布からサンプリングできちゃうってことが、ちゃんと証明できるんだよ。

ただし、サンプルされるパターンには依存性があつで独立ではない。連番のパターン同士は2つの箇所を入れ換えただけだからね。独立したパターンをサンプルしたければ、十分な数だけ、例えば、100回繰り返してサンプルする。初期パターンの依存性をなくすためにも、そんな風にする。

ああ、あと、もうひとつ大切なことがあった。規則Tにはルールがあって、iからjを選ぶ確率と、jからiを選ぶ確率は同じでなくてはならない。前の要素を交換するする方法はその条件を満たしているよね。