パラレルテンパリング法

実際に，(8)式のように温度を変えた分布に対して， 交換操作を導入したのが パラレルテンパリング (parallel tempering) 法と呼ばれる手法である． ただし，定常分布を不変に保つために，交換は 単純に行えばいいというわけではなく，適切な確率で行わなければならない． $x^{(j)}$ と $x^{(k)}$ を交換する候補として選んだとしよう． $j$ と $k$ は任意の確率分布によって選んでもよいが， 実際に交換するかどうかは以下の確率で決める．

$$\beta(x^{(j)},x^{(k)}) = \frac{p_{T_k}(x^{(j)}) p_{T_j}(x^{(k)})} {p_{T_j}(x^{(j)}) p_{T_k}(x^{(k)})}$$ (9)

ただし， $\beta(x^{(j)},x^{(k)})\ge1$ の場合は必ず交換する． この交換が全体の極限分布を不変に保つことは，全変数の MCMC と見てやれば 容易に確認できる．

(9) 式を見るとわかるように，交換は相手の温度に移ったときに やはり高い確率をとっていないと採択される確率が低いため，通常は 近い温度をもつ変数同士 ($x^{(k)}$ と $x^{(k+1)}$ など) で行われる．

パラレルテンパリング法は，温度の高い分布や低い分布を行ったり来たり しながら探索を行う． そのため，シミュレーテッドアニーリングと似た 効果を持ち，温度の下げ方に神経質になる必要もない． そのかわり， $T_1,\ldots,T_K$ をどのように設定するかはそれなりに重要 となる． あまり密に配置すると，計算時間のオーバーヘッドなどが増えて 無駄になる上，温度の高いところと低いところを行き来するのに多くの ステップを必要とするために，最適化の効率も逆に悪くなる可能性もある． 一方，あまりスパースに配置すると前に述べたように交換の採択確率が 下がってしまう． そこで，経験的に(あるいは漸近理論などを用いて)，ある程度 一定の採択率をもつような温度の配置がいろいろ提案されている[8]．