python - ランダムはほとんどランダムではありませんか?

Question

randint のランダム性をテストするためにこれを行いました。

>>> from random import randint
>>>
>>> uniques = []
>>> for i in range(4500):  # You can see I was optimistic.
...     x = randint(500, 5000)
...     if x in uniques:
...         raise Exception('We duped %d at iteration number %d' % (x, i))
...     uniques.append(x)
...
Traceback (most recent call last):
  File "<stdin>", line 4, in <module>
Exception: We duped 887 at iteration number 7

約 10 倍以上試してみたところ、最高の結果はリピーターの前に 121 回の繰り返しでした。これは、標準ライブラリから得られる最良の結果ですか?

Answer 1

誕生日のパラドックス、または PRNG が思ったよりも頻繁に重複を生成する理由。

OPの問題には、いくつかの問題があります。1 つは上記の誕生日のパラドックスであり、2 番目は生成するものの性質であり、特定の数字が繰り返されないことを本質的に保証するものではありません。

誕生日のパラドックスは、ジェネレーターの期間中に特定の値が複数回発生する可能性がある場合に適用されます。したがって、値のサンプル内で重複が発生する可能性があります。誕生日のパラドックスの効果は、そのような重複を取得する実際の可能性が非常に高く、それらの間の平均期間が他の方法で考えられていたよりも短いことです. 認識された確率と実際の確率との間のこの不協和は、​​誕生日のパラドックスを認知バイアスの良い例にしています。

疑似乱数ジェネレーター (PRNG) の簡単な入門書

問題の最初の部分は、乱数ジェネレーターの公開された値を取得し、それをはるかに小さい数値に変換しているため、可能な値のスペースが減少することです。一部の疑似乱数ジェネレーターは、期間中に値を繰り返さないものもありますが、この変換により、ドメインがはるかに小さいものに変更されます。ドメインが小さいほど、「繰り返しなし」条件が無効になるため、繰り返しが発生する可能性が非常に高くなることが予想されます。

線形合同 PRNG ( A'=AX|M)などの一部のアルゴリズムは、期間全体の一意性を保証します。LCG では、生成された値にアキュムレータの状態全体が含まれ、追加の状態は保持されません。ジェネレーターは決定論的であり、期間内に数値を繰り返すことはできません。特定のアキュムレーター値は、可能な連続する値を 1 つだけ暗示することができます。したがって、各値はジェネレーターの期間内に 1 回しか発生しません。ただし、このような PRNG の期間は比較的短く (LCG アルゴリズムの一般的な実装では約 2^30)、個別の値の数より大きくなる可能性はありません。

すべての PRNG アルゴリズムがこの特性を共有しているわけではありません。期間内に特定の値を繰り返すものもあります。OPの問題では、Mersenne Twisterアルゴリズム（Pythonのランダムモジュールで使用）の周期は非常に長く、2 ^ 32をはるかに超えています。線形合同 PRNG とは異なり、アキュムレータには追加の状態が含まれるため、結果は純粋に前の出力値の関数ではありません。32 ビット整数出力と ~2^19937 の期間では、そのような保証を提供することはおそらくできません。

Mersenne Twister は、優れた統計的および幾何学的特性と非常に長い周期 (シミュレーション モデルで使用される PRNG に望ましい特性) を備えているため、PRNG の一般的なアルゴリズムです。

• 優れた統計的特性とは、アルゴリズムによって生成された数値が均等に分布しており、他の数値よりも出現確率が大幅に高い数値がないことを意味します。統計特性が悪いと、結果に望ましくない偏りが生じる可能性があります。

• 優れた幾何学的特性とは、N 個の数の集合が N 次元空間の超平面上にないことを意味します。幾何学的特性が悪いと、シミュレーション モデルで疑似相関が生成され、結果が歪む可能性があります。

• 期間が長いということは、シーケンスが先頭に戻る前に多くの数値を生成できることを意味します。モデルが多数の反復を必要とする場合、または複数のシードから実行する必要がある場合、典型的な LCG 実装から得られる 2^30 程度の離散数では不十分な場合があります。MT19337 アルゴリズムの周期は非常に長く、2^19337-1、つまり約 10^5821 です。比較すると、宇宙の原子の総数は約 10^80 と見積もられています。

MT19337 PRNG によって生成される 32 ビット整数は、このような長い期間の繰り返しを避けるのに十分な離散値を表すことができない可能性があります。この場合、重複値が発生する可能性が高く、サンプルが十分に大きい場合は避けられません。

一言で言えば誕生日のパラドックス

この問題はもともと、同じ部屋にいる 2 人の人物が同じ誕生日である確率として定義されていました。重要な点は、部屋にいる2人が誕生日を共有できるということです。人々はこの問題を単純に、部屋にいる誰かが特定の個人と誕生日を共有する確率として誤解する傾向があり、これがしばしば人々が確率を過小評価する原因となる認知バイアスの原因です. これは間違った仮定です。一致が特定の個人と一致する必要はなく、任意の 2 人の個人が一致する可能性があります。

一致が特定の日付である必要はないため、任意の 2 人の個人間で一致が発生する確率は、特定の個人と一致する確率よりもはるかに高くなります。むしろ、同じ誕生日を共有する 2 人の個人を見つけるだけで済みます。このグラフ (テーマに関するウィキペディアのページにあります) から、この方法で一致する 2 人を見つける確率が 50% になるには、部屋に 23 人いるだけでよいことがわかります。

この件に関するウィキペディアのエントリから、すばらしい要約を得ることができます。 OPの問題では、365ではなく4,500の可能な「誕生日」があります。生成された特定の数のランダム値（「人」に相当）について、シーケンス内に2つの同一の値が現れる確率を知りたいです。

OPの問題に対する誕生日のパラドックスの影響の可能性を計算する

100 個の数字のシーケンスの場合、潜在的に一致する可能性のある ペア (「問題の理解」を参照) があります (つまり、最初の数字が 2 番目、3 番目などと一致し、2 番目が 3 番目、4 番目などと一致する可能性があります)。一致する可能性のある組み合わせの数は、100 を超えることはありません。

確率の計算からの式を取得します 。以下の Python コードのスニペットは、一致するペアが発生する確率を単純に評価します。

# === birthday.py ===========================================
#
from math import log10, factorial

PV=4500          # Number of possible values
SS=100           # Sample size

# These intermediate results are exceedingly large numbers;
# Python automatically starts using bignums behind the scenes.
#
numerator = factorial (PV)          
denominator = (PV ** SS) * factorial (PV - SS)

# Now we need to get from bignums to floats without intermediate
# values too large to cast into a double.  Taking the logs and 
# subtracting them is equivalent to division.
#  
log_prob_no_pair = log10 (numerator) - log10 (denominator)

# We've just calculated the log of the probability that *NO*
# two matching pairs occur in the sample.  The probability
# of at least one collision is 1.0 - the probability that no 
# matching pairs exist.
#
print 1.0 - (10 ** log_prob_no_pair)

これにより、4500 の可能な値の母集団からサンプリングされた 100 の数値内で一致が発生した場合、 p=0.669という妥当な結果が得られます。(誰かがこれを確認して、間違っている場合はコメントを投稿できるかもしれません)。このことから、OP によって観測された一致する数値間の実行の長さは非常に合理的であるように見えることがわかります。

脚注: シャッフルを使用して疑似乱数の一意のシーケンスを取得する

保証された一意の乱数セットを取得する手段については、以下の S. Mark の回答を参照してください。ポスターが参照している手法では、数値の配列 (ユーザーが提供するため、それらを一意にすることができます) を取り、それらをランダムな順序にシャッフルします。シャッフルされた配列から順番に数字を引き出すと、繰り返されないことが保証されている疑似乱数のシーケンスが得られます。

脚注: 暗号的に安全な PRNG

MT アルゴリズムは、数列を観察することでジェネレーターの内部状態を推測するのが比較的簡単であるため、暗号的に安全ではありません。Blum Blum Shubなどの他のアルゴリズムは暗号化アプリケーションに使用されますが、シミュレーションや一般的な乱数アプリケーションには適さない場合があります。暗号的に安全な PRNG は高価である (おそらく bignum 計算が必要) か、適切な幾何学的特性を持たない可能性があります。このタイプのアルゴリズムの場合、主な要件は、一連の値を観察することによってジェネレーターの内部状態を推測することが計算上実行不可能であることです。

Answer 2

Python のせいにする前に、確率と統計の理論をブラッシュ アップする必要があります。誕生日のパラドックスについて読むことから始めましょう

ところで、randomPython のモジュールはMersenne twister PRNG を使用しています。これは非常に優れていると考えられており、膨大な期間があり、広範囲にテストされています。ですから安心してください。

Answer 3

繰り返しが必要ない場合は、順次配列を生成し、random.shuffleを使用します

Answer 4

Nimbuzの答えに対する答えとして：

http://xkcd.com/221/

Answer 5

真のランダム性には、可能な値のセット全体が使い果たされる前の値の繰り返しが確実に含まれます。それ以外の場合は、値が繰り返されない期間を予測できるため、ランダムではありません。

サイコロを振ったことがあるなら、必ず 3 つの 6 が連続して出ることがよくあります。

Answer 6

Python のランダムな実装は、実際には非常に最先端です。

• http://en.wikipedia.org/wiki/Mersenne_twister
• http://docs.python.org/library/random.html

Answer 7

4500範囲から乱数を生成しています500 <= x <= 5000。次に、各番号が以前に生成されたかどうかを確認します。誕生日の問題は、これらの数字のうちの 2 つがn範囲外の試行で一致する確率を教えてくれますd。

数式を逆にして、重複を生成する可能性が より大きくなるまで、生成しなければならない数を計算することもできます50%。この場合、反復>50%後に重複する数値を見つける可能性があり79ます。

Answer 8

それはリピーターではありません。リピーターとは、同じシーケンスを繰り返すことです。1つの数字だけではありません。

Answer 9

この問題を抱えている他の人のために、私はuuid.uuid4（）を使用しましたが、これは魅力のように機能します。

Answer 10

4501 個の値 (500 ～ 5000) のランダム空間を定義し、4500 回反復しています。基本的に、作成したテストで衝突が発生することが保証されています。

別の方法で考えるには：

• 結果配列が空の場合 P(dupe) = 0
• 配列の 1 つの値 P(dupe) = 1/4500
• 配列の 2 つの値 P(dupe) = 2/4500
• 等

したがって、45/4500 に到達するまでに、その挿入が重複している可能性は 1% であり、その可能性は後続の挿入ごとに増加し続けます。

ランダム関数の能力を真にテストするテストを作成するには、可能なランダム値の範囲を増やします (例: 500-500000)。ただし、平均してはるかに多くの反復が得られます。

Answer 11

誕生日のパラドックスがあります。これを考慮すると、「764、3875、4290、4378、764」またはそのようなものを見つけることは、そのシーケンスの数字が繰り返されるため、あまりランダムではないということがわかります. それを行う本当の方法は、シーケンスを互いに比較することです。これを行うための python スクリプトを作成しました。

from random import randint
y = 21533456
uniques = []
for i in range(y):  
    x1 = str(randint(500, 5000))
    x2 = str(randint(500, 5000))
    x3 = str(randint(500, 5000))
    x4 = str(randint(500, 5000))
    x = (x1 + ", " + x2 + ", " + x3 + ", " + x4)
if x in uniques:
    raise Exception('We duped the sequence %d at iteration number %d' % (x, i))
else:
    raise Exception('Couldn\'t find a repeating sequence in %d iterations' % (y))
uniques.append(x)