乱数について考える

1 ：名無しさん＠お腹いっぱい。：2011/06/16(木) 15:04:38.73 ID:0UPIgSTh0.net

線形合同法やメルセンヌツイスターみたいな擬似乱数や
そうじゃない乱数も考えよう

11 ：名無しさん＠お腹いっぱい。：2011/06/19(日) 23:57:51.53 ID:LEcKXzV40.net

>>10
素晴らしい。
でも、πが乱数としての要件を満たすかどうかは別問題。
しかし、仮にπが乱数として機能していなかったと仮定しても、πに周期性はない。
つまり、πは周期性の無いデータとして活用できる事になる。

ここで、"周期"と"疑似乱数"という情報を別々に考えてみよう。
つまり、πを計算するチューリングマシンと、一般的な疑似乱数を計算するチューリングマシン2つを用意してみよう。
つまり、この2つの計算結果を入力できる多テープチューリングマシンを考えると言う事だ。

これでもう分るな。

12 ：名無しさん＠お腹いっぱい。：2011/06/20(月) 01:54:28.98 ID:oY/pV47+0.net

「乱数」に何を求めるかで「乱数とは何か？」という問いに対する答えはガラッと変わる

単にどの数（例えば10進展開だと０〜９）も同じ出現頻度だということを乱数に求めるならば円周率πの10進展開も立派な乱数
モンテカルロ法を用いた数値積分で素直な関数を数値積分する場合のモンテカルロ法に用いる乱数なんかはそれでもOK
だけど例えば暗号プロトコルなどで用いる乱数は相手が規則性を見抜いて破れないことが重要だから
アルゴリズム性が強いものはアウトなのでπの展開なんてのは論外
一番良いのは放射性物質に向けたガイガーカウンタの一定時間内のカウント数みたいに本質的にランダムな自然現象を乱数生成のソースにすること

UNIXのrand関数の出す「乱数」は偶数と奇数とが交代で出てくる極めて規則的な数列なので暗号用なんかには論外もいいところだが
モンテカルロ法による数値積分ならばあれでも十分に使い物になる場合も多い

13 ：名無しさん＠お腹いっぱい。：2011/06/20(月) 15:02:05.47 ID:frGl6khw0.net

>単にどの数（例えば10進展開だと０〜９）も同じ出現頻度だということを乱数に求めるならば円周率πの10進展開も立派な乱数
この主張は危険。

じゃあこれも乱数生成器か?
#include <stdio.h>

void main(void){
　unsigned int i;

　for(i=0;1;i++){
　　printf("%d,",i%10);
　}
}

単に 0,1,2,3,4,5,6,7,8,9,0,1,2,3,4......と繰り返されるだけのものも乱数になってしまう。

あと、πの10進展開で0〜9の数字の出現頻度が極限で等しくなるという証明はあるの?

14 ：名無しさん＠お腹いっぱい。：2011/06/20(月) 15:14:03.57 ID:frGl6khw0.net

それと、私は単に周期の無い疑似乱数をチューリングマシン上で生成できると主張しているだけな。

暗号用の奴なんて大体周期あるんじゃないか?

私は周期の無い疑似乱数は作れないという考え方を私は改めてほしいんだよ。

何処の研究者の本も口を揃えて無理と書いてあるけどさ。

15 ：名無しさん＠お腹いっぱい。：2011/06/20(月) 15:16:30.34 ID:DSAmwjwB0.net

>>13 一応現在考えられてるほとんどの検定に、πとかeとか√2はみんなパスするとは思うけど。

>>11 普通に考えるところの疑似乱数生成系は有限の内部記憶を前提としてますので。以上。

16 ：名無しさん＠お腹いっぱい。：2011/06/20(月) 18:44:03.94 ID:AEH2P24V0.net

>>15
>一応現在考えられてるほとんどの検定に、πとかeとか√2はみんなパスするとは思うけど。
証明されていない事は危険。

>普通に考えるところの疑似乱数生成系は有限の内部記憶を前提としてますので。以上。
生成する桁数が有限なら、領域計算量も有限にできるでしょ?
あと、極論を言えば領域計算量も桁数nに対してO(loglogloglogloglogloglogloglogloglogloglogloglogloglogloglogloglogloglogloglog n)に抑える事だって可能。
無限の疑似乱数を生成するなら話は別だが。

17 ：名無しさん＠お腹いっぱい。：2011/06/20(月) 22:33:11.59 ID:NLymxfIV0.net

>>16
「現在考えられてるほとんどの検定」ってのがザルだという噺では？
厳密な証明は不可能であるって、Algorithmic Information Theory が示している事だと思いまする。

18 ：名無しさん＠お腹いっぱい。：2011/06/21(火) 00:55:22.10 ID:XmMJPd4L0.net

まぁ、無理数を応用した疑似乱数も立派な疑似乱数なので、周期の無い疑似乱数をTM上で作れないという主張が間違いなのは事実。

>>17
参考文献は??

もしかしてこれ??
http://www.amazon.co.jp/Algorithmic-Information-Cambridge-Theoretical-Computer/dp/0521616042

私は不可能なんて話初耳だ。
不可能だと証明されているのだろうか??

19 ：名無しさん＠お腹いっぱい。：2011/06/21(火) 17:34:38.69 ID:WXXbJOcU0.net

普通疑似乱数生成系に無理数とかは含めないとは思うけどな。

疑似乱数列って定義的に無限の長さを前提とするんじゃない？
だから2の何万乗というオーダーであっても「循環する」って言ってると思うんだけど。

乱数の検定ってのは基本的には証明するもんじゃない。
証明できるものもあるけど。

20 ：名無しさん＠お腹いっぱい。：2011/06/21(火) 19:20:59.73 ID:MjoDb62X0.net

>>19
貴方の言う疑似乱数の定義は
>一般に疑似乱数を定義するのに使う、内部状態ベクトルと、それを更新する関数、
>というモデルでは不可能だと思うが。
で合っているの??

じゃあ、その疑似乱数生成器が生成した疑似乱数列と無理数の各桁の排他的論理和を取ったものを、
結果として出力するという疑似乱数生成器は、周期性が無く、上の定義にも合致するが??

それとも無理数を応用した疑似乱数生成器は疑似乱数生成器ではないと??

じゃあこれは何?
疑似乱数じゃないなら何?
私は世界で初めて新たな何かを発見してしまったの??

もしも、これが疑似乱数であるならば、周期の無い疑似乱数をTM上で作れないという主張が間違いなのは紛れも無い事実なんですが。

>疑似乱数列って定義的に無限の長さを前提とするんじゃない？
>だから2の何万乗というオーダーであっても「循環する」って言ってると思うんだけど。
それは、"非常に大きな有限の数"を前提にしても成立するが?
計算量等では"無限"ではなく"非常に大きな有限の数"を前提にして考える機会が多いと思うが。
"無限"にしてしまうと色々問題が出てくる場合があるんで。
頭の中で考える時に"無限"として考える分には問題無いかもしれないが、議論の場で"無限"とか簡単に口にするとボロクソに叩かれる事ありますよ。