3

次の入力を検討してください。

1,1,2,3,5,8-ランダムではありません

2,4,8,16,32-これも

4,1,2,11,5,9-これはランダムシーケンスのように見えます

入力がランダムであるかどうかを証明するためのそのようなアルゴリズムがあるかどうかを尋ねたいと思います。

4

3 に答える 3

5

いいえ、そのような証明はありません。完全に乱数がある場合、長さnの各シーケンスの確率は等しくなります。ただし、乱数ジェネレーターの品質を評価するための統計的検定があります。これはおそらくあなたが探しているものです。Diehardテストを参照してください。

于 2013-01-14T15:45:05.263 に答える
1

他の人が述べているように、シーケンスがランダムに生成されたかどうかを証明することはできません。@timosが提案したことに加えて、いくつかの追加要件があるようです。シーケンスが、よく知られている「非ランダム」シーケンスの仮想リストからのものではないことを確認したいようです。その場合は、整数シーケンスのオンライン百科事典の学習に興味があるかもしれません。

特定のシーケンスを念頭に置いている場合は、データベースと照合してチェックできます。たとえば1,1,2,3,5,8、いくつかのシーケンスで登場しますが、最も目立つのはA000045（フィボナッチ数）です。のようなシーケンス4,1,2,11,5,9は、そこでの検索には表示されません。

これは何も証明しませんが、おそらくこれはこの場合のあなたの目標とより一致しています。

于 2013-01-14T16:44:39.757 に答える
0

ここで強調したいのは、「ランダム」という言葉は、同じように分布しているだけでなく、他のすべてから独立している（他の選択肢から独立していることを含む）ことを意味します。

さまざまな統計プローブの実行からp値を推定するテストや、ビットシーケンスのほぼ最小の「圧縮率」レベルで最も関連性の高いエントロピーである最小エントロピーを推定するテストなど、多数の「ランダム性テスト」を利用できます。「安全な乱数発生器」の測定。von NeumannやPeres抽出器など、さまざまな「ランダム性抽出器」もあり、ビットシーケンスからどれだけの「ランダム性」を抽出できるかを知ることができます。ただし、これらすべてのテストと方法は、このランダム性の定義の最初の部分（「同一分布」）の方が、2番目の部分（「独立」）よりも信頼性が高くなります。

一般に、一連の数列だけから、そのプロセスが何であるかを知らなくても、プロセスが独立して同じように分散された方法でそれらを生成したかどうかを判断できるアルゴリズムはありません。したがって、たとえば、特定のビットシーケンスに1よりも多くのゼロがあるか、明確なパターンがないことはわかりますが、それらのビットかどうかはわかりません— </ p>

  • 他の選択肢とは無関係に本当に生成された、または
  • 「局所的にランダム」である非常に長い周期列の一部を形成する、または
  • 別のプロセスから単に再利用された、または
  • 他の方法で生産された、

...プロセスに関する詳細情報なし。重要な例の1つとして、パスワードを選択するプロセスがこの意味で「ランダム」になることはめったにありません。これは、パスワードには、他の理由の中でも、なじみのある単語や名前が含まれる傾向があるためです。

この質問も参照してください：ランダム性の適切でシンプルな測定

于 2020-12-07T12:13:58.977 に答える