グラフの最小カットを確実にするための独立した時間少なくとも1つのトライアルが成功する

Question

私はちょうどcourseraの専門コースの最初のモジュールで終わった。

私がかなり理解できなかった試験問題がありました。私はその試験に合格したので、それを取り戻す必要はありません。

私はこの質問の周りの原則を学びたいと思います。

質問が等投稿されました：

はランダム化アルゴリズム（0 < P < 1）確率pで（例えば、正しくグラフの 最小カットを計算する）成功した​​と仮定する。 ε を小さな正の数（1未満）にします。

確率が少なくとも1-εで、少なくとも1回の試行が成功することを確実にするために、アルゴリズムを実行するために何回独立時間が必要ですか？所与

オプションは以下の通りであった：

ログ（1-P）/logε

ログ（P）/logε

logε/ログ（P）

logε/log（1-p）

2回の試みとその両方が間違っていた。私の試みがあった。

1. ログ（1-P）/logε
2. logε/ログ

それはそんなに私は正しい答えを知りたいではありません（1-P） 。私はこの質問の背後にある原則とそれが求めていることを学びたいと思っています。私は将来同様の質問に答える方法を知っています。

私はフォーラムにこれを掲載しましたが、誰も1か月後に回答しませんでした。だから私はここでそれを試しています。

いいえ、直接回答を投稿する必要はありません。あなたが私に瞬間をさせるようになったら、それを正しいものとしてマークします。

ありがとうございました。

Answer 1

少なくとも1-εの確率で少なくとも1回の試行が成功するように、アルゴリズムを実行するために何回独立した時間が必要ですか？

のは、それを少し言い換えてみましょう：

失敗し、それらのすべての確率がε以下となるように独立試行の最小の数は何ですか？

independent eventsの定義によって、それらのすべてが発生する確率は、個々の確率の積である。 1回の試行で失敗する確率は(1-p)なので、n試行が失敗する確率は(1-p)^nです。

これは私たちにnのための不平等を与える：

(1-p)^n <= ϵ