algorithm - ランダム化アルゴリズムの特性 (モンテカルロ、ラスベガス)

Question

私は現在、ラスベガスとモンテカルロのアルゴリズムを自分で学んでおり、2つの質問は簡単かもしれませんが、誰かが私を助けてくれれば答えられません...事前に感謝します

1. 確率 y(n) で正しい解を生成するサイズ n の任意のインスタンスで予想実行時間が最大 T(n) である問題 P のモンテカルロ アルゴリズム A を考えます。さらに、P の解が与えられた場合、時間 t(n) でその正しさを検証できるとします。P に対して常に正しい答えを与え、最大で期待される時間 (T(n)+t(n))/y(n) で実行されるラスベガス アルゴリズムを取得する方法を示します。

2. 0<ε2<ε1<1 とする。入力に関係なく、少なくとも 1-ε1 の確率で問題の正しい解を与えるモンテカルロ アルゴリズムを考えてみましょう。入力に関係なく、少なくとも 1-ε2 の正しい解を得る確率を上げるには、このアルゴリズムを何回独立して実行すれば十分ですか?

Answer 1

1. 正しい答えが得られるまで、アルゴリズムの実行と結果のテストを繰り返すだけです。各実行とチェックには (T(n) + t(n)) 単位の時間がかかり、実行回数は平均 1 / y(n) の幾何確率変数です。

2. 1回の実行で失敗する確率は? 2回の実行で？nラン？n 回の実行の失敗確率を e2 に設定し、n について解きます。