True呼び出されたときに RNG を使用して30% の確率で返すルーチンがあるとしFalseます。それはかなり簡単です。Trueしかし、そのルーチンを 100 億回呼び出した場合に得られる結果の数をシミュレートしたい場合はどうなるでしょうか?
ループで 100 億回呼び出すと、時間がかかりすぎます。100 億に 30% を掛けると、統計的に期待される結果は 30 億になりますが、実際のランダム性は含まれません。(そして、結果が正確に30 億になる確率はそれほど高くありません。)
そのような一連のランダムイベントの集計結果をシミュレートするアルゴリズムはありますか?複数回呼び出された場合、結果は、シミュレートしているランダムシリーズを実際に複数回実行した場合と同じ分布曲線を示します。 O(1) 時間 (つまり、シミュレートするシリーズの長さが長くなっても、実行に時間がかからない)?
私は言うでしょう-それはO（1）で行うことができます！
状況を説明する二項分布は、（状況によっては）正規分布で近似できます。n*pとの両方n*(1-p)が 5 より大きい場合p=0.3に実行できるため、すべての に対して実行できますn > 17。が本当に大きくなったときn(数百万のように)、その近似はどんどん良くなっています。
正規分布の乱数は、ボックス ミュラー変換を使用して簡単に計算できます。必要なのは、0 と 1 の間の 2 つの乱数だけです。ボックス ミュラー変換ではN(0,1)、標準正規分布と呼ばれる分布から 2 つの乱数が得られます。式N(μ, σ2)を使用して達成できます。ここで、は標準法線です。X = μ + σZZ
他のレビュアーが述べたように、二項分布を使用できます。ただし、非常に多数のサンプルを扱っているため、正規分布近似の使用を検討する必要があります。