Livre sur la probabilité

32

Alors que j'ai réussi quelques cours sur la théorie des probabilités, tant au lycée qu'à l'université, j'ai du mal à lire les articles TCS en matière de probabilité.

Il semble que les auteurs des articles du TCS connaissent très bien la probabilité. Ils fonctionnent comme par magie avec des formules de probabilité et prouvent les théorèmes très facilement; alors que je dois travailler de bonnes heures pour comprendre comment une formule a été dérivée et comment les identités (ou inégalités) sont prouvées.

J'ai décidé de résoudre mon problème une fois pour toutes: je veux lire un livre de couverture en couverture.

Donc, si on vous demande de suggérer un et un seul livre sur la probabilité, quel livre recommanderez-vous?

incroyable
la source
3
+1 parce que j'apprécierais une bonne référence. Aussi, puis-je suggérer qu'un tel livre devrait couvrir l'inférence bayésienne?
Steve
4
@Incredible: Pourriez-vous clarifier davantage? Un livre de probabilités en général ou un livre de probabilités axé sur le lien avec l'informatique théorique?
Yoshio Okamoto
@Yoshio: Je ne cherche pas un livre dans lequel la probabilité dans le contexte du TCS est expliquée. J'ai juste besoin d'un livre qui, après l'avoir lu de bout en bout, je peux me familiariser avec les probabilités pour que la lecture et la démystification des papiers TCS fonctionnent comme un charme.
Incroyable
@Steve: Oui, l'inférence bayésienne est appréciée. J'ai récemment lu un article ( Lower Bounds for Zero Knowledge on Internet ) dans lequel l'inférence bayésienne était utilisée de manière essentielle, et je ne pouvais pas facilement décrypter les théorèmes et les lemmes.
MS Dousti
1
comment se fait-il que cela ne soit jamais devenu CW?
Suresh Venkat

Réponses:

22

Avez-vous essayé ces deux livres?

  1. Probabilité et calcul: algorithmes randomisés et analyse probabiliste par Mitzenmacher et Upfal.
  2. Algorithmes randomisés de Motwani et Raghavan

Notez que ces deux livres couvrent bien plus que des algorithmes aléatoires, par exemple ils couvrent la méthode probabiliste, la théorie de la chaîne de Markov, les martingales, etc., bien sûr avec de nombreuses applications dans TCS. Le premier livre est plus facile à lire avec de nombreux exemples dont les épreuves ont été élaborées en détail. Le deuxième livre est vraiment un classique, pas très mis à jour, mais toujours très utile. Ils ont tous deux beaucoup d'exercices, vous aurez donc beaucoup de matériel pour mettre en pratique ce que vous avez appris.

Dai Le
la source
12

Le manuel canonique de premier cycle pour la théorie des probabilités reste un premier cours de probabilité par Sheldon Ross. Le livre est une excellente référence / recyclage pour tout le monde. Indépendamment de ce que quelques critiques grincheux d'Internet affirment, le livre couvre tous les sujets les plus importants en probabilité élémentaire de manière claire et avec de solides exemples de motivation.

Huck Bennett
la source
11

Je pense que la solution à votre problème n'est pas de lire un livre de probabilités, mais de lire plus d'articles dans TCS.

La plupart des articles de TCS n'utilisent pas réellement d'outils de probabilité très avancés. La plupart d'entre eux utilisent une petite collection d'astuces de probabilité de base et bien connues. La raison pour laquelle vous avez du mal à les suivre est que vous n'êtes pas encore familier avec ce sac d'astuces, et beaucoup de ces articles ne prennent pas la peine d'expliquer ces astuces car ils supposent que le lecteur les connaît. Certains de ces trucs ne sont pas enseignés dans la plupart des livres de probabilités, du moins pas sous la forme spécifique qu'ils sont utilisés dans les articles TCS.

Une autre raison est que les articles TCS utilisent une terminologie légèrement différente de celle enseignée dans les cours de probabilité de base - par exemple, dans les articles TCS, une variable aléatoire peut généralement prendre des valeurs dans , tandis que dans les cours probabilistes, les variables aléatoires sont définis comme prenant des valeurs réelles.{0,1}n

Ainsi, en lisant plus d'articles TCS, vous vous familiariserez avec le sac d'astuces courantes et avec la terminologie, et avec le temps, ils seront plus faciles à comprendre.

Cela dit, lire un livre sur les probabilités est toujours une bonne idée. Parmi les livres suggérés ci-dessus, je ne connais que "Probability and Computing: Randomized Algorithms and Probabilistic Analysis" de Mitzenmacher et Upfal, et c'est une très bonne lecture - en particulier, cela vous aidera à vous familiariser avec certaines terminologies et astuces utilisées dans TCS.

Ou Meir
la source
Bien dit! Je souhaite que nous puissions rassembler quelques articles de ce "sac d'astuces", afin d'aider les nouveaux arrivants sur le terrain. Vous pouvez peut-être créer un wiki communautaire avec un exemple.
MS Dousti
1
Concernant l'exemple des variables aléatoires: Je me souviens il y a 6 ans, quand j'avais cette même question: pourquoi les RV TCS ne sont-ils pas définis sur des réels? J'ai cherché et trouvé la réponse: les VR sont plus que ce que nous apprenons dans les classes de probabilité élémentaires. Voici un lien pour les personnes intéressées: en.wikipedia.org/wiki/… .
MS Dousti
9

Un autre classique de la probabilité orientée TCS / combinatoire est la méthode probabiliste d'Alon et Spencer .

Yonatan
la source
1
C'est une bonne recommandation. Comme Or Meir l'a dit dans sa réponse, TCS utilise un ensemble relativement limité de trucs de la théorie des probabilités. Le livre d'Alon et Spencer se concentre sur ce sac d'astuces sans s'enliser dans les détails techniques de la théorie des probabilités qui ne sont pas si pertinents pour TCS.
Timothy Chow
8

Plusieurs sujets connexes sur différents sites Web SE:

  1. Réservez pour la probabilité
  2. Prérequis sur la théorie des probabilités
  3. Lecture supplémentaire pour les études de théorie des probabilités
  4. Quel livre recommanderiez-vous aux non-statisticiens (surtout des livres statistiques)

Bien que je n'aie lu aucun de ces livres, j'ai eu le luxe de jeter un œil à certains d'entre eux. J'ai aimé la série en trois volumes de HPS (Hoel, Port et Stone). Il ne s'attendait pas à beaucoup de contexte, et il y avait une distinction claire entre la probabilité des sujets, les statistiques et les processus stochastiques (un volume séparé est consacré à chaque sujet). De plus, chaque volume est assez court.

Je dois souligner à nouveau que je ne suis au courant du contenu d'aucun des livres répertoriés. J'invite les autres membres à commenter ce post.

M.S. Dousti
la source
6

Plusieurs affiches dans cette discussion ont recommandé l'ensemble en deux volumes de Feller . Grimmett et Stirzaker sont un manuel plus récent et également très bon . De plus, voici une bibliographie intéressante par un statisticien professionnel.

Mikhail Glushenkov
la source
J'ai eu Feller et Grimmet et Stirzaker. Avec le cours en ligne du MIT "Fundamentals of Probability", il s'est avéré une bonne passerelle vers les concepts de probabilité dont vous aurez besoin en tant qu'étudiant avancé avancé / junior.
chazisop
4

Un très bon livre:

Probabilité par Leo Breiman

Sylvain Peyronnet
la source
4
La préface dit: « Une condition sine qua non est une certaine connaissance de la vraie théorie des variables, comme les idées de mesure, fonctions mesurables, etc. En gros, les premiers. Sept chapitres de théorie de la mesure par Paul Halmos est suffisamment d' expérience ... Aucune connaissance préalable de probabilité est supposé, mais parcourir un livre élémentaire tel que celui de William Feller (Vol. I) ... donne une excellente sensation pour le sujet. " Ce doit être un livre avancé !
MS Dousti
4

Mathématiques concrètes par Knuth et al. Une grande partie de la probabilité consiste à déterminer la taille de votre univers, et à partir de là, à déterminer quelle fraction de votre univers vous intéresse.

Chad Brewbaker
la source
4

Henk Tijms, Understanding Probability, Cambridge University Press, 2e éd., 2007 constitue un excellent livre d'introduction aux probabilités pour les informaticiens. Ce livre se distingue des autres textes d'introduction sur les probabilités en mettant l'accent sur les raisons pour lesquelles la probabilité fonctionne et comment l'appliquer.

Chris
la source
4

Parmi les livres mentionnés, je suis d'accord sur "Probability" de Brieman, le livre de Sheldon Ross "A First Course in Probability" Le livre "Probability" de Hoel, Port et Stone de leurs trois volumes. La plupart des autres livres que je ne connais pas ou qui ne me semblent pas appropriés. Les statistiques bayésiennes ne font pas partie de la théorie des probabilités. "Un cours en théorie des probabilités" de Kai Li Chung est celui que j'ai appris avec le volume II du livre de Feller "Une introduction à la théorie des probabilités et ses applications" sont de bons livres que j'ai appris. Feller est bon pour l'heuristique et les problèmes intéressants. Chung est bon pour les mathématiques formelles. Feller et Chung peuvent être difficiles à lire, surtout pour l'auto-apprentissage. Un autre grand écrivain de livres de probabilités est Sid Resnick. Son livre "A Probability Path" est agréable à lire. Le "Calcul de probabilité" de Neveu était un autre livre que nous avons utilisé dans mon cours de probabilité diplômé.

Michael Chernick
la source
2

Un grand livre avec EE slant: http://www.mhhe.com/engcs/electrical/papoulis/ un livre fantastique avec CS slant: http://www.amazon.com/dp/0471333417/ .

utilisateur4563
la source
J'aime aussi Papoulis, même si je ne suis pas sûr qu'il ait fallu une augmentation de 50% en volume, ou un nouvel auteur, pour une nouvelle édition. Si vous voyez une édition plus ancienne (par exemple la deuxième édition de réimpression qui a été publiée par Dell et vendue en grande quantité) à bon marché, achetez-la.
András Salamon
1

Ce livre est utilisé pour une classe de probabilité d'introduction au MIT. http://vfu.bg/en/e-Learning/Math--Bertsekas_Tsitsiklis_Introduction_to_probability.pdf

Table des matières:

  • Échantillon d'espace et probabilité
  • Variables aléatoires discrètes
  • Variables aléatoires générales
  • Autres sujets sur les variables aléatoires et les attentes
  • Les processus de Bernoulli et de Poisson
  • Chaînes de Markov
  • Théorèmes limites
sk8asd123
la source