乱数に見える数列が擬似乱数でない、ということを証明することは可能ですか？

乱数列（以下乱数と呼ぶ）は、次に来る数を予測できない数列のことと聞きました。

コンピューターの内部処理は、偶然性を排除し、何度でも同じ結果を出すように設計されているので、同じ初期値と同じアルゴリズムを使用すれば同じ結果をゲットできるので、コンピューターで生成した数列は厳密には乱数とは言えず、擬似乱数列（以下擬似乱数）と呼ばれるそうです。

質問: 乱数のように見える数列が与えられた時、この数列が乱数か擬似乱数か判定する事が可能でしょうか？

例題: 任意の巨大素数の下1,000桁を初期値とし、次のメンバーは、上述の巨大素数を小さい素数で除した余りの下1,000桁を採用。以下同様に上述の巨大素数と小さな素数列のn番目を使って計算可能な数値を採用する。この数列を示し、乱数か擬似乱数かの判定を要求するものとする。

乱数研究者や数学愛好家の皆さんよりアドバイス頂けると有難いです。
よろしくお願いします。

質問者からの補足コメント

• マサさんの回答に対するお礼欄で追加の確認質問をした格好になっていますが、無用な質問ででした。失礼しました。

  No.5の回答に寄せられた補足コメントです。 補足日時：2019/06/16 15:16

No.1 回答者： hanzo2000 回答日時： 2019/06/10 12:07

アルゴリズムが未知の状態であるなら、疑似乱数を判定することはできないでしょう。

同じ初期値とアルゴリズムなら同じ結果が得られるというのはその通りですが、
たとえば内部時計の数値を初期値とし、生成プロセスもリアルタイムの内部時計数値を使った乱数を発生させるアルゴリズムの場合、
発生時刻が変われば同じ結果を得られないため、乱数であるか疑似乱数であるかを判別するのは非常に困難です。

例題についてはちょっと意味がわかりませんでした。

そのようなプロセスで生成した数列を疑似乱数として利用するということでしょうか。
偶然性を一切排除した確定的なアルゴリズムであれば判定することは不可能ではないかもしれませんが、
そもそもアルゴリズムが未知であるなら、無限にあるアルゴリズムのどれを利用したのかという予測が困難であるため、
数列としては乱数に見えると言っていいのではないでしょうか。

この回答へのお礼

有難うございます。

乱数と思っている数列は、実は乱数であることが証明されない数列である、という事になりますかね？

お礼日時：2019/06/11 00:33

No.2 ベストアンサー 回答者： Tacosan 回答日時： 2019/06/11 00:22

そもそも「乱数」かどうかすら判定不可能だ.

この回答へのお礼

ありがとうございます。

ある数列が乱数か乱数でないかを、数列自体を回帰分析しても判定する方法が無いという事ですね。

ということは、
ケース1: 数列の作成者が生成のアルゴリズムを説明した 、、、、アルゴリズムがあるのだから乱数でない。
ケース2: 数列を作成者は作成方法を秘匿した（乱数であるかどうか不明）、、、乱数であることは証明できない。
という事になるので、

「この数列は乱数である」と言明できる必要条件が何だ？

もしご存知であれば、ご教示いただきたく。

お礼日時：2019/06/11 00:31

No.3 回答者： masa2211 回答日時： 2019/06/14 01:14

＞例題: 任意の巨大素数の下1,000桁を初期値とし、次のメンバーは、上述の巨大素数を小さい素数で除した余りの下1,000桁を採用。

以下同様に上述の巨大素数と小さな素数列のn番目を使って計算可能な数値を採用する。
以下のような計算、ですよね？　（1000桁を桁数縮小して例示。）
初期値：9699691 (この値は(2*3*5*....19) +1 であるので、素数。）
乱数1個め　mod(9699691,2)=1
乱数2個め　mod(9699691,3)=1
:
乱数8個め　mod(9699691,19)=1
乱数９個め　mod(9699691,23)=16

というわけで、例題は明らかに乱数ではありません。まあ、最初に選んだ初期値が最悪であり、
小さな素数列といっても流石に２，３，５とか使ってはダメで、少なくとも1000桁以上の素数からはじめるもかもしれませんが．．．
でも、こういうものでも質問文の定義に矛盾しないので、ババ引いたらえらいことに．．．．

以下、メルセンヌ－ツイスタ　アルゴリズムの開発者の松本さんの論文より。
↓コレ。
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/TEA …

○シミュレーションにおいて、乱数を多量に消費する。
　よって、
１．再現性が必要。つまり、疑似乱数でないとならない。
２．高速な乱数発生が必要。
　したがって、例題: の乱数（＝バカでかい素数を順番に要求する）は、乱数発生速度がダメなのでＮＧ。
　※得られた数値が乱数かどうかには、乱数発生速度は関係ないけど．．．．

○乱数の周期をそろえた場合、線形合同法よりメルセンヌ－ツイスタのほうが乱数発生が高速。
　※正確には、周期2^19937−1（＝4.3×10^6001)のメルセンヌ－ツイスタのほうが
　　周期２^48の線形合同法より速い。　　話にならないほど速いじゃんか。
　※※線形合同法とは、Ｘn＋1＝mod(a*Ｘn+b ,M) a,bは定数、Ｍは周期=２^48。
　※※※うん、まあ、それでも線形合同法は、1980年代の乱数標準アルゴリズムであり、この頃では
　　　　標準実装されてる。（注意：周期=2^16くらいでの実装です。）　　　　

○3次元ランダム点プロットを行うと、線形合同法はダウン。メルセンヌ－ツイスタは623次元までセーフ。

ということは、
たとえば650次元プロットすれば、メルセンヌ－ツイスタはダウト判定。
メルセンヌ－ツイスタ以前のアルゴリズムは、623次元以前にダウトになるか生成速度遅すぎでダウト判定。
　※何しろ、線形合同法が生成速度でダウト喰らってる。
で、メルセンヌ－ツイスタ以後のアルゴリズムなら、たとえ速度特化でもｎ次元プロットにはそこそこ耐えると思うが．．．

この回答へのお礼

投稿ありがとうございます。

9699691 2 1
9699691 3 1
9699691 5 1
9699691 7 1
9699691 11 1
9699691 13 1
9699691 17 1
9699691 19 1
9699691 23 16
9699691 29 3
9699691 31 8
9699691 37 30
9699691 41 34
9699691 43 9
9699691 47 19
9699691 53 2
9699691 59 32
9699691 61 20
9699691 67 34

上記の表の右端のコラムだけを示された時に「例題は明らかに乱数では有りません」と断言できるのはなぜですか？

アルゴリズムを知ってるから「乱数でない」という早とちりをしたのではないですか？

お礼日時：2019/06/14 13:20

No.4 回答者： Tacosan 回答日時： 2019/06/14 01:58

「乱数かどうかが判定不可能」だというのに

「この数列は乱数である」と言明できる必要条件
が存在するとどうして思えるのだろうか... と思ったのだが, 「必要条件」ならあるな.

例えば
1～6 の目が出るサイコロを振った
という「乱数」を考えているときに
-3+π/2
なんて値を書いてくるようなら駄目出しできるからなぁ.

この回答へのお礼

数学では、乱数の判定ができないと言うのは新鮮な驚きでした！

改めてあるがとうございました。

お礼日時：2019/06/14 13:22

No.5 回答者： masa2211 回答日時： 2019/06/16 11:12

＞上記の表の右端のコラムだけを示された時に「例題は明らかに乱数では有りません」と断言できるのはなぜですか？

乱数か擬似乱数の判定方法ですが．．．
たとえば、乱数列が
「１６２５４３」であり、これで全部だとすれば、乱数でないというイチャモンは、ほぼ不可能。
　※１～６をシャッフルしたもの、という可能性があるが、あくまで可能性であって乱数でないとは言えない。
で、この乱数列がもっと長いのに１～６しか現れない、よって（０～９の）乱数ではない。（正確には、乱数である確率はあまりにも低い。）
というように、確率評価するしかないです。ここを否定されると、何も言えなくなるので、ココは前提条件としてください。
ですので、乱数かどうかの判定は、まずは出目が一様かどうかの判定から。
イカサマサイコロを振ってできた数列（１～６の）を疑似乱数とは言わないけど、乱数ではないですよね？
でも、疑似乱数ではないです。そもそもが乱数かどうかの判定でしかないから。よって、当初質問
＞乱数か擬似乱数か判定の方法
といったところで、
真の乱数かそうでないかの判定しかできない。かつ、確率評価しかできない。
こうなるのは仕方ないですよね？

ですので、出目が一様の次は、偶数奇数が交互にあらわれる、とか、出目が周期を持っている、とかをチェックし、ＮＧなら出目にクセがある、よって真の乱数ではない。



で、
＞上記の表の右端のコラム
に戻りますが、これを、１の位だけ取り出す、ということとします。（２桁以上の取り出しは、１桁取り出しより悲惨であるので。）
見て解るとおり、いきなりの、１の８個連続ゾロ目。８個連続ゾロ目（１以外ok）は、数値８個なら、確率1^-7。
よって、当該数列がランダムかどうか検定するのに、10^8個かそれ以上の数列を確認します。
当該数列は、約３３万個まで（9699691以下の素数の数）。コレ知っているから、８個連続ゾロ目でダメ出ししました。
よって、　アルゴリズムを知ってるから「乱数でない」　と言ったことに。

この回答へのお礼

再投稿ありがとうございした。

私が提示した例題は、小さな素数（9699691）を初期値に選び、2から始まる最小の素数列を適用した場合を調べると1が8回連続するので、アルゴリズムを知らない人間でも乱数ではないと断言できるのですね。

この判定基準を一般化すれば、同じ数字が8回（以上）連続する部分をどこかに含む数列は乱数ではないと断言できることになりますか？

乱数であることの条件は「次に現れる数字を予測することができない」という条件でした。
対偶を取ると、次に現れる数字を予測できれば乱数ではない、と言う定義になります。
8回続いた1の次に来る数字を（アルゴリズムを知らない人が）予測できれば、乱数ではないのですが、9番目に16が来ることは、どの様に予測できるのですか？

もし知見をお持ちであれば、アドヴァイス頂きたく。

お礼日時：2019/06/16 13:10