乱数の生成アルゴリズムとその応用|問題演習で理解する統計学【8】

下記などで取り扱った、乱数の生成に関する問題演習を通した理解ができるように問題・解答・解説をそれぞれ作成しました。
https://www.hello-statisticians.com/explain-terms-cat/random_sampling1.html

基本問題

線形合同法・乗算型合同法

・問題
線形合同法(linear congruential method)は1948年頃にレーマー(Lehmer)が提案した手法で、仕組みがシンプルであるので乱数生成のイメージを掴むにあたって適した手法である。また、乗算型合同法は線形合同法の特殊な場合と考えられるので、両者は同時に理解することができる。
さて、線形合同法を理解するにあたっては、「整数に関する合同」と「数列の漸化式」の理解があれば十分であると思われる。以下の問題に答えよ。
i) $x_{n+1} = x_{n} + 2, x_1 = 1$のように表せるとき、$x_2, x_3$を求めよ。
ⅱ) $x_{n+1} = 2x_{n} + 1, x_1 = 1$のように表せるとき、$x_2, x_3$を求めよ。
ⅲ) 合同は「整数$x$を整数$M$で割った時の余りが等しいか」を表す概念である。このときの$M$を法(modulus)という。たとえば2と5は3で割った際にどちらも余りが2であるので、3を法とするとき合同であるといえる。このことは「$2 = 3 \quad (mod 3)$」のように表すことができる。
上記に基づいて、法を5とするときに2と合同な自然数を5つ答えよ。
iv) 9を法とするとき、$x_{n+1}=4x_{n}+2 \quad (mod 9), x_1=1$に従って$x_2, x_3$を求めよ。
v) iv)の例の$x_4$以降を計算すると下記のようになる。
$$
\begin{align}
x_4=7, x_5=3, x_6=5, x_7=4, x_8=0, x_9=2, x_{10}=1, x_{11}=6, x_{12}=8
\end{align}
$$
上記には周期があると考えることができるが、どのような周期か答えよ。

・解答
i)
$x_2, x_3$は下記のように求めることができる。
$$
\begin{align}
x_2 &= x_{1} + 2 \\
&= 1 + 2 \\
&= 3 \\
x_3 &= x_{2} + 2 \\
&= 3 + 2 \\
&= 5
\end{align}
$$

ⅱ)
$x_2, x_3$は下記のように求めることができる。
$$
\begin{align}
x_2 &= 2x_{1} + 1 \\
&= 2 + 1 \\
&= 3 \\
x_3 &= 2x_{2} + 1 \\
&= 6 + 1 \\
&= 7
\end{align}
$$

ⅲ)
$$
\begin{align}
7, 12, 17, 22, 27
\end{align}
$$

iv)
$$
\begin{align}
x_2 &= 4x_{1} + 2 \\
&= 4 + 2 \\
&= 6 \\
x_3 &= 4x_{2} + 2 \\
&= 24 + 2 \\
&= 26 \\
&= 8 \quad (mod 9)
\end{align}
$$

v)
$x_1$〜$x_9$と$x_{10}$〜$x_{18}$は一致し、これを周期とみなすことができる。線形合同法の計算の仕組み上、1度でも同じ値が出てくると以後の値は周期的に繰り返す。

・解説
線形合同法は「整数の合同」と「数列の漸化式」について理解していればそれほど難しくない手法だと思います。乗算合同法は線形合同法の定数項がないパターンであり、重複した値が得られやすい一方で計算コスト自体は低いため、合わせて抑えておくと良いと思います。
線形合同法、乗算型合同法の数式は下記でまとめたので、詳しくは下記も参照してみてください。
https://www.hello-statisticians.com/explain-terms-cat/random_sampling1.html

M系列

正規分布に従う乱数の生成

発展問題

モンテカルロ積分

MCMC

参考書籍

・自然科学の統計学(東京大学出版)