2011年11月2期11: 乱数について考える (60) TOP カテ一覧 スレ一覧 2ch元 削除依頼

乱数について考える


1 :11/06/16 〜 最終レス :11/10/27
線形合同法やメルセンヌツイスターみたいな擬似乱数や
そうじゃない乱数も考えよう

2 :
人が乱数に使うものは乱数ではなく擬似乱数である。
なぜなら次の出目の確率は予測可能である。
つまり完全に予測困難なものではない。
完全な予測困難性をもつものを人は乱数とは認めたくない故に
ホワイトノイズのような特定の性質をもったものを乱数としているだけ。
そして有限の矩形を切り取った乱数列を人が求め、それを乱数と
認識したがっている。
完全な予測困難性があるならば有限ではなく無限数列となるわけな。
一般の乱数の答えは出ている。カオスを利用した事実上周期が見えない
超長周期の大きなデータ値を扱えるものである。基本はどれも二重振り子
の原理の延長にすぎない。
真の乱数であるならば、たとえ同じ結果が1億回続いたとしても
それを超える無限の流れの1つであるならば別に問題はないわけです。
次に得る乱数が連続してはいけないというルールなど人が決定している
だけの理屈にすぎない。それこそ擬似乱数である。

3 :
意味不明な文を連ねてるなぁと思えば。
たとえ1億回、ってw たった10^8ぽっちの数を持ち出してくるあたりが頭の弱さを物語ってますな。
たとえばメルセンヌツイスタの周期は2^19937だし、二重振り子の原理なんかじゃない。
ちゃんと勉強してから出直せ、以上。

4 :
>一般の乱数の答えは出ている。カオスを利用した事実上周期が見えない
>超長周期の大きなデータ値を扱えるものである。基本はどれも二重振り子
>の原理の延長にすぎない。
考え付かないなら教えておくが、チューリングマシン上で完全に周期性の無い乱数を生成することは可能だからな。
>真の乱数であるならば、たとえ同じ結果が1億回続いたとしても
>それを超える無限の流れの1つであるならば別に問題はないわけです。
但し、実質無限の乱数を生成した場合に十分な一様性が無いと問題かもな。
同じ結果が1億回続いても問題無いかどうかは、問題無い事を証明出来てからの話だな。
>次に得る乱数が連続してはいけないというルールなど人が決定している
誰がそんな事決定したんだよ?
あと、理論ってものは定義を元に発展させていくものだと思うぞ。
その定義は人が決めないとダメだろ。
>だけの理屈にすぎない。それこそ擬似乱数である。
貴方の決定した疑似乱数の定義じゃあ、様々な理論が崩壊しそうで心配だお。(´・ω・`)

5 :
一応訂正

>考え付かないなら教えておくが、チューリングマシン上で完全に周期性の無い乱数を生成することは可能だからな。

考え付かないなら教えておくが、チューリングマシン上で完全に周期性の無い疑似乱数を生成することは可能だからな。

6 :
> チューリングマシン上で完全に周期性の無い疑似乱数を生成することは可能
どうやるんだ?
一般に疑似乱数を定義するのに使う、内部状態ベクトルと、それを更新する関数、
というモデルでは不可能だと思うが。

7 :
>>6
ヒント:チューリングマシンのメモリは無限。
これでも分らなかったら答え晒すわ。

8 :
無限に大きくなる数列?

9 :
>>8
その数列の集合の中にはその数列を応用する事で周期性の無い疑似乱数になり得るものもあると思うので、
それも一つの答えとして間違いではないと思います。

10 :
例えば円周率πの値を計算するプログラムとか?

11 :
>>10
素晴らしい。
でも、πが乱数としての要件を満たすかどうかは別問題。
しかし、仮にπが乱数として機能していなかったと仮定しても、πに周期性はない。
つまり、πは周期性の無いデータとして活用できる事になる。
ここで、"周期"と"疑似乱数"という情報を別々に考えてみよう。
つまり、πを計算するチューリングマシンと、一般的な疑似乱数を計算するチューリングマシン2つを用意してみよう。
つまり、この2つの計算結果を入力できる多テープチューリングマシンを考えると言う事だ。
これでもう分るな。

12 :
「乱数」に何を求めるかで「乱数とは何か?」という問いに対する答えはガラッと変わる
単にどの数(例えば10進展開だと0〜9)も同じ出現頻度だということを乱数に求めるならば円周率πの10進展開も立派な乱数
モンテカルロ法を用いた数値積分で素直な関数を数値積分する場合のモンテカルロ法に用いる乱数なんかはそれでもOK
だけど例えば暗号プロトコルなどで用いる乱数は相手が規則性を見抜いて破れないことが重要だから
アルゴリズム性が強いものはアウトなのでπの展開なんてのは論外
一番良いのは放射性物質に向けたガイガーカウンタの一定時間内のカウント数みたいに本質的にランダムな自然現象を乱数生成のソースにすること
UNIXのrand関数の出す「乱数」は偶数と奇数とが交代で出てくる極めて規則的な数列なので暗号用なんかには論外もいいところだが
モンテカルロ法による数値積分ならばあれでも十分に使い物になる場合も多い

13 :
>単にどの数(例えば10進展開だと0〜9)も同じ出現頻度だということを乱数に求めるならば円周率πの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 :
それと、私は単に周期の無い疑似乱数をチューリングマシン上で生成できると主張しているだけな。
暗号用の奴なんて大体周期あるんじゃないか?
私は周期の無い疑似乱数は作れないという考え方を私は改めてほしいんだよ。
何処の研究者の本も口を揃えて無理と書いてあるけどさ。

15 :
>>13 一応現在考えられてるほとんどの検定に、πとかeとか√2はみんなパスするとは思うけど。
>>11 普通に考えるところの疑似乱数生成系は有限の内部記憶を前提としてますので。以上。

16 :
>>15
>一応現在考えられてるほとんどの検定に、πとかeとか√2はみんなパスするとは思うけど。
証明されていない事は危険。
>普通に考えるところの疑似乱数生成系は有限の内部記憶を前提としてますので。以上。
生成する桁数が有限なら、領域計算量も有限にできるでしょ?
あと、極論を言えば領域計算量も桁数nに対してO(loglogloglogloglogloglogloglogloglogloglogloglogloglogloglogloglogloglogloglog n)に抑える事だって可能。
無限の疑似乱数を生成するなら話は別だが。

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

18 :
まぁ、無理数を応用した疑似乱数も立派な疑似乱数なので、周期の無い疑似乱数をTM上で作れないという主張が間違いなのは事実。
>>17
参考文献は??
もしかしてこれ??
http://www.amazon.co.jp/Algorithmic-Information-Cambridge-Theoretical-Computer/dp/0521616042
私は不可能なんて話初耳だ。
不可能だと証明されているのだろうか??

19 :
普通疑似乱数生成系に無理数とかは含めないとは思うけどな。
疑似乱数列って定義的に無限の長さを前提とするんじゃない?
だから2の何万乗というオーダーであっても「循環する」って言ってると思うんだけど。
乱数の検定ってのは基本的には証明するもんじゃない。
証明できるものもあるけど。

20 :
>>19
貴方の言う疑似乱数の定義は
>一般に疑似乱数を定義するのに使う、内部状態ベクトルと、それを更新する関数、
>というモデルでは不可能だと思うが。
で合っているの??
じゃあ、その疑似乱数生成器が生成した疑似乱数列と無理数の各桁の排他的論理和を取ったものを、
結果として出力するという疑似乱数生成器は、周期性が無く、上の定義にも合致するが??
それとも無理数を応用した疑似乱数生成器は疑似乱数生成器ではないと??
じゃあこれは何?
疑似乱数じゃないなら何?
私は世界で初めて新たな何かを発見してしまったの??
もしも、これが疑似乱数であるならば、周期の無い疑似乱数をTM上で作れないという主張が間違いなのは紛れも無い事実なんですが。
>疑似乱数列って定義的に無限の長さを前提とするんじゃない?
>だから2の何万乗というオーダーであっても「循環する」って言ってると思うんだけど。
それは、"非常に大きな有限の数"を前提にしても成立するが?
計算量等では"無限"ではなく"非常に大きな有限の数"を前提にして考える機会が多いと思うが。
"無限"にしてしまうと色々問題が出てくる場合があるんで。
頭の中で考える時に"無限"として考える分には問題無いかもしれないが、議論の場で"無限"とか簡単に口にするとボロクソに叩かれる事ありますよ。

21 :
>>11
パイを最後まで計算できると過程した脳内妄想での話しで
それはチューリングマシンがデジタル値を使い
リアル値も扱えるといっているのと同じ、
実用として使えない円周率では、実用で使った範囲で周期性をもつのは
明白だろう。どんな方法でやってもその計算の限界で周期性は現れるし
人が乱数という特徴を乱数の一部を切り取って判断する限り、それは不完全な
擬似乱数を超えることはできない、人が神を定義できないようにそんなこと
できると言い張るほうがアフォくさい。

22 :
乱数について定義したものはいないが、コンピュータ上で使う
乱数とは人がアプリケーションで利用するのに都合の良い
規則性やら周期性が見えてこないことである。
それが重要であって真の乱数とか哲学のようなもの、定義した奴も
いるが簡単なのは次にでる値は予測不可能でルールが適用不可能と
証明されること。

23 :
じゃあ何?
そんなに「俺が通説をひっくり返した」と自慢したいなら学会に論文として投稿すれば、って感じだな。

24 :
>>21
申し訳ないが、全体的に何を言いたいのか上手く理解できない。
"無理数を応用すれば、周期性の無い疑似乱数を生成出来る"という事は紛れもない事実ですよね??
それを無理という主張は間違いである事も事実ですよね?
何がおかしいの??
有限のメモリ上で無限桁生成できなければならないなんていう定義が疑似乱数生成器にあるならば話は別だが、そんな話このスレ見て初めて言われたよ。
生成する桁数が有限桁である以上有限のメモリで周期性の無い乱数は作れますがな。
勝手に有限のメモリで無限桁生成できないといけないとか定義するなって話なんだが。。。
いつだがあった数学板の乱数スレとは偉いクオリティの差だな。
とりあえず、有限のメモリで無限桁生成できなければならないという疑似乱数生成器の定義はどっから引っ張り出して来たんだ??
実用っていっても、実用上であるんだったら無限桁疑似乱数を生成する事だってあり得ない思うが??
あと、神なんて人が定義したものでしょ。
その定義は人それぞれ違うでしょうが。
神が人を創ったのではなく、人が神という幻想を創りだしたのさ。
それこそ、脳内妄想の世界。

25 :
>>22
"暗号技術入門 秘密の国のアリス"という書籍では、
無作為性:統計的に隔たりが無く、でたらめな数列になっているという性質。
予測不可能性:過去の数列から、次の数を予測できないという性質。
再現不可能性:同じ数列を再現出来ない性質。
が紹介されてたな。
最低限無作為性が満たされていれば疑似乱数と呼んでいいらしい。

26 :
>>23
そういえば、以前ネタで"世界初"とか謳って公開したら某雑誌に載ったな。

27 :
>>25
>予測不可能性:過去の数列から、次の数を予測できないという性質。
真の乱数があるみたいなことを行っているバカはこれを全面否定
しているよ。
人が作り出す乱数はたとえ自然界であっても狭い範囲の抽出
さいころを生涯に2度だけふった目もそれは乱数であるという
そこに乱数の性質があるか?
真の乱数があるとすれば無限に続く意味のない問答のようなもの
どこかの部分だけを抽出して10回さいころを振ってどのどの目も
同じ確率だ、そして1万回、1億回ふってそれを確認しても同じ目の
確率だという、それは範囲が無限ではないから出目が歪んでいる
ことに気が付いていない。
一定の範囲での出目が乱数のように見えてもそれをミクロとして
マクロ的な位置から全体を見れば性質がでてくるもの。
範囲(有限回)で語る乱数は人の都合のよい乱数であり、デジタルで
アナログを近似するのと同じ。どこまで突き詰めても擬似乱数である。
誤差が利用する値より小さいならば、誤差は存在しないという考えかた
である。

28 :
>>13
> 単にどの数(例えば10進展開だと0〜9)も同じ出現頻度だということを乱数に求めるならば円周率πの10進展開も立派な乱数
> この主張は危険。
・・・
> 単に 0,1,2,3,4,5,6,7,8,9,0,1,2,3,4......と繰り返されるだけのものも乱数になってしまう。
ああスマン。筆というかキーボードが滑った
正確には1桁だけじゃなくて「任意の有限桁数についてその桁数の全ての数の出現頻度が漸近的に(数列を長く取れば取るほど)等しくなる」(★)と書くべきだった
π(や恐らくeも)はその性質(★)を満たしてたと思うがソースは覚えてない

29 :
>>24
誰にも相手にしてもらえないだろ、それあまりにも根拠がない
感情論とかだから女の腐ったのと同じ理屈ってこと。
冷めても自覚できないなら統合失調症の可能性があるぞ。

30 :
真の乱数とは単に完全に予測不可能だと証明できるものでいいはず。
そしてそれを証明することはできないもの現実。
人が作った乱数は人が乱数利用として都合のよい形態であり特徴を
持っているわけで、良い乱数と悪い乱数としたときに悪い乱数という
特徴を持っていないという特徴があるのは明白であり、それを確率的に
予測することは可能であります。

31 :
女の腐ったの、とかいう形容を使う奴もロクでもないことが大半だが

32 :
test

33 :
>>30
> 真の乱数とは単に完全に予測不可能だと証明できるものでいいはず。
>
> そしてそれを証明することはできないもの現実。
その主張は理解できるが不正確だな。
本質的に確率が絡む量子力学に基づく自然現象、例えば宇宙線などの自然放射線を計測器で測って得られる信号は
量子力学はミクロの現象を支配しているという命題を数学上の公理として認めれば、完全に予測不可能と証明できる。
そしてその命題、量子力学がミクロの世界の現象の基本法則でありミクロ世界の現象は本質的に確率的だ、という命題に
疑問を抱かせるどのような経験的事実も知られていない。
むしろ、物理現象は本質的に確率的だという意味で非決定論に立つ量子力学を受け入れられないアインシュタインのような人間のために
量子力学に対抗する決定論の頼みの綱として期待されたボームに始まる隠れた変数理論の方は、アスペの実験などの事実から
「もしも隠れた変数理論が正しいとしても、それは容易には受け入れがたい…局所性の放棄が必要な…代物だ」という事は既に検証済み。
> 人が作った乱数は人が乱数利用として都合のよい形態であり特徴を
> 持っているわけで、良い乱数と悪い乱数としたときに悪い乱数という
> 特徴を持っていないという特徴があるのは明白であり、それを確率的に
> 予測することは可能であります。
ここは意味不明。
人が作る「乱数」(正しくは疑似乱数と呼ぶべき)がアルゴリズムで作られる限りにおいて、
その疑似乱数生成のアルゴリズムが知られればそれだけで破られる(予測される)可能性がぐんと高くなる。
ただし破られても良いような目的での乱数の使用(つまり数が一様に散らばってれば良い、例えばモンテカルロ法による数値積分とか)ならば
乱数が破られやすい(予測しやすい)か否かは別に問題でない。

34 :
>>33
人が作る乱数の連続集合は常に、有限の数の数列故に
その発生確率やら規則性を人から見た乱数のように捉えるから
擬似乱数になるだけ。
そもそも人に真の乱数など不要である、真の乱数の一部に規則性が
見えてもそれは長い周期の一部に低い確率として存在すること、
そんな確率も許されないなら擬似乱数でしかない。
人が定義した乱数はそういう人が乱数に見えるという特徴を有している
故に乱数の個々の1つは予測しえなくても特徴が連続することは予測
可能になってしまう。なぜならそれは乱数という特徴を人が作っている
からである。

35 :
>>34
>そもそも人に真の乱数など不要である
真の乱数がなければ実現が現実的に困難なアルゴリズムもあるけどな。
まぁ、それを説明したところで貴方はその重要性を理解できないだろうが。
>>33の思考回路は科学重視。
>>34の思考回路は工学重視。
大学の研究室では愛されるが、取っつきにくそうな人が>>33
職場でとりあえず仕事しそうなのは>>34
どっちが優れているとかそういう問題でも無いんだろうけど、>>1の趣旨からすれば>>33のような人種の方が好まれるんだろうな。

36 :
> 人が作る「乱数」(正しくは疑似乱数と呼ぶべき)がアルゴリズムで作られる限りにおいて、
> その疑似乱数生成のアルゴリズムが知られればそれだけで破られる(予測される)可能性がぐんと高くなる。
↑暗号の常識を全く知りません、と大声で宣伝してるだけだし。

37 :
結局、コンピューターで作る乱数は、全部カオスなんだよね

38 :
どこが?
たとえばM系列をカオスで説明してる論文か文献があるなら教えてほしいものだが。

39 :
>>38
放送大学で普通に放送している。

40 :
ヨコヤリだけど、M系列がカオス?
カオスがPseudo Noiseの一系譜、ならまぁまだ分かるんだけど。
そもそもカオスをよく知らないんだけど、明確な定義って何なの?
ただの出来の悪い数列ジェネレータというイメージなんだが。初期値鋭敏性は乱数に向いてる風だけど、変に周期持ってたりして乱数には使えないという。
エントロピー的に中途半端な状態に思える。
カオスの特徴って何かに利用できるんだろうか??

41 :
>>39
放送大学で普通に放送している内容を、また勝手にカオスなんだと変な解釈しているだけなんじゃね?

42 :
放送大学の内容であるなら、確か教科書を印刷してる筈だな。
どの教科書にそう書いてあるか指摘してくれ。

43 :
>>37>>39
http://ja.wikipedia.org/wiki/%E3%82%AB%E3%82%AA%E3%82%B9%E7%90%86%E8%AB%96
とりあえずこの程度の知識は身につけたほうが良い。

44 :
M系列も、数式で作っている乱数ならば、結局はカオスなんじゃないの?

45 :
俺はカオスっての良くわかんないけど、
http://ja.wikipedia.org/wiki/%E3%82%AB%E3%82%AA%E3%82%B9%E7%90%86%E8%AB%96には
カオス理論(カオスりろん、Chaos theory)は、力学系の一部に見られる、予測できない複雑な様子を示す現象を扱う理論である。
カオス力学ともいう。…(1)
また、カオスより擬似乱数を発生させることはできる…(2)
等が書かれている。
(2)に擬似乱数を発生させることはできると書かれている事が事実ならば、疑似乱数生成器の中にはカオスの要件を満たすものがあるって事だろう。
でも、(1)には予測できない複雑な様子を示す現象を扱うと書かれている。
問題になっているM系列は1BITの漸化式。
X[n]=X[n-p] XOR X[n-q] (p>q)
http://www.nagoya-bunri.ac.jp/~t-ymzm/rand/rand_index.html
つまり、式のp,qが分ってしまえば、簡単に予測出来るし、2*p-q桁目まで疑似乱数列を観測すれば100%次の桁を予測出来るし、元の式まで100%見切れてしまう。
だから、(1)の予測できない複雑な様子の定義からは外れるって事なんじゃない?

46 :
カオスだって漸化式なんだし、結果は決まってる。
M系列だってカオスだって、初期値が決まってれば、あとは計算回せば決まった値になる。

47 :
>>46
で、1bitのM系列は予測できない複雑な様子なの?

48 :
ttp://buturi.hiro.kindai.ac.jp/buturi/chaos/chaos.html より
> 「初期条件の微小な誤差が時間と共に急速に(指数関数的に)成長し続けることを、
> 初期値に関する鋭敏な依存性(SEDIC : Sensitive Dependence on Initial Conditions)という。
> SEDIC を示す系の振る舞いをカオス(Chaos)という。
M系列のふるまいは「微小な誤差が時間と共に急速に(指数関数的に)成長」するものではありません。
よって、M系列はカオスではありません。
以上。

49 :
指数関数的に、の部分はリアプノフ指数なりを計算して評価しろって事なんだろうね。
ただパイこね変換(テント写像)の左側を0、右側を1に対応づけると、カオスからビットストリームを作れますよね?このビットストリームのカオスっぽさは、どう評価すればいいの?

50 :
               ,, -―-、       
             /     ヽ
       / ̄ ̄/  /i⌒ヽ、|    オエーー!!!!
      /  (゜)/   / /
     /     ト、.,../ ,ー-、
    =彳      \\‘゚。、` ヽ。、o
    /          \\゚。、。、o
   /         /⌒ ヽ ヽU  o
   /         │   `ヽU ∴l
  │         │     U :l
                _ U ∴ ol
               / /∴ U :l
              |   | U o∴。l
              |   | : ∴ ol    ゴクゴク!!!!
              |  ∨∴ U∴U
             ∧  ∨U o∴ l
             /  \ ∨∴ oUl   _ノ!
             | (゚ ) Y ̄ ̄ ̄ ̄ ̄_ ノ
             |      ̄ ̄ ̄| ̄
             》         }
            /         /
            /         │
           │         │

51 :
>>49
カオス好きですね。w
>ただパイこね変換(テント写像)の左側を0、右側を1に対応づけると、カオスからビットストリームを作れますよね?
ここの部分の主張が良く分らん。
実際にそのビットストリームとやらを作る手続きを示してみな。

52 :
>> 51
単純に写像を繰り返した時に、テントの左側に値が居るのを0、右側を1とするのさ。
写像を繰り返して、
0.4→0.8→0.4→0.8となったなら、出力ビットストリームは0101ってな風。
テントの傾き(係数)が2以上なら、初期値0.4000で始めた場合と0.40001で始めた場合とで、途中から出力が不一致になって、大きく異なる軌道をとるようになる。
これって初期値鋭敏でしょう。
で、この出力ビットストリームの乱数性はどう評価すればいいのかな、と。

53 :
>>52
図を示して左とか言ってるんだったらまだしも、いきなり左とか言われても。。。
でも、とりあえず言いたい事は分った。
俺は専門じゃないから、的確なアドバイスは出来ないかもしれないが、統計学的な検定をするのが妥当じゃないか?

54 :
>>53
すまぬすまぬ。
テント写像で画像検索したら、テントっぽい画像が出るのでそれです。というか、ただの三角ですわ。
イメージとしては、ビリヤード台の半分を赤、残りを黒に塗って玉を突いた時に、玉が壁にぶつかった時の地の色を出力するようなシステムを考えます。適当な場所から玉突いて、摩擦が無ければ、システムは赤黒黒赤…と出力ストリームを吐き出し続けます。
ビリヤード台が四角ならカオスじゃないんだけど、平行四辺形とか楕円とかならカオスになるはず。ビリヤード問題、カオス、とかで調べてちょ。

55 :
>>54
貴方がそこまでカオスに固執する理由は何?

56 :
香田徹さんのカオスによる信号処理、ネットにPDF落ちてるから読んだ。
ロジスティック写像(やテント写像も?)から、均等分布の乱数ビット列が得られるところまで、とりあえず読んだ。

57 :
>>55
すまぬすまぬ。カオススレじゃなかったな。
そもそも誰かがM系列がカオスとか言い出すからいかんのです。
個人的にはカオスは質の悪い(偏った)乱数に過ぎないんじゃないの?って思ってるんですが。
まぁあんまりスレチもアレなんで、カオススレに行きますかね。

58 :
M系列自体は疑似乱数の話だからスレ違いじゃないな。

59 :
これって乱数の一つだろうか
http://www.youtube.com/watch?v=fLFEIBW2Go4

60 :11/10/27

中野剛志先生がTPP賛成論者の詭弁を全滅させたようです
http://www.youtube.com/watch?v=9amjatPD_l4
http://www.youtube.com/watch?v=8G29qFqId2w
中野先生が敗北宣言、暗される?
日本が米国の植民地に。すでに99%手遅れか?
http://www.nicovideo.jp/watch/sm15973549
テレビ・新聞にだまされるな。
気づいたら、
「my日本」で検索

TOP カテ一覧 スレ一覧 2ch元 削除依頼