You are previewing The Theory of Probability.
O'Reilly logo
The Theory of Probability

Book Description

From classical foundations to advanced modern theory, this self-contained and comprehensive guide to probability weaves together mathematical proofs, historical context and richly detailed illustrative applications. A theorem discovery approach is used throughout, setting each proof within its historical setting and is accompanied by a consistent emphasis on elementary methods of proof. Each topic is presented in a modular framework, combining fundamental concepts with worked examples, problems and digressions which, although mathematically rigorous, require no specialised or advanced mathematical background. Augmenting this core material are over 80 richly embellished practical applications of probability theory, drawn from a broad spectrum of areas both classical and modern, each tailor-made to illustrate the magnificent scope of the formal results. Providing a solid grounding in practical probability, without sacrificing mathematical rigour or historical richness, this insightful book is a fascinating reference and essential resource, for all engineers, computer scientists and mathematicians.

Table of Contents

  1. Cover
  2. Title Page
  3. Copyright Page
  4. Dedication Page
  5. Contents
  6. Preface
  7. A - ELEMENTS
    1. I - Probability Spaces
      1. 1 From Early Beginnings to a Model Theory
      2. 2 Chance Experiments
      3. 3 The Sample Space
      4. 4 Sets and Operations on Sets
      5. 5 The Algebra of Events
      6. 6 The Probability Measure
      7. 7 Probabilities in Simple Cases
      8. 8 Generated σ-algebras, Borei Sets
      9. 9 A little Point Set Topology
      10. 10 Problems
    2. II - Conditional Probability
      1. 1 Chance Domains with Side Information
      2. 2 Gender bias? Simpson’s Paradox
      3. 3 The Theorem of Total Probability
      4. 4 Le Problème Des Rencontres, Matchings
      5. 5 Pólya’s Urn Scheme, Spread of Contagion
      6. 6 The Ehrenfest Model of Diffusion
      7. 7 Bayes’s Rule for events, the Map Principle
      8. 8 Laplace’s Law of Succession
      9. 9 Back to the Future, the Copernican Principle
      10. 10 Ambiguous Communication
      11. 11 Problems
    3. III - A First Look at Independence
      1. 1 A Rule of Products
      2. 2 What Price Intuition?
      3. 3 An Application in Genetics, Hardy’s Law
      4. 4 Independent trials
      5. 5 Independent Families, Dynkin’s π–λ Theorem
      6. 6 Problems
    4. IV - Probability Sieves
      1. 1 Inclusion and Exclusion
      2. 2 The Sieve of Eratosthenes
      3. 3 On Trees and a Formula of Cayley
      4. 4 Boole’s Inequality, the Borel-Cantelli Lemmas
      5. 5 Applications in Ramsey Theory
      6. 6 Bonferroni’s Inequalities, Poisson Approximation
      7. 7 Applications in Random Graphs, Isolation
      8. 8 Connectivity, from Feudal States to Empire
      9. 9 Sieves, the Lovász Local Lemma
      10. 10 Return to Ramsey Theory
      11. 11 Latin Transversals and a Conjecture of Euler
      12. 12 Problems
    5. V - Numbers Play a Game of Chance
      1. 1 A formula of Viète
      2. 2 Binary Digits, Rademacher Functions
      3. 3 The Independence of the Binary Digits
      4. 4 The Link to Coin Tossing
      5. 5 The Binomial makes an Appearance
      6. 6 An Inequality of Chebyshev
      7. 7 Borel Discovers Numbers are Normal
      8. 8 Problems
    6. VI - The Normal Law
      1. 1 One Curve to Rule them All
      2. 2 A little Fourier Theory I
      3. 3 A little Fourier Theory II
      4. 4 An Idea of Markov
      5. 5 Lévy Suggests a Thin Sandwich, De Moivre Redux
      6. 6 A local Limit Theorem
      7. 7 Large Deviations
      8. 8 The Limits of Wireless Cohabitation
      9. 9 When Memory Fails
      10. 10 Problems
    7. VII - Probabilities on the Real Line
      1. 1 Arithmetic Distributions
      2. 2 Lattice Distributions
      3. 3 Towards the Continuum
      4. 4 Densities in One Dimension
      5. 5 Densities in Two and more Dimensions
      6. 6 Randomisation, Regression
      7. 7 How Well can we Estimate?
      8. 8 Galton on the Heredity of Height
      9. 9 Rotation, Shear, and Polar Transformations
      10. 10 Sums and Products
      11. 11 Problems
    8. VIII - The Bernoulli Schema
      1. 1 Bernoulli Trials
      2. 2 The Binomial Distribution
      3. 3 On the Efficacy of Polls
      4. 4 The Simple Random Walk
      5. 5 The Arc Sine Laws, will a Random Walk Return?
      6. 6 Law of Small Numbers, the Poisson Distribution
      7. 7 Waiting Time Distributions
      8. 8 Run Lengths, Quality of Dyadic Approximation
      9. 9 The Curious Case of the Tennis Rankings
      10. 10 Population Size, the Hypergeometric Distribution
      11. 11 Problems
    9. IX - The Essence of Randomness
      1. 1 The Uniform Density, a Convolution Formula
      2. 2 Spacings, a Covering Problem
      3. 3 Lord Rayleigh’s Random Flights
      4. 4 M. Poincaré Joue à La Roulette
      5. 5 Memoryless Variables, the Exponential Density
      6. 6 Poisson Ensembles
      7. 7 Waiting Times, the Poisson Process
      8. 8 Densities Arising in Queuing Theory
      9. 9 Densities Arising in Fluctuation Theory
      10. 10 Heavy-tailed Densities, Self-similarity
      11. 11 Problems
    10. X - The Coda of the Normal
      1. 1 The Normal Density
      2. 2 Squared Normals, the Chi-squared Density
      3. 3 A little Linear Algebra
      4. 4 The Multivariate Normal
      5. 5 An Application in Statistical Estimation
      6. 6 Echoes from Venus
      7. 7 The Strange Case of Independence Via Mixing
      8. 8 A continuous, nowhere Differentiable Function
      9. 9 Brownian Motion, from Phenomena to Models
      10. 10 The Haar System, a Curious Identity
      11. 11 A Bare Hands Construction
      12. 12 The Paths of Brownian Motion are Very Kinky
      13. 13 Problems
  8. B - Foundations
    1. XI - Distribution Functions and Measure
      1. 1 Distribution Functions
      2. 2 Measure and its Completion
      3. 3 Lebesgue Measure, Countable Sets
      4. 4 A Measure on a Ring
      5. 5 From Measure to Outer Measure, and Back
      6. 6 Problems
    2. XII - Random Variables
      1. 1 Measurable Maps
      2. 2 The Induced Measure
      3. 3 Discrete Distributions
      4. 4 Continuous Distributions
      5. 5 Modes of Convergence
      6. 6 Baire Functions, Coordinate Transformations
      7. 7 Two and More Dimensions
      8. 8 Independence, Product Measures
      9. 9 Do independent Variables Exist?
      10. 10 Remote Events are Either Certain or Impossible
      11. 11 Problems
    3. XIII - Great Expectations
      1. 1 Measures of Central Tendency
      2. 2 Simple Expectations
      3. 3 Expectations Unveiled
      4. 4 Approximation, Monotone Convergence
      5. 5 Arabesques of Additivity
      6. 6 Applications of Additivity
      7. 7 The Expected Complexity of Quicksort
      8. 8 Expectation in the Limit, Dominated Convergence
      9. 9 Problems
    4. XIV - Variations on a Theme of Integration
      1. 1 Utile Erit Scribit ∫ Pro Omnia
      2. 2 Change of Variable, Moments, Correlation
      3. 3 Inequalities Via Convexity
      4. 4 Lp-spaces
      5. 5 Iterated Integrals, a Cautionary Example
      6. 6 The Volume of an n-dimensional Ball
      7. 7 The Asymptotics of the Gamma Function
      8. 8 A Question from Antiquity
      9. 9 How Fast can we Communicate?
      10. 10 Convolution, Symmetrisation
      11. 11 Labeyrie Ponders the Diameter of Stars
      12. 12 Problems
    5. XV - Laplace Transforms
      1. 1 The Transform of a Distribution
      2. 2 Extensions
      3. 3 The Renewal Equation and Process
      4. 4 Gaps in the Poisson Process
      5. 5 Collective Risk and the Probability of Ruin
      6. 6 The Queuing Process
      7. 7 Ladder Indices and a Combinatorial Digression
      8. 8 The Amazing Properties of Fluctuations
      9. 9 Pólya Walks the Walk
      10. 10 Problems
    6. XVI - The Law of Large Numbers
      1. 1 Chebyshev’s Inequality, Reprise
      2. 2 Khinchin’s Law of Large Numbers
      3. 3 A physicist Draws Inspiration from Monte Carlo
      4. 4 Triangles and Cliques in Random Graphs
      5. 5 A Gem of Weierstrass
      6. 6 Some Number-theoretic Sums
      7. 7 The dance of the Primes
      8. 8 Fair Games, the St. Petersburg Paradox
      9. 9 Kolmogorov’s Law of Large Numbers
      10. 10 Convergence of Series with Random Signs
      11. 11 Uniform Convergence Per Glivenko and Cantelli
      12. 12 What can be Learnt per Vapnik and Chervonenkis
      13. 13 Problems
    7. XVII - From Inequalities to Concentration
      1. 1 Exponential Inequalities
      2. 2 Unreliable Transcription, Reliable Replication
      3. 3 Concentration, the Gromov–Milman Formulation
      4. 4 Talagrand Views a Distance
      5. 5 The Power of Induction
      6. 6 Sharpening, or the Importance of Convexity
      7. 7 The Bin-packing Problem
      8. 8 The Longest Increasing Subsequence
      9. 9 Hilbert Fills Space with a Curve
      10. 10 The Problem of the Travelling Salesman
      11. 11 Problems
    8. XVIII - Poisson Approximation
      1. 1 A Characterisation of the Poisson
      2. 2 The Stein–Chen Method
      3. 3 Bounds from Stein’s Equation
      4. 4 Sums of Indicators
      5. 5 The Local Method, Dependency Graphs
      6. 6 Triangles and Cliques in Random Graphs, Reprise
      7. 7 Pervasive Dependence, the Method of Coupling
      8. 8 Matchings, Ménages, Permutations
      9. 9 Spacings and Mosaics
      10. 10 Problems
    9. XIX - Convergence in Law, Selection Theorems
      1. 1 Vague Convergence
      2. 2 An Equivalence Theorem
      3. 3 Convolutional Operators
      4. 4 An inversion Theorem for Characteristic Functions
      5. 5 Vector Spaces, Semigroups
      6. 6 A Selection Theorem
      7. 7 Two by Bernstein
      8. 8 Equidistributed Numbers, from Kronecker to Weyl
      9. 9 Walking Around the Circle
      10. 10 Problems
    10. XX - Normal Approximation
      1. 1 Identical Distributions, the Basic Limit Theorem
      2. 2 The Value of a Third Moment
      3. 3 Stein’s Method
      4. 4 Berry–Esseen Revisited
      5. 5 Varying Distributions, Triangular Arrays
      6. 6 The Coupon Collector
      7. 7 On the Number of Cycles
      8. 8 Many Dimensions
      9. 9 Random Walks, Random Flights
      10. 10 A Test Statistic for Aberrant Counts
      11. 11 A Chi-squared Test
      12. 12 The Strange Case of Sir Cyril Burt, Psychologist
      13. 13 Problems
  9. C - Appendix
    1. XXI - Sequences, Functions, Spaces
      1. 1 Sequences of Real Numbers
      2. 2 Continuous Functions
      3. 3 Some L2 Function Theory
  10. Index