モンテカルロ法
乱数を使って、確率変数の期待値や分散を推定する方法の総称をモンテカルロ法という。モンテカルロはモナコ公国（カジノが盛んで、初めて作られたカジノがモンテカルロ・カジノ）の地区の名前であるらしい。期待値や分散
\[ \small \begin{align*} &E[X] = \int_D xp(x)dx \\ &V[X] = \int_D (x-E[x])^2p(x)dx \end{align*} \]
は確率分布の定義域\(\small D\)全体を積分することで計算するため、モンテカルロ法は数値積分の一種とみなされることが多い。特に、次元数の多い積分は解析式や離散化による数値積分で評価することが難しいため、モンテカルロ法が良く用いられる。
例えば、正規分布に従う確率変数\(\small x\sim N(\mu,\sigma^2)\)が与えられたとき、それに依存して値が決定する関数\(\small f(x)\)の期待値を求めたという場合、確率変数\(\small x\)のサンプルを\(\small x_1,\cdots,x_n\)と表せば
\[ \small E\left[f(x)\right] \approx \frac{1}{n} \sum_{i=1}^n f(x_i) \]
と近似することができる。サンプルの数を増やしていけばサンプルの確率分布は元の確率分布に収束していくため
\[ \small \lim_{n\rightarrow \infty} \frac{1}{n} \sum_{i=1}^n f(x_i) \rightarrow E\left[f(x)\right] \]
と収束することは容易に推測できるだろう。確率論や統計学では、この収束がどの程度の確かさで収束するかを細かく議論するが、ここでは取り上げない。
モンテカルロ法では、指定された確率分布\(\small F(x)\)に従う乱数を生成する必要がある。これは確率分布ごとに様々な方法論があるが、汎用的な方法として、一様分布に従う乱数\(\small u_i\sim U[0,1]\)を用いて（すべてのプログラミング言語においてこれを生成する関数が実装されている）、\(\small x_i=F^{-1}(u_i)\)と生成することができる。これは逆関数法と言われる。多変数の乱数を生成することは一般的には困難であり、マルコフ連鎖モンテカルロ法と言われるベイズ統計学に基づいた手法で生成することが多いようである。多変数の正規乱数については比較的容易に生成することができるため、その方法は後述する。
ランダム・ウォークとブラウン運動
モンテカルロ法は確率過程のシミュレーションにもよく用いられており、金融工学では株価や為替レートを乱数でシミュレーションすることで複雑な金融商品の時価を推定するということを行っている。確率過程は、時間の関数として生成される確率変数\(\small x(t)\)の総称である。例えば、\(\small w_1,\cdots,w_n\)が標準正規分布\(\small N(0,1)\)に従う場合
\[ \small \begin{align*} &w(t) = w_t \\ &r(t) = \sum_{i=1}^t w_i, \quad t=1,2,\cdots, n \end{align*} \]
と表される確率過程は、それぞれホワイトノイズ過程、ランダム・ウォークと言われる確率過程である。
このランダム・ウォークの概念を連続時間の確率過程にしたものがブラウン運動と言われる確率過程である。ブラウン運動は分散が時間\(\small t\)に比例する正規分布に従う確率過程であり
\[ \small B(t)\sim N(\mu t, \sigma^2t) \]
が確率分布になる。単純化して、\(\small \mu=0,\sigma^2=1\)と置いて、時間を\(\small n\)等分に離散化すると
\[\small B(t)=\lim_{n\rightarrow \infty} \sqrt{\frac{t}{n}} \sum_{i=1}^n w_i =\lim_{\Delta t\rightarrow 0} \sum_{i=1}^n w_i \sqrt{\Delta t} \]
という形式で表現することができる。このように離散近似すれば、ブラウン運動もコンピュータ上でシミュレーションできることになる。勘違いしやすいが
\[ \small B(t) = \frac{t}{n}\sum_{i=1}^n w_i = \sum_{i=1}^n w_i \Delta t \]
は、\(\small n\rightarrow \infty\)とすると0に収束してしまうため、ブラウン運動にはならないことに注意しておく。
多変数の正規乱数
複数の確率変数をモンテカルロシミュレーションする場合、互いに相関がない独立な確率変数であれば個別に乱数を生成してシミュレーションを行うことができる。しかし、多変数の確率変数を扱う場合、相関がない独立な変数として扱うことができるケースというのは稀なことである。ここでは、相関係数を反映した多変数の正規分布に従う乱数を生成する方法を考えよう。
\(\small m\)個の正規分布に従う確率変数\(\small x_1,x_2,\cdots,x_m\)の相関係数が\(\small \rho_{ij},i,j=1,\cdots,m\)で与えられていると仮定する。行列の形式
\[ \small \Sigma = \left[ \begin{array}{cccc} 1&\rho_{12}&\cdots&\rho_{1m} \\ \rho_{21}&1&\cdots&\rho_{2m} \\ \vdots&\vdots&\ddots&\vdots \\ \rho_{m1}&\rho_{m2}&\cdots&1 \end{array} \right] \]
で表したものを相関行列といい、相関行列\(\small \Sigma\)の\(\small m\)次元標準正規分布を\(\small N_{m,\Sigma}(0,1)\)と表す。この確率分布に従う\(\small m\)個の乱数を生成するアルゴリズムを考えたいということである。
これはコレスキー分解という行列の分解を計算することで生成できることが知られている。コレスキー行列は
\[ \small \begin{align*} &\Sigma = LL^{T} \ &L = \left[ \begin{array}{cccc} l_{11}&0&\cdots&0 \\ l_{21}&l_{22}&\cdots&0 \\ \vdots&\vdots&\ddots&\vdots \\ l_{m1}&l_{m2}&\cdots&l_{mm} \end{array} \right] \end{align*} \]
を満たす下半三角行列である。コレスキー分解は以下のアルゴリズムで手前の列\(\small j\)から順番に求めることができる。
\[ \small \begin{align*} &l_{jj} = \sqrt{ 1 -\sum_{k=1}^{j-1} l_{jk}^2} \qquad \qquad \quad \;\; \\ &l_{ij} = \frac{1}{l_{jj}} \left( \rho_{ij} -\sum_{k=1}^{j-1} l_{ik} l_{jk} \right), \;\; i > j \end{align*} \]
独立な標準正規分布に従う乱数\(\small w_1,w_2,\cdots, w_m\)と相関行列のコレスキー分解\(\small L\)を用いて、
\[ \small x = \left[ \begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_m \end{array} \right] = \left[ \begin{array}{cccc} l_{11}&0&\cdots&0 \\ l_{21}&l_{22}&\cdots&0 \\ \vdots&\vdots&\ddots&\vdots \\ l_{m1}&l_{m2}&\cdots&l_{mm} \end{array} \right] \left[ \begin{array}{c} w_1 \\ w_2 \\ \vdots \\ w_m \end{array} \right] \]
と計算すれば、\(\small x_1,x_2,\cdots,x_m\)は相関行列\(\small \Sigma\)の\(\small m\)次元標準正規分布に従う乱数になる。これを繰り返すことで多変数の正規分布に関するモンテカルロシミュレーションを実行することができる。
例：テキサスホールデム
ドローポーカーに慣れている人は、テキサスホールデムにおけるうまい賭け方に慣れるのに時間がかかるかもしれない。というのも、ドローポーカーと比較してテキサスホールデムにおける勝利確率の推測というのは大分様相が異なるからである。例えば、ストレートやフラッシュができれば強い役であるため、勝ちやすいと思うかもしれないが、共通カードから4枚使っている場合、他のプレイヤーもフラッシュやストレートになる確率が高いため、勝利確率が低い場合がある。反対に、ワンペアなどでも共通カードがバラバラで役がほとんどできそうもない場合は非常に勝利確率が高い場合がある。こういった勝利確率の推測に慣れるだけでも、相応には強いプレイヤーになれるかもしれない。
しかし、闇雲にプレイしているだけだとこの勝利確率の感覚をつかむことが容易ではない側面がある可能性がある。前回の投稿でテキサスホールデムのカードの組み合わせはプレイヤーが4人の場合、
\[ \small {}_{52}C_5\times{}_{47}C_2\times{}_{45}C_2\times{}_{43}C_2\times{}_{41}C_2 = 2.0595 \times 10^{18} \]
だけ組み合わせがあると説明した。例えば、プリフロップの段階では
\[ \small {}_{50}C_5\times{}_{48}C_2\times{}_{46}C_2\times{}_{44}C_2 = 2.34 \times 10^{15} \]
通りの組み合わせがあるし、フロップの段階では
\[ \small {}_{47}C_2\times{}_{45}C_2\times{}_{43}C_2\times{}_{41}C_2 = 7.924 \times 10^{11} \]
通りの組み合わせが存在する。そのため、厳密に勝利する確率を計算するということは非常に困難であると推測できる。繰り返しプレイすることで感覚的に確率を覚えようという方法は、アプローチとして効率が非常に悪いものであることが理解できるだろう。
しかし、すべての組み合わせを計算しなくても、モンテカルロシミュレーションでカードをランダムに生成し、一定の回数シミュレーションすれば大体の確率に収束することが期待できるだろう。実際に試してみると、1万回から10万回ぐらいのシミュレーションを行えば、確率はほぼ収束するように見える。したがって、すべての組み合わせを計算しなくても、手札や共通カードから勝利する確率を推定することは比較的容易に行うことができる。手札や共通カードの組み合わせから勝利確率を推測する感覚を身に着けるには、実際にシミュレーションで計算した確率を見て覚えた方がよほど効率的であるかもしれない。実際に実装したプログラムは以下のページに置いておくので、試してみたい方は試してみるとよいだろう。
