Venkatesh S.S. The Theory of Probability: Explorations and Applications

Cambridge: Cambridge University Press, 2012. - 828p.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.ElementsFrom early beginnings to a model theory
Chance experiments
The sample space
Sets and operations on sets
The algebra of events
The probability measure
Discrete Spaces
Contious Spaces
Generated σ-algebras Borel sets
A little point set topology
ProblemsChance domains with side information
Gender bias? Simpson’s paradox
The theorem of total probability
Le problème des rencontres matchings
Pólya’s urn scheme spread of contagion
The Ehrenfest model of diffusion
Extension: Birth-Death Chains
Bayes’s rule for events the MAP principle
Laplace’s law of succession
Back to the future the Copernican principle
Ambiguous communication
ProblemsA rule of products
What price intuition?
An application in genetics Hardy’s law
Independent trials
Independent families Dynkin’s π–λ theorem
Problems
Inclusion and exclusion
The sieve of Eratosthenes
On trees and a formula of Cayley
Theorem I: Every finite tree contains at least two leaves
Theorem II: Every tree on n vertices contains n − edges
Boole’s inequality the Borel–Cantelli lemmas
Applications in Ramsey theory
Bonferroni’s inequalities Poisson approximation
Applications in random graphs isolation
Connectivity from feudal states to empire
Sieves the Lovász local lemma
Return to Ramsey theory
Latin transversals and a conjecture of Euler
ProblemsA formula of Viète
Binary digits Rademacher functions
The independence of the binary digits
The link to coin tossing
The binomial makes an appearance
An inequality of Chebyshev
Borel discovers numbers are normal
ProblemsOne curve to rule them all
A little Fourier theory I
A little Fourier theory II
An idea of Markov
Lévy suggests a thin sandwich de Moivre redux
A local limit theorem
Large deviations
The limits of wireless cohabitation
When memory fails
ProblemsArithmetic distributions
Lattice distributions
Towards the continuum
Densities in one dimension
Densities in two and more dimensions
Randomisation regression
How well can we estimate?
Galton on the heredity of height
Rotation shear and polar transformations
Sums and products
ProblemsBernoulli trials
The binomial distribution
On the efficacy of polls
The simple random walk
The arc sine laws will a random walk return?
Law of small numbers the Poisson distribution
Waiting time distributions
Run lengths quality of dyadic approximation
The curious case of the tennis rankings
Population size the hypergeometric distribution
ProblemsThe Essence of RandomnessThe uniform density a convolution formula
Spacings a covering problem
Lord Rayleigh’s random flights
M Poincaré joue à la roulette
Memoryless variables the exponential density
Poisson ensembles
Waiting times the Poisson process
Densities arising in queuing theory
Densities arising in fluctuation theory
Heavy-tailed densities self-similarity
ProblemsThe normal density
Squared normals the chi-squared density
A little linear algebra
The multivariate normal
An application in statistical estimation
Echoes from Venus
The strange case of independence via mixing
A continuous nowhere differentiable function
Brownian motion from phenomena to models
The Haar system a curious identity
A bare hands construction
The paths of Brownian motion are very kinky
ProblemsFoundationsDistribution Functions and MeasureDistribution functions
Measure and its completion
Lebesgue measure countable sets
A measure on a ring
From measure to outer measure and back
ProblemsMeasurable maps
The induced measure
Discrete distributions
Continuous distributions
Modes of convergence
Baire functions coordinate transformations
Two and more dimensions
Independence product measures
Do independent variables exist?
Remote events are either certain or impossible
ProblemsMeasures of central tendency
Simple expectations
Expectations unveiled
Approximation monotone convergence
Arabesques of additivity
Applications of additivity
The expected complexity of Quicksort
Expectation in the limit dominated convergence
ProblemsUtile eris scribit pro omnia
Integrals with Respect to General Measures
Change of variable moments correlation
Inequalities via convexity
Lp-spaces
CompletenessS
Iterated integrals a cautionary example
The volume of an n-dimensional ball
The asymptotics of the gamma function
A question from antiquity
How fast can we communicate?
Convolution symmetrisation
Symmetrisation
Labeyrie ponders the diameter of stars
One-Dimensional Stars
Two-Dimensional Stars
ProblemsThe transform of a distribution
Extensions
The renewal equation and process
Gaps in the Poisson process
Collective risk and the probability of ruin
The queuing process
Ladder indices and a combinatorial digression
The amazing properties of fluctuations
Pólya walks the walk
ProblemsChebyshev’s inequality reprise
Khinchin’s law of large numbers
A physicist draws inspiration from Monte Carlo
Triangles and cliques in random graphs
A gem of Weierstrass
Some number-theoretic sums
The dance of the primes
Fair games the St Petersburg paradox
Kolmogorov’s law of large numbers
Convergence of series with random signs
Uniform convergence per Glivenko and Cantelli
Vapnik-Chervonenkis Classes
The Geometry of Situation
A Question of Identification
ProblemsExponential inequalities
Unreliable transcription reliable replication
Concentration the Gromov–Milman formulation
Talagrand views a distance
The Induction Base
The Induction Step
Sharpening or the importance of convexity
The bin-packing problem
The longest increasing subsequence
Hilbert fills space with a curve
The problem of the travelling salesman
ProblemsPoisson ApproximationA characterisation of the Poisson
The Stein–Chen method
Bounds from Stein’s equation
Sums of indicators
The local method dependency graphs
Triangles and cliques in random graphs reprise
Extension: Cliques
Pervasive dependence the method of coupling
Matchings ménages permutations
Spacings and mosaics
ProblemsVague convergence
An equivalence theorem
Convolutional operators
An inversion theorem for characteristic functions
Vector spaces semigroups
A selection theorem
Two by Bernstein
Equidistributed numbers from Kronecker to Weyl
Walking around the circle
ProblemsIdentical distributions the basic limit theorem
The value of a third moment
Stein’s method
Berry–Esseen revisited
Varying distributions triangular arrays
The coupon collector
On the number of cycles
Many dimensions
Random walks random flights
A test statistic for aberrant counts
A chi-squared test
The strange case of Sir Cyril Burt psychologist
ProblemsAppendix
Sequences of real numbers
Continuous functions
Some L function theory