モンテカルロ法とシミュレーション

「モンテカルロ法とシミュレーション」　津田孝夫著
この本のp36、7行目～p37、2行目は、M系列について以下のように説明しています。

～～～～～～～～～～～～～～～～～～～～
【Ａ】最大周期列（M系列）
ガロア体GF(q)のn次多項式f(x)が原始的(primitive)であるとき、最大周期q^n-1をもつ数列をf(x)より生成できる。

(中略)

GF(2)で要素{0,1}のみを対象とするとき、
ある固定したmについて

s[0]=a[0]、s[1]=a[1]、・・・、s[m-1]=a[m-1]　　（[・]は添え字を表すこととします。）

を与えると、mod2の線形漸化式

f[0]s[i]+f[1]s[i-1]+・・・+f[m]s[i-m]=0　　(mod2)　　(2･27)
（i=m、m+1、m+2、・・・　;　f[m]≠0、f[0]≠0）

より、要素{0,1}の無限数列

s={s[0]、s[1]、s[2]、・・・、s[m-1]、s[m]、・・・}　　　　(2･28)

が順次（再帰的に）得られる。

ここで

s[j]∈GF(2)、f[k]∈GF(2)　（j=0、1、2、・・・、m、m+1、・・・; k=0、1、2、・・・、m）

すなわち、ともに、0または1の数である。

(2･27)に対し、多項式

f(x)=f[0]+f[1]x+f[2]x^2+・・・f[m]x^m　　（f[0]=f[m]=0）　　(2･29)
をその特性多項式といい、無限数列(2･28)は、多項式(2･29)より生成されるという。

～～～～～～～～～～～～～～～～～～～～

ところが、(2･27)の線形漸化式では、M系列は生成されません。
以下の漸化式でなければならないのです。

f[0]s[i-m]+f[1]s[i-m+1]+f[2]s[i-m+2]+・・・+f[m-1]s[i-1]+f[m]s[i]=0　　　(ｱ)

この本の初版は　昭和44年6月20日、改訂版は　昭和52年11月15日、　改訂版第3刷が昭和55年10月30日にでています。

初版は50年前に、改訂版第3刷でも40年前のものです。
今さら気づいても、どうにもならないでしょうし、こんな古い本で勉強するする人も、もはやいないでしょうし。

そもそもコンピュータを使うのであれば、線形漸化式より、特性多項式からのM系列生成が本流というものです。
誰も線形漸化式を使って数列を計算してみようなどとは思わなかったのでしょう。「ふむふむ」と一瞥して次の段階に移行していったのでしょう。

50年経って、ようやく物好きが現れて、計算してみたら「あれ？」ってなことになったのですね。

メデタシ、メデタシ。

ちなみに、
m=5、初期値{11111}、f[0]=f[2]=f[5]=1、f[1]=f[3]=f[4]=0　としたときに、

(2･27)で算出した数列（1周期分）は、
s→1、1、1、1、1、0、0、1、1、0、1、0、1、1、1、0、1、1、0、0、0、1、1、1、1、1、0、0、1、1、0。

一方、(ｱ)で算出した数列（1周期分）は、
s→1、1、1、1、1、0、0、0、1、1、0、1、1、1、0、1、0、1、0、0、0、0、1、0、0、1、0、1、1、0、0。

これらを、本書p39、12行目に例として示されている原始多項式

f(x)=x^5+x^2+1　　　　(2･33)

初期値s[0]=s[1]=s[2]=s[3]=s[4]=1

から算出される最初の1周期分の数列
s[i]→1、1、1、1、1、0、0、0、1、1、0、1、1、1、0、1、0、1、0、0、0、0、1、0、0、1、0、1、1、0、0。

と比較すると、(ｱ)から算出された数列に一致することが分かります。

ヨカッタ、ヨカッタ。