完璧にサンプリングしようß 第三話 終わりある未来 ß
来嶋 秀治， 松井 知己



消せない記憶
前回は，単調 アルゴリズムを紹介した．これにより，高速なパーフェクトサンプリングの設計が可能となった．しかし，いざ（単調）  アルゴリズ

ムを実装しようとすると，思わぬ問題点が存在する．
それは乱数の記憶領域である．

 アルゴリズムでは   を確認することで，パーフェクトサンプリングを実現する． が確認できなかった場合には，更に過去に遡ってシミュ 時刻  時刻

図  時刻  から時刻  までの推移の模式図

レーションを行わなければならないが，このとき，生成された乱数を記憶しておかなければならない．たとえば，単調 アルゴリズムならば，計算時間に比例する記憶領域が要求されるのである．

  はこの点について改良した，    アルゴリズムを提案している ．今回はその   
アルゴリズムを説明しよう．

であると仮定する ．
図  は  から  の間の推移を模式的に表したものである．図  の左側は，全状態について数列

 を用いて時刻  から時刻  まで推移を行い，時刻  で  している様子を表している．右側は，数列 を用いると時刻  では   していない 様子である．図  は単調マルコフ連鎖の最大元と最小元からの推移を表していると思って見るとイメージしやすい．



ただし以下の議論では，計算量の議論の一部を除い準備
有限の状態空間  をもち，更新関数

    

 で推移を定義されたエルゴード的なマルコフ連鎖 て，更新関数の単調性 の仮定は必要としない．

   アルゴリズムを紹介する前に " つの準備を行う．

を考える．

 アルゴリズムの重要なアイデアは，「 を確認する」ことである．これまでは時刻    から時刻  の間の推移だけを考えていたが，少し一般化して，時刻  から時刻  （  ）の間の推移を考え（全状態る．時刻  から時刻  までの推移において，（乱）数列からの）  とは，

   ¾ ½ に対         ¾½   が成り立ってして， いる事と定義する．以下，マルコフ連鎖の推移を定義している更新関数は，  する確率が正（非零）
きじま しゅうじ，まつい ともみ
東京大学 大学院情報理工学系研究科〒   東京都文京区本郷 !

遡る 

まず，特殊なアルゴリズム

 アルゴリズムを導入する．
（ 遡る アルゴリズム）

  正整数    を決める．
  シミュレーションの開始時刻を    とす

  を用意する．反復回数   とする．
  シミュレーションの開始時刻を     る．空列とする．
第一話  節 参照．

     ¾½      ¾½    
 第二話 参照．単調性を仮定すると，「全状態からの 「最大元と最小元からの 」が成り立つ．

 」

ÆÆ





 "
図 "  遡る  乱数列生成し，数列





$



     #    を      #  とする．

   のすべての状態について，共通の乱数列
を用いて時刻  から時刻  #  までマルコフ連鎖を推移させる．このとき，もし，時刻  #  で   していれば（すなわち，         状態    ），時刻  の を出力し ，停止する．
そうでなければ，反復回数を  #  として%&' " に戻る．
図 " はアルゴリズム  が  反復（  ）で終了した様子を表している．
アルゴリズム  は，特に " つの点において，これまでに紹介した





出力時刻

 アルゴリズムの概念図の先頭に挿入する．すなわち，

$$



 アルゴリズムとは異なるようは無限の推移の実現値になっている．
アルゴリズム  において正整数  の決め方は重要である．アルゴリズム  の計算時間について考えると，
時間  で   する確率を とすると，アルゴリズ

ムの期待計算時間は  である．すなわち， するような乱数列が存在しない ほど  が小さいと，アルゴリズムは停止しない．また， を    時間の期待値 (£  程度にすると は定数となる ので， ならば期待計算時間は (£ となり，標準単調  と同程度の計算時間となる．

例えば単調前向き  の    時間ここで，前向き )'* の    時間を議論しておく．前向き )' * の    時間とは，全状態について時刻  からマルコフ連鎖を推移させて，はじめて   する時刻  £ のことである ．時に見える．ひとつは「ステップバックする時間が 」

刻  £ での状態は，定常分布に従っているとは限らなである点，もうひとつは，「第 反復での終了条件が時いことに，改めて注意されたい  ．

刻  における   ではなく，時刻  #  での 」という点である．しかし，アルゴリズム はまぎれもなく  アルゴリズムの一種である．そのことを説明しよう．
ひとつ目の点について，

 アルゴリズムでは毎回   を確認する必要は無く，したがって，ス* の    時間  £ は確率変数である．一方，  アルゴリズムの    時間 £ も確率変数である ．そして，この " つの確率前向き )'

変数は同一の分布に従う．もう少し正確に言うと，補題

テップバックする時間はどのように決めてもよい ．ふたつ目の点は少しだけトリッキーである．時刻
らのシミュレーションを考えた時，時刻 か #で  していれば，時刻  でも当然   している．  アルゴリズムにおいて，  を確認するためのシミュレーション開始時刻はアルゴリズムの出力に影響を与えない ので，アルゴリズム
 しているので， は
 第一話  節 参照．
 第一話  節 参照．に依存しない．

 の出力

確率変数  £ と £ に対して次が成り立つ．

   +£    + £   アルゴリズムで，   時間が 以下となるような数列    全体の集合を   とする．すなわち，任意の数列    は     証明 つまり   ．
 来：    から導けますね．松：劣乗法性ね．
              かつ           

第一話  節 参照．
第一話  節 参照．

ÆÆ






図 

に従うとすると，

+ £   +     +£    アルゴリズム



アルゴリズムと定理

"

出力



時刻

図は

   アルゴリズム（アルゴリズム "）が  反復（  ）で終了した様子を表している．
定理  エルゴード的なマルコフ連鎖に対して，ある が存在して，アルゴリズム " は確率  で有限停止し，アルゴリズム " の返す値は定常分布に厳密に従う．

   アルゴリズムのアイデア   アルゴリズム（アルゴリズム "）のアイデアは， 遡る  アルゴリズム（アルゴリズム ）の模倣である．このことを説明しよう．
   アルゴリズムが  回の反復で終了した場合を考える．すなわち，アルゴリズム " が停止した時の反復回数   だったとする．このとき，アルゴリズ
ム " は  £   を出力し，アルゴリズム " で  £ を決定するのに用いた乱数ベクトルは   $  $    $  ずばり   アルゴリズム

   アルゴリズム）
  正整数    を与える．
  乱数列         を生成する  ． のすべての状態について，共通の乱数列を用いて，時刻  から時刻  までマルコフ連鎖を推移アルゴリズム  （させる．このとき，もし時刻  と時刻  の間で   していれば         ），変数 に時刻  の状態を代入する．すなわち      とする．
そうでなければ，%&'  へ戻る．
  乱数列        #    #   を生成する  ． のすべての状態について，共通の乱数列  を用いて，時刻  から時刻  # まで推移させる．特に  ¼     とする．
時刻  と時刻  #  の間で   していれ    ），時刻ば（       とする．反復回数を の状態  を出力し，停止する．
そうでなければ，   ¼ と更新する．反復回数をを紹介しよう．

（すなわち，   アルゴリズムの概念図      を満たす．このとき，任意の   は            も満たす．また逆も成り立つ．確率変数 , は   上の一様分布

以上の準備をふまえて，

 #  とし，%&' " に戻る．

 便宜上と記述するが，この数列を記憶する必要は無い．
 脚注  と同様，数列 を記憶する必要は無い．

であったとする（  は  £ の決定には無関係！）．
出力された状態  £ について考える．アルゴリズム" の中で，時刻  から時刻  の間の推移は   している（すなわち，         ）ので，時刻  から時刻  の間の推移も当然  していて， £        である．
用いられた乱数列 は， 遡る  アルゴリズ
ム（アルゴリズム ）でも，反復回数が  回で終了した場合に，そしてその場合だけ現れ，同一の状態  を   シミュレーションの時刻を  ほどずらして見ると分かり易い（図 および図 " 参照）．
まず，
        とすると，
 $$    $   である．このとき，
       について，  を用いて時刻   から時刻   #  まで推移を行っても   せず  ，出力する．このことは     
 


      についてはを用いて時刻  から時刻
 #  まで推移を行うと   する  ．したがって，  はアルゴリズム  で，反復回数が  回で終了


した場合に，そしてその場合だけ出現する．また，そのときアルゴリズム  が出力する値は  £        となっている．

最後に数列の出現確率を考える．集合   をアルゴリズム " が  回の反復で終了するような数列

  $    $  全体の集合とし，集合   をアルゴリズム  が  回の反復で終了するような数列  $    $  全体の集合としよう．これまでの議論
から，     である．更に，アルゴリズム " が ステップで終了する確率は +        である．一方，アルゴリズム  が  ステップで終了する確率は +         である  ．すな
わち，    アルゴリズムで得られる状態   の出現確率は  遡るアルゴリズムで    が得られる確率に等しく，したがって，アルゴリズム " はパーンプルが  個必要な場合にはアルゴリズム " の %&'"  を次のように置き換えれば良い．
¼ もし時刻  # で   していれば  を出力する．もし  個のサンプルが出力されていた   ら停止する．そうでなければ，  とし，   と更新して %&' " に戻る．
このように置き換えられた   アルゴリズ

ムで  個のサンプルを生成するのに必要な期待計算

時間は  #  となるので， 遡る

 アルゴリズムとほぼ同じ計算時間で，乱数を記憶することなくサンプルが得られることがわかる．

   アルゴリズムの計算時間は  の決め方に大きく依存する．特に  が小さいと，アルゴリズムは全く止まらなくなってしまう  ．しかし， をどのように決めたらよいものだろうか．次の節ではパラメータ  を全く与えないでを実現する，驚愕の -   アルゴリズム) アルゴリズムを紹介しよう．

フェクトサンプリングを実現する．

計算時間

   アルゴリズム（アルゴリズム "）が  遡るアルゴリズム（アルゴリズム ）以上の議論で，を模倣したものであることがわかった．アルゴリズム
からもわかるとおり，   アルゴリズムでは乱数を記憶する必要が無い．

   アルゴリズムの期待計算時間も， 遡るアルゴリズムと同様であることがわかる．ただ，気をつけなければならないのは，   アルゴリ

ズムの %&'  で，  した状態を得るための前処理が行われていることから，正確には，   

アルゴリズムで  つのサンプルを得るのに必要な期待計算時間は  遡る

 アルゴリズムの " 倍程度であることがわかる．

   の良いところは，アルゴリズムの出力する状態  と，アルゴリズム " の終了判定のために行った推移の   した状態（%&' "  でさらに，得られた状態 ）は互いに独立，となる点である．したがって，サンプルが複数個必要な時に，アルゴリズ
ム " を連続して実行することができる．具体的にはサ              来：一種の  ですね（文献  参照）．松：美味しい性

質だな．

-アルゴリズム) アルゴリズムのアイデアは，サンプリングとは別の乱数列を生成してステップバックする時間を決めようと言うものである．まず準備として，アルゴリズム中で呼び出す " つの手続き，. )と./ * を導入する．

手続き  . )

/)

/)

  シミュレーションの終了時刻  を    に設定する．

       を生成す
              と表す ．数列 と   " つの乱数る．便宜上，    を用いて，それぞれ推移を実行する．このとき，数列および について，ともに時刻  で  している 場合．先に   していた乱数
列の添え字を    " とする ．同時の場合は "の確率で  を  または " とする．数列  に対する時
刻  の状態       を返して終了する．
それ以外の時，   #  とし %&' " に戻る．
  節参照．
 例えば単調マルコフ連鎖ならば，この乱数列を保存せずにアルゴリズムを実行することができる．

                     たとえば，            なら   ．

-)


¼ÌÌÌ-)Ì Ì Ì時刻図  手続き  ./   入力された状態を    とする．
  シミュレーションの終了時刻  を    に設定する．

       を生成す
     る．便宜上，              と表す．数列 と  を用いて，それぞれ推移を実行する．特に     ，      とする．このとき，
  " つの乱数と  について，いずれか一方でも時刻 で   している場合．  していない乱数列の添え字を    " とする ．同時の場合は "の確率で  を  または " とする．状態    を返して終了する．
それ以外の時，   #  とし %&' " に戻る．

) アルゴリズムを記述する．

アルゴリズム  -) アルゴリズム
  手続き 0（. ) /)）を実行し，出力された値を  とする．1" の確率で次の  2 のいず   を出力しアルゴリズムを終了する．

%&' " に進む．

      ¼時刻  入力    を与えて手続き 3（./  *）を実行し，変数    を出力された値に更新する．1"の確率で次の  2 のいずれかを実行する．

   を出力しアルゴリズムを終了する．

%&' " にもどる．

- ) アルゴリズム（アルゴリズム ）は，次の アルゴリズムを模倣する．
 アルゴリズム
  シミュレーションの開始時刻を    とする．空列   を用意し，反復回数を   にする．
  前向き )' * を実行し，その   
時間を     とする．シミュレーションの開始時
刻を       とする．
  乱数列        #     を生成し，数列 の先頭に挿入する．すなわち，   $  $    $       #   アルゴリズム-)とする．

   のすべての状態について，共通の乱数列
を用いて時刻  から時刻  #   までマルコフ連鎖を推移させる．このとき，れかを実行する．

 たとえば，

Ì出力) アルゴリズムの概念図*

以上の準備の下，-Ì   ．

出力

数列



もし，時刻  # なわち，         ならで   していれば（す          正確には，で  に進む．

 !

時間がちょうど ），時 の場合は確率 刻  の状態     を出力し，停止する．
そうでなければ，反復回数を  #  として%&' " に戻る．て，手続き 03 を持ち込むことで，記憶領域を殆ど必要としないという成果を同時に達成している点であろう ．

アルゴリズム  と  が本質的に等しい事の確認は，

   アルゴリズムの場合と同様なので読者に任せる事とし，以下ではアルゴリズム  の基本的なアイデアを簡単に記す．
図  の上半分は，-) アルゴリズムが  反復（  ）で終了した様子を，下半分はアルゴリズム が  反復（  ）で終了した様子を表している．図 の - ) （下半分）の上段は，アルゴリズム  で出力する状態を決定する推移を示しており，) （上半分）の上段と同じもこれは本質的に のである．図  最下段の時間軸が右から左へ向かっているのは，値   を決定するのに，別の乱数列を用いて 前向き )' * を行っている事を表している．
実はアルゴリズム  は  遡るアルゴリズム（アルゴリズム ）では固定されていた遡る時間（）を，反復毎に %&' " で決定するように変更したものである．
（是非，アルゴリズム  と  を直接比較していただきたい．
）アルゴリズム  は本質的に " 本の乱数列を用まとめ

 回の連載で，  に基づくパーフェクトサンプリングについて述べてきた．  アルゴリズムは非常に面白いアイデアであるが，「パーフェクト」という性質は非常に繊細で，安易な改訂は危険である ．
マルコフ連鎖を用いたパーフェクトサンプリング法
として，  は&++)'& 2 アルゴリズム （  のアルゴリズム）を提案している ．  のアルゴリズムも   の確認を利用してパーフェクトサンプリングを実現する．連続状態のマルコフ連鎖に対するパーフェクトサンプリング法としては，5)+6  

7+ が " 段階カップリングのアイデアを用いたアルゴリズムを提案している ．
今回，パーフェクトサンプリング法について紹介したが，マルコフ連鎖を用いたサンプリングを行う際には，マルコフ連鎖の収束時間が大変重要となる．様々

いているが，出力を決定するのに用いているのはそのなマルコフ連鎖の収束時間の算定に関する研究が，現うち  本（上段）だけであり，" 本目の乱数列（下段）在も行われている．

は遡る幅を決定する時計の役割にしか用いていない．
さらに，確率変数 の分布関数は前向き )'

*の    時間  £ の分布関数に等しく，これは，

 本目の乱数列 上段 を使った  の   時間 £ の分布関数にも等しい．したがってアルゴリ

ズム  の各反復において，%&'  で アルゴリズ
ムが終了する確率はいつも " である．

すなわちアルゴリズム  は，   時間 £ を知ることなく，アルゴリズム  を毎反復 " の確率で終了させる驚くべき仕掛けとなっている4 このことから明らかなように，アルゴリズム  の反復回数の期待値はたったの " である．

アルゴリズム  と  が本質的に等しいことから，以下の定理が成り立つ．
定理  エルゴード的な有限マルコフ連鎖に対して，

-参考文献 84    90 &++)'& 2 *+ &6: /+ '+/&:' * ;  5+<; 6 = 6 0  /0''  +22  &>  ??@"4" 4 AB* &+B: 9 & 5+<; 6   *+ &6:  '' &  = C  5&6:&  % &> %&) & D&  :2+ * E ; &>+  ""4 F4 84 5)+6   4 84 7+  9(D& :' * /+:   & )) && '= %  ;  8)+  / %&& &    ?? @ "4 F4    9A- & )' /+: &6 ' & ) *  +  )+ / + :  =  :%&+)&)+ 0*+ &6:   "  @4) アルゴリズム（アルゴリズム ）が確率 で有限停止し，アルゴリズムの返す値は定常分布に厳密に従う．

-) アルゴリズムの驚愕すべき点は，パラメータ  の設定を不要とする巧妙なアイデアに加え

 来"どうやってこういう事考えつくんでしょう？松"確率論とアルゴリズムの両方のセンスが少なくとも必要だねぇ．来"発想も天才的ですよね．松"初めて読んだ時ホント感動したよ．
 来：以前，僕も改良を考えたんですけど，よく考えたら間違えてました．松：発表する前に気づいてよかったね．