Probabilidad de algoritmos aleatorios

Question

Estoy tomando un curso de algoritmos aleatorios de nivel de graduación en el otoño. El profesor es conocido por estar muy orientado a los detalles y matemáticamente riguroso, por lo que se requerirá que tenga una comprensión profunda de la probabilidad. ¿Cuál sería un buen libro de probabilidad para aprender de eso sería intuitivo, pero también tiene algún rigor matemático?

Answer 1

¿Qué libros de texto recomiendan el curso? Me gusta "probabilidad y computación" de Mitzenmacher y UPFAL y "Algoritmos aleatorios" de Motwani y Raghavan. Presentan la teoría necesaria desde un punto de vista de algoritmos. También recomiendo un libro sobre desigualdades, ya que limitar las cosas es bastante esencial para el análisis de algoritmos aleatorios. Por lo menos esta hoja de trucos.

Answer 2

En realidad, no necesita un texto matemáticamente riguroso sobre la teoría de la probabilidad. Dudo que el profesor use $ Sigma $-Algebras y similares (a menos que mencionen martingales y prefieran discutirlos usando estos términos; nadie podría seguir). Lo que probablemente necesite es un comprensión de teoría de probabilidad, que solo puedes obtener "jugando" con ella, por ejemplo, en un curso como ese. Si no tiene antecedentes, simplemente tome un texto introductorio y trabaje a través de algunos de los ejercicios.