ランダム性を理解する
1. 概要
このチュートリアルでは、ランダム性の概念とそのコンピューターサイエンスへの応用について学習します。
まず、ランダム性の存在論的および認識論的基盤について説明することから始めます。 次に、ランダム生成とランダムサンプリングの問題を研究します。
このチュートリアルの終わりに、ランダム性がコンピュータサイエンス、統計、および暗号化の両方で非常に重要な概念である理由を理解します。
2. ランダム性の理論的根拠
2.1. ランダム性の理論の紹介
テクノロジーにおけるランダム性の実際のアプリケーションに取り組む前に、その理論的基礎を紹介するのが最善です。 ランダム性の概念は、その抽象的な形では、は明確に定義されていません。これは、純粋なランダム性が何を意味するかについて意見の相違があることを意味します。 ただし、ランダム現象とランダムサンプリングの考え方については一般的な合意があるため、代わりにそれらを研究することができます。
ランダム性の概念は、哲学、カオス理論、確率論、そして最近ではコンピューターサイエンスによる共同研究の主題です。 、人工知能、および量子コンピューティング。 その重要性は、暗号化や人工群知能などの多くの実世界のテクノロジーが、理論的基盤の一部としてそれを必要とするという事実にあります。
ただし、ランダム性には、より深い意味があります。 これは、イベントの結果が先験的に予測できないという考えに関連しているためです。 科学では、ランダム性の仮定は、すぐにわかるように、自然が予測可能な一連のルールに決定論的に還元されるのを防ぎます。
2.2. 理論だけでなく
しかしまた、ランダム性は、科学研究の理論だけでなく、方法論においても重要な役割を果たします。 これは、科学的仮説の検証には経験的なテストが必要なためです。 これには、次に、より大きな母集団に対して収集された観測値のサンプリングバイアスを解決する方法が必要です。 これについては後で詳しく説明します。
しかし、ランダム性が現実の世界に存在するのか、それとも人間が持っている限られた知識の産物であるのかについては議論されています。 最初のアプローチ、つまりランダム性を自然の特性と見なすアプローチは、いわゆる「存在論的ランダム性」を前提としています。 第二に、それを観察者の知識に帰するものは、代わりに「認識論的ランダム性」を仮定します。 この記事の最初のセクションでは、両方のアプローチについて学習します。
ランダム性の存在論的および認識論的基盤を理解すると、それに基づく技術の開発において、実際の使用法を理解できるようになります。
2.3. 非決定論的宇宙
世界で最も古い考えの1つは、宇宙であるコスモスが固有の秩序と完全性を持っているというものです。 この完璧さは、星、惑星、そして地球に生息する人間の生命の動きの算術的精度に対応しています。 このアイデアは、終端という単語の定義または制限から「決定論」の名前を取ります。
決定論は、20世紀の前半まで、科学への実りあるアプローチであることが証明されました。 物理学では、決定論により、ニュートンは後で改ざんされたにもかかわらず、彼の宇宙論モデルを構築することができました。 ニュートン力学では、宇宙は時計仕掛けのメカニズムとして機能し、そのすべてのコンポーネントが決定された予測可能な方法で動作します。
この理論の下で、宇宙の未来の完全で正確な予測が可能です。 ある瞬間の宇宙の状態の知識、およびその振る舞いを規制する規則の知識は、したがって、未来と過去の両方の完全な知識を与えるでしょう。 したがって、ニュートン力学はランダム性を考慮していないと言えます。
ニュートン宇宙では、ラプラスの悪魔のように、宇宙の状態と規則についての正確な知識を持っている存在は、あらゆる目的のために全知であるでしょう。 そのため、サイコロを投げた結果は事前にわかっているので、将来についての不確実性はありません。
2.4. カオス理論とランダム性
しかし、絶対決定論はカオス理論によって改ざんされました。これは、同じシステムの進化軌道が、類似しているが同一ではない元の状態の下で大きく変化する可能性があることを示唆しています。 カオス理論は、システムの初期条件をわずかに変更すると、その進化の結果が完全に異なる可能性があることを示唆しています。 これは、初期条件への敏感な依存として知られている概念です。
この概念の最も有名な例は、ロジスティックマップです。 システムはによってパラメータ化されますが、それ以外の場合は完全に決定論的です。 ただし、その動作は初期構成に応じて劇的に変化します。 この場合、パラメータの値に。 これは、ロジスティックマップのいわゆる分岐図のマップです。
システムの動作は、オブザーバーにとってランダムに見える場合があります。 ただし、単純な決定論的ルールが存在し、そこから奇妙な動作が発生します。 したがって、システムの正確な初期構成がわかっていれば、システムの将来の進化を完全な精度で予測できます。
この考察から、システムの動作は、そのシステムについての知識に応じて、ランダムに見える場合とそうでない場合があるという考えが生まれます。 無知なオブザーバーの場合、システムはランダムに動作する可能性があります。 知識のあるオブザーバーの場合、同じシステムが決定論的に動作する可能性があります。 オブザーバーの特性としてのランダム性、またはむしろ彼が保持する知識の概念は、科学的な議論に入り始めます。
2.5. 量子ランダム性
ランダム性の概念の別の発展は、量子力学、特に有名な二重スリット実験に由来します。 この実験は、システムの状態を測定する行為が、どの状態またはどのシステムに関係なく、それを変更することを示しました。 これは、順番に、そうでなければ健全であるかもしれない予測を無効にするでしょう。
宇宙はおそらくの量子系であるため、これは、予測の精度を決定するために、宇宙で量子測定を行う必要があることを意味します。 これは、順番に、宇宙の状態を変更し、その後それらを無効にします。
問題は、測定のための特定の結果がどのように正確に選択されるかということです。 コペンハーゲン解釈は、測定を実行すると、可能な結果の1つがランダムに選択され、他のすべての可能な結果が破棄されることを示唆しています。 ここで、オブザーバーとシステムの相互作用の結果として、ランダム性が物理的に作用します。
2.6. 1つではなく、多くの世界
別の考えは、ランダム性はまったく存在しないということです。なぜなら、イベントの結果は、複数の可能性があるときはいつでも、すべて同時に発生するからです。 いわゆるエベレッティの解釈では、測定結果のランダムな選択は存在しないと提案されています。 むしろ、測定のすべての可能な結果は同時に現れます。 ただし、オブザーバーがアクセスできるのは1つだけです。
このコンテキストでは、確率変数の確率分布は、世界の確率分布として解釈できます。 想像上、私たちがサイコロを振ると、宇宙は分裂し、私たちの転がりの可能な結果のいずれかのためにそれ自体のコピーを1つ作成します。
ただし、オブザーバーは、それらが存在する宇宙に関連するロールの結果のみを認識します。
異なる解釈は二重スリット実験のより深い意味に同意しませんが、しかしそれらはすべて、イベントの結果の基本としての観察者と観察の役割を考慮することに同意します。 これは、ランダム性の存在論的解釈ではなく認識論的解釈への扉を開きます。
2.7. 認識論的正当化
次に、この2番目のルートをたどり、ランダム性を宇宙の特性としてではなく、オブザーバーに関連するイベントのプロパティとして研究できます。イベントのランダム性がオブザーバーに由来する場合、ランダムイベントは次のようになります。 1人の特定のオブザーバーを参照せずにそのように説明することはできません。
2人の異なるオブザーバーが同じプロセスの結果に割り当てるランダム性も異なる場合があります。 次の例を見てみましょう。
画面の後ろで、最初のオブザーバーがサイコロを振ってその結果を確認します。 2番目のオブザーバーは、最初はロールの結果を確認しません。 宇宙がランダム性を許容する場合、ロールの結果は最終的に両方のオブザーバーに対してランダムになります。 しかし、最初のオブザーバーがロールの結果を見ると、それはもうランダムですか？
2番目のオブザーバーの観点からは、結果はまだランダムであると言えます。 ただし、2番目のオブザーバーが結果を学習した場合、ロールのランダム性はなくなったと主張できます。
したがって、ランダム性の正当な説明は、オブザーバーが保持している知識に関連しているように思われます。 オブザーバーがイベントについてより多くの知識を獲得すると、そのランダム性は減少するか、さらには消える可能性があります。
この例は、ランダム性に対するいわゆる認識論的アプローチを支持する議論です。 このコンテキストでは、ランダム性は、予測または一部の測定結果に関する特定のオブザーバーの不確実性のみを示しますが、より深い存在論的意味はありません。
2.8. なぜそれが重要なのですか？
ランダム性の問題の存在論的および認識論的基盤。 これは、ブロックチェーンや暗号化などの多くの重要なテクノロジーが、意図したとおりに機能するためにランダム性が存在する必要があるためです。 上で見たように、ランダム性が存在論的性質を持っていること、そしてそれが代わりにオブザーバーの状態を参照していないことはそれほど明白ではありません。
宇宙が本質的にランダムでない限り、ランダム性を利用するアプリケーションを開発するときは、オブザーバーの説明を含める必要があります。 これは、特定のコンテキスト、特に暗号化への敵対的アプローチでは、確率変数の将来の値を予測する能力が異なるオブザーバーにあるためです。 結果として、彼らはどの変数をランダムと見なすか、そしてその理由について意見が一致しない可能性があります。
ランダム性が存在しない場合、それを使用して何も構築できないと言えば十分です。 そして、先に見たように、ランダム性が宇宙の特性であるかどうかは不明です。 ただし、予測の不確実性を測定するための良い方法かもしれません。 そして、この意味で、ランダム性の理論は、技術開発の理論的基盤の中にその位置を見出しています。
3. ランダムシーケンスとランダム生成
3.1. シーケンスのランダム性
次に、確率変数の生成とサンプリングの問題について説明します。 これらは、実際的な意味で、ランダム性の理論を適用する2つの主要な分岐です。
このセクションでは、新しい数列に直面したときに、その数列がランダムであるかどうかを理解することに関心があります。 誰かが私たちに単一の番号を教えてくれたとしましょう：
この番号はランダムですか？ その数字は確かに互いに関係がないように見えるので、関係があるのではないかと思われるかもしれません。 次に何が起こるかを確認するために、同じ人にもう少し番号を聞いてみましょう。
対話者が番号を生成するために従う基準が何であれ、シーケンス内の次の番号は他のすべての番号と同じであるように見えます。 これは、シーケンス内の任意の番号が、情報コンテンツを持っている場合、非常に制限されていることを意味します。
ここで、対話者が別の新しいシーケンスを提供すると想像してみましょう。
この新しいシーケンスは、本能的に前のシーケンスよりも「ランダム」に見えます。 これは、相手がシーケンスを生成するために従う手順が何であれ、数字自体だけを見ても簡単に推測できないためです。
3.2. 乱数生成
この考察により、ランダムシーケンスの生成が紹介されます。 理想的には、ランダムな数字のシーケンスには、前に与えられたシーケンスの次の要素を予測できるアルゴリズムがまったくないようにする必要があります。 ただし、アルゴリズム、任意のアルゴリズムを使用して数列を生成する場合、定義上、同じアルゴリズムでシーケンス内の任意の要素を計算できます。
残念ながら、アルゴリズムなしでは手続き的に数値を生成することはできません。 結果として、私たちができる最善のことは、私たちが使用する手順の再構築を特に複雑またはコストのかかるにするアルゴリズムを使用することです。 これらのアルゴリズムは、真のランダム性を利用するのではなく、その近似を利用するため、「疑似ランダムジェネレータ」の名前を取ります。
3.3. 疑似ランダム生成：ミドルスクエア
疑似乱数の生成は、フォンノイマンなどの数学者の関心事でした。 彼には、疑似乱数の任意の長さのシーケンスの計算を可能にする、いわゆるミドルスクエア法の発見があります。
この方法は、シーケンスの「シード」と呼ばれる特定の数の2乗と、正方形の中央の桁の抽出で構成されます。 これらの真ん中の数字は、シーケンスの次の数字を形成し、それらに同じアルゴリズムを何度も適用します。 この表は、いくつかのシードについて、各シーケンスの最初のいくつかの要素の計算を示しています。
ただし、この方法には重大な問題があります。 これは、上の表のシード「1000」を含む3行目を見ると明らかです。 シーケンス内のいずれかの数字の中央の数字にゼロが表示された場合、その数字は無期限にそこに留まります。 これは、シードが1000のシーケンスがゼロに収束することを意味し、その特定のシードではアルゴリズムが役に立たなくなります。
他の疑似乱数ジェネレータにはさらに重大な問題があります。 たとえば、二重楕円曲線疑似乱数生成器は、生成される数値の実際の予測可能性に関する論争に巻き込まれています。 脆弱であることが証明された後、将来の出力を予測するための隠された些細な方法のために、最終的に市場から撤退しました。
これは、ランダムな数値を生成するために選択した方法が重要であり、注意しないと些細なシーケンスになってしまう可能性があることを意味します。 したがって、このセクションは次のように結論付けることができます。
4. 無作為抽出
4.1. ランダムサンプリングと統計
ランダム性は、バイアスによるミスを回避しながら、より小さなサンプルの特性に基づいて母集団の特性を研究するのにも役立ちます。 大規模なデータセットをランダムにサンプリングする場合、サンプルサイズが大きくなると、サンプルの統計は母集団の統計になる傾向があります。
これは通常、すべての統計とすべての母集団に有効です。 ただし、サンプルの選択はランダムに実行する必要があります。そうしないと、このルールは無効になります。
4.2. 非ランダムサンプリング
実際、ランダムにサンプリングしないとどうなるかを確認できます。 原則として、非ランダムサンプリングは、そのサンプルで計算された統計に重大なエラーを引き起こします。
前の画像のデータポイントに対して非ランダムサンプリングを実行する小さな実験でこれを示しましょう。 たとえば、中央値に最も近い10個の観測値を取得し、それらの統計を計算することを任意に決定する場合があります。
結果が以前と大幅に異なることがわかります。 そして、これはランダムではありません。サンプルのランダムでない選択は、結果の歪みと一般母集団に対する代表性の喪失につながります。
4.3. 確率変数の分布
これで、確率変数の分布の形について説明できます。 一部の形状は、特に直感的に理解できます。 たとえば、一様分布（0、1）からサイズをランダムにサンプリングすると、次のようになります。
確率的変動を除いて、ほぼ等しい数のドローが、等しいサイズの一様分布の任意に選択されたサブインターバルに分類されます。 代わりに、正規分布からサンプリングすることもできます。 また、結果の変数は、サンプリングされた分布と同じように、通常の形状になります。
原則として、分布からランダムにサンプリングされた変数は、同じ形状のです。
4.4. 確率変数の組み合わせ
単一の変数に有効な規則は当てはまりませんが、複数の変数とそれらの線形結合には当てはまりません。 これを実験的にテストできます。 とが一様分布からサンプリングした確率変数であると仮定しましょう。 したがって、それらの線形結合を調べることができます。
驚いたことに、それらの合計はもはや均一に分布していませんが、むしろそれは非常に独特な形をとっています。 一様分布からサンプリングした3番目の変数を追加して、実験を繰り返しましょう。
これで、形状がより目立つようになります。 最後に、一様分布からサンプリングされた100個の変数を使用して実験を繰り返します。
これで、形状がより明確になり、正規分布とまったく同じように見えます。
4.5. 中心極限定理
中心極限定理の名前をとる上記の観察を数学的に形式化することができます。 定理は、私たちが考える確率変数の数が増えるにつれて、それらを生成した分布の形に関係なく、それらの合計は正規分布に向かう傾向があると述べています。
定理は正式な表記法で表現できます。 が変数の平均を示し、ががそれぞれ、すべての分布の平均と標準偏差を示している場合、すべての合計の分布は次のように表すことができます。
正規分布はどこにありますか。
4.6. 中心極限定理の適用
この定理の重要性は、実際の例で最もよく理解できます。 2つのサイコロを振った結果を合計してみましょう。 元の2つのサイコロは区間内で均一に分布しているため、合計も区間内で均一に分布すると予想される場合があります。
ただし、これは2つのサイコロの合計の分布であり、仮説が正しくないことを証明しています。
そして、これはチャートの形で、上記の表の同じ内容です：
2つのサイコロを合計すると、分布の通常の形状がすでに現れ始めていることがわかります。 中心極限定理によると、2つ以上のサイコロを合計すると、ガウス形状がより目立つようになります。
5. 結論
この記事では、最初にランダム性の存在論的および認識論的基礎を研究しました。
次に、ランダム生成とランダムサンプリングが、コンピュータサイエンスの実際のアプリケーションでどのように異なるかを調べました。
