9

min場合によっては、 からまでの範囲の乱数の反復に対してループを実行する必要がありますmax。実用的な解決策の 1 つは、次のようなことです。

int numIterations = randomInteger(min, max);
for (int i = 0; i < numIterations; i++) {
   /* ... fun and exciting things! ... */
}

多くの初心者プログラマーが犯すよくある間違いは、次のようにすることです。

for (int i = 0; i < randomInteger(min, max); i++) {
   /* ... fun and exciting things! ... */
}

これにより、反復ごとにループの上限が再計算されます。

これは、ループが からまでの範囲で繰り返される回数の均一な分布を与えないのではないかと思いますが、このようなことをしたときにどのような分布が得られるか正確にはわかりません。ループの反復回数の分布がどうなるか知っている人はいますか?minmax

具体例として、min= 0 とmax= 2 と仮定します。その場合、次の可能性があります。

  • の場合i = 0、ランダム値は 0 です。ループは 0 回実行されます。
  • の場合i = 0、ランダム値は非ゼロです。それで：
    • の場合i = 1、ランダム値は 0 または 1 です。ループは 1 回実行されます。
    • の場合i = 1、ランダム値は 2 です。ループは 2 回実行されます。

この最初のイベントの確率は 1/3 です。2 番目のイベントの確率は 2/3 で、その中で最初のサブケースの確率は 2/3、2 番目のイベントの確率は 1/3 です。したがって、平均配布数は

0 × 1 / 3 + 1 × 2 / 3 × 2 / 3 + 2 × 2 / 3 × 1 / 3

= 0 + 4 / 9 + 4 / 9

= 8 / 9

分布が実際に均一である場合、1 回のループ反復が得られると予想されますが、現在は平均で 8/9 しか得られないことに注意してください。私の質問は、この結果を一般化して、反復回数のより正確な値を取得できるかどうかです。

ありがとう！

4

4 に答える 4

5

最終編集（たぶん！）。これが適切な標準ディストリビューションの 1 つではないことは 95% 確信しています。確率を与えるコードの方が読みやすいと思うので、この記事の最後に分布が何であるかを記載しました! に対する平均反復回数のプロットをmax以下に示します。

ここに画像の説明を入力

興味深いことに、最大値を増やすと反復回数が減少します。他の誰かが自分のコードでこれを確認できれば興味深いでしょう。

これをモデル化し始めるとしたら、幾何分布から始めます。、それを変更してみてください。基本的に、私たちは離散的で境界のある分布を見ています。したがって、0 回以上の「失敗」(停止条件を満たさない) の後に 1 つの「成功」が続きます。ここでの問題点は、幾何学的またはポアソンと比較して、成功の確率が変化することです (また、ポアソンと同様に、幾何学的分布は無制限ですが、構造的には幾何学的が良いベースであると思います)。min=0 と仮定すると、P(X=k) の基本的な数学的形式 0 <= k <= max (k はループが実行される反復回数) は、幾何学的分布と同様に、k 個の故障項とループ条件の k 個の「偽」と 1 個の「真」に対応する 1 つの成功項。(停止の可能性は 1 であるため、これは最後の確率の計算にも当てはまることに注意してください。

これに続いて、R のコードでこれを実装しようとすると、次のようになります。

fx = function(k,maximum)
{
    n=maximum+1;
    failure = factorial(n-1)/factorial(n-1-k) / n^k;
    success = (k+1) / n;
    failure * success
}

これは min=0 を想定していますが、任意minの s に一般化することは難しくありません (OP に関する私のコメントを参照してください)。コードを説明します。まず、OPで示されているように、確率はすべて(min+1)分母として持っているので、分母を計算しますn。次に、故障項の積を計算します。factorial(n-1)/factorial(n-1-k)これは、たとえば、min=2、n=3、k=2 の場合、2*1 を意味します。そして、それは一般化して (n-1) (n-2) ... を総失敗確率として与えます。成功する確率は、ループに入るにつれて増加し、最終的にk=maximumが 1 になるまで続きます。

この解析式をプロットすると、OP と同じ結果が得られ、John Kugelman によってプロットされたシミュレーションと同じ形になります。

ここに画像の説明を入力

ちなみにこれを行うRコードは以下の通り

plot_probability_mass_function = function(maximum)
{
    x=0:maximum;
    barplot(fx(x,max(x)), names.arg=x, main=paste("max",maximum), ylab="P(X=x)");
}

par(mfrow=c(3,1))
plot_probability_mass_function(2)
plot_probability_mass_function(10)
plot_probability_mass_function(100)

数学的には、私の数学が正しければ、分布は次のようになります。

ここに画像の説明を入力

これは次のように単純化されます

ここに画像の説明を入力

( http://www.codecogs.com/latex/eqneditor.phpに感謝します)

後者はR関数によって与えられます

function(x,m) { factorial(m)*(x+1)/(factorial(m-x)*(m+1)^(x+1)) }

平均反復回数のプロットは、R では次のように行われます

meanf = function(minimum)
{
    x = 0:minimum
    probs = f(x,minimum)
    x %*% probs
}

meanf = function(maximum)
{
    x = 0:maximum
    probs = f(x,maximum)
    x %*% probs
}

par(mfrow=c(2,1))
max_range = 1:10
plot(sapply(max_range, meanf) ~ max_range, ylab="Mean number of iterations", xlab="max")
max_range = 1:100
plot(sapply(max_range, meanf) ~ max_range, ylab="Mean number of iterations", xlab="max")
于 2013-04-19T20:26:12.030 に答える
0

十分な量の実行が与えられたとしても、randomInteger関数の分布に準拠すると思います。

しかし、これはおそらくMATHEMATICSで質問するのに適した質問です。

于 2013-04-19T19:23:23.927 に答える