1

多くの人が知っているように、PythonはMersenne Twister（MT）アルゴリズムを使用して乱数を処理します。ただし、非常に長い期間（〜2 ^ 19937）があるにもかかわらず、2080要素を超えるシーケンスをシャッフルすると（！2081> 2 ^ 19937）、すべてのランダム順列に到達できないこともよく知られています。私は順列を扱っており、統計的特性は私にとって重要であるため、繰り返しを避けるために、Pythonジェネレーターを追加のランダム性のソースと混合または再シードする最良の方法を見つけようとしています。

現在、私のコンセプトは、システム乱数ジェネレーター（SystemRandom）を使用して、MTジェネレーターに外部のランダム性のソースを追加することです。これを行うために私が考えることができる2つの方法があります：

  1. SystemRandom乱数とMT乱数のXOR
  2. SystemRandomを使用してMTを再シードします

最初のアプローチは、バイアス傾向を減らすために、ハードウェア乱数ジェネレーターによってある程度の頻度で使用されます。ただし、これは非常に非効率的です。Windows XPマシンでは、SystemRandomは標準のPythonランダム関数よりも50倍遅くなります。ほとんどの関数がシャッフルを伴う場合、これはパフォーマンスに大きな打撃を与えます。それを考えると、SystemRandomを使用してMTを再シードすると、大幅に効率が向上するはずです。

ただし、そのアプローチにも2つの問題があります。まず、操作中にMTを再シードすると、その統計的特性が損なわれる可能性があります。MT値の各実行は（開始点に関係なく）整形式である必要があるため、MTが十分に長く実行されれば、これは問題にならないはずです。ただし、MTの再シードの間にかなりの期間が望ましいことを示しています。第二に、再シードをトリガーする最も効率的な方法は何かという問題があります。これを処理する最も簡単な方法は、カウンターを使用することです。ただし、より効率的な方法が可能かもしれません。

したがって、この点について3つの質問があります。

  1. N個のサンプルごとにランダムな値でMTを再シードすると、その望ましい統計的特性が変わるという趣旨の何かを読んだ人はいますか？
  2. カウンターをインクリメントして再シードをトリガーするよりも効率的な方法を知っている人はいますか？
  3. 最後に、この問題に取り組むための一般的により良い方法を誰かが知っているなら、私はすべての耳です。
4

2 に答える 2

4

再シードは役に立ちません。それはどこか別の場所で（非常に）長いMTシーケンスにジャンプします。データをシャッフルすると、偏った結果が得られますか？なぜなら、宇宙の存続期間中に、考えられるすべてのシーケンスを生成するのに十分な時間がないからです。したがって、一部のシーケンスが生成されない可能性があることを知っていても、生成されたシーケンスにバイアスがかかることを意味するわけではありません。最善の策は、shuffleコマンドをそのまま使用することだと思います。

numpy.random.shuffleのソースコード（4376行目）を見ると、基本的に使用されているアルゴリズムは次のとおりです（わかりやすくするために簡略化しています）。

i = len(x) - 1
while i > 0:
    j = randint(0, i)
    x[i], x[j] = x[j], x[i]
    i = i - 1

つまり、最後から、すべての値が交換されるまで、配列内でその前にランダムに取得されたランダムな値と値を交換します。最終状態は、ランダムジェネレーターだけでなく、配列の初期状態にも依存します。これは、理論的には、十分なシャッフルを実行すれば、すべての順列にアクセスできるはずであることを意味します。

于 2013-02-06T17:53:52.290 に答える
1

これは1年以上前のことだと思いますが、振り返ってみると、簡単な解決策があります。SystemRandomから、MT RNGからの出力をk回ごとにXORする新しい値を取得するだけです。毎回。たとえば、SystemRandom が 50 倍遅く、k = 5000 に設定した場合、新しい結合された RNG は最大 1% 遅くなるだけであり、(SystemRandom が「本当に」ランダムであると仮定すると) 5000 を超える RNG を含むすべての実行で任意の順列に到達できます。呼び出します。

于 2014-07-22T00:30:25.050 に答える