Problem Books in Mathematics EditedbyP.Winkler Problem Books in Mathematics SeriesEditors:PeterWinkler Pell’s Equation byEdward J. Barbeau Polynomials byEdward J. Barbeau Problems in Geometry byMarcel Berger, Pierre Pansu, Jean-Pic Berry, and Xavier Saint-Raymond Problem Book for First Year Calculus byGeorge W. Bluman Exercises in Probability byT. Cacoullos Probability Through Problems byMarek Capin´ski and Tomasz Zastawniak An Introduction to Hilbert Space and Quantum Logic byDavid W. Cohen Unsolved Problems in Geometry byHallard T. Croft, Kenneth J. Falconer, and Richard K. Guy Berkeley Problems in Mathematics (Third Edition) byPaulo Ney de Souza and Jorge-Nuno Silva The IMO Compendium: A Collection of Problems Suggested for the International Mathematical Olympiads: 1959–2004 byDuˇsan Djuki´c, Vladimir Z. Jankovi´c, Ivan Mati´c, and Nikola Petrovi´c Problem-Solving Strategies byArthur Engel Problems in Analysis byBernard R. Gelbaum Problems in Real and Complex Analysis byBernard R. Gelbaum (continuedaftersubjectindex) Wolfgang Schwarz 40 Puzzles and Problems in Probability and Mathematical Statistics WolfgangSchwarz Universita¨tPotsdam HumanwissenschaftlicheFakulta¨t Karl-LiebknechtStrasse24/25 D-14476Potsdam-Golm Germany [email protected] SeriesEditor: PeterWinkler DepartmentofMathematics DartmouthCollege Hanover,NH03755 USA [email protected] ISBN-13:978-0-387-73511-5 e-ISBN-13:978-0-387-73512-2 MathematicsSubjectClassification(2000):60-xx LibraryofCongressControlNumber:2007936604 (cid:2)c 2008SpringerScience+BusinessMedia,LLC Allrightsreserved.Thisworkmaynotbetranslatedorcopiedinwholeorinpartwithoutthewritten permissionofthepublisher(SpringerScience+BusinessMedia,LLC,233SpringStreet,NewYork,NY 10013,USA),exceptforbriefexcerptsinconnectionwithreviewsorscholarlyanalysis.Useinconnection withanyformofinformationstorageandretrieval,electronicadaptation,computersoftware,orbysimilar ordissimilarmethodologynowknownorhereafterdevelopedisforbidden. Theuseinthispublicationoftradenames,trademarks,servicemarksandsimilarterms,eveniftheyare notidentifiedassuch,isnottobetakenasanexpressionofopinionastowhetherornottheyaresubject toproprietaryrights. Printedonacid-freepaper. 9 8 7 6 5 4 3 2 1 springer.com We often felt that there is not less, and perhaps even more, beauty in the result of analysis than there is to be found in mere contemplation. Niko Tinbergen, Curious Naturalists (1958). Preface As a student I discovered in our library a thin booklet by Frederick Mostellerentitled50ChallengingProblemsinProbability.Itreferredtoasup- plementary “regular textbook” by William Feller, An Introduction to Proba- bilityTheoryanditsApplications.SoItookthisonealong,too,andstartedon thefirstofMosteller’s problems onthetrain ridinghome. Fromthat evening, Icaughtontoprobability.Thesetwobookswerenotprimarilyaboutabstract formalisms but rather about basic modeling ideas and about ways — often extremely elegant ones — to apply those notions to a surprising variety of empirical phenomena. Essentially, these books taught the reader the skill to “thinkprobabilistically”andtoapplysimpleprobabilitymodelstoreal-world problems. The present book is in this tradition; it is based on the view that those cognitive skills are best acquired by solving challenging, nonstandard proba- bility problems. My own experience, both in learning and in teaching, is that challenging problems often help to develop, and to sharpen, our probabilistic intuition much better than plain-style deductions from abstract concepts. TheproblemsIselectedfallintotwobroadcategories,eventhoughitisin thespiritofthiscollectionthatthereactuallyisnosharpdividinglinebetween them.Problemsrelatedtoprobabilitytheorycomefirst,followedbyproblems related to the application of probability in the field of mathematical statis- tics. Statistical applications are by now probably the most important reason to study probability. Thus, it seemed important to me to select problems il- lustrating in an elementary but nontrivial way that probabilistic techniques form the basis of many statistical applications. All problems seek to convey a nonstandard aspect or an approach that is not immediately obvious. The word puzzles in the title refers to questions in which some qualitative nontechnicalinsightismostimportant.Ideally,puzzlescanteachaproductive new way of framing or representing a given situation. An obvious example of this is the introductory “To Begin Or Not To Begin.” Although the border between the two is not perfectly sharp (and crosses occur), problems tend to requireamoresystematicapplicationofformaltoolsandtostressmoretech- nical aspects. Examples of this deal with the distribution of various statistics such as the range or the maximum, the linearization of problems with the VIII Preface powerful so-called Delta technique, or the precision (standard error) of cer- tain estimates. These examples have in common that they all seek to apply basic probability notions to more or less applied situations. Such approaches — the Delta technique mentioned earlier is a typical example — are not usu- ally covered in introductory books. Rather, they often appear hidden behind thick technical jargon in more advanced treatments, even though their prob- abilistic background is often essentially elementary. Thus, a major aim of the present collection is to help bridge the wide gap between introductory texts and rigorous state-of-the-art books. Many puzzles and problems presented here are either new within a problem-solving context (although as topics infundamental researchtheyare of course long known) or variations of classical problems. A small number of particularly instructive problems have been taken from previous sources, which in this case are generally given (the titles referenced at the end of the book contain a large number of related challenging problems). My approach in the Solutions section is often fairly heuristic, and I fo- cus on the conceptual probabilistic reasoning. I think that — especially with natural science students — purely technical issues are in fact not usually the majorobstacle:afterall,themathematicallevelofmostelementaryprobabil- ityapplicationsisnottooadvancedwhencomparedto,say,evenintroductory fluid dynamics. Rather, the hardest part is often to develop an adequate un- derstanding of, and intuition for, the characteristic patterns of reasoning and representingtypicallyusedinprobability.Thus,technicaltoolssuchasderiva- tives or Taylor series are used freely whenever this seemed practical, but in a clearly informal, engineer-like, and nonrigorous way. My advice is: whenever you hit upon a problem or a solution that seems too technical, simply skip it and try the next one. Tospecifythebackgroundrequiredforthisbook,afairnumberofproblems collected here require little more than elementary probability and straight logicalreasoning.Otherproblemsclearlyassumesomefamiliaritywithnotions suchas,say,generatingfunctions,orthefactthataroundtheoriginex ≈1+x. It is probably fair to say that anybody with a basic knowledge of probability, calculus, and statistics will benefit from trying to solve the problems posed here.Ofcourse,youmusttryanywayofattackthatmightpromisesuccess— including considering significant special cases and concrete examples — and resist the temptation to look up the solution! To help you along this way, I haveprovidedaseparatesectionofshorthints,whichindicateadirectioninto which you might orient your attention. Potsdam, April 2007 Wolf Schwarz Contents 0 Notation and Terminology................................. 1 1 Problems .................................................. 3 1.1 To Begin or Not to Begin?................................ 3 1.2 A Tournament Problem .................................. 3 1.3 Mean Waiting Time for 1−1 vs. 1−2 ..................... 4 1.4 How to Divide up Gains in Interrupted Games .............. 4 1.5 How Often Do Head and Tail Occur Equally Often? ......... 4 1.6 Sample Size vs. Signal Strength ........................... 5 1.7 Birthday Holidays ....................................... 5 1.8 Random Areas .......................................... 5 1.9 Maximize Your Gain..................................... 6 1.10 Maximize Your Gain When Losses Are Possible ............. 6 1.11 The Optimal Level of Supply ............................. 6 1.12 Mixing RVs vs. Mixing Their Distributions ................. 7 1.13 Throwing the Same vs. Different Dice ...................... 8 1.14 Random Ranks.......................................... 8 1.15 Ups and Downs ......................................... 9 1.16 Is 2X the Same as X +X ?.............................. 9 1 2 1.17 How Many Donors Needed?............................... 10 1.18 Large Gaps ............................................. 10 1.19 Small Gaps ............................................. 11 1.20 Random Powers of Random Variables ...................... 11 1.21 How Many Bugs Are Left?................................ 11 1.22 ML Estimation with the Geometric Distribution ............. 11 1.23 How Many Twins Are Homozygotic?....................... 12 1.24 The Lady Tasting Tea ................................... 12 1.25 How to Aggregate Significance Levels ...................... 13 1.26 Approximately How Tall Is the Tallest? .................... 13 1.27 The Range in Samples of Exponential RVs.................. 14 1.28 The Median in Samples of Exponential RVs................. 14 X Contents 1.29 Breaking the Record ..................................... 15 1.30 Paradoxical Contribution................................. 15 1.31 Attracting Mediocrity.................................... 16 1.32 Discrete Variables with Continuous Error................... 16 1.33 The High-Resolution and the Black-White View............. 17 1.34 The Bivariate Lognormal ................................. 18 √ 1.35 The arcsin( p) Transform................................ 18 1.36 Binomial Trials Depending on a Latent Variable............. 19 1.37 The Delta Technique with One Variable .................... 19 1.38 The Delta Technique with Two Variables ................... 20 1.39 How Many Trials Produced a Given Maximum? ............. 20 1.40 Waiting for Success ...................................... 21 2 Hints ...................................................... 23 2.1 To Begin or Not to Begin?................................ 23 2.2 A Tournament Problem .................................. 23 2.3 Mean Waiting Time for 1−1 vs. 1−2 ..................... 23 2.4 How to Divide up Gains in Interrupted Games .............. 24 2.5 How Often Do Head and Tail Occur Equally Often? ......... 24 2.6 Sample Size vs. Signal Strength ........................... 24 2.7 Birthday Holidays ....................................... 24 2.8 Random Areas .......................................... 24 2.9 Maximize Your Gain..................................... 25 2.10 Maximize Your Gain When Losses Are Possible ............. 25 2.11 The Optimal Level of Supply ............................. 25 2.12 Mixing RVs vs. Mixing Their Distributions ................. 25 2.13 Throwing the Same vs. Different Dice ...................... 26 2.14 Random Ranks.......................................... 26 2.15 Ups and Downs ......................................... 26 2.16 Is 2X the Same as X +X ?.............................. 27 1 2 2.17 How Many Donors Needed?............................... 27 2.18 Large Gaps ............................................. 27 2.19 Small Gaps ............................................. 27 2.20 Random Powers of Random Variables ...................... 27 2.21 How Many Bugs Are Left?................................ 28 2.22 ML Estimation with the Geometric Distribution ............. 28 2.23 How Many Twins Are Homozygotic?....................... 28 2.24 The Lady Tasting Tea ................................... 29 2.25 How to Aggregate Significance Levels ...................... 29 2.26 Approximately How Tall Is the Tallest? .................... 29 2.27 The Range in Samples of Exponential RVs.................. 30 2.28 The Median in Samples of Exponential RVs................. 30 2.29 Breaking the Record ..................................... 30 2.30 Paradoxical Contribution................................. 31 2.31 Attracting Mediocrity.................................... 31 Contents XI 2.32 Discrete Variables with Continuous Error................... 31 2.33 The High-Resolution and the Black-White View............. 31 2.34 The Bivariate Lognormal ................................. 32 √ 2.35 The arcsin( p) Transform................................ 32 2.36 Binomial Trials Depending on a Latent Variable............. 32 2.37 The Delta Technique with One Variable .................... 33 2.38 The Delta Technique with Two Variables ................... 33 2.39 How Many Trials Produced a Given Maximum? ............. 34 2.40 Waiting for Success ...................................... 34 3 Solutions .................................................. 35 3.1 To Begin or Not to Begin?................................ 35 3.2 A Tournament Problem .................................. 36 3.3 Mean Waiting Time for 1−1 vs. 1−2 ..................... 37 3.4 How to Divide up Gains in Interrupted Games .............. 40 3.5 How Often Do Head and Tail Occur Equally Often? ......... 42 3.6 Sample Size vs. Signal Strength ........................... 45 3.7 Birthday Holidays ...................................... 47 3.8 Random Areas ......................................... 49 3.9 Maximize Your Gain..................................... 50 3.10 Maximize Your Gain When Losses Are Possible ............. 52 3.11 The Optimal Level of Supply ............................. 54 3.12 Mixing RVs vs. Mixing Their Distributions ................. 56 3.13 Throwing the Same vs. Different Dice ...................... 59 3.14 Random Ranks.......................................... 61 3.15 Ups and Downs ......................................... 62 3.16 Is 2X the Same as X +X ?.............................. 63 1 2 3.17 How Many Donors Needed?............................... 64 3.18 Large Gaps ............................................. 66 3.19 Small Gaps ............................................. 67 3.20 Random Powers of Random Variables ...................... 68 3.21 How Many Bugs Are Left?................................ 70 3.22 ML Estimation with the Geometric Distribution ............. 72 3.23 How Many Twins Are Homozygotic?....................... 75 3.24 The Lady Tasting Tea ................................... 77 3.25 How to Aggregate Significance Levels ...................... 80 3.26 Approximately How Tall Is the Tallest? .................... 82 3.27 The Range in Samples of Exponential RVs.................. 84 3.28 The Median in Samples of Exponential RVs................. 86 3.29 Breaking the Record ..................................... 87 3.30 Paradoxical Contribution................................. 90 3.31 Attracting Mediocrity.................................... 91 3.32 Discrete Variables with Continuous Error................... 96 3.33 The High-Resolution and the Black-White View............. 98 3.34 The Bivariate Lognormal .................................103