The theory of probability: explorations and applications

Cover......Page 1
THE THEORY OF PROBABILITY......Page 3
Title......Page 5
Copyright......Page 6
Dedication......Page 7
Contents......Page 9
Preface......Page 17
Part A: ELEMENTS......Page 27
1 From early beginnings to a model theory......Page 29
2 Chance experiments......Page 31
3 The sample space......Page 35
4 Sets and operations on sets......Page 38
5 The algebra of events......Page 40
6 The probability measure......Page 42
DISCRETE SPACES......Page 45
CONTINUOUS SPACES......Page 49
8 Generated σ-algebras, Borel sets......Page 50
9 A little point set topology......Page 52
10 Problems......Page 56
1 Chance domains with side information......Page 61
2 Gender bias? Simpson’s paradox......Page 66
3 The theorem of total probability......Page 68
4 Le problème des rencontres, matchings......Page 73
5 Pólya’s urn scheme, spread of contagion......Page 75
6 The Ehrenfest model of diffusion......Page 78
EXTENSION: BIRTH–DEATH CHAINS......Page 80
7 Bayes’s rule for events, the MAP principle......Page 82
8 Laplace’s law of succession......Page 85
9 Back to the future, the Copernican principle......Page 87
10 Ambiguous communication......Page 90
11 Problems......Page 92
1 A rule of products......Page 97
2 What price intuition?......Page 100
3 An application in genetics, Hardy’s law......Page 103
4 Independent trials......Page 107
5 Independent families, Dynkin’s π–λ theorem......Page 113
6 Problems......Page 116
1 Inclusion and exclusion......Page 119
2 The sieve of Eratosthenes......Page 125
3 On trees and a formula of Cayley......Page 128
THEOREM 1 Every finite tree contains at least two leaves.......Page 129
THEOREM 2 Every tree on n vertices contains n − 1 edges.......Page 130
4 Boole’s inequality, the Borel–Cantelli lemmas......Page 132
5 Applications in Ramsey theory......Page 135
6 Bonferroni’s inequalities, Poisson approximation......Page 139
7 Applications in random graphs, isolation......Page 145
8 Connectivity, from feudal states to empire......Page 147
9 Sieves, the Lovász local lemma......Page 151
10 Return to Ramsey theory......Page 156
11 Latin transversals and a conjecture of Euler......Page 157
12 Problems......Page 161
1 A formula of Viète......Page 165
2 Binary digits, Rademacher functions......Page 167
3 The independence of the binary digits......Page 170
4 The link to coin tossing......Page 174
5 The binomial makes an appearance......Page 176
6 An inequality of Chebyshev......Page 179
7 Borel discovers numbers are normal......Page 181
8 Problems......Page 185
1 One curve to rule them all......Page 189
2 A little Fourier theory I......Page 192
3 A little Fourier theory II......Page 198
4 An idea of Markov......Page 203
5 Lévy suggests a thin sandwich, de Moivre redux......Page 207
6 A local limit theorem......Page 210
7 Large deviations......Page 215
8 The limits of wireless cohabitation......Page 217
9 When memory fails......Page 219
10 Problems......Page 221
1 Arithmetic distributions......Page 223
2 Lattice distributions......Page 226
3 Towards the continuum......Page 230
4 Densities in one dimension......Page 232
5 Densities in two and more dimensions......Page 236
6 Randomisation, regression......Page 243
7 How well can we estimate?......Page 247
8 Galton on the heredity of height......Page 249
9 Rotation, shear, and polar transformations......Page 253
10 Sums and products......Page 256
11 Problems......Page 258
1 Bernoulli trials......Page 261
2 The binomial distribution......Page 263
3 On the efficacy of polls......Page 265
4 The simple random walk......Page 270
5 The arc sine laws, will a random walk return?......Page 273
6 Law of small numbers, the Poisson distribution......Page 278
7 Waiting time distributions......Page 282
8 Run lengths, quality of dyadic approximation......Page 288
9 The curious case of the tennis rankings......Page 290
10 Population size, the hypergeometric distribution......Page 294
11 Problems......Page 297
IX The Essence of Randomness......Page 301
1 The uniform density, a convolution formula......Page 302
2 Spacings, a covering problem......Page 306
3 Lord Rayleigh’s random flights......Page 310
4 M. Poincaré joue à la roulette......Page 314
5 Memoryless variables, the exponential density......Page 318
6 Poisson ensembles......Page 320
7 Waiting times, the Poisson process......Page 323
8 Densities arising in queuing theory......Page 329
9 Densities arising in fluctuation theory......Page 331
10 Heavy-tailed densities, self-similarity......Page 333
11 Problems......Page 336
1 The normal density......Page 341
2 Squared normals, the chi-squared density......Page 345
3 A little linear algebra......Page 346
4 The multivariate normal......Page 350
5 An application in statistical estimation......Page 356
6 Echoes from Venus......Page 363
7 The strange case of independence via mixing......Page 367
8 A continuous, nowhere differentiable function......Page 372
9 Brownian motion, from phenomena to models......Page 374
10 The Haar system, a curious identity......Page 378
11 A bare hands construction......Page 381
12 The paths of Brownian motion are very kinky......Page 386
13 Problems......Page 389
Part B: FOUNDATIONS......Page 393
XI Distribution Functions and Measure......Page 395
1 Distribution functions......Page 396
2 Measure and its completion......Page 398
3 Lebesgue measure, countable sets......Page 401
4 A measure on a ring......Page 406
5 From measure to outer measure, and back......Page 410
6 Problems......Page 417
1 Measurable maps......Page 419
2 The induced measure......Page 423
3 Discrete distributions......Page 425
4 Continuous distributions......Page 428
5 Modes of convergence......Page 432
6 Baire functions, coordinate transformations......Page 435
7 Two and more dimensions......Page 437
8 Independence, product measures......Page 441
9 Do independent variables exist?......Page 446
10 Remote events are either certain or impossible......Page 448
11 Problems......Page 450
1 Measures of central tendency......Page 453
2 Simple expectations......Page 455
3 Expectations unveiled......Page 459
4 Approximation, monotone convergence......Page 464
5 Arabesques of additivity......Page 472
6 Applications of additivity......Page 477
7 The expected complexity of Quicksort......Page 481
8 Expectation in the limit, dominated convergence......Page 485
9 Problems......Page 488
1 UTILE ERIT SCRIBIT ∫PRO OMNIA......Page 491
INTEGRALS WITH RESPECT TO GENERAL MEASURES......Page 495
2 Change of variable, moments, correlation......Page 497
3 Inequalities via convexity......Page 504
4 Lp-spaces......Page 508
COMPLETENESS......Page 510
5 Iterated integrals, a cautionary example......Page 511
6 The volume of an n-dimensional ball......Page 518
7 The asymptotics of the gamma function......Page 520
8 A question from antiquity......Page 522
9 How fast can we communicate?......Page 526
10 Convolution, symmetrisation......Page 532
SYMMETRISATION......Page 535
11 Labeyrie ponders the diameter of stars......Page 537
ONE-DIMENSIONAL STARS......Page 538
TWO-DIMENSIONAL STARS......Page 540
12 Problems......Page 542
1 The transform of a distribution......Page 549
2 Extensions......Page 555
3 The renewal equation and process......Page 558
4 Gaps in the Poisson process......Page 562
5 Collective risk and the probability of ruin......Page 564
6 The queuing process......Page 568
7 Ladder indices and a combinatorial digression......Page 572
8 The amazing properties of fluctuations......Page 576
9 Pólya walks the walk......Page 581
10 Problems......Page 583
1 Chebyshev’s inequality, reprise......Page 587
2 Khinchin’s law of large numbers......Page 589
3 A physicist draws inspiration from Monte Carlo......Page 592
4 Triangles and cliques in random graphs......Page 594
5 A gem of Weierstrass......Page 597
6 Some number-theoretic sums......Page 600
7 The dance of the primes......Page 608
8 Fair games, the St. Petersburg paradox......Page 611
9 Kolmogorov’s law of large numbers......Page 613
10 Convergence of series with random signs......Page 619
11 Uniform convergence per Glivenko and Cantelli......Page 621
VAPNIK–CHERVONENKIS CLASSES......Page 625
THE GEOMETRY OF THE SITUATION......Page 626
A QUESTION OF IDENTIFICATION......Page 628
13 Problems......Page 630
1 Exponential inequalities......Page 635
2 Unreliable transcription, reliable replication......Page 640
3 Concentration, the Gromov–Milman formulation......Page 642
4 Talagrand views a distance......Page 645
THE INDUCTION BASE......Page 651
THE INDUCTION STEP......Page 652
6 Sharpening, or the importance of convexity......Page 656
7 The bin-packing problem......Page 659
8 The longest increasing subsequence......Page 662
9 Hilbert fills space with a curve......Page 664
10 The problem of the travelling salesman......Page 667
11 Problems......Page 672
XVIII Poisson Approximation......Page 677
1 A characterisation of the Poisson......Page 678
2 The Stein–Chen method......Page 682
3 Bounds from Stein’s equation......Page 683
4 Sums of indicators......Page 686
5 The local method, dependency graphs......Page 689
6 Triangles and cliques in random graphs, reprise......Page 691
EXTENSION: CLIQUES......Page 692
7 Pervasive dependence, the method of coupling......Page 694
8 Matchings, ménages, permutations......Page 698
9 Spacings and mosaics......Page 705
10 Problems......Page 711
1 Vague convergence......Page 715
2 An equivalence theorem......Page 718
3 Convolutional operators......Page 721
4 An inversion theorem for characteristic functions......Page 724
5 Vector spaces, semigroups......Page 726
6 A selection theorem......Page 731
7 Two by Bernstein......Page 735
8 Equidistributed numbers, from Kronecker to Weyl......Page 738
9 Walking around the circle......Page 741
10 Problems......Page 743
1 Identical distributions, the basic limit theorem......Page 745
2 The value of a third moment......Page 750
3 Stein’s method......Page 756
4 Berry–Esseen revisited......Page 759
5 Varying distributions, triangular arrays......Page 763
6 The coupon collector......Page 768
7 On the number of cycles......Page 771
8 Many dimensions......Page 773
9 Random walks, random flights......Page 777
10 A test statistic for aberrant counts......Page 779
11 A chi-squared test......Page 785
12 The strange case of Sir Cyril Burt, psychologist......Page 789
13 Problems......Page 793
Part C: APPENDIX......Page 795
1 Sequences of real numbers......Page 797
2 Continuous functions......Page 802
3 Some L2 function theory......Page 809
Index......Page 815