「ランダムに選ばれた」の意味は明瞭ではない. おそらく望んでいるのは
randの次々の呼び出しは一様分布という統計の性質を持つ数列を生成することである. 適切な数列の発生法はここでは論じない. そうではなく, 手続きrand-updateがあり, ある数x1から出発し,
x2 = (rand-update x1)
x3 = (rand-update x2)
を作ると, 値の列x1, x2, x3, ... は望みの統計的性質を持つと仮定する.6
randをある固定した値random-initに初期化される局所状態変数xを持った手続きとして実装出来る. randを呼び出す度にxの現在値のrand-updateを計算し, これを乱数として返し, またそれをxの新しい値とする.
(define rand
(let ((x random-init))
(lambda ()
(set! x (rand-update x))
x)))
もちろん同じ乱数の列を単にrand-updateを直接呼び出すことで, 代入なしに生成することが出来る. しかしプログラムの乱数を使う部分は rand-updateに引数として渡すxの値をしっかり覚えていなければならないことを意味する. これが煩わしいことを知るため, モンテカルロシミュレーション(Monte Carlo simulation)という技法を実装するのに乱数を使うことを考えよう.
モンテカルロ法は, 大きい集合からランダムにサンプル実験を選ぶこと, これらの実験の結果を見て, 推測した確率を基に, 推定を行うことで出来ている. 例えばランダムに選んだ二つの整数が共通の因子を持たない, つまりそれらの最大公約数が1である確率が6π2だという事実を使って πの近似値を得ることが出来る.7 πの近似値を得るには, 多数回の実験を行う. 各実験で二つの整数をランダムに選び, その GCDが1かどうかのテストを行う. テストが成功した回数の比率が6π2の推定を与え, これからπの近似値を得る.
プログラムの中心は, 実験を試みる回数と, 実験中毎回真か偽のいずれかを返す引数なしの手続きとして表現した実験を引数にとる手続き monte-carloである. monte-carloは指示された試行回数だけ実験を行い, 実験が真となった割合を返す.
(define (estimate-pi trials)
(sqrt (/ 6 (monte-carlo trials cesaro-test))))
(define (cesaro-test)
(= (gcd (rand) (rand)) 1))
(define (monte-carlo trials experiment)
(define (iter trials-remaining trials-passed)
(cond ((= trials-remaining 0)
(/ trials-passed trials))
((experiment)
(iter (- trials-remaining 1) (+ trials-passed 1)))
(else
(iter (- trials-remaining 1) trials-passed))))
(iter trials 0))
今度はrandではなく, rand-updateを直接使って同じ計算をしてみよう. 代入が出来なければ, 局所状態をモデル化するのに, こうしなければならない:
(define (estimate-pi trials)
(sqrt (/ 6 (random-gcd-test trials random-init))))
(define (random-gcd-test trials initial-x)
(define (iter trials-remaining trials-passed x)
(let ((x1 (rand-update x)))
(let ((x2 (rand-update x1)))
(cond ((= trials-remaining 0)
(/ trials-passed trials))
((= (gcd x1 x2) 1)
(iter (- trials-remaining 1)
(+ trials-passed 1)
x2))
(else
(iter (- trials-remaining 1)
trials-passed
x2))))))
(iter trials 0 initial-x))
このプログラムはまだ単純ではあるが, 部品化に対する苦しい裂け目が見え始めている. randを使った初めの版のプログラムでは, モンテカルロ法を, 任意のexperiment手続きを引数にとる一般のmonte-carlo手続きとして, 直接表すことが出来た. 乱数発生のための局所状態のない二番目の版のプログラムでは, random-gcd-testは, 乱数x1, x2を明示的に扱い, rand-updateの新しい入力として, x2を反復ループを通して戻さなければならい. 乱数の明示的扱いは, テストの結果をアキュムレートする構造と, この特定の実験では乱数を二つ使うという事実とを合体させている. しかし, もう一方のモンテカルロ実験は乱数は一つでも三つでも使える. 最上レベルの手続きestimate-piも最初の乱数を補うことに気を使わなければならない. 乱数発生器の内部が外のプログラムの他の部分に洩れ出している事実は, モンテカルロの考えを隔離し, 他の作業にも使おうとするのを困難にしている. 初めの版のプログラムでは, 代入が乱数発生器の状態を rand手続きの中にカプセル化し, 乱数発生器の細部は,プログラムの他の部分と独立になっている.
モンテカルロ法の例が示した一般的現象はこうだ: 複雑なプロセスの一部から見ると, 他の部分は時と共に変化しているように見える. そこには隠された時間変化する局所状態がある. こういう分解を反映する構造の計算機プログラムを書こうと思えば, (銀行口座や乱数発生器のような)その振舞いが時と共に変化する計算オブジェクトを作る. われわれは状態を局所状態変数でモデル化し, 状態の変化をこれらの変数への代入でモデル化している.
われわれは, 代入の導入と状態を局所変数に隠す技法があれば, 追加のパラメタで引き渡し, 状態が明示的に扱われるよりも更に部品化の流儀でシステムが構造化出来るといって, この議論を終りたい気もするが, 残念ながら話はそう単純ではない.
問題 3.5
モンテカルロ積分(Monte Carlo integration)はモンテカルロシミュレーションを使って定積分を見積る方法である. 領域の中の点(x, y)では真,
外の点では偽になる述語P(x, y)で記述した空間の領域の面積を計算することを考える. 例えば中心(5, 7)で半径が3の円に含まれる領域は, (x - 5)2
+ (y - 7)2 ≤ 32をテストする述語で記述出来る. そういう述語で記述した領域の面積を見積るには, まず領域を囲む四角形を選ぶ. 例えば対角線上で向い合う頂点を(2, 4)と(8, 10)に持つ四角形は上の円を含む. 欲しい積分は四角形の中で領域に入る部分の面積である. 四角形の中の点(x, y)をランダムにとり, 各点でそれが領域の中にあるかどうか決めるため, P(x, y)をテストして積分を見積る. これを何回も試みれば領域の中に落ちた点の割合が,
四角形の中で領域に入る部分の面積を与える. 従ってこの割合に四角形の面積を掛けると, 積分が見積もれる.
モンテカルロ積分を, 手続き estimate-integralとして実装せよ. 手続きは引数として述語P, 四角形の上限と下限のx1, x2, y1およびy2, 見積りを出すために実行する試みの回数をとる. 手続きは上でπを見積った時に使ったのと同じmonte-carlo手続きを使うこと. estimate-integralを使い, 単位円の面積を測定することで, πの見積りを出せ.
与えられた範囲からランダムに選んで数を返す手続きがあれば便利であろう. 次のrandom-in-range手続きは, 1.2.6節の, 入力より小さい非負の数を返すrandom手続きを使ってこれを実装している.8
(define (random-in-range low high)
(let ((range (- high low)))
(+ low (random range))))
6
rand-updateを実装する通常のやり方は, a, b, mを適切に選んだ整数とし, mを法としてxをax + bで更新する規則を使うことである.
Knuth 1981の3章にはランダムな数列を生成し, 統計的性質を確立させる技法の広範な議論がある. rand-update手続きは数学的関数を計算することに注意しよう: 同じ入力を二回与えられると同じ出力を出す. 従って「ランダム」を, 数列の各数が前の数と無関係と主張するなら, rand-updateの生成する数列は絶対に「ランダム」ではない. 「真のランダム性」と,決定的計算で生成され, しかも適切な統計的性質を持つ, いわゆる
疑似乱数(pseudo-random)の列との関係は, 数学, 哲学上の困難な論点を含む, 複雑な問題である.
Kolmogorov, SolomonoffおよびChaitinはこの問題の明確化を大きく進歩させた; 議論はChaitin 1975で見ることが出来る.
7
この定理は
E. Cesàroによる. 議論と証明は
Knuth 1981の4.5.2節参照
8
MIT Schemeにはこの手続きがある.
randomは1.2.6節のように正確な整数が与えられると正確な整数を返すが, (この問題のように)小数の値を与えられると小数の値を返す.