第 3 章 発散，収束，周期性 20
3.4 整数ロジスティック写像の周期性
3.4.3 非周期状態長
整数ロジスティック写像が初期値X0から生成できる非周期状態長は`+Sと なる．任意に選ばれた初期値が落ち入るループも異なり，リーダー長`も異なる のは一般的である．整数ロジスティック写像を用いて乱数生成システムを設計 するとき，計算精度と得られる平均的な非周期状態長の関係を知る必要がある．
整数ロジスティック写像において，計算精度9∼16ビットのときの周期長と リーダー長の平均値が既に示されている[18]．しかし，整数ロジスティック写像 を用いて乱数を生成する際に，初期値はランダムに選ばれることは一般に考え られる．そのとき，選ばれた初期値で生成される順軌道が落ち入るループは，最 頻度のループになる確率が最も高い．平均的な非周期状態長を求めるとき，こ のことを考える必要がある．
計算精度と得られる平均的な非周期状態長の関係を求める最も単純な方法は，
3.4. 整数ロジスティック写像の周期性 モンテカルロ法によって実現できる．たとえば，ランダムにM個の初期値を選 び，それぞれの初期値から生成される順軌道に対し，リーダー長と周期長を求 め，総数M の平均を求めるとよい．
ある初期値X0から得られる順軌道が持つリーダー長と周期長を求めるには，
その初期値が持つリーダー長は未知であるため，これを推定する必要がある．そ れを推定リーダー長と呼び，`0で表す．ループはt≥`からなるため，`0 < `の 時は，ループは検出できない．リーダー長と周期長を求めるアルゴリズムLS1 は以下のようになる．
アルゴリズムLS1
入力：計算精度N，初期値X0．出力：リーダー長`，周期長S．
1. `0 = 2N/2+1と設定する．
2. 整数ロジスティック写像を初期値X0から`0回計算してX`0 を得る．
3. 引き続き，整数ロジスティック写像を繰返し計算し，X`0 =X`0+Sとなった 時点で，周期長Sのループが検出される．
4. X`0+Sから逆へ，X`0−i 6=X`0+S−iとなる最小のiを見つけ，リーダー長` =
`0−iが得られる．
5. `とSを出力する． ¤ ただし，上のアルゴリズムLS1において，ステップ4の比較を行うためには，
あらかじめステップ2で求められたX0, . . . , X`0 と，ステップ3で求められた X`0+1, . . . , X`0+Sを記録しておく．また，ステップ1での`0の設定においては，
節3.4.2の実験と同じ条件で，最大リーダー長を求めた結果（付録C参照）に
より，` <2N/2+1を得ている．
こうして，一つのX0に対し，対応する正確なリーダー長が求まる．さらに，
X0をランダムに選べば，モンテカルロ法により平均的なリーダー長を求める ことができるが，計算精度Nが大きいと，ステップ4の比較を行うための計算 量とステップ2の記録のために必要のメモリがN の指数関数的に増大し，実現
第3章 発散，収束，周期性
は難しい．そこで，本節は計算量と必要のメモリを減らすために，正確なリー ダー長を求めず，平均リーダー`を推定する方法を取る．アルゴリズムLS2は 以下のようになる．
アルゴリズムLS2
入力：計算精度N，初期値X0．出力：推定リーダー長`0，周期長S． 1. L= 2N/2+1を設定する．
2. アルゴリズムLS1のステップ2と3に基づき，ループを検出する．
3. L=L/2にして，ステップ2，3をループが検出できなくなるまで繰り返す．
4. `0 = 2LとSを出力する． ¤ こうすると，M 個の初期値Xi(i= 1, . . . , M)に対し，アルゴリズムLS2を 適用して，得られた出力を`0iとおく．すべての初期値において，`iをXiとした 場合のリーダー長とすると，必ずしも正確なリーダー長は求められないが，`i
とアルゴリズムLS2の出力`0iの間に，
`0i/2< `i < `0i
の関係が成立つ．そこで，近似的な平均リーダー長`を
` = XM
i=1
1
M3`0i/4 (3.22)
で与える．式(3.22)で与える近似的な平均リーダー長と実際の`との誤差`−` は，
− XM
i=1
1
M`0/4∼ XM
i=1
1 M`0/4 にあることが分かる．
計算精度N = 36 ∼ 72に対し，初期値の数M は，表3.3と同様にして，` の値を求めた結果を図3.7に示す．図3.7において，横軸は計算精度N，縦軸
3.4. 整数ロジスティック写像の周期性
図 3.7: 計算精度と平均リーダー長`の関係．
は近似的な平均リーダー長`に底２の対数を取った値である． なお，同図中，
f1(N) =N/2−1を実線で表示している．
それぞれの計算精度で求まった複数のループの中，最も長い周期長をもつルー プを最長周期SLと呼び，最頻度のループを最多周期SM と呼ぶことにして，そ れぞれ計算精度との関係を図3.8に示す．
図3.8において，横軸は計算精度N，縦軸は(a)に最長周期の長さ，(b)に最 多周期の長さに，それぞれ底２の対数を取った値を示す． 図3.8(a)と(b)にお いて，それぞれf2(N) =N/2−2とf3(N) =N/2−3を実線で示している．
以上の結果より，最長周期長，最多周期長，平均リーダー長`は計算精度N と近似的に，図3.7と3.8に示すように，
SL≈2N/2−2
SM ≈2N/2−3
` ≈2N/2−1 で表せることがわかる．
整数ロジスティック写像の非周期状態長（`+S）の推定値Lcとして，M個 のランダムな初期値に対してアルゴリズムLS2を適用して求められた`とSM
第3章 発散，収束，周期性
図 3.8: 最長周期長(a)，最多周期長(b)と計算精度N の関係．
を用いて，
Lc = `+SM (3.23)
とおく．
SM ≈2N/2−3，`≈2N/2−1なので，すると，上述の実験結果から，
Lc≈5×2N/2−3 で与えられる．