ランダム探索

問題にほとんど何も制限がないので，とりあえずランダムに $x\in\cal X$ を発生させ， $f(x)$ が小さな値を取るような $x$ を選ぶことにしよう． できれば，小さな値を取る $x$ を優先的にサンプルする方が効率がよい． そこで，

$$p_T(x)=\frac1{Z_T}\exp(-f(x)/T)$$ (2)

という確率分布に従って $x$ を生成することにする²． $\exp$ の上に乗せたのは確率値を正の値にするためで，$Z_T$ は正規化定数

$$Z_T = \sum_{x\in X} \exp(-f(x)/T)$$ (3)

で，式の形を見ればわかるように，一般に $Z_T$ を計算するのは大変である． $T>0$ は温度と呼ばれ，$T$ が 0 に近づくにつれ， 最小値を取る $x$ でピークを持つ分布になる．

$p_T(x)$ が $x$ の事後分布のとき，$f(x)$ の最小値を求める問題は 最大事後分布推定 (MAP = Maximum a posterior estimation) を行っていることになる．

問題は $p_T(x)$ に従う乱数を発生させるのに，$f(x)$ に関して多くの 知識を必要とすることである． これは，$f(x)$ に関しては何も制限を 設けないと仮定したのに反する． この問題を解決するための一つの方法は，以下で述べるように， $p_T(x)$ に収束するマルコフ連鎖を構成することである．