隨機算法的性質（蒙特卡洛，拉斯維加斯）

Question

我現在正在學習拉斯維加斯和蒙特卡羅算法，並有兩個問題可能很簡單，但我無法回答他們，如果有人可以幫助我......謝謝預先

1. 考慮蒙特卡洛算法爲一個問題P上產生的概率Y（N）正確的溶液大小爲n的任何實例，其預期的運行時間爲至多T（n）中。進一步假設給出了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. 一次運行失敗的概率是多少？兩次運行？ n運行？設n次運行失敗的概率等於e2並求解n。