ランダム化問題で困っています。:)
ランダム化されたアルゴリズムである A は、入力 x が素数であるかどうかを判断します。
このアルゴリズムは次のように機能します。
1- x が素数の場合、A は YES を出力します
2- x が素数でない場合、A は確率 3/4 で NO を出力します。
アルゴリズム A が少なくとも 1-(1/k) の確率で NO を出力するようにしたい場合、少なくとも何回 A を実行する必要がありますか?
注: 1 つの NO の答えは、与えられた入力 x が素数でないことを意味します。
何か案が？
数値が素数でない場合、アルゴリズムの繰り返しでx「はい」になる確率は です。n(1/4)^n = 4^(-n) = 2^(-2n)
したがって、 を達成したい場合、実際には最大 の確率で偽陽性1-(1/k)を探していることになり、上記から次のことが必要になります。1/k
2^(-2n) <= 1/k //log_2 on both sides:
-2n <= log(1/k) = log(1)-log(k) = 0 - log(k)
2n >= log(k)
n >= log(k)/2
したがって、 の確率で真陰性を保証するために、n可能な限り最小の整数を選択する必要があります。n >= log(k)/21-1/k
(注: すべてlog()ベース 2 です)。
例:
99% の確率で正しくなりたい場合は、実際には1-1/k=0.99, so1/k=1/100およびを探していますk=100。
ここで、上記の式によると、 に注意してください。log_2(100) ~= 6.64したがって、最小nのものn >= log_2(100)/2はn==4です。
つまり、99% を達成するには、アルゴリズムを 4 回繰り返す必要があります。
これが正しいことを確認しましょう:
1-(1/4)^4 = 1-(1/256) ~= 0.996 >= 0.99ます。したがって、確率は問題ありません。1-(1/4)^3 = 1-1/64 ~= 0.984 < 0.99確認してくださいn==3。