Problems and Snapshots from the World of Probability

We, the authors of this book, are three ardent devotees of chance, or some­ what more precisely, of discrete probability. When we were collecting the material, we felt that one special pleasure of the field lay in its evocation of an earlier age: many of our 'probabilistic forefathers' were dexterous solvers of discrete problems. We hope that this pleasure will be transmitted to the readers. The first problem-book of a similar kind as ours is perhaps Mosteller's well-known Fifty Challenging Problems in Probability (1965). Possibly, our book is the second. The book contains 125 problems and snapshots from the world of prob­ ability. A 'problem' generally leads to a question with a definite answer. A 'snapshot' is either a picture or a bird's-eye view of some probabilistic field. The selection is, of course, highly subjective, and we have not even tried to cover all parts of the subject systematically. Limit theorems appear only seldom, for otherwise the book would have become unduly large. We want to state emphatically that we have not written a textbook in probability, but rather a book for browsing through when occupying an easy-chair. Therefore, ideas and results are often put forth without a machinery of formulas and derivations; the conscientious readers, who want to penetrate the whole clockwork, will soon have to move to their desks and utilize appropriate tools.

1. Welcoming problems.- 1.1 The friendly illiterate.- 1.2 Tourist with a short memory.- 1.3 The car and the goats.- 1.4 Patterns I.- 1.5 Classical random walk I.- 1.6 Number of walks until no shoes.- 1.7 Banach’s match box problem.- 1.8 The generous king.- 2. Basic probability theory I.- 2.1 Remarkable conditional probabilities.- 2.2 Exchangeability I.- 2.3 Exchangeability II.- 2.4 Combinations of events I.- 2.5 Problems concerning random numbers.- 2.6 Zero-one random variables I.- 3. Basic probability theory II.- 3.1 A trick for determining expectations.- 3.2 Probability generating functions.- 3.3 People at the corners of a triangle.- 3.4 Factorial generating functions.- 3.5 Zero-one random variables II.- 3.6 Combinations of events II.- 4. Topics from early days I.- 4.1 Cardano — a pioneer.- 4.2 Birth of probability.- 4.3 The division problem.- 4.4 Huygens’s second problem.- 4.5 Huygens’s fifth problem.- 4.6 Points when throwing several dice.- 4.7 Bernoulli and the game of tennis.- 5. Topics from early days II.- 5.1 History of some common distributions.- 5.2 Waldegrave’s problem I.- 5.3 Petersburg paradox.- 5.4 Rencontre I.- 5.5 Occupancy I.- 5.6 Stirling numbers of the second kind.- 5.7 Bayes’s theorem and Law of Succession.- 5.8 Ménage I.- 6. Random permutations.- 6.1 Runs I.- 6.2 Cycles in permutations.- 6.3 Stirling numbers of the first kind.- 6.4 Ascents in permutations.- 6.5 Eulerian numbers.- 6.6 Exceedances in permutations.- 6.7 Price fluctuations.- 6.8 Oscillations I.- 6.9 Oscillations II.- 7. Miscellaneous I.- 7.1 Birthdays.- 7.2 Poker.- 7.3 Negative binomial.- 7.4 Negative hypergeometric I.- 7.5 Coupon collecting I.- 7.6 Coupon collecting II.- 7.7 Ménage II.- 7.8 Rencontre II.- 8. Poisson approximation.- 8.1 Similar pairs and triplets.- 8.2 A Lotto problem.- 8.3 Variation distance.- 8.4 Poisson-binomial.- 8.5 Rencontre III.- 8.6 Ménage III.- 8.7 Occupancy II.- 9. Miscellaneous II.- 9.1 Birthdays and similar triplets.- 9.2 Comparison of random numbers.- 9.3 Grouping by random division.- 9.4 Records I.- 9.5 Records II.- 9.6 A modification of blackjack.- 10. Random walks.- 10.1 Introduction.- 10.2 Classical random walk II.- 10.3 One absorbing barrier.- 10.4 The irresolute spider.- 10.5 Stars I.- 10.6 Closed stopping region.- 10.7 The reflection principle.- 10.8 Ballot problem.- 10.9 Range of a random walk.- 11. Urn models.- 11.1 Randomly filled urn.- 11.2 Pólya’s model I.- 11.3 Pólya’s model II.- 11.4 Pólya’s model III.- 11.5 Ehrenfest’s model I.- 11.6 Ehrenfest’s game.- 11.7 A pill problem.- 12. Cover times.- 12.1 Introduction.- 12.2 Complete graph.- 12.3 Linear finite graph.- 12.4 Polygon.- 12.5 A false conjecture.- 12.6 Stars II.- 12.7 Inequality for cover times.- 13. Markov chains.- 13.1 Review I.- 13.2 Review II.- 13.3 Random walk: two reflecting barriers.- 13.4 Ehrenfest’s model II.- 13.5 Doubly stochastic transition matrix.- 13.6 Card shuffling.- 13.7 Transition times for Markov chains.- 13.8 Reversible Markov chains.- 13.9 Markov chains with homesickness.- 14. Patterns.- 14.1 Runs II.- 14.2 Patterns II.- 14.3 Patterns III.- 14.4 A game for pirates.- 14.5 Penney’s game.- 14.6 Waldegrave’s problem II.- 14.7 How many patterns?.- 15. Embedding procedures.- 15.1 Drawings with replacement.- 15.2 Repetition of colours.- 15.3 Birthdays revisited.- 15.4 Coupon collecting III.- 15.5 Drawings without replacement.- 15.6 Socks in the laundry.- 15.7 Negative hypergeometric II.- 15.8 The first-to-r game I.- 16. Special topics.- 16.1 Exchangeability III.- 16.2 Martingales.- 16.3 Wald’s equation.- 16.4 Birth control.- 16.5 The r-heads-in-advance game.- 16.6 Patterns IV.- 16.7 Random permutation of 1’s and (?1)’s.- 17. Farewell problems.- 17.1 The first-to-r game II.- 17.2 Random walk on a chessboard.- 17.3 Game with disaster.- 17.4 A rendezvous problem.- 17.5 Modified coin-tossing.- 17.6 Palindromes.- References.