Libro sobre probabilidad

32

Si bien he aprobado algunos cursos sobre teoría de la probabilidad, tanto en la escuela secundaria como en la universidad, me cuesta leer los documentos de TCS cuando se trata de probabilidad.

Parece que los autores de los artículos de TCS están muy familiarizados con la probabilidad. Trabajan mágicamente con fórmulas de probabilidad y prueban teoremas muy fácilmente; mientras que tengo que trabajar algunas horas para comprender cómo se derivó una fórmula y cómo se prueban las identidades (o desigualdades).

Decidí resolver mi problema de una vez por todas: quiero leer un libro de principio a fin.

Entonces, si se le pide que sugiera un solo libro sobre probabilidad, ¿qué libro recomendará?

increíble
fuente
3
+1 porque agradecería una buena referencia. Además, ¿puedo sugerir que un libro de este tipo debería cubrir la inferencia bayesiana?
Steve
44
@Incredible: ¿Podría aclarar más? ¿Un libro de probabilidades en general, o un libro de probabilidades que se centre en la conexión con la informática teórica?
Yoshio Okamoto
@Yoshio: No busco un libro en el que se explique la probabilidad en el contexto de TCS. Solo necesito un libro que, después de leerlo de principio a fin, pueda familiarizarme con la probabilidad para que leer y desmitificar los documentos de TCS funcionen de maravilla.
Increíble el
@ Steve: Sí, se aprecia la inferencia bayesiana. Hace poco leí un artículo ( Límites inferiores para conocimiento cero en Internet ) en el que se usaba la inferencia bayesiana de una manera esencial, y no podía descifrar fácilmente teoremas y lemas.
MS Dousti 01 de
1
¿Cómo es que esto nunca se convirtió en CW?
Suresh Venkat

Respuestas:

22

¿Has probado estos dos libros?

  1. Probabilidad e informática: algoritmos aleatorios y análisis probabilístico de Mitzenmacher y Upfal.
  2. Algoritmos aleatorizados por Motwani y Raghavan

Tenga en cuenta que estos dos libros cubren mucho más que algoritmos aleatorios, por ejemplo, cubren el Método Probabilístico, la Teoría de la Cadena de Markov, Martingales, etc., por supuesto, con muchas aplicaciones en TCS. El primer libro es más fácil de leer con muchos ejemplos cuyas pruebas se elaboraron en detalle. El segundo libro es realmente un clásico, no muy actualizado, pero aún muy útil. Ambos tienen muchos ejercicios, por lo que tendrás mucho material para practicar lo que has aprendido.

Dai Le
fuente
12

El libro de texto canónico de pregrado para la teoría de la probabilidad sigue siendo un primer curso de probabilidad de Sheldon Ross. El libro es una excelente referencia / actualización para todos los demás. Independientemente de lo que afirman algunos críticos grupales de Internet, el libro cubre todos los temas más importantes en probabilidad elemental de manera clara y con fuertes ejemplos motivadores.

Huck Bennett
fuente
11

Creo que la solución a su problema no es leer un libro de probabilidades, sino leer más documentos en TCS.

La mayoría de los documentos en TCS en realidad no usan herramientas de probabilidad muy avanzadas. La mayoría de ellos usan una pequeña colección de trucos de probabilidad básicos y bien conocidos. La razón por la que tiene dificultades para seguirlos es que aún no está familiarizado con esta bolsa de trucos, y muchos de esos documentos no se molestan en explicar estos trucos porque suponen que el lector los conoce. Algunos de esos trucos no se enseñan en la mayoría de los libros de probabilidad, al menos no en la forma específica en que se usan en los documentos de TCS.

Otra razón es que los documentos de TCS usan una terminología ligeramente diferente a la que se enseña en los cursos de probabilidad básica; por ejemplo, en los documentos de TCS, una variable aleatoria generalmente puede tomar valores en , mientras que generalmente en los cursos de probabilidad de variables aleatorias se definen como tomar valores reales.{0,1}n

Entonces, al leer más documentos de TCS, se familiarizará más con la bolsa de trucos comunes y con la terminología, y con el tiempo serán más fáciles de entender.

Dicho esto, leer un libro sobre probabilidad es siempre una buena idea. Entre los libros sugeridos anteriormente, solo estoy familiarizado con "Probabilidad e informática: algoritmos aleatorios y análisis probabilístico" de Mitzenmacher y Upfal, y es una muy buena lectura, en particular, te ayudará a familiarizarte con algunos de los términos. y trucos usados ​​en TCS.

O meir
fuente
¡Bien dicho! Ojalá pudiéramos reunir algunos artículos de esta "bolsa de trucos" para ayudar a los recién llegados al campo. Tal vez puedas comenzar un wiki comunitario con un ejemplo.
MS Dousti
1
Con respecto al ejemplo de variables aleatorias: recuerdo hace 6 años, cuando tenía esta misma pregunta: ¿Por qué los RV TCS no se definen sobre los reales? Busqué y encontré la respuesta: hay más RV que aprendemos en las clases de probabilidad elementales. Aquí hay un enlace para los interesados: en.wikipedia.org/wiki/… .
MS Dousti
9

Otro clásico de la probabilidad orientada a TCS / Combinatoria es el Método Probabilístico de Alon y Spencer .

Yonatan
fuente
1
Esta es una buena recomendación. Como dijo Or Meir en su respuesta, TCS usa una bolsa de trucos relativamente limitada de la teoría de la probabilidad. El libro de Alon y Spencer se enfoca en esta bolsa de trucos sin atascarse en detalles técnicos de la teoría de la probabilidad que no son tan relevantes para TCS.
Timothy Chow
8

Varios temas relacionados en diferentes sitios web de SE:

  1. Libro de probabilidad
  2. Prerrequisitos sobre teoría de probabilidad
  3. Lectura suplementaria para estudios de teoría de probabilidad
  4. ¿Qué libro recomendaría para los no estadísticos (en su mayoría libros de estadísticas)

Si bien no he leído ninguno de estos libros, tuve el lujo de echar un vistazo a algunos de ellos. Me gustó la serie de tres volúmenes de HPS (Hoel, Port y Stone). No esperaba mucho antecedente, y había una clara distinción entre la probabilidad de los temas, las estadísticas y los procesos estocásticos (se dedica un volumen separado a cada tema). Además, cada volumen es bastante corto.

Debo enfatizar que no conozco el contenido de ninguno de los libros enumerados. Invito a otros miembros a comentar sobre esta publicación.

M.S. Dousti
fuente
6

Varios carteles en esta discusión recomendaron el conjunto de dos volúmenes de Feller . Un libro de texto más reciente y, según informes, muy bueno es Grimmett y Stirzaker . Además, aquí hay una bibliografía interesante de un estadístico profesional.

Mikhail Glushenkov
fuente
Tengo a Feller, Grimmet y Stirzaker. Junto con el curso en línea del MIT "Fundamentos de probabilidad", ha demostrado ser una buena puerta de entrada a los conceptos de probabilidad que necesitará como un estudiante avanzado de posgrado senior / junior.
chazisop
4

Un muy buen libro:

Probabilidad por Leo Breiman

Sylvain Peyronnet
fuente
44
El prefacio dice: "Un requisito previo es cierto conocimiento de la teoría de la variable real, como las ideas de medida, funciones medibles, etc. Aproximadamente, los primeros siete capítulos de la Teoría de la Medida por Paul Halmos son antecedentes suficientes ... Sin conocimiento previo se asume la probabilidad, pero navegar a través de un libro elemental como el de William Feller (Vol. I) ... da una excelente sensación sobre el tema ". ¡Este debe ser un libro avanzado !
MS Dousti 01 de
4

Matemáticas concretas por Knuth et al. Gran parte de la probabilidad es determinar el tamaño de su universo y, a partir de ahí, determinar qué fracción de su universo le interesa.

Chad Brewbaker
fuente
4

Henk Tijms, Understanding Probability, Cambridge University Press, 2nd ed., 2007. Este libro se distingue de otros textos introductorios de probabilidad por su énfasis en por qué funciona la probabilidad y cómo aplicarla.

Chris
fuente
4

De los libros mencionados, estoy de acuerdo con "Probability" de Brieman, el libro de Sheldon Ross "A First Course in Probability" El libro "Probability" de Hoel, Port y Stone de sus tres series de Volume. La mayoría de los otros libros que no conozco o no creo que sean apropiados. La estadística bayesiana no es parte de la teoría de la probabilidad. "Un curso de teoría de la probabilidad" de Kai Li Chung es el que aprendí junto con el volumen II del libro de Feller "Introducción a la teoría de la probabilidad y sus aplicaciones" son buenos libros de los que aprendí. Feller es bueno para la heurística y los problemas interesantes. Chung es bueno para las matemáticas formales. Sin embargo, Feller y Chung pueden ser difíciles de leer, especialmente para el autoaprendizaje. Otro gran escritor de libros de probabilidad es Sid Resnick. Es encantador leer su libro "Un camino de probabilidad". El "Cálculo de probabilidad" de Neveu fue otro libro que usamos en mi curso de probabilidad de posgrado.

Michael Chernick
fuente
2

Un gran libro con inclinación EE: http://www.mhhe.com/engcs/electrical/papoulis/ un libro fantástico con inclinación CS: http://www.amazon.com/dp/0471333417/ .

usuario4563
fuente
También me gusta Papoulis, aunque no estoy seguro de que necesitara un aumento del 50% en volumen, o un nuevo autor, para una nueva edición. Si ve que una edición anterior (por ejemplo, la segunda edición de reimpresión que fue publicada por Dell y vendida en grandes cantidades) se vuelve barata, cómprela.
András Salamon