Stochastik für Informatiker

Stochastische Methoden finden in der Informatik zahlreiche Einsatzfelder, insbesondere in der Bio- und Medizinischen Informatik. Ziel des Buches ist es eine Einführung in die Grundlagen der Stochastik zu geben, wobei viele Anwendungsbeispiele für die notwendigen Theorie motivieren und diese illustriert. Über weite Strecken konzentriert sich das Buch auf die für die Informatik besonders wichtigen diskreten Modelle. Besonderes Augenmerk wird auch darauf gelegt, die Brücke zur Numerik zu schlagen, weshalb z.B. exakte Konfidenzintervalle sehr ausführlich behandelt werden. Um dem immer wichtiger werdenden Gebiet der Bioinformatik Rechnung zu tragen, werden entsprechende Beispiele (z.B. Hardy-Weinberg-Gesetz, medizinische Tests, Sequenzvergleiche) und Methoden (exponentielle Schranken, EM-Algorithmus) behandelt, so dass auch Informatiker mit Nebenfach Medizin und Biologie das Buch mit Gewinn lesen können. Hinweise zu weiterführender Literatur runden das Buch ab.

1 Einleitung.- 2 Laplace-Verteilungen und diskrete Modelle.- 2.1 Stichproben und Permutationen.- 2.2 Diskrete Wahrscheinlichkeitsräume.- 2.3 Übungsaufgaben.- 3 Bedingte Wahrscheinlichkeiten und stochastische Unabhängigkeit.- 3.1 Kolmogorovs Axiome für Wahrscheinlichkeiten.- 3.2 Bedingte Wahrscheinlichkeiten.- 3.3 Stochastische Unabhängigkeit.- 3.4 Das Hardy-Weinberg-Gesetz.- 3.5 Produkträume.- 3.6 Übungsaufgaben.- 4 Zufallsvariablen und spezielle Verteilungen.- 4.1 Stochastische Unabhängigkeit.- 4.2 Spezielle Verteilungen.- 4.3 Kodierungen von Permutationen.- 4.4 Faltungen.- 4.5 Die Laufzeit von 'QuickSort'.- 4.6 Übungsaufgaben.- 5 Statistische Anwendungen: Konfidenzbereiche.- 5.1 Konfidenzbereiche.- 5.2 Konfidenzschranken für Binomialparameter.- 5.3 Konfidenzschranken für hypergeometrische Verteilungen.- 5.4 Vergleich zweier Binomialparameter.- 5.5 Übungsaufgaben.- 6 Erwartungswerte und Standardabweichungen.- 6.1 Definition und Eigenschaften des Erwartungswertes.- 6.2 Die Markov-Ungleichung.- 6.3 Produkte von Zufallsvariablen.- 6.4 Varianzen und Standardabweichungen.- 6.5 Kovarianzen.- 6.6 Anwendungen.- 6.7 Das schwache Gesetz der großen Zahlen.- 6.8 Übungsaufgaben.- 7 Erzeugende Funktionen und Exponentialungleichungen.- 7.1 Erzeugende Funktionen.- 7.2 Momentenerzeugende Funktionen.- 7.3 Exponentialungleichungen.- 7.4 Die Hoeffding-Ungleichung.- 7.5 Übungsaufgaben.- 8 Informationstheorie.- 8.1 Fragestrategien und Kodes.- 8.2 Entropie.- 8.3 Optimale Kodierung nach der Huffman-Methode.- 8.4 Übungsaufgaben.- 9 Allgemeine Wahrscheinlichkeitsräume.- 9.1 Die Kolmogorovschen Axiome.- 9.2 Existenz und Eindeutigkeit von Maßen.- 9.3 Bernoullifolgen.- 9.4 Wahrscheinlichkeitsmaße auf R.- 9.5 Übungsaufgaben.- 10 Integrale und Erwartungswerte.- 10.1Lebesgue-Integrale.- 10.2 Erwartungswerte.- 10.3 Der Satz von Fubini.- 10.4 Die Transformationsformel für das Lebesguemaß.- 10.5 Starke Gesetze der großen Zahlen.- 10.6 Übungsaufgaben.- 11 Computersimulation von Zufallsvariablen.- 11.1 Monte-Carlo-Schätzer.- 11.2 Pseudozufallszahlen.- 11.3 Acceptance-Rejection-Verfahren.- 11.4 Übungsaufgaben.- 12 Markovketten.- 12.1 Definition, Beispiele und allgemeine Eigenschaften.- 12.2 Homogene Markovketten.- 12.3 Absorptionswahrscheinlichkeiten.- 12.4 Das Langzeitverhalten.- 12.5 Simulated Annealing.- 12.6 Übungsaufgaben.- 13 Approximation von Verteilungen.- 13.1 Die Poissonapproximation.- 13.2 Poissonprozesse.- 13.3 Normalapproximationen.- 13.4 Übungsaufgaben.- 14 Maximum-Likelihood-Schätzer und EM-Algorithmus.- 14.1 Maximum-Likelihood-Schätzer.- 14.2 Der Expectation-Maximization-Algorithmus.