ランダム化されたアルゴリズムの確率

Question

秋には、グレードレベルのランダム化アルゴリズムコースを取得しています。教授は非常に詳細指向で数学的に厳密であることで知られているので、私は確率を深く理解する必要があります。それから学ぶための良い確率の本は何でしょうか？

Answer 1

コースはどのような教科書を推奨していますか？ MitzenmacherとUpfalによる「確率とコンピューティング」、MotwaniとRaghavanによる「ランダム化アルゴリズム」が好きです。彼らは、アルゴリズムの視点から必要な理論を紹介します。また、ランダム化されたアルゴリズムの分析には境界のあるものが非常に不可欠であるため、不平等に関する本もお勧めします。少なくとも このチートシート.

Answer 2

実際には、確率理論に関する数学的に厳密なテキストは必要ありません。教授が$ sigma $ -lgebrasなどを使用することを疑います（彼らがマーティンガレスに言及し、これらの用語を使用してそれらについて議論することを好む場合を除き、誰も従うことができません）。おそらく必要なのはです 理解 たとえば、そのようなコースでは、「プレイ」だけで得られる可能性のある理論の理論です。背景がまったくない場合は、紹介テキストを撮影して、いくつかの演習で作業してください。