Buch zur Wahrscheinlichkeit

32

Während ich sowohl an der High School als auch an der Universität einige Kurse über Wahrscheinlichkeitstheorie absolviert habe, fällt es mir schwer, TCS-Artikel zu lesen, wenn es um Wahrscheinlichkeit geht.

Es scheint, dass die Autoren der TCS-Artikel mit der Wahrscheinlichkeit sehr vertraut sind. Sie arbeiten magisch mit Wahrscheinlichkeitsformeln und beweisen Theoreme sehr leicht; während ich einige gute Stunden arbeiten muss, um zu verstehen, wie eine Formel abgeleitet wurde und wie Identitäten (oder Ungleichungen) bewiesen werden.

Ich habe mich entschlossen, mein Problem ein für alle Mal zu lösen: Ich möchte ein Buch von vorne bis hinten lesen.

Also, wenn Sie gebeten werden, ein und nur ein Buch zur Wahrscheinlichkeit vorzuschlagen, welches Buch werden Sie empfehlen?

Unglaublich
quelle
3
+1, weil ich eine gute Referenz schätzen würde. Darf ich auch vorschlagen, dass ein solches Buch die bayesianische Folgerung behandeln müsste?
Steve
4
@Incredible: Würdest du mehr klären? Ein Wahrscheinlichkeitsbuch im Allgemeinen oder ein Wahrscheinlichkeitsbuch, das sich mit der Verbindung zur theoretischen Informatik befasst?
Yoshio Okamoto
@Yoshio: Ich suche kein Buch, in dem die Wahrscheinlichkeit im Zusammenhang mit TCS erklärt wird. Ich brauche nur ein Buch, das ich, nachdem ich es vollständig durchgelesen habe, mit der Wahrscheinlichkeit vertraut machen kann, dass das Lesen und Entmystifizieren von TCS-Papieren wie ein Zauber wirkt.
Unglaublicher
@Steve: Ja, Bayesianische Folgerungen werden geschätzt. Ich habe kürzlich eine Arbeit gelesen ( Lower Bounds for Zero Knowledge im Internet ), in der Bayes'sche Folgerungen auf eine wesentliche Weise verwendet wurden, und ich konnte Theoreme und Lemmas nicht leicht entschlüsseln.
MS Dousti
1
wie kommt es, dass dies niemals CW wurde?
Suresh Venkat

Antworten:

22

Hast du diese beiden Bücher ausprobiert?

  1. Wahrscheinlichkeit und Rechnen: Randomisierte Algorithmen und probabilistische Analysen von Mitzenmacher und Upfal.
  2. Randomisierte Algorithmen von Motwani und Raghavan

Beachten Sie, dass diese beiden Bücher viel mehr als nur randomisierte Algorithmen behandeln, z. B. Probabilistische Methode, Markov-Ketten-Theorie, Martingale usw., natürlich mit vielen Anwendungen in TCS. Das erste Buch ist leichter zu lesen mit vielen Beispielen, deren Beweise detailliert ausgearbeitet wurden. Das zweite Buch ist wirklich ein Klassiker, nicht sehr aktualisiert, aber dennoch sehr nützlich. Beide haben viele Übungen, sodass Sie viel Material haben, um das zu üben, was Sie gelernt haben.

Dai Le
quelle
12

Das kanonische Grundstudium der Wahrscheinlichkeitstheorie bleibt ein erster Kurs in Wahrscheinlichkeit von Sheldon Ross. Das Buch ist eine hervorragende Referenz / Auffrischung für alle anderen. Ungeachtet dessen, was einige mürrische Internet-Rezensenten behaupten, behandelt das Buch alle wichtigen Themen in elementarer Wahrscheinlichkeit klar und mit starken motivierenden Beispielen.

Huck Bennett
quelle
11

Ich denke, die Lösung für Ihr Problem ist nicht das Lesen eines Wahrscheinlichkeitsbuchs, sondern das Lesen weiterer Artikel in TCS.

Die meisten Artikel in TCS verwenden keine hochentwickelten Wahrscheinlichkeitstools. Die meisten von ihnen verwenden eine kleine Sammlung grundlegender und bekannter Wahrscheinlichkeitstricks. Der Grund, warum Sie Schwierigkeiten haben, ihnen zu folgen, ist, dass Sie mit dieser Trickkiste noch nicht vertraut sind und viele dieser Artikel sich nicht die Mühe machen, diese Tricks zu erklären, da sie davon ausgehen, dass der Leser sie kennt. Einige dieser Tricks werden in den meisten Wahrscheinlichkeitsbüchern nicht gelehrt, zumindest nicht in der spezifischen Form, in der sie in TCS-Artikeln verwendet werden.

Ein weiterer Grund ist, dass TCS-Papiere eine etwas andere Terminologie verwenden als die in grundlegenden Wahrscheinlichkeitskursen gelehrten - z. B. kann in TCS-Papieren eine Zufallsvariable normalerweise Werte in annehmen , während in Wahrscheinlichkeitskursen Zufallsvariablen definiert sind als reale Werte nehmen.{0,1}n

Wenn Sie also mehr TCS-Artikel lesen, werden Sie sich mit den gängigen Tricks und der Terminologie vertraut machen und mit der Zeit werden sie leichter verständlich.

Trotzdem ist es immer eine gute Idee, ein Buch über Wahrscheinlichkeit zu lesen. Unter den oben vorgeschlagenen Büchern kenne ich mich nur mit "Wahrscheinlichkeitsrechnung und Computing: Randomisierte Algorithmen und Wahrscheinlichkeitsanalyse" von Mitzenmacher und Upfal aus, und es ist eine sehr gute Lektüre - insbesondere wird es Ihnen dabei helfen, sich mit einigen Begriffen vertraut zu machen und Tricks in TCS.

Oder Meir
quelle
Gut gesagt! Ich wünschte, wir könnten einige Gegenstände aus dieser "Trickkiste" sammeln, um Neulingen auf dem Gebiet zu helfen. Vielleicht kannst du ein Community-Wiki mit einem Beispiel starten.
MS Dousti
1
Bezüglich des Beispiels für Zufallsvariablen: Ich erinnere mich an vor 6 Jahren, als ich die gleiche Frage hatte: Warum werden TCS-Wohnmobile nicht über Real definiert? Ich suchte und fand die Antwort: Wohnmobile haben mehr zu bieten, als wir in elementaren Wahrscheinlichkeitsklassen lernen. Hier ist ein Link für Interessierte: en.wikipedia.org/wiki/… .
MS Dousti
9

Ein neueres Buch von Dubhashi und Panconesi liefert, um die Antwort von Dai Le zu ergänzen, viele Beispiele für die Verwendung der Wahrscheinlichkeit bei der Analyse von Algorithmen.

RJK
quelle
9

Ein weiterer Klassiker der TCS / Combinatorics-orientierten Wahrscheinlichkeit ist Alon and Spencer's The Probabilistic Method .

Yonatan
quelle
1
Dies ist eine gute Empfehlung. Wie Or Meir in seiner Antwort sagte, verwendet TCS eine relativ begrenzte Menge von Tricks aus der Wahrscheinlichkeitstheorie. Alons und Spencers Buch konzentriert sich auf diese Trickkiste, ohne sich in technischen Details der Wahrscheinlichkeitstheorie zu verlieren, die für TCS nicht so relevant sind.
Timothy Chow
8

Mehrere verwandte Themen auf verschiedenen SE-Websites:

  1. Buch für die Wahrscheinlichkeit
  2. Voraussetzungen zur Wahrscheinlichkeitstheorie
  3. Ergänzende Lektüre für Wahrscheinlichkeitsstudien
  4. Welches Buch würden Sie Nicht-Statistikern empfehlen (meist statistische Bücher) ?

Obwohl ich keines dieser Bücher gelesen habe, hatte ich den Luxus, mir einige davon anzuschauen. Ich mochte die dreibändige Serie von HPS (Hoel, Port und Stone). Es wurde nicht viel Hintergrund erwartet, und es gab eine klare Unterscheidung zwischen den Themen Wahrscheinlichkeit, Statistik und stochastischen Prozessen (für jedes Thema ist ein separater Band vorgesehen). Außerdem ist jeder Band ziemlich kurz.

Ich muss noch einmal betonen, dass mir der Inhalt der aufgelisteten Bücher nicht bekannt ist. Ich lade andere Mitglieder ein, diesen Beitrag zu kommentieren.

M.S. Dousti
quelle
6

Mehrere Plakate in dieser Diskussion empfahlen Fellers Set mit zwei Bänden . Ein neueres und angeblich auch sehr gutes Lehrbuch sind Grimmett und Stirzaker . Außerdem finden Sie hier eine interessante Bibliographie eines professionellen Statistikers.

Mikhail Glushenkov
quelle
Ich habe Feller und Grimmet und Stirzaker. Zusammen mit dem Online-MIT-Kurs "Fundamentals of Probability" hat es sich als ein gutes Tor zu Konzepten der Wahrscheinlichkeit erwiesen, die Sie als fortgeschrittener Senior- / Junior-Doktorand benötigen.
Chazisop
4

Ein sehr gutes Buch:

Wahrscheinlichkeit von Leo Breiman

Sylvain Peyronnet
quelle
4
Das Vorwort lautet: "Voraussetzung sind Kenntnisse der realen Variablentheorie, wie z. B. die Vorstellungen von Maß, messbaren Funktionen usw. Die ersten sieben Kapitel der Maßtheorie von Paul Halmos reichen in etwa aus ... Keine Vorkenntnisse von der Wahrscheinlichkeit wird ausgegangen, aber das Stöbern in einem elementaren Buch wie dem von William Feller (Vol. I) ... gibt ein ausgezeichnetes Gefühl für das Thema. " Dies muss ein fortgeschrittenes Buch sein!
MS Dousti
4

Konkrete Mathematik von Knuth et al. Viel Wahrscheinlichkeit besteht darin, die Größe Ihres Universums herauszufinden und von dort aus herauszufinden, an welchem ​​Bruchteil Ihres Universums Sie interessiert sind.

Chad Brewbaker
quelle
4

Ein ausgezeichnetes Einführungsbuch für Wahrscheinlichkeitsrecherchen für Informatiker ist Henk Tijms, Understanding Probability, Cambridge University Press, 2. Auflage, 2007. Dieses Buch unterscheidet sich von anderen einführenden Wahrscheinlichkeitstexten durch die Betonung, warum Wahrscheinlichkeit funktioniert und wie sie anzuwenden ist.

Chris
quelle
4

Von den genannten Büchern stimme ich Briemans "Probability", Sheldon Ross 'Buch "A First Course in Probability", dem Buch "Probability" von Hoel, Port and Stone aus ihren drei Bänden zu. Die meisten anderen Bücher kenne ich entweder nicht oder halte sie nicht für angemessen. Die Bayes'sche Statistik gehört nicht zur Wahrscheinlichkeitstheorie. Kai Li Chungs "A Course in Probability Theory" ist der Kurs, aus dem ich zusammen mit Band II von Fellers Buch "An Introduction to Probability Theory and its Applications" (Eine Einführung in die Wahrscheinlichkeitstheorie und ihre Anwendungen) gelernt habe. Feller ist gut für Heuristiken und interessante Probleme. Chung ist gut für die formale Mathematik. Feller und Chung können jedoch schwierig zu lesen sein, insbesondere für das Selbststudium. Ein weiterer großer Autor von Wahrscheinlichkeitsbüchern ist Sid Resnick. Sein Buch "A Probability Path" ist erfreulich zu lesen. Neveu's "Calculus of Probability" war ein weiteres Buch, das wir in meinem Absolventen-Wahrscheinlichkeitskurs verwendet haben.

Michael Chernick
quelle
2

Ein großartiges Buch mit EE-Slant: http://www.mhhe.com/engcs/electrical/papoulis/ Ein fantastisches Buch mit CS-Slant: http://www.amazon.com/dp/0471333417/ .

Benutzer4563
quelle
Ich mag auch Papoulis, obwohl ich nicht sicher bin, ob es für eine neue Ausgabe eine 50-prozentige Erhöhung des Volumens oder einen neuen Autor benötigt. Wenn Sie feststellen, dass eine ältere Ausgabe (z. B. die zweite Auflage, die von Dell veröffentlicht und in großen Mengen verkauft wurde) billig ist, kaufen Sie sie.
András Salamon
1

Dieses Buch wird für eine Intro-Wahrscheinlichkeitsklasse am MIT verwendet. http://vfu.bg/en/e-Learning/Math--Bertsekas_Tsitsiklis_Introduction_to_probability.pdf

Inhaltsverzeichnis:

  • Probenraum und Wahrscheinlichkeit
  • Diskrete Zufallsvariablen
  • Allgemeine Zufallsvariablen
  • Weitere Themen zu Zufallsvariablen und Erwartungen
  • Die Bernoulli- und Poisson-Prozesse
  • Markov-Ketten
  • Grenzwertsätze
sk8asd123
quelle