text:
Main Probability and statistics by example. Basic probability and statistics
Probability and statistics by example. Basic probability and statisticsSuhov Y., Kelbert M.
You may be interested in
Most frequently terms
You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you've read. Whether you've loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them.
Probability and Statistics by Example: I Probability and statistics are as much about intuition and problem solving, as they are about theorem proving. Because of this, students can find it very difficult to make a successful transition from lectures to examinations to practice, since the problems involved can vary so much in nature. Since the subject is critical in many modern applications such as mathematical finance, quantitative management, telecommunications, signal processing, bioinformatics, as well as traditional ones such as insurance, social science and engineering, the authors have rectified deficiencies in traditional lecture-based methods by collecting together a wealth of exercises for which they've supplied complete solutions. These solutions are adapted to the needs and skills of students. To make it of broad value, the authors supply basic mathematical facts as and when they are needed, and have sprinkled some historical information throughout the text. Probability and Statistics by Example Volume I. Basic Probability and Statistics Y. SUHOV University of Cambridge M. KELBERT University of Wales–Swansea cambridge university press Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo Cambridge University Press The Edinburgh Building, Cambridge cb2 2ru, UK Published in the United States of America by Cambridge University Press, New York www.cambridge.org Information on this title: www.cambridge.org/9780521847667 © Cambridge University Press 2005 This publication is in copyright. Subject to statutory exception and to the provision of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published in print format isbn-13 isbn-10 978-0-511-13283-4 eBook (NetLibrary) 0-511-13283-2 eBook (NetLibrary) isbn-13 isbn-10 978-0-521-84766-7 hardback 0-521-84766-4 hardback isbn-13 isbn-10 978-0-521-61233-3 paperback 0-521-61233-0 paperback Cambridge University Press has no responsibility for the persistence or accuracy of urls for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. Contents Preface page vii Part I Basic probability 1 1.1 1.2 1.3 1.4 Discrete outcomes A uniform distribution Conditional Probabilities. The Bayes Theorem. Independent trials The exclusion–inclusion formula. The ballot problem Random variables. Expectation and conditional expectation. Joint distributions The binomial, Poisson and geometric distributions. Probability generating, moment generating and characteristic functions Chebyshev's and Markov's inequalities. Jensen's inequality. The Law of Large Numbers and the De Moivre–Laplace Theorem Branching processes 3 3 6 27 Continuous outcomes Uniform distribution. Probability density functions. Random variables. Independence Expectation, conditional expectation, variance, generating function, characteristic function Normal distributions. Convergence of random variables and distributions. The Central Limit Theorem 108 1.5 1.6 1.7 2 2.1 2.2 2.3 1 33 54 75 96 108 142 168 Part II Basic statistics 191 3 3.1 3.2 3.3 3.4 3.5 193 193 204 209 213 215 Parameter estimation Preliminaries. Some important probability distributions Estimators. Unbiasedness Sufficient statistics. The factorisation criterion Maximum likelihood estimators Normal samples. The Fisher Theorem v vi Contents 3.6 3.7 3.8 3.9 Mean square errors. The Rao–Blackwell Theorem. The Cramér–Rao inequality Exponential families Confidence intervals Bayesian estimation 218 225 229 233 4 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 Hypothesis testing Type I and type II error probabilities. Most powerful tests Likelihood ratio tests. The Neyman–Pearson Lemma and beyond Goodness of fit. Testing normal distributions, 1: homogeneous samples The Pearson 2 test. The Pearson Theorem Generalised likelihood ratio tests. The Wilks Theorem Contingency tables Testing normal distributions, 2: non-homogeneous samples Linear regression. The least squares estimators Linear regression for normal distributions 242 242 243 252 257 261 270 276 289 292 5 Cambridge University Mathematical Tripos examination questions in IB Statistics (1992–1999) 298 Appendix 1 Tables of random variables and probability distributions 346 Appendix 2 Index of Cambridge University Mathematical Tripos examination questions in IA Probability (1992–1999) 349 Bibliography 352 Index 358 Preface The original motivation for writing this book was rather personal. The first author, in the course of his teaching career in the Department of Pure Mathematics and Mathematical Statistics (DPMMS), University of Cambridge, and St John's College, Cambridge, had many painful experiences when good (or even brilliant) students, who were interested in the subject of mathematics and its applications and who performed well during their first academic year, stumbled or nearly failed in the exams. This led to great frustration, which was very hard to overcome in subsequent undergraduate years. A conscientious tutor is always sympathetic to such misfortunes, but even pointing out a student's obvious weaknesses (if any) does not always help. For the second author, such experiences were as a parent of a Cambridge University student rather than as a teacher. We therefore felt that a monograph focusing on Cambridge University mathematics examination questions would be beneficial for a number of students. Given our own research and teaching backgrounds, it was natural for us to select probability and statistics as the overall topic. The obvious starting point was the first-year course in probability and the second-year course in statistics. In order to cover other courses, several further volumes will be needed; for better or worse, we have decided to embark on such a project. Thus our essential aim is to present the Cambridge University probability and statistics courses by means of examination (and examination-related) questions that have been set over a number of past years. Following the decision of the Board of the Faculty of Mathematics, University of Cambridge, we restricted our exposition to the Mathematical Tripos questions from the years 1992–1999. (The questions from 2000–2004 are available online at http://www.maths.cam.ac.uk/ppa/.) Next, we included some IA Probability regular example sheet questions from the years 1992–2003 (particularly those considered as difficult by students). Further, we included the problems from Specimen Papers issued in 1992 and used for mock examinations (mainly in the beginning of the 1990s) and selected examples from the 1992 list of so-called sample questions. A number of problems came from example sheets and examination papers from the University of Wales-Swansea. Of course, Cambridge University examinations have never been easy. On the basis of examination results, candidates are divided into classes: first, second (divided into two categories: 2.1 and 2.2) and third; a small number of candidates fail. (In fact, a more detailed list ranking all the candidates in order is produced, but not publicly disclosed.) The examinations are officially called the 'Mathematical Tripos', after the three-legged stools on which candidates and examiners used to sit (sometimes for hours) during oral vii viii Preface examinations in ancient times. Nowadays all examinations are written. The first-year of the three-year undergraduate course is called Part IA, the second Part IB and the third Part II. For example, in May–June of 2003 the first-year mathematics students sat four examination papers; each lasted three hours and included 12 questions from two subjects. The following courses were examined: algebra and geometry, numbers and sets, analysis, probability, differential equations, vector calculus, and dynamics. All questions on a given course were put in a single paper, except for algebra and geometry, which appears in two papers. In each paper, four questions were classified as short (two from each of the two courses selected for the paper) and eight as long (four from each selected course). A candidate might attempt all four short questions and at most five long questions, no more than three on each course; a long question carries twice the credit of a short one. A calculation shows that if a student attempts all nine allowed questions (which is often the case), and the time is distributed evenly, a short question must be completed in 12–13 minutes and a long one in 24–25 minutes. This is not easy and usually requires special practice; one of the goals of this book is to assist with such a training programme. The pattern of the second-year examinations has similarities but also differences. In June 2003, there were four IB Maths Tripos papers, each three hours long and containing nine or ten short and nine or ten long questions in as many subjects selected for a given paper. In particular, IB statistics was set in Papers 1, 2 and 4, giving a total of six questions. Of course, preparing for Part IB examinations is different from preparing for Part IA; we comment on some particular points in the corresponding chapters. For a typical Cambridge University student, specific preparation for the examinations begins in earnest during the Easter (or Summer) Term (beginning in mid-April). Ideally, the work might start during the preceding five-week vacation. (Some of the examination work for Parts IB and II, the computational projects, is done mainly during the summer vacation period.) As the examinations approach, the atmosphere in Cambridge can become rather tense and nervous, although many efforts are made to diffuse the tension. Many candidates expend a great deal of effort in trying to calculate exactly how much work to put into each given subject, depending on how much examination credit it carries and how strong or weak they feel in it, in order to optimise their overall performance. One can agree or disagree with this attitude, but one thing seemed clear to us: if the students receive (and are able to digest) enough information about and insight into the level and style of the Tripos questions, they will have a much better chance of performing to the best of their abilities. At present, owing to great pressures on time and energy, most of them are not in a position to do so, and much is left to chance. We will be glad if this book helps to change this situation by alleviating pre-examination nerves and by stripping Tripos examinations of some of their mystery, at least in respect of the subjects treated here. Thus, the first reason for this book was a desire to make life easier for the students. However, in the course of working on the text, a second motivation emerged, which we feel is of considerable professional interest to anyone teaching courses in probability and statistics. In 1991–2 there was a major change in Cambridge University to the whole Preface ix approach to probabilistic and statistical courses. The most notable aspect of the new approach was that the IA Probability course and the IB Statistics course were redesigned to appeal to a wide audience (200 first-year students in the case of IA Probability and nearly the same number of the second-year students in the case of IB Statistics). For a large number of students, these are the only courses from the whole of probability and statistics which they attend during their undergraduate years. Since more and more graduates in the modern world have to deal with theoretical and (especially) applied problems of a probabilistic or statistical nature, it is important that these courses generate and maintain a strong and wide appeal. The main goal shifted, moving from an academic introduction to the subject towards a more methodological approach which equips students with the tools needed to solve reasonable practical and theoretical questions in a 'real life' situation. Consequently, the emphasis in IA Probability moved further away from sigma-algebras, Lebesgue and Stiltjies integration and characteristic functions to a direct analysis of various models, both discrete and continuous, with the aim of preparing students both for future problems and for future courses (in particular, Part IB Statistics and Part IB/II Markov chains). In turn, in IB Statistics the focus shifted towards the most popular practical applications of estimators, hypothesis testing and regression. The principal determination of examination performance in both IA Probability and IB Statistics became students' ability to choose and analyse the right model and accurately perform a reasonable amount of calculation rather than their ability to solve theoretical problems. Certainly such changes (and parallel developments in other courses) were not always unanimously popular among the Cambridge University Faculty of Mathematics, and provoked considerable debate at times. However, the student community was in general very much in favour of the new approach, and the 'redesigned' courses gained increased popularity both in terms of attendance and in terms of attempts at examination questions (which has become increasingly important in the life of the Faculty of Mathematics). In addition, with the ever-growing prevalence of computers, students have shown a strong preference for an 'algorithmic' style of lectures and examination questions (at least in the authors' experience). In this respect, the following experience by the first author may be of some interest. For some time I have questioned former St John's mathematics graduates, who now have careers in a wide variety of different areas, about what parts of the Cambridge University course they now consider as most important for their present work. It turned out that the strongest impact on the majority of respondents is not related to particular facts, theorems, or proofs (although jokes by lecturers are well remembered long afterwards). Rather they appreciate the ability to construct a mathematical model which represents a real-life situation, and to solve it analytically or (more often) numerically. It must therefore be acknowledged that the new approach was rather timely. As a consequence of all this, the level and style of Maths Tripos questions underwent changes. It is strongly suggested (although perhaps it was not always achieved) that the questions should have a clear structure where candidates are led from one part to another. The second reason described above gives us hope that the book will be interesting for an audience outside Cambridge. In this regard, there is a natural question: what is x Preface the book's place in the (long) list of textbooks on probability and statistics. Many of the references in the bibliography are books published in English after 1991, containing the terms 'probability' or 'statistics' in their titles and available at the Cambridge University Main and Departmental Libraries (we are sure that our list is not complete and apologise for any omission). As far as basic probability is concerned, we would like to compare this book with three popular series of texts and problem books, one by S. Ross [Ros1–Ros6], another by D. Stirzaker [St1–St4], and the third by G. Grimmett and D. Stirzaker [GriS1–GriS3]. The books by Ross and Stirzaker are commonly considered as a good introduction to the basics of the subject. In fact, the style and level of exposition followed by Ross has been adopted in many American universities. On the other hand, Grimmett and Stirzaker's approach is at a much higher level and might be described as 'professional'. The level of our book is intended to be somewhere in-between. In our view, it is closer to that of Ross or Stirzaker, but quite far away from them in several important aspects. It is our feeling that the level adopted by Ross or Stirzaker is not sufficient to get through Cambridge University Mathematical Tripos examinations with Class 2.1 or above. Grimmett and Stirzaker's books are of course more than enough – but in using them to prepare for an examination the main problem would be to select the right examples from among a thousand on offer. On the other hand, the above monographs, as well as many of the books from the bibliography, may be considered as good complementary reading for those who want to take further steps in a particular direction. We mention here just a few of them: [Chu], [Dur1], [G], [Go], [JP], [Sc] and [ChaY]. In any case, the (nostalgic) time when everyone learning probability had to read assiduously through the (excellent) two-volume Feller monograph [Fe] had long passed (though in our view, Feller has not so far been surpassed). In statistics, the picture is more complex. Even the definition of the subject of statistics is still somewhat controversial (see Section 3.1). The style of lecturing and examining the basic statistics course (and other statistics-related courses) at Cambridge University was always rather special. This style resisted a trend of making the exposition 'fully rigorous', despite the fact that the course is taught to mathematics students. A minority of students found it difficult to follow, but for most of them this was never an issue. On the other hand, the level of rigour in the course is quite high and requires substantial mathematical knowledge. Among modern books, the closest to the Cambridge University style is perhaps [CaB]. As an example of a very different approach, we can point to [Wil] (whose style we personally admire very much but would not consider as appropriate for first reading or for preparing for Cambridge examinations). A particular feature of this book is that it contains repetitions: certain topics and questions appear more than once, often in slightly different form, which makes it difficult to refer to previous occurrences. This is of course a pattern of the examination process which becomes apparent when one considers it over a decade or so. Our personal attitudes here followed a proverb 'Repetition is the mother of learning', popular (in various forms) in several languages. However, we apologise to those readers who may find some (and possibly many) of these repetitions excessive. Preface xi This book is organised as follows. In the first two chapters we present the material of the IA Probability course (which consists of 24 one-hour lectures). In this part the Tripos questions are placed within or immediately following the corresponding parts of the expository text. In Chapters 3 and 4 we present the material from the 16-lecture IB Statistics course. Here, the Tripos questions tend to embrace a wider range of single topics, and we decided to keep them separate from the course material. However, the various pieces of theory are always presented with a view to the rôle they play in examination questions. Displayed equations, problems and examples are numbered by chapter: for instance, in Chapter 2 equation numbers run from (2.1) to (2.102), and there are Problems 2.1–2.55. Symbol marks the end of a solution of a given problem. Symbol marks the end of an example. A special word should be said about solutions in this book. In part, we use students' solutions or our own solutions (in a few cases solutions are reduced to short answers or hints). However, a number of the so-called examiners' model solutions have also been used; these were originally set by the corresponding examiners and often altered by relevant lecturers and co-examiners. (A curious observation by many examiners is that, regardless of how perfect their model solutions are, it is rare that any of the candidates follow them.) Here, we aimed to present all solutions in a unified style; we also tried to correct mistakes occurring in these solutions. We should pay the highest credit to all past and present members of the DPMMS who contributed to the painstaking process of supplying model solutions to Tripos problems in IA Probability and IB Statistics: in our view their efforts definitely deserve the deepest appreciation, and this book should be considered as a tribute to their individual and collective work. On the other hand, our experience shows that, curiously, students very rarely follow the ideas of model solutions proposed by lecturers, supervisors and examiners, however impeccable and elegant these solutions may be. Furthermore, students understand each other much more quickly than they understand their mentors. For that reason we tried to preserve whenever possible the style of students' solutions throughout the whole book. Informal digressions scattered across the text have been borrowed from [Do], [Go], [Ha], the St Andrew's University website www-history.mcs.st-andrews.ac.uk/history/ and the University of Massachusetts website www.umass.edu/wsp/statistics/tales/. Conversations with H. Daniels, D.G. Kendall and C.R. Rao also provided a few subjects. However, a number of stories are just part of folklore (most of them are accessible through the Internet); any mistakes are our own responsibility. Photographs and portraits of many of the characters mentioned in this book are available on the University of York website www.york.ac.uk/depts/maths/histstat/people/ and (with biographies) on http://members.aol.com/jayKplanr/images.htm. The advent of the World Wide Web also had another visible impact: a proliferation of humour. We confess that much of the time we enjoyed browsing (quite numerous) websites advertising jokes and amusing quotations; consequently we decided to use some of them in this book. We apologise to the authors of these jokes for not quoting them (and sometimes changing the sense of sentences). xii Preface Throughout the process of working on this book we have felt both the support and the criticism (sometimes quite sharp) of numerous members of the Faculty of Mathematics and colleagues from outside Cambridge who read some or all of the text or learned about its existence. We would like to thank all these individuals and bodies, regardless of whether they supported or rejected this project. We thank personally Charles Goldie, Oliver Johnson, James Martin, Richard Samworth and Amanda Turner, for stimulating discussions and remarks. We are particularly grateful to Alan Hawkes for the limitless patience with which he went through the preliminary version of the manuscript. As stated above, we made wide use of lecture notes, example sheets and other related texts prepared by present and former members of the Statistical Laboratory, Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, and Mathematics Department and Statistics Group, EBMS, University of Wales-Swansea. In particular, a large number of problems were collected by David Kendall and put to great use in Example Sheets by Frank Kelly. We benefitted from reading excellent lecture notes produced by Richard Weber and Susan Pitts. Damon Wischik kindly provided various tables of probability distributions. Statistical tables are courtesy of R. Weber. Finally, special thanks go to Sarah Shea-Simonds and Maureen Storey for carefully reading through parts of the book and correcting a great number of stylistic errors. Part I Basic probability 1 Discrete outcomes 1.1 A uniform distribution Lest men suspect your tale untrue, Keep probability in view. J. Gay (1685–1732), English poet In this section we use the simplest (and historically the earliest) probabilistic model where there are a finite number m of possibilities (often called outcomes) and each of them has the same probability 1/m. A collection A of k outcomes with k ≤ m is called an event and its probability A is calculated as k/m: A = the number of outcomes in A the total number of outcomes (1.1) An empty collection has probability zero and the whole collection one. This scheme looks deceptively simple: in reality, calculating the number of outcomes in a given event (or indeed, the total number of outcomes) may be tricky. Problem 1.1 You and I play a coin-tossing game: if the coin falls heads I score one, if tails you score one. In the beginning, the score is zero. (i) What is the probability that after 2n throws our scores are equal? (ii) What is the probability that after 2n + 1 throws my score is three more than yours? Solution The outcomes in (i) are all sequences HHH H THH H TTT T formed by 2n subsequent letters H or T (or, 0 and 1). The total number of outcomes is m = 22n , each carries probability 1/22n . We are looking for outcomes where the number of Hs equals that of T s. The number k of such outcomes is 2n!/n!n! (the number of ways to choose positions for n Hs among 2n places available in the sequence). The probability 1 2n! × 2n . in question is n!n! 2 In (ii), the outcomes are the sequences of length 2n + 1, 22n+1 in total. The probability equals 2n + 1! 1 × n + 2!n − 1! 22n+1 3 Discrete outcomes 4 Problem 1.2 A tennis tournament is organised for 2n players on a knock-out basis, with n rounds, the last round being the final. Two players are chosen at random. Calculate the probability that they meet (i) in the first or second round, (ii) in the final or semi-final, and (iii) the probability they do not meet. Solution The sentence 'Two players are chosen at random' is crucial. For instance, one may think that the choice has been made after the tournament when all results are known. Then there are 2n−1 pairs of players meeting in the first round, 2n−2 in the second round, two in the semi-final, one in the final and 2n−1 + 2n−2 + · · · + 2 + 1 = 2n − 1 in all rounds. n 2 The total number of player pairs is = 2n−1 2n − 1. Hence the answers: 2 i 3 2n−1 + 2n−2 = 2n−1 2n − 1 22n − 1 ii 3 2n−1 2n − 1 and iii 1 2n−1 2n − 1 − 2n − 1 = 1 − n−1 n−1 n 2 2 − 1 2 Problem 1.3 There are n people gathered in a room. (i) (ii) What is the probability that two (at least) have the same birthday? Calculate the probability for n = 22 and 23. What is the probability that at least one has the same birthday as you? What value of n makes it close to 1/2? Solution The total number of outcomes is 365n . In (i), the number of outcomes not in the event is 365 × 364 × · · · × 365 − n + 1. So, the probability that all birthdays are distinct is 365 × 364 × · · · × 365 − n + 1 365n and that two or more people have the same birthday 365 × 364 × · · · × 365 − n + 1 365n For n = 22: 1− 1− 344 365 364 × ×···× = 04927 365 365 365 and for n = 23: 1− 365 364 343 × ×···× = 05243 365 365 365 In (ii), the number of outcomes not in the event is 364n and the probability in question 1 − 364/365n . We want it to be near 1/2, so 1 364 n 1 ≈ 25261 ≈ i.e. n ≈ − 365 2 log2 364/365 1.1 A uniform distribution 5 Problem 1.4 Mary tosses n + 1 coins and John tosses n coins. What is the probability that Mary gets more heads than John? Solution 1 We must assume that all coins are unbiased (as it was not specified otherwise). Mary has 2n+1 outcomes (all possible sequences of heads and tails) and John 2n ; jointly 22n+1 outcomes that are equally likely. Let HM and TM be the number of Mary's heads and tails and HJ and TJ John's, then HM + TM = n + 1 and HJ + TJ = n. The events HM > HJ and TM > TJ have the same number of outcomes, thus HM > HJ = TM > TJ . On the other hand, HM > HJ if and only if n − HM < n − HJ , i.e. TM − 1 < TJ or TM ≤ TJ . So event HM > HJ is the same as TM ≤ TJ , and TM ≤ TJ = HM > HJ . But for any (joint) outcome, either TM > TJ or TM ≤ TJ , i.e. the number of outcomes in TM > TJ equals 22n+1 minus that in TM ≤ TJ . Therefore, TM > TJ = 1 − TM ≤ TJ . To summarise: HM > HJ = TM > TJ = 1 − TM ≤ TJ = 1 − HM > HJ whence HM > HJ = 1/2. Solution 2 (Fallacious, but popular with some students.) Again assume that all coins are unbiased. Consider pair HM HJ , as an outcome; there are n + 2n + 1 such possible pairs, and they all are equally likely (wrong: you have to have biased coins for this!). Now count the number of pairs with HM > HJ . If HM = n + 1, HJ can take any value 0 1 n. In general, ∀l ≤ n + 1, if HM = l, HJ will take values 0 l − 1. That is, the number of outcomes where HM > HJ equals 1 + 2 + · · · + n + 1 = 21 n + 1n + 2. Hence, HM > HJ = 1/2. Problem 1.5 You throw 6n dice at random. Show that the probability that each number appears exactly n times is 6n! n!6 6n 1 6 Solution There are 66n outcomes in total (six for each die), each has probability 1/66n . We want n dice to show one dot, n two, and so forth. The number of such outcomes is counted by fixing first which dice show one: 6n! n!5n! . Given n dice showing one, we fix which remaining dice show two: 5n! n!4n!], etc. The total number of desired outcomes is the product that equals 6n!n!6 . This gives the answer. In many problems, it is crucial to be able to spot recursive equations relating the cardinality of various events. For example, for the number fn of ways of tossing a coin n times so that successive tails never appear: fn = fn−1 + fn−2 , n ≥ 3 (a Fibonacci equation). 6 Discrete outcomes Problem 1.6 (i) Determine the number gn of ways of tossing a coin n times so that the combination HT never appears. (ii) Show that fn = fn−1 + fn−2 + fn−3 , n ≥ 3, is the equation for the number of ways of tossing a coin n times so that three successive heads never appear. Solution (i) gn = 1 + n; 1 for the sequence HH H, n for the sequences T TH H (which includes T T ). (ii) The outcomes are 2n sequences y1 yn of H and T . Let An be the event {no three successive heads appeared after n tosses}, then fn is the cardinality #An . Split: An = Bn1 ∪ Bn2 ∪ Bn3 , where Bn1 is the event {no three successive heads appeared after n tosses, and the last toss was a tail}, Bn2 = {no three successive heads appeared after n tosses, and the last two tosses were TH} and Bn3 ={no three successive heads appeared after n tosses, and the last three tosses were THH}. Clearly, Bni ∩ Bnj = ∅, 1 ≤ i = j ≤ 3, and so fn = #Bn1 + #Bn2 + #Bn3 . Now drop the last digit yn : y1 yn ∈ Bn1 iff yn = T , y1 yn−1 ∈ An−1 , i.e. 1 #Bn−1 = fn−1 . Also, y1 yn ∈ Bn2 iff yn−1 = T , yn = H, and y1 yn−2 ∈ An−2 . This allows us to drop the two last digits, yielding #Bn2 = fn−2 . Similarly, #Bn3 = fn−3 . The equation then follows. 1.2 Conditional Probabilities. The Bayes Theorem. Independent trials Probability theory is nothing but common sense reduced to calculation. P.-S. Laplace (1749–1827), French mathematician Clockwork Omega (From the series 'Movies that never made it to the Big Screen'.) From now on we adopt a more general setting: our outcomes do not necessarily have equal probabilities p1 pm , with pi > 0 and p1 + · · · + pm = 1. As before, an event A is a collection of outcomes (possibly empty); the probability A of event A is now given by A = outcome i∈A pi = pi Ii ∈ A (1.2) outcome i (A = 0 for A = ∅.) Here and below, I stands for the indicator function, viz.: Ii ∈ A = 1 if i ∈ A 0 otherwise The probability of the total set of outcomes is 1. The total set of outcomes is also called the whole, or full, event and is often denoted by , so = 1. An outcome is 1.2 Conditional probabilities , and if p is its probability, then A = p = p I ∈ A 7 often denoted by ∈A (1.3) ∈ As follows from this definition, the probability of the union A1 ∪ A2 = A1 + A2 (1.4) for any pair of disjoint events A1 , A2 (with A1 ∩ A2 = ∅). More generally, A1 ∪ · · · ∪ An = A1 + · · · + An (1.5) for any collection of pair-wise disjoint events (with Aj ∩ Aj = ∅ ∀j = j ). Consequently, (i) the probability Ac of the complement Ac = \A is 1 − A, (ii) if B ⊆ A, then B ≤ A and A− B = A\B, and (iii) for a general pair of events A B: A\B = A\A ∩ B = A − A ∩ B. Furthermore, for a general (not necessarily disjoint) union: A1 ∪ · · · ∪ An ≤ n Ai i=1 a more detailed analysis of the probability ∪Ai is provided by the exclusion–inclusion formula (1.12); see below. Given two events A and B with B > 0, the conditional probability A B of A given B is defined as the ratio A B = A ∩ B B (1.6) At this stage, the conditional probabilities are important for us because of two formulas. One is the formula of complete probability: if B1 Bn are pair-wise disjoint events partitioning the whole event , i.e. have Bi ∩ Bj = ∅ for 1 ≤ i < j ≤ n and B1 ∪ B2 ∪ · · · ∪ Bn = , and in addition Bi > 0 for 1 ≤ i ≤ n, then A = A B1 B1 + A B2 B2 + · · · + A Bn Bn (1.7) The proof is straightforward: A = 1≤i≤n A ∩ Bi = A ∩ Bi Bi = A Bi Bi Bi 1≤i≤n 1≤i≤n The point is that often it is conditional probabilities that are given, and we are required to find unconditional ones; also, the formula of complete probability is useful to clarify the nature of (unconditional) probability A. Despite its simple character, this formula is an extremely powerful tool in literally all areas dealing with probabilities. In particular, a large portion of the theory of Markov chains is based on its skilful application. Representing A in the form of the right-hand side (RHS) of (1.7) is called conditioning (on the collection of events B1 Bn ). 8 Discrete outcomes Another formula is the Bayes formula (or the Bayes Theorem) named after T. Bayes (1702–1761), an English mathematician and cleric. It states that under the same assumptions as above, if in addition A > 0, then the conditional probability Bi A can be expressed in terms of probabilities B1 Bn and conditional probabilities A B1 A Bn as A Bi Bi Bi A = A Bj Bj (1.8) 1≤j≤n The proof is the direct application of the definition and the formula of complete probability: Bi A = A ∩ Bi A ∩ Bi = A Bi Bi A and A = A Bj Bj j A standard interpretation of equation (1.8) is that it relates the posterior probability Bi A (conditional on A) with prior probabilities Bj (valid before one knew that event A occurred). In his lifetime, Bayes finished only two papers: one in theology and one called 'Essay towards solving a problem in the doctrine of chances'; the latter contained the Bayes Theorem and was published two years after his death. Nevertheless he was elected a Fellow of The Royal Society. Bayes' theory (of which the above theorem is an important part) was for a long time subject to controversy. His views were fully accepted (after considerable theoretical clarifications) only at the end of the nineteenth century. Problem 1.7 Four mice are chosen (without replacement) from a litter containing two white mice. The probability that both white mice are chosen is twice the probability that neither is chosen. How many mice are there in the litter? Solution Let the number of mice in the litter be n. We use the notation 2 = two white chosen and 0 = no white chosen. Then n−2 n 2 = 2 4 Otherwise, 2 could be computed as: 2 n−2 1 2 n−2 n−3 1 n−2 2 1 2 1 + + + n n−1 n n−1 n−2 n n−1 n−2 n−3 n n−1 n−2 + n−2 2 n−3 1 12 1 n−2 n−3 2 + = n n−1 n−2 n−3 n n − 1 n − 2 n − 3 nn − 1 1.2 Conditional probabilities 9 On the other hand, 0 = n−2 4 n 4 Otherwise, 0 could be computed as follows: 0 = n − 2 n − 3 n − 4 n − 5 n − 4n − 5 = n n−1 n−2 n−3 nn − 1 Solving the equation 12 n − 4n − 5 =2 nn − 1 nn − 1 we get n = 9 ± 5 2; n = 2 is discarded as n ≥ 6 (otherwise the second probability is 0). Hence, n = 7. Problem 1.8 Lord Vile drinks his whisky randomly, and the probability that, on a given day, he has n glasses equals e−1 n!, n = 0 1 Yesterday his wife Lady Vile, his son Liddell and his butler decided to murder him. If he had no whisky that day, Lady Vile was to kill him; if he had exactly one glass, the task would fall to Liddell, otherwise the butler would do it. Lady Vile is twice as likely to poison as to strangle, the butler twice as likely to strangle as to poison, and Liddell just as likely to use either method. Despite their efforts, Lord Vile is not guaranteed to die from any of their attempts, though he is three times as likely to succumb to strangulation as to poisoning. Today Lord Vile is dead. What is the probability that the butler did it? Solution Write dead strangle = 3r dead poison = r, and 1 drinks no whisky = drinks one glass = e 2 drinks two glasses or more = 1 − e Next: 2 1 strangle Lady V = poison Lady V = 3 3 1 2 strangle butler = poison butler = 3 3 and 1 strangle Liddell = poison Liddell = 2 10 Discrete outcomes Then the conditional probability butler dead is d bb d bb + d LVLV + d LddlLddl 3r × 2 r 2 + 1− e 3 3 = 3r × 2 r 2 1 3r r × 2 1 3r r + + + 1− + + e 3 3 e 3 3 e 2 2 = e−2 ≈ 03137 e − 3/7 Problem 1.9 At the station there are three payphones which accept 20p pieces. One never works, another always works, while the third works with probability 1 2. On my way to the metropolis for the day, I wish to identify the reliable phone, so that I can use it on my return. The station is empty and I have just three 20p pieces. I try one phone and it does not work. I try another twice in succession and it works both times. What is the probability that this second phone is the reliable one? Solution Let A be the event in the question: the first phone tried did not work and second worked twice. Clearly: A 1st reliable = 0 A 2nd reliable = 1st never works 2nd reliable 1 + × 1st works half-time 2nd reliable 2 1 1 1 3 = + × = 2 2 2 4 and the probability A 3rd reliable equals 1 1 1 × × 2nd works half-time 3rd reliable = 8 2 2 The required probability 2nd reliable is then 1/3 × 3/4 6 = 1/3 × 0 + 3/4 + 1/8 7 Problem 1.10 Parliament contains a proportion p of Labour Party members, incapable of changing their opinions about anything, and 1 − p of Tory Party members changing their minds at random, with probability r, between subsequent votes on the same issue. A randomly chosen parliamentarian is noticed to have voted twice in succession in the same way. Find the probability that he or she will vote in the same way next time. 1.2 Conditional probabilities 11 Solution Set A1 = Labour chosen A2 = Tory chosen B = the member chosen voted twice in the same way We have A1 = p, A2 = 1 − p, B A1 = 1, B A2 = 1 − r. We want to calculate A1 B = A1 ∩ B A1 B A1 = B B and A2 B = 1 − A1 B. Write B = A1 B A1 + A2 B A2 = p · 1 + 1 − p1 − r Then A1 B = p 1 − r1 − p A2 B = p + 1 − r1 − p p + 1 − r1 − p and the answer is given by p + 1 − r2 1 − p the member will vote in the same way B = p + 1 − r1 − p Problem 1.11 The Polya urn model is as follows. We start with an urn which contains one white ball and one black ball. At each second we choose a ball at random from the urn and replace it together with one more ball of the same colour. Calculate the probability that when n balls are in the urn, i of them are white. Solution Denote by n the conditional probability given that there are n balls in the urn. For n = 2 and 3 n one white ball = 1 n = 2 1 n = 3 2 and n two white balls = 21 n = 3 Make the induction hypothesis k i white balls = 1 k−1 ∀ k = 2 n − 1 and i = 1 k − 1. Then, after n − 1 trials (when the number of balls is n), n i white balls i−1 n−1−i = n−1 i − 1 white balls × + n−1 i white balls × n−1 n−1 1 i = 1 n − 1 = n−1 Discrete outcomes 12 Hence, n i white balls = 1 i = 1 n − 1 n−1 Problem 1.12 You have n urns, the rth of which contains r − 1 red balls and n − r blue balls, r = 1 n. You pick an urn at random and remove two balls from it without replacement. Find the probability that the two balls are of different colours. Find the same probability when you put back a removed ball. Solution The totals of blue and red balls in all urns are equal. Hence, the first ball is equally likely to be any ball. So 1 1st blue = = 1st red 2 Now, n 1 1st red, 2nd blue = 1st red, 2nd blue urn k chosen × n k=1 = 1 k − 1n − k n k n − 1n − 2 = n n 1 n k − 1 − kk − 1 nn − 1n − 2 k=1 k=1 nn − 1n n + 1nn − 1 1 − nn − 1n − 2 2 3 n n+1 nn − 1 1 − = = nn − 1n − 2 2 3 6 = We used here the following well-known identity: n 1 ii − 1 = n + 1nn − 1 3 i=1 By symmetry: different colours = 2 × 1 1 = 6 3 If you return a removed ball, the probability that the two ball are of different colours becomes 1/2. Problem 1.13 You are on a game show and given a choice of three doors. Behind one is a car; behind the two others are a goat and a pig. You pick door 1, and the host opens door 3, with a pig. The host asks if you want to pick door 2 instead. Should you switch? What if instead of a goat and a pig there were two goats? 1.2 Conditional probabilities 13 Solution A popular solution of this problem always assumes that the host knows behind which door the car is, and takes care not to open this door rather than doing so by chance. (It is assumed that the host never opens the door picked by you.) In fact, it is instructive to consider two cases, depending on whether the host does or does not know the door with the car. If he doesn't, your chances are unaffected, otherwise you should switch. Indeed, consider the events Yi = you pick door i Ci = the car is behind door i Hi = the host opens door i Gi /Pi = a goat/pig is behind door i with Yi = Ci = Gi = Pi = 1/3 i = 1 2 3. Obviously, event Yi is independent of any of the events Cj Gj and Pj i j = 1 2 3. You want to calculate C1 Y1 ∩ H3 ∩ P3 = C1 ∩ Y1 ∩ H3 ∩ P3 Y1 ∩ H3 ∩ P3 In the numerator: C1 ∩ Y1 ∩ H3 ∩ P3 = C1 Y1 C1 P3 C1 ∩ Y1 H3 C1 ∩ Y1 ∩ P3 1 1 1 1 1 = × × × = 3 3 2 2 36 If the host doesn't know where the car is, then Y1 ∩ H3 ∩ P3 = Y1 P3 Y1 H3 Y1 ∩ P3 1 1 1 1 = × × = 3 3 2 18 and C1 Y1 ∩ H3 ∩ P3 = 1 2. But if he does then Y1 ∩ H3 ∩ P3 = Y1 ∩ C1 ∩ H3 ∩ P3 + Y1 ∩ C2 ∩ H3 ∩ P3 1 1 1 1 1 1 1 1 = × × × × × × ×1= 3 3 2 2 3 3 2 12 and C1 Y1 ∩ H3 ∩ P3 = 1/3. The answer remains the same if there were two goats instead of a goat and a pig. Another useful exercise is to consider the case where the host has some 'preference' choosing a door with the goat with probability pg and that with the pig with probability pp = 1 − pg . We continue our study by introducing the definition of independent events. The concept of independence was an important invention in probability theory. It shaped the theory at an early stage and is considered one of the main features specifying the place of probability theory within more general measure theory. 14 Discrete outcomes We say that events A and B are independent if A ∩ B = AB (1.9) A convenient criterion of independence is: events A and B, where say B > 0 are independent iff A B = A, i.e. knowledge that B occurred does not change the probability of A. Trivial examples are the empty event ∅ and the whole set : they are independent of any event. The next example we consider is when each of the four outcomes 00 01 10, and 11 have probability 1/4. Here the events A = 1st digit is 1 and B = 2nd digit is 0 are independent: A = p10 + p11 = 1 1 1 1 = p10 + p00 = B A ∩ B = p10 = = × 2 4 2 2 Also, the events 1st digit is 0 and both digits are the same are independent, while the events 1st digit is 0 and the sum of digits is > 0 are dependent. These examples can be easily re-formulated in terms of two unbiased coin-tossings. An important fact is that if A B are independent then Ac and B are independent: Ac ∩ B = B\A ∩ B = B − A ∩ B = B − AB by independence = 1 − A B = Ac B Next, if (i) A1 and B are independent, (ii) A2 and B are independent, and (iii) A1 and A2 are disjoint, then A1 ∪ A2 and B are independent. If (i) and (ii) hold and A1 ⊂ A2 then B and A2 \A1 are also independent. Intuitively, independence is often associated with an 'absence of any connection' between events. There is a famous joke about A.N. Kolmogorov (1903–1987), the renowned Russian mathematician considered the father of the modern probability theory. His monograph [Ko], which originally appeared in German in 1933, was revolutionary in understanding the basics of probability theory and its rôle in mathematics and its 1.2 Conditional probabilities 15 applications. When in the 1930s this monograph was translated into Russian, the Soviet government enquired about the nature of the concept of independent events. A senior minister asked if this concept was consistent with materialistic determinism, the core of Marxist–Leninist philosophy, and about examples of such events. Kolmogorov had to answer on the spot, and he had to be cautious as subsequent events showed, such as the infamous condemnation by the authorities of genetics as a 'reactionary bourgeois pseudo-science'. The legend is that he did not hesitate for a second, and said: 'Look, imagine a remote village where there has been a long drought. One day, local peasants in desperation go to the church, and the priest says a prayer for rain. And the next day the rain arrives! These are independent events.' In reality, the situation is more complex. A helpful view is that independence is a geometric property. In the above example, the four probabilities p00 p01 p10 and p11 can be assigned to the vertices 0 0 0 1 1 1 and 1 0 of a unit square. See Figure 1.1. Each of these four points has a projection onto the horizontal and the vertical line. The projections are points 0 and 1 on each of these lines, and a vertex is uniquely determined by its projections. If the projection points have probability mass 1/2 on each line then each vertex has pij = 1 1 1 × = i j = 0 1 2 2 4 In this situation one says that the four-point probability distribution 1 1 1 1 4 4 4 4 is a product of two two-point distributions 1 1 2 2 1/4 1/4 1/2 (1) (2) p ij = p i p j 1/4 1/4 1/2 Figure 1.1 1/2 1/2 16 Discrete outcomes It is easy to imagine a similar picture where there are m points along the horizontal and n along the vertical line: we would then have mn pairs i j (lattice sites) where i = 0 m − 1 j = 0 n − 1 and each pair will receive probability mass 1/mn. Moreover, the equidistribution can be replaced by a more general law: 1 2 pij = pi pj where 1 2 pi i = 0 m − 1 and pj j = 0 n − 1 are probability distributions for the two projections. Then any event that is expressed in terms of the horizontal projection (e.g., digit i is divisible by 3) is independent of any event expressed in terms of the vertical projection (e.g., digit j is ≤ n/2). This is a basic (and in a sense the only) example of independence. More generally, we say that events A1 An are mutually independent (shortly, independent) if ∀ subcollections Ai1 Ail , Ai1 ∩ · · · ∩ Ail = Ai1 Ail (1.10) This includes the whole collection A1 An . It is important to distinguish this situation from the one where (1.10) holds only for some subcollections; say pairs Ai Aj 1 ≤ i < j ≤ n, or only for the whole collection A1 An . See Problems 1.20 and 1.21. This gives rise to an important model: a sequence of independent trials, each with two or more outcomes. Such a model is behind many problems, and it is essential to familiarize yourself with it. So far, we assumed that the total number of outcomes is finite, but the material in this section can be extended to the case where is a countable set, consisting of points x1 x2 , say, with assigned probabilities pi = xi i = 1 2 Of course, the labelling of the outcomes can be different, for instance, by i ∈ , the set of integers. The requirements are as before: each pi ≥ 0 and i pi = 1. We can also work with infinite sequences of events. For example, equations (1.7) and (1.8) do not change form: A = A Bi Bi A Bj Bj Bi A = A Bj Bj 1≤j< (1.11) 1≤j< Problem 1.14 A coin shows heads with probability p on each toss. Let n be the probability that the number of heads after n tosses is even. By showing that n+1 = 1 − pn + p1 − n n ≥ 1, or otherwise, find n . (The number 0 is considered even.) Solution 1 As always in the coin-tossing models, we assume that outcomes of different throws are independent. Set An = nth toss is a head, with An = p and 1.2 Conditional probabilities 17 Bn = even number of heads after n tosses, with n = Bn . Then, by conditioning on An+1 and Acn+1 : Bn+1 = Bn+1 ∩ An+1 + Bn+1 ∩ Acn+1 = Bn+1 An+1 An+1 + Bn+1 Acn+1 Acn+1 Next, Bn+1 ∩ An+1 = Bnc ∩ An+1 and Bn+1 ∩ Acn+1 = Bn ∩ Acn+1 . In view of independence, Bnc ∩ An+1 = Bnc An+1 and Bn ∩ Acn+1 = Bn Acn+1 which implies Bn+1 = Bnc An+1 + Bn Acn+1 = 1 − Bn p + Bn 1 − p with B0 = 1. That is, n+1 = 1 − pn + p1 − n = 1 − 2pn + p Substituting n = a1 − 2pn + b gives that b = 1/2, and the condition 0 = 1 that a = 1/2. Then n = 1 − 2pn + 1 /2. A shorter way to derive the recursion is by conditioning on Bn and Bnc : n+1 = Bn+1 = Bn+1 ∩ Bn + Bn+1 ∩ Bnc = Acn+1 Bn Bn + An+1 Bnc Bnc = 1 − pn + p1 − n Writing recursive equations like the one in the statement of the current problem is a convenient instrument used in a great many situations. Solution 2 (Look at this solution after reading Section 1.5.) Let Xi = 0 or 1 be the outcome of the ith trial, and Yn = X1 + · · · + Xn the total number of successes in n trials. Then the probability generating function of Yn s = ps + 1 − p n Then the probability that n trials result in an even number of successes is 1 1 1 + −1 = 1 + 1 − 2pn 2 2 Problem 1.15 My Aunt Agatha has given me a clockwork orange for my birthday. I place it in the middle of my dining table which happens to be exactly 2 metres long. One minute after I place it on the table it makes a loud whirring sound, emits a puff of green smoke and moves 10 cm towards the left-hand end of the table with probability 3/5, or 10 cm towards the right with probability 2/5. It continues in this manner (the direction of each move being independent of what has gone before) at one minute intervals until it 18 Discrete outcomes reaches the edge of the table where it promptly falls off. If it falls off the left-hand end it will break my Ming vase (also a present from Aunt Agatha). If it falls off the right-hand end it will land safely in a bucket of water. What is the probability that the Ming vase will survive? Solution Set p to be falls at RH end was at distance × 10 cm from the LH end then 1 − p equals falls at LH end was at distance × 10 cm from LH end We have p0 = 0 p20 = 1 and p = 35 p−1 + 25 p+1 or 5 3 p+1 = p − p−1 2 2 In other words, vector p p+1 = p−1 p A with 0 − 23 A= 1 25 This yields p p+1 = p0 p1 A = 0 p1 A i.e. p should be a linear combination of the th powers of the eigenvalues of A. The eigenvalues are 1 = 23 and 2 = 1 and so: 3 p = b1 + b2 2 We have the equations b1 + b2 = 0 1 = b1 20 3 + b2 2 whence 20 3 b1 = −b2 = −1 2 and −1 10 3 1 1 1 − = p10 = 20 20 2 3/2 − 1 3/2 − 1 3/210 + 1 Problem 1.16 Dubrovsky sits down to a night of gambling with his fellow officers. Each time he stakes u roubles there is a probability r that he will win and receive back 2u roubles (including his stake). At the beginning of the night he has 8000 roubles. If ever 1.2 Conditional probabilities 19 he has 256 000 roubles he will marry the beautiful Natasha and retire to his estate in the country. Otherwise, he will commit suicide. He decides to follow one of two courses of action: (i) (ii) to stake 1000 roubles each time until the issue is decided; to stake everything each time until the issue is decided. Advise him (a) if r = 1/4 and (b) if r = 3/4. What are the chances of a happy ending in each case if he follows your advice? Solution Let p be the probability that Dubrovsky wins 256 000 with the starting capital thousands while following strategy (i). Reasoning as in Problem 1.15 yields that p = b1 1 + b2 2 where 1 = 1 − r/r and 2 = 1 are the eigenvalues of the matrix 0 1 − r/r A= 1 1/r The boundary conditions p0 = 0 and p256 = 1 yield b1 = −b2 = 1−r r 256 −1 −1 For r = 1/4, 1 − r/r = 3. Then he should choose (ii) as p8 = 38 − 1 3256 − 1 which is tiny compared with 1/45 , the chance to win 256 000 in five successful rounds by gambling on everything he obtains. For r = 3/4, 1 − r/r = 1/3. Then p8 = 1 − 1/38 1 − 1/3256 which is much larger than 3/45 . Therefore, he should choose (i). Remark In both Problems 1.15 and 1.16 one of the eigenvalues of the recursion matrix A equals one. This is not accidental and is due to the fact that in equation (1.7) (which gives rise to the recursive equations under consideration) the sum j Bj = 1. Problem 1.17 I play the dice game 'craps' against 'Lucky' Pete Jay as follows. On each throw I throw two dice. If my first throw is 7 or 11, then I win and if it is 2, 3 or 12, then I lose. If my first throw is none of these, I throw repeatedly until I score the same as my first throw, in which case I win, or I throw a 7, in which case I lose. What is the probability that I win? Discrete outcomes 20 Solution Write I win = I win at the 1st throw + I win, but not at the 1st throw The probability I win at the 1st throw is straightforward and equals 6 6 6 2 2 1 1 Ii + j = 7 + Ii + j = 11 = + = 36 36 9 ij=1 36 ij=1 36 Here Ii + j = 7 = 1 if i + j = 7 0 otherwise For the second probability we have I win, but not at the 1st throw = pi qi i=4568910 Here pi = the 1st score is i and qi = get i before 7 in the course of repeated throws the 1st score is i = get i before 7 in the course of repeated throws Then for qi , by conditioning on the result of the first throw: qi = pi + 1 − pi − p7 qi i.e. qi = pi pi + p 7 Equivalently, qi = pi + 1 − pi − p7 pi + 1 − pi − p7 2 pi + · · · with the same result. Now q4 = 3 1 4 2 3/36 4/36 = = q5 = = = 3/36 + 6/36 3 + 6 3 4/36 + 6/36 4 + 6 5 and likewise, q6 = 5 5 5/36 5 2 1 = = q = q = q = 5/36 + 6/36 5 + 6 11 8 11 9 5 10 3 giving for I win, but not at the 1st throw the value 1 1 1 2 5 5 5 5 1 1 1 1 134 × + × + × + × + × + × = 12 3 9 5 36 11 36 11 9 5 12 3 495 1.2 Conditional probabilities 21 Then I win = 2 134 244 + = 9 495 495 Problem 1.18 Two darts players throw alternately at a board and the first to score a bull wins. On each of their throws player A has probability pA and player B pB of success; the results of different throws are independent. If A starts, calculate the probability that he/she wins. Solution Consider the diagram below. 1 − pA • −→ 1 − pB • −→ 1 − pA • −→ 1 − pB • −→ pA A wins pB B wins pA A wins pB B wins If q = A wins, then q = pA + 1 − pA 1 − pB pA + 1 − pA 2 1 − pB 2 pA + · · · pA pA = = 1 − 1 − pA 1 − pB pA + pB − pA pB Equivalently, by conditioning on the first and the second throw, one gets the equation A wins = pA + 1 − pA 1 − pB A wins which is immediately solved to give the required result. Remark In Problems 1.17 and 1.18 we used an equation for the probabilities q and qi that was equivalent to their representation as series. This is another useful idea; for example, it allowed us to avoid the use of infinite outcome spaces. However, we will not be able to avoid it much longer. Problem 1.19 A fair coin is tossed until either the sequence HHH occurs in which case I win or the sequence THH occurs, when you win. What is the probability that you win? Solution In principle, the results of the game could be I win, you win and the game lasts Observe that I win only if HHH occurs at the beginning: the probability forever. 3 is 1/2 = 1/8. Indeed, if HHH occurs but not at the beginning then THH should have occurred before then you will have already won. But HHH will appear sooner or later, with probability 1. In fact, ∀ N , the event A = HHH never occurs Discrete outcomes 22 is contained in the event AN = HHH does not occur among the first N subsequent triples (we partition first 3N trials into N subsequent triples). So A ≤ AN . But the probability AN = 1 − 1/8N → 0 as N → . Hence, A = 0. Therefore, the game cannot continue forever, and the probability that you win is 1 − 1/8 = 7/8. Problem 1.20 (i) Give examples of the following phenomena: (a) three events A B C that are pair-wise independent but not independent; (b) three events that are not independent, but such that the probability of the intersection of all three is equal to the product of the probabilities. (ii) Three coins each show heads with probability 3/5 and tails otherwise. The first counts 10 points for a head and 2 for a tail, the second counts 4 points for a head and tail, and the third counts 3 points for a head and 20 for a tail. You and your opponent each choose a coin; you cannot choose the same coin. Each of you tosses your coin once and the person with the larger score wins 1010 points. Would you prefer to be the first or the second to choose a coin? Solution (i) (a) Toss two unbiased coins, with A = 1st toss shows H B = 2nd toss shows H and C = both tosses show the same side Then 1 1 = AB A ∩ C = pHH = = AC 4 4 1 B ∩ C = pHH = = BC 4 A ∩ B = pHH = and A ∩ B ∩ C = pHH = 1 = ABC 4 Or throw three dice, with A = dice one shows an odd score B = dice two shows an odd score C = overall score odd and A = B = C = 1/2. Then 1 A ∩ B = A ∩ C = B ∩ C = but A ∩ B ∩ C = 0 4 1.2 Conditional probabilities 23 (b) Toss three coins, with A = 1st toss shows H B = 3rd toss shows H C = HHH HHT HTT TTT = no subsequent TH Then A = B = C = 1/2, 3 1 1 A ∩ B ∩ C = HHH and A ∩ B ∩ C = = 8 2 But 3 A ∩ C = HHH HHT HTT and A ∩ C = 8 while 1 B ∩ C = HHH and B ∩ C = 8 Or (as the majority of students' attempts did so far), take A = ∅, and any dependent pair B C (say, B = C with 0 < B < 1). Then A ∩ B ∩ C = ∅ and A ∩ B ∩ C = 0 = ABC but B ∩ C = BC (ii) Suppose I choose coin 1 and you coin 2, then you win = 2/5. But if you choose 3 then you win = 2 3 2 16 1 + × = > 5 5 5 25 2 Similarly, if I choose 2 and you choose 1, you win = 3/5 > 1/2. Finally, if I choose 3 and you choose 2 then you win = 3/5 > 1/2. Thus, it's always better to be the second. Problem 1.21 Let A1 An be independent events, with Ai < 1. Prove that there exists an event B with B > 0 such that B ∩ Ai = ∅, for 1 ≤ i ≤ n. Give an example of three events A1 A2 A3 which are not independent, but are such that for each i = j the pair Ai Aj is independent. Solution If Ac denotes the complement of event A, then A1 ∪ · · · ∪ An = 1 − n Aci =1− i=1 n Aci < 1 i=1 as Aci > 0 ∀ i. So, if B = Ai c , then B > 0 and B ∩ Ai = ∅ ∀ i. Next, take events A1 = 1 4 A1 = 2 4 A3 = 3 4 24 Discrete outcomes where the probability assigned to each outcome k = 1 2 3 4 equals 1/4. Then Ai = 1/2 i = 1 2 3, and Ai ∩ Aj = 4 = 2 1 = Ai Aj 1 ≤ i < j ≤ 3 2 However, the intersection A1 ∩ A2 ∩ A3 consists of a single outcome 4. Hence A1 ∩ A2 ∩ A3 = 3 1 1 = = A1 A2 A3 4 2 Problem 1.22 n balls are placed at random into n cells. Find the probability pn that exactly two cells remain empty. Solution 'At random' means here that each ball is put in a cell with probability 1/n, independently of other balls. First, consider the cases n = 3 and n = 4. If n = 3 we have one cell with three balls and two empty cells. Hence, 1 1 n × n= p3 = 2 n 9 If n = 4 we either have two cells with two balls each (probability p4 ) or one cell with one ball and one cell with three balls (probability p4 ). Hence, p4 = p4 + p4 = 21 nn − 1 n − 2 n = × 4 + × 2 nn 4 64 Here 4 stands for a number of ways to select three balls that will go to one cell, and nn − 1/4 stands for the number of ways to select two pairs of balls that will go to two prescribed cells. For n ≥ 5 to have exactly two empty cells means that either there are exactly two cells with two balls in them and n − 4 with a single ball, or there is one cell with three balls and n − 3 with a single ball. Denote probabilities in question by pn and pn , respectively. Then pn = pn + pn . Further, 2 1 1 1 n n−2 n−2 n−3 n ··· × pn = × × 2 2 2 2 n n n n 1 n! n n − 2 = 2 4 nn 2 Here the first factor, n2 , is responsible for the number of ways of choosing two empty cells among n. The second factor, 1 n n−2 2 2 2 1.2 Conditional probabilities 25 accounts for choosing which balls 'decide' to fall in cells that will contain two balls and also which cells will contain two balls. Finally, the third factor, 1 n−2 n−3 n n n gives the probability that n − 2 balls fall in n − 2 cells, one in each, and the last 1/n2 that two pairs of balls go into the cells marked for two-ball occupancy. Next, n n n − 3! pn = × n − 2 × 2 3 nn Here the first factor n2 is responsible for the number of ways of choosing two empty cells among n, the second n − 2 is responsible for the number of ways of choosing the cell with three balls, the third n3 is responsible for the number of ways of choosing three n − 3! describes the distribution of all balls balls to go into this cell, and the last factor nn into the respective cells. Problem 1.23 You play a match against an opponent in which at each point either you or he/she serves. If you serve you win the point with probability p1 but if your opponent serves you win the point with probability p2 . There are two possible conventions for serving: (i) alternate serves; (ii) the player serving continues until he/she loses a point. You serve first and the first player to reach n points wins the match. Show that your probability of winning the match does not depend on the serving convention adopted. Solution Both systems give you equal probabilities of winning. In fact, suppose we extend the match beyond the result achieved, until you have served n and your opponent n − 1 times. (Under rule (i) you just continue the alternating services and under (ii) the loser is given the remaining number of serves.) Then, under either rule, if you win the actual game, you also win the extended one, and vice versa (as your opponent won't have enough points to catch up with you). So it suffices to check the extended matches. An outcome of an extended match is = 1 2n−1 , a sequence of 2n − 1 subsequent values, say zero (you lose a point) and one (you gain one). You may think that 1 n represent the results of your serves and n+1 2n−1 those of your opponent. Define events Ai = you win your ith service and Bj = you win his jth service Their respective indicator functions are 1 ∈ Ai I ∈ Ai = 0 ∈ Ai 1 ≤ i ≤ n 26 Discrete outcomes and I ∈ Bj = 1 ∈ Bj ∈ Bj 1 ≤ j ≤ n − 1 0 Under both rules, the event that you win the extended match is = 1 2n−1 i ≥n 1≤i≤2n−1 and the probability of outcome p1 i IAi 1 − p1 n− i IAi is p2 j IBj n− 1 − p2 j IBj Because they do not depend on the choice of the rule, the probabilities are the same. Remark The -notation was quite handy in this solution. We will use it repeatedly in future problems. Problem 1.24 The departmental photocopier has three parts A B and C which can go wrong. The probability that A will fail during a copying session is 10−5 . The probability that B will fail is 10−1 if A fails and 10−5 otherwise. The probability that C will fail is 10−1 if B fails and 10−5 otherwise. The 'Call Engineer' sign lights up if two or three parts fail. If only two parts have failed I can repair the machine myself but if all three parts have failed my attempts will only make matters worse. If the 'Call Engineer' sign lights up and I am willing to run a risk of no greater than 1 per cent of making matters worse, should I try to repair the machine, and why? Solution The final outcomes are A f B f C f, probability 10−5 × 10−1 × 10−1 = 10−7 A f B w C f, probability 10−5 × 9 · 10−1 × 10−5 = 9 · 10−11 A f B f C w, probability 10−5 × 10−1 × 9 · 10−1 = 9 · 10−7 A w B f C f, probability 1 − 10−5 × 10−5 × 10−1 = 1 − 10−5 · 10−6 So, 3 parts fail 2 or 3 fail = = = ≈ 3 fail 2 or 3 fail A B C f A B f C w + A C f B w + B C f A w + A B C f 9 · 10−7 + 9 × 10−11 10−7 + 1 − 10−5 · 10−6 + 10−7 1 10−7 1 > = 9 · 10−7 + 10−6 + 10−7 20 100 Thus, you should not attempt to mend the photocopier: the chances of making things worse are 1/20. 1.3 The exclusion–inclusion formula 1.3 27 The exclusion–inclusion formula. The ballot problem Natural selection is a mechanism for generating an exceedingly high degree of improbability. R.A. Fisher (1890–1962), British statistician The exclusion–inclusion formula helps to calculate the probability A, where A = A1 ∪ A2 ∪ · · · ∪ An is the union of a given collection of events A1 An . We know (see Section 1.2) that if events are pair-wise disjoint, Ai A = 1≤i≤n In general, the formula is more complicated: A = A1 + · · · + An − A1 ∩ A2 − A1 ∩ A3 − · · · − An−1 ∩ An + A1 ∩ A2 ∩ A3 + · · · + An−2 ∩ An−1 ∩ An + · · · + −1n+1 A1 ∩ · · · ∩ An n = −1k−1 ∩k1 Aij k=1 (1.12) 1≤i1 <···<ik ≤n The proof is reduced to a counting argument: on the left-hand side (LHS) we count each outcome from 1≤i≤n Ai once. But if we take the sum 1≤i≤n Ai then those outcomes that enter more than one event among A1 An will be counted more than once. Now if we subtract the sum 1≤i<j≤n Ai ∩ Aj we will count precisely once the outcomes that enter exactly two events A1 An , but will be in trouble with the outcomes that enter three or more events. Therefore we have to add 1≤i<j<k≤n Ai ∩ Aj ∩ Ak , and so on. A formal proof can be carried by induction in n. It is convenient to begin the induction with n = 2 (for n = 1 the formula is trivial). For two events A and B, A ∪ B coincides with A \ A ∩ B ∪ B \ A ∩ B ∪ A ∩ B, the union of non-intersecting events. Hence, A ∪ B can be written as A \ A ∩ B + B \ A ∩ B + A ∩ B = A − A ∩ B + B − A ∩ B + A ∩ B = A + B − A ∩ B The induction hypothesis is that the formula holds for any collection ofn or less events. Then for any collection A1 An+1 of n + 1 events, the probability ∪n+1 1 Ai equals: n n n A ∪ A = + ∩ A − A A A i n+1 i n+1 i n+1 1 1 1 = n −1k−1 k=1 1≤i1 < <ik ≤n n A A + − A ∩ A i n+1 i n+1 j 1 1 k 28 Discrete outcomes For the last term we have, again by the induction hypothesis: n n k A − Aij ∩ An+1 ∩ A −1k = i n+1 1 1 = k=1 1≤i1 < <ik ≤n n −1k k=1 k 1≤i1 < <ik ≤n ∩ A A i n+1 j 1 We see that the whole sum in the expansion for n+1 Ai includes all possible terms 1 identified on the RHS of formula (1.12) for n + 1, with correct signs. This completes the induction. An alternative proof (which is instructive as it shows relations between various concepts of probability theory) will be given in the next section, after we introduce random variables and expectations. The exclusion–inclusion formula is particularly efficient under assumptions of independence and symmetry. It also provides an interesting asymptotical insight into various probabilities. Example 1.1 An example of using the exclusion–inclusion formula is the following matching problem. An absent-minded person (some authors prefer talking about a secretary) has to put n personal letters in n addressed envelopes, and he does it at random. What is the probability pmn that exactly m letters will be put correctly in their envelopes? Verify the limit lim pmn = n→ 1 em! The solution is as follows. The set of outcomes consists of n! possible matchings of the letters to envelopes. Let Ak = letter k in correct envelope. Then Ai1 ∩ Ai2 ∩ · · · ∩ Air = and so n − r! n! n n − r! 1 = Ai1 ∩ Ai2 ∩ · · · ∩ Air = r n! r! i1 <i2 <···<ir Thus, at least one letter in the correct envelope n 1 1 1 = = 1 − + − · · · + −1n−1 A i=1 i 2! 3! n! and no letter in the correct envelope n 1 1 1 =1− = 1 − 1 + + + · · · + −1n A i i=1 2! 3! n! 1.3 The exclusion–inclusion formula 29 which tends to e−1 as n → . The number of outcomes in the event {no letter put in the correct envelope} equals = n!p0n , and so n n − m!p0 n − m Pmn = m n! Therefore, 1 1 1 1 pmn = p0 n − m = 1 − + · · · + −1n−m m! m! 1! n − m! which approaches e−1 /m! as n → . Problem 1.25 A total of n male psychologists remembered to attend a meeting about absentmindness. After the meeting, none could recognise his own hat so they took hats at random. Furthermore, each was liable, with probability p and independently of the others, to lose the hat on the way home. Assuming, optimistically, that all arrived home, find the probability that none had his own hat with him, and deduce that it is approximately e−1−p . Solution Set Aj ={psychologist j had his own hat}, then the event A ={none had his own hat} is the complement of symmetry: A = 1 − nA1 + 1≤j≤n Aj . By the exclusion–inclusion formula and the nn − 1 A1 ∩ A2 − · · · + −1n A1 ∩ · · · ∩ An 2 Next, n − 1! n! n − 2! A1 ∩ A2 = 1 − p2 n! 1 A1 ∩ · · · ∩ An = 1 − pn n! A1 = 1 − p Then A = 1 − 1 − p + 1 − p2 1 − pn − · · · + −1n 2! n! which is the partial sum of e−1−p . Problem 1.26 It is certain that at least one, but no more than two of the events A1 An occur. Given that A1 = p1 for all i, and Ai ∩ Aj = p2 for all i j i = j, show that nn − 1 1 = np1 − p2 2 Deduce that p1 ≥ 1/n and p2 ≤ 2/n. 30 Discrete outcomes Solution As Ai1 ∩ · · · ∩ Aik = 0 for k > 2, the exclusion–inclusion formula gives 1 = np1 − nn − 1p2 /2. Rearranging: p1 = 1 n−1 1 + p2 ≥ n 2 n as p2 ≥ 0. Finally, p2 = 2 1 2 1 2 p1 − ≤ 1− = n−1 n n−1 n n Problem 1.27 State the exclusion–inclusion formula for n i=1 Ai . A large and cheerful crowd of n junior wizards leave their staff in the Porter's Lodge on the way to a long night in the Mended Drum. On returning, each collects a staff at random from a pile, return to his room and attempts to cast a spell against hangovers. If a junior wizard attempts this spell with his own staff, there is a probability p that he will turn into a bullfrog. If he attempts it with someone else's staff, he is certain to turn into a bullfrog. Show that the probability that in the morning we will find n very surprised bullfrogs is approximately ep−1 . Solution Set Ai = Ai n = wizard i gets his own stuff. Then ∀r = 1 n and 1 ≤ i1 < < ir ≤ n: Ai1 ∩ Ai2 ∩ · · · ∩ Air = n − r! n! as there are n − r! ways of distributing the remaining stuff. So, by the exclusion–inclusion formula, the probability ni=1 Ai is equal to n n n n − r! 1 1 n = −1r−1 = 1 − −1r −1r−1 r n! r! r! r=1 r=1 r=0 which tends to 1 − e−1 as n → . We can also consider similar events Ai k defined for a given subset of k wizards, 1 ≤ k ≤ n. Further, if Pr k = precisely r out of given k get their own staff then 1 k k − r! P0 k − r = P0 k − r 0 ≤ r ≤ k Pr k = r k! r! Also: P0 k − r = 1 − ∪k−r i=1 Ai k − r = k−r −1i i=1 1 → e−1 i! −1 as k → . So, Pr k ≈ e /r! for k sufficiently large. Finally all turn into bullfrogs = n r=0 for n large enough. Pr npr ≈ n r=0 e−1 pr = e−1 ep = ep−1 r! 1.3 The exclusion–inclusion formula 31 n → ep−1 one needs an assertion guaranteeing that the term-wise convergence (in our case Pr npr → e−1 pr /r! ∀ r) implies the convergence of the sum of the series. For example, the following theorem will do: If an m → an ∀ n as m → and an m ≤ bn , where n bn < , then the sum Sm = n an m → S = n an . In fact, Pr npr = P0 n − rpr /r! ≤ pr /r! = br , and the series r≥0 pr /r! converges to ep for all p (i.e. r br < ). The remaining part of this section addresses the so-called ballot problem. Its original formulation is: a community of voters contains m conservatives and n anarchists voting for their respective candidates, where m ≥ n. What is the probability that in the process of counting the secret ballot papers the conservative candidate will never be behind the anarchist? This question has emerged in many situations (but, strangely, not in Cambridge University IA Mathematical Tripos papers so far). However, at the University of WalesSwansea it has been actively discussed, in the slightly modified form presented below. We start with a particular case m = n. A series of 2n drinks is on offer, n of them are gin and n tonic. In a popular local game, a blindfolded participant drinks all 2n glasses, one at a time, selected in a random order. The participant is declared a winner if the volume of gin drunk is always not more than that of tonic. We will check that this occurs with probability 1/n + 1. Consider a random walk on the set −n −n + 1 n where a particle moves one step up if a glass of tonic was selected and one down if it was gin. The walk begins at the origin (no drink consumed) and after 2n steps always comes back to it (the number of gins = the number of tonics). On Figure 1.2 that includes time, every path Xt of the walk begins at 0 0 and ends at 2n 0 and each time jumps up and to the right or down and to the right. We look for the probability that the path remains above the line X = −1. Remark To formally prove the convergence r=0 Pr np r x (1,1) +1 t (2n,0) –1 (1,–3) Figure 1.2 Discrete outcomes 32 The total number of paths from 0 0 to 2n 0 is 2n!/n!n!. The number of paths staying above the line is the same as the total number of paths from 1 1 to 2n 0 less the total number of paths from 1 −3 to 2n 0. In fact, the first step from 0 0 must be up. Next, if a path 0 0 to 2n 0 touches or crosses line X = −1, then we can reflect its initial bit and obtain a path from 1 −3 to 2n 0. This is sometimes called the reflection principle. Hence, the probability of winning is 2n − 1! 1 2n! nn − 1 1 2n − 1! − = n− = n!n − 1! n + 1!n − 2! n!n! 2n n+1 n+1 Now assume that the number m of tonics is > n, the number of gins. As before, winning the game means that at each time the number of consumed tonics is not less than that of gins. Then the total number of paths from 0 0 to m + n m − n equals m + n!/m!n!. Again, the first step of a winning path is always up. The total number of paths from 1 1 to m + n m − n equals m + n − 1!/m − 1!n!. Using the reflection principle, we see that the number of losing paths equals the total number of paths from 1 −3 to m + n m − n, which is m + n − 1!/m + 1!n − 2!. Finally, the winning probability is m + n − 1! m + n! m − n + 1 m + n − 1! − = m − 1!n! m + 1!n − 2! m!n! m+1 We apply these results to the following. Problem 1.28 n married couples have to cross from the left to the right bank of a river via a narrow bridge, one by one. They decided that at any time on the left bank the number of men should be no less than that of women; apart from this the order can be arbitrary. Find the probability that every man will cross the river after his own wife. Solution Set A = every man crosses after his own wife B = at all times, the # of men on the left bank ≥ that of women Then PA B = PA ∩ B/PB = PA/PB = n+1 2n We conclude this section with another story about Kolmogorov. He began his academic studies as a historian, and at the age of 19 finished a work focused on the principles of distribution and taxation of arable land in fifteenth and sixteenth century Novgorod, an ancient Russian state (a principality and a republic at different periods of its existence, fully or partially independent, until it was annexed by Moscow in 1478). In this work, he used mathematical arguments to answer the following question: was it (i) a village that 1.4 Random variables 33 was taxed in the first place, and then the tax was divided between households, or (ii) the other way around, where it was a household that was originally taxed, and then the sum represented the total to be paid by the village? The sources were ancient cadastres and other official manuscripts of the period. Because the totals received from the villages were always an integer number of (changing) monetary units, Kolmogorov proved that it was rule (ii) that was adopted. Kolmogorov reported his findings at a history seminar at Moscow University in 1922. However, the head of the seminar, a well-known professor (a street in Moscow was later named after him) commented that the conclusions of his young colleague could not be considered final, because 'in history, every statement must be supported by several proofs'. Kolmogorov then decided to move to a discipline where 'a single proof would be sufficient for a statement to be considered correct', i.e. mathematics. 1.4 Random variables. Expectation and conditional expectation. Joint distributions He who has heard the same thing told by 12 000 eye-witnesses has only 12 000 probabilities, which are equal to one strong probability, which is far from certain. F.M.A. Voltaire (1694–1778), French philosopher This section is considerably larger than the previous ones: the wealth of problems generated here is such that getting through it allows a student to secure in principle at least the first third of the Cambridge University IA Probability course. The definition of a random variable (RV) is that it is a function X on the total set of outcomes , usually with real, sometimes with complex values, X ∈ (in the complex case we may consider a pair formed by the real and imaginary parts of X). A simple (and important) example of an RV is the indicator function of an event: 1 if ∈ A ∈ → I ∈ A = (1.13) 0 if ∈ A It is obvious that the product I ∈ A1 I ∈ A2 equals 1 iff ∈ A1 ∩ A2 , i.e. I ∈ A1 I ∈ A2 = I ∈ A1 ∩ A2 On the other hand, I ∈ A1 ∪ A2 = I ∈ A1 + I ∈ A2 − I ∈ A1 I ∈ A2 In the case of finitely many outcomes, every RV is a finite linear combination of indicator functions; if there are countably many outcomes, then infinite combinations will be needed. The expected value (or the expectation, or the mean value, or simply the mean) of a RV X taking values x1 xm with probabilities p1 pm is defined as the sum X = p i xi = xi X = xi (1.14) 1≤i≤m 1≤i≤m 34 in the Discrete outcomes -notation: X = p X (1.15) ∈ If X ≡ b is a constant RV, then X = b. This definition is meaningful also for RVs taking countably many values x1 , x2 with probabilities p1 , p2 : X = pi xi i provided that the series converges absolutely: i pi xi < . If i pi xi = , one says that X does not have a finite expected value. In many applications, it is helpful to treat the expected value X as the position of the centre of mass for the system of massive points x1 , x2 with masses p1 , p2 . The first (and a very useful) observation is that the expected value of the indicator IA = I ∈ A of an event equals the probability: IA = p I ∈ A = p = A (1.16) ∈A ∈ Furthermore, if RVs X, Y have X ≤ Y , then X ≤ Y . Next, the expectation of a linear combination of RVs equals the linear combination of expectations. The shortest proof is in the -notation: c1 X1 + c2 X2 = p c1 X1 + c2 X2 = c1 p X1 + c2 p X2 = c1 X1 + c2 X2 This fact (called the linearity of the expectation) can be easily extended to n summands: ck Xk = ck Xk 1≤k≤n 1≤k≤n in particular if Xk = for every k, then 1≤k≤n Xk = n. A similar property also holds for an infinite sequence of RVs X1 , X2 : ck Xk = ck Xk (1.17) k k provided that the series on the RHS converges absolutely: k ck Xk < . (The precise statement is that if k ck Xk < , then the series k≥1 ck Xk defines an RV with a finite mean equal to the sum k≥1 ck Xk .) Also, for a given function g → gX = p gX = pi gxi (1.18) ∈ i 1.4 Random variables 35 provided that the sum i pi gxi < . In fact, writing Y = gX and denoting the values of Y by y1 , y2 , we have Y = yj PgX = yj = j j yj Igxi = yj X = xi i which is simply i pi gxi under the condition that i pi gxi < , as we then can do summation by grouping terms. Remark Formula (1.18) is a discrete version of what is known as the Law of the Unconscious Statistician. See equation (2.69). Given two RVs, X and Y , with values X and Y , we can consider events X = xi Y = yj (shortly, X = xi Y = yj ) for any pair of their values xi , yj . The probabilities X = xi Y = yj will specify the joint distribution of the pair X, Y . The 'marginal' probabilities X = xi and Y = yj are obtained by summation over all possible values of the complementary RV: X = xi = X = xi Y = yj y (1.19) j Y = yj = X = xi Y = yj xi We can also consider the conditional probabilities X = xi Y = yj = X = xi Y = yj Y = yj (1.20) Similar concepts are applicable in the case of several RVs X1 , Xn . For example, for the sum X + Y of RVs X and Y with joint probabilities X = xi Y = yj : X + Y = u = X = xi Y = yj xi yj xi +yj =u = X = x Y = u − x x = X = u − y Y = y (1.21) y Similarly, for the product XY : XY = u = X = xi Y = yj xi yj xi yj =u = X = x Y = u/x x = y X = u/y Y = y (1.22) Discrete outcomes 36 A powerful tool is the formula of conditional expectation: if X and N are two RVs then X = X N (1.23) Here, on the RHS, the external expectation is relative to the probabilities N = nj with which RV N takes its values nj : X N = N = nj X N = nj j The internal expectation is relative to the conditional probabilities X = xi N = nj of values xi of RV X, given that N = nj : X N = nj = xi X = xi N = nj i To prove formula (1.23), we simply substitute and use the definition of the conditional probability: X N = N = nj xi X = xi N = nj j = i xi X = xi N = nj = xi X = xi = X xi nj xi We see that formula (1.23) is merely a paraphrase of (2.6). We will say again that it is the result of conditioning by RV N . A handy formula is that for N with non-negative integer values (1.24) N = N ≥ n n≥1 In fact, N ≥ n = n≥1 N = k = n≥1 k≥n = N = k k≥1 1 1≤n≤k N = kk = N k≥1 Of course, in formula (1.23) the rôles of X and N can be swapped. For example, in Problem 1.17, the expected duration of the game is N = N X = 12 pi N X = i i=2 where X is the combined outcome of the first throw, and pi = X = i. We have: N X = i = 1 i + 2 3 7 11 12 1 N X = i = 1 + i = 4 5 6 8 9 10 pi + p 7 Substituting the values of pi we get N = 557/165 ≈ 338. 1.4 Random variables 37 Further, we say that RVs X and Y with values xi and yj are independent if for any pair of values X = xi Y = yj = X = xi Y = yj (1.25) For a triple of variables X, Y , Z, we require that for any triple of values X = xi Y = yj Z = zk = X = xi Y = yj Z = zk . This definition is extended to the case of any number of RVs X1 , Xn : ∀ x1 , xn : X1 = x1 X2 = x2 Xn = xn = n Xi = xi (1.26) i=1 Furthermore, an infinite sequence of RVs X1 X2 is called independent if ∀n the variables X1 Xn are independent. One may ask here why it suffices to consider in equation (1.26) the 'full' product n while in the definition of independent events it was carefully stated that ∩Aik = i=1 Aik for any subcollection (see equation (1.10)). The answer is: because we require it for any collection of values x1 , xn of our RVs X1 Xn . In fact, when some of the RVs are omitted, we should take the summation over their values, viz. X2 = x2 Xn = xn = X1 = x1 X2 = x2 Xn = xn x1 as the events X1 = x1 Xn−1 = xn−1 Xn = xn are pair-wise disjoint for different x1 s, and partition the event X2 = x2 Xn = xn . So, if X1 = x1 Xn = xn = n Xi = xi i=1 then X2 = x2 Xn = xn = X1 = x1 X2 = x2 Xn = xn x1 = X2 = x2 Xn = xn i.e. the subcollection X2 Xn is automatically independent. However, the inverse is not true. For instance, if each of X Y , X Z and Y Z is a pair of independent RVs, it does not necessarily mean that the triple X Y Z is independent. An example is produced from Problem 1.21: you simply take IA1 , IA2 and IA3 from the solution. An important concept that now emerges and will be employed throughout the rest of this volume is a sequence of independent, identically distributed (IID) RVs X1 , X2 . Here, in addition to the independence, it is assumed that the probability Xi = x is the same for each i = 1 2 . A good model here is coin-tossing: Xn may be a function of the result of the nth tossing, viz. 1 if the nth toss produces a head Xn = Inth toss a head = 0 if the nth toss produces a tail 38 Discrete outcomes More generally, you could divide trials into disjoint 'blocks' of some given length l and think of Xn as a function of the outcomes in the nth block. An immediate consequence of the definition is that for independent RVs X, Y , the expected value of the product equals the product of the expected values: XY = xi yj X = xi Y = yj xi yj = xi yj X = xi Y = yj xi yj = xi X = xi xi yj Y = yj = XY (1.27) yj However, the inverse assertion is not true: there are RVs with XY = XY which are not independent. A simple example is the following. Example 1.2 ⎧ 1 ⎪ ⎪ −1 probability , ⎪ ⎪ ⎪ 3 ⎨ 1 X = 0 probability , ⎪ 3 ⎪ ⎪ ⎪ 1 ⎪ ⎩1 probability , 3 2 Y = − + X2 3 Here, 2 X = 0 Y = 0 XY = − X + X 3 = 0 3 But, obviously, X and Y are dependent. On the other hand, it is impossible to construct an example of dependent RVs X and Y taking two values each such that XY = XY . In fact, let X Y = 0 1, with X = Y = 0 = w PX = 1 Y = 0 = x X = 0 Y = 1 = y PX = Y = 1 = z Here X = 0 = w + y Y = 0 = w + x X = 1 = x + z PY = 1 = y + z and independence occurs iff z = x + zy + z. Next, XY = z XY = x + zy + z and XY = XY iff z = x + zy + z. 1.4 Random variables 39 The variance of RV X with real values and mean X = is defined as Var X = X − 2 (1.28) by expanding the square and using linearity of expectation and the fact that the expected value of a constant equals this constant we have Var X = X 2 − 2X + 2 = X 2 − 2X + 2 = X 2 − 22 + 2 = X 2 − X2 (1.29) In particular, if X is a constant RV: X ≡ b then Var X = b2 − b2 = 0. The variance √ is considered as a measure of 'deviation' of RV X from its mean. (The square root Var X is called the standard deviation.) From the first definition we see that Var X ≥ 0, i.e. X2 ≤ X 2 . This is a particular case of the so-called Cauchy–Schwarz (CS) inequality XY 2 ≤ X 2 Y 2 (1.30) valid for any pair of real or complex RVs X and Y , with Y standing for the complex conjugation. (This inequality implies that if X 2 and Y 2 have finite expected values then XY also has a finite expected value.) The CS inequality is named after two famous mathematicians: the Frenchman A.-L. Cauchy (1789–1857) who is credited with its discovery in the discrete case and the German H.A. Schwarz (1843–1921) who proposed it in the continuous case. The proof of the CS inequality provides an elegant algebraic exercise (and digression); for simplicity, we will conduct it for real RVs. Observe that ∀ ∈ , the RV X + Y 2 is ≥ 0 and hence has X + Y 2 ≥ 0. As a function of it gives an expression X + Y 2 = X 2 + 2XY + 2 Y 2 which is a quadratic polynomial. To be ≥ 0 for ∀ ∈ , it must have a non-positive discriminant, i.e. 2 4 XY ≤ 4X 2 Y 2 A concept closely related to the variance is the covariance of two RVs X Y defined as Cov X Y = X − XY − Y = XY − XY (1.31) By the CS inequality, Cov X Y 2 ≤ Var X Var Y . For independent variables, Cov X Y = 0. Again, the inverse assertion does not hold: there are non-independent variables X Y for which Cov X Y = 0. See Example 1.2. However, as we checked before, if X and Y take two values (or one) and Cov X Y = 0, they will be independent. RVs with Cov X Y = 0 are called uncorrelated. Discrete outcomes 40 For the variance Var X + Y of the sum X + Y we have the following representation: Var X + Y = Var X + Var Y + 2Cov X Y (1.32) In fact, Var X + Y equals 2 X − X + Y − Y 2 2 = X − X + 2 X − X Y − Y + Y − Y which is the RHS of equation (1.32). An important corollary is that the variance of the sum of independent variables equals the sum of the variances: Var X + Y = Var X + Var Y This fact is easily extended to any number of independent summands: Var X1 + · · · + Xn = Var X1 + · · · + Var Xn (1.33) In the case of IID RVs, Var Xi does not depend on i, and if Var Xi = 2 (a standard 2 probabilistic notation) then Var 1≤j≤n Xj = n . On the other hand, if c is a real constant then Var cX = cX2 − cX2 = c2 X 2 − X2 = c2 Var X. Hence, Var nX = n2 Var X. That is summing identical RVs produces a quadratic growth in the variance, whereas summing IID RVs produces only a linear one. At the level of mean values both options give the same (linear) growth. A constant RV taking a single value (X ≡ b) is independent of any other RV (and group of RVs). Therefore, Var X + b = Var X + Var b = Var X. Summarising, for independent RVs X1 X2 and real coefficients c1 c2 , Var ci Xi = ci2 Var Xi i i provided that the series in the RHS converges absolutely. More precisely, if , then the series i ci Xi defines an RV with finite variance i ci2 Var Xi . Finally, formulas (1.21), (1.22) in the case of independent RVs become X + Y = u = X = u − yY = y 2 i ci Var Xi < y = X = xY = u − x (1.34) y and XY = u = X = u/yY = y y = X = xY = u/x x Equation (1.34) is often referred to as the convolution formula. (1.35) 1.4 Random variables 41 Remark There is variation in the notation: many authors write X , Var X and/or Var X. As we usually follow the style of the Tripos questions, such notation will also occasionally appear in our text. Concluding this section, we give an alternative proof of the exclusion–inclusion for mula (1.12) for probability A of a union A = 1≤i≤n Ai . By using the indicators IAi of events Ai , the formula becomes −1k+1 IAi IAi IA = 1≤k≤n 1≤i1 < <ik ≤n 1 k Given an outcome ∈ 1≤i≤n Ai , let Aj1 Ajs be the list of events containing ∈ Aj1 ∩ · · · ∩ Ajs and ∈ Aj ∀ Aj not in the list. Without loss of generality, assume that j1 js = 1 s; otherwise relabel events accordingly. Then for this the RHS must contain terms IAi IAi with 1 ≤ k ≤ s and 1 ≤ i1 < < ik ≤ s only. More 1 k precisely we want to check that −1k+1 IAi IAi 1 = I∪1≤i≤n Ai = 1≤k≤s But the RHS is k+1 −1 1≤k≤s 1≤i1 < <ik ≤s 1 k s s k −1 = 1 − 1 − 1s = 1 =1− 1+ k k 1≤k≤s Taking the expectation yields the result. Problem 1.29 I arrive home from a feast and attempt to open my front door with one of the three keys in my pocket. (You may assume that exactly one key will open the door and that if I use it I will be successful.) Find the expected number a of tries that I will need if I take the keys at random from my pocket but drop any key that fails onto the ground. Find the expected number b of tries that I will need if I take the keys at random from my pocket and immediately put back into my pocket any key that fails. Find a and b and check that b − a = 1. Solution Label the keys 1, 2 and 3 and assume that keys 2 and 3 are wrong. Consider the following cases (i) the first chosen key is right, (ii) the second key is right, and (iii) the third key is right. Then for a we have 1 1 1 1 1 × 1 + 2 × × × 2 + 2 × × × 3 = 2 a= 3 3 2 3 2 For b, use conditioning by the result of the first attempt: b= 2 1 × 1 + × 1 + b whence b = 3 3 3 Here factor 1 + b reflects the fact that when the first attempt fails, we spend one try, and the problem starts again, by independence. 42 Discrete outcomes Remark The equation for b is similar to earlier equations for probabilities q and qi ; see Problems 1.17 and 1.18. Problem 1.30 Let N be a non-negative integer-valued RV with mean 1 and variance 12 , and X1 X2 be identically distributed RVs with mean 2 and variance 22 furthermore, assume that N X1 X2 are independent. Calculate the mean and variance of the RV SN = X1 + X2 + · · · + XN . Solution 1 By conditioning, N n Xi SN = SN N = N = n n=0 = N i=1 N = n n2 = 1 2 n=0 Next, SN2 2 N n 2 = SN N = N = n Xi = N ⎡ N = n ⎣Var n=0 = N n=0 i=1 n Xi + i=1 n 2 ⎤ Xi ⎦ i=1 N = n n22 + n2 2 n=0 = 1 22 + 22 N 2 = 1 22 + 22 21 + 12 Therefore, Var SN = SN2 − SN 2 = 1 22 + 22 12 Solution 2 (Look at this solution after you have learnt about probability generating functions in Section 1.5.) Write s = sSn = ghs where hs = sX1 gs = sN . Differentiating yields s = g hsh s, and so SN = 1 = g h1h 1 = g 1h 1 = 1 2 Further, s = g hsh s2 + g hsh 1 and so SN SN − 1 = 1 = g 1h 12 + g 1h 1 and Var SN = 1 + 1 − 12 = 1 22 + 22 12 1.4 Random variables 43 Problem 1.31 Define the variance Var X of a random variable X and the covariance Cov X Y of the pair X Y . Let X1 X2 Xn be random variables. Show that Var X1 + X2 + · · · + Xn = n Cov Xi Xj ij=1 Ten people sit in a circle, and each tosses a fair coin. Let N be the number of people whose coin shows the same side as both of the coins tossed by the two neighbouring people. Find N = 9 and N = 10. By representing N as a sum of random variables, or otherwise, find the mean and variance of N . Solution Let Yi = Xi − Xi . Then Var n i=1 Xi 2 n n n Yi = Yi Yj = Yi Yj = i=1 ij=1 ij=1 But Yi Yj = Cov Xi Xj , hence the result. Next observe that N = 9 = 0. Indeed, you can't have nine people out of ten in agreement with their neighbours and just one person in disagreement, as his neighbours must quote him. Further, N = 10 = 2 × 1/210 : there are two ways to fix the side, and 1/210 is the probability that all ten coins show this particular side. Finally, write N = IA1 + · · · + IAn , where IAi is the indicator of the event Ai = ith person has two neighbours with the same side showing By symmetry, N = 10A1 = 10 × 1 = 25 4 Further, RVs IAi IAj are pair-wise independent if i is not next to j. In fact, when i and j do not have a common neighbour, this is obvious, as each RV depends on disjoint collection of independent trials. Next, assume that i and j have a (single) common neighbour. Then IAi = 1 IAj = 1 = 1 1 1 + = 32 32 16 At the same time, 1 IAi = 1 = IAj = 1 = 4 Thus, Var N = 10 Var IA1 + 20 Cov IA1 IA2 2 1 1 1 + 20 IA1 IA2 − − = 10 4 4 16 44 Discrete outcomes Further, IA1 IA2 = IA1 = 1 IA2 = 1IA2 = 1 = Thus, Var N = 10 × 1 1 1 × = 2 4 8 1 1 3 + 20 − = 3125 16 8 16 Problem 1.32 X1 Xn are independent, identically distributed RVs with mean and variance 2 . Find the mean of n n 1 S = Xi − X2 where X = X n 1 i i=1 Solution First, consider the mean value and the variance of X: n n 1 1 1 Xi = · n = X = Xi = n i=1 n i=1 n and Var X = Next, S = n 1 2 Var Xi = 2 n i=1 n n Xi2 − 2X n i=1 = n Xi + nX 2 = i=1 xi2 − nX i=1 2 = n Xi2 2 − 2nX + nX 2 i=1 n Xi2 − nX 2 i=1 = n + − n X2 + Var X 2 2 = n2 + 2 − n2 + 2 = 2 n − 1 n Problem 1.33 Xk is a sequence of independent identically distributed positive RVs, where Xk = a and Xk−1 = b exist. Let Sn = ni=1 Xk . Show that Sm /Sn = m/n if m ≤ n, and Sm /Sn = 1 + m − na Sn−1 if m > n. Solution For m ≤ n write Sm Sn But for m = n: m X + · · · + Xm = = 1 Sn i=1 X1 Sn Hence Sm Sn = m n. 1 = n Xi Sn = m X1 Sn 1.4 Random variables 45 For m > n, n m Xj Sm Sn 1 = + =1+ Xj Sn Sn S S n j=m+1 n j=n+1 1 = 1 + m − na Sn The mean value 1/Sn is finite (and is ≤ b) since 1/Sn ≤ 1/X1 . It is important to stress that Sn and Sm are not independent. Problem 1.34 Suppose that X and Y are independent real random variables with X Y ≤ K for some constant K. If Z = XY show that the variance of Z is given by Var Z = Var XVar Y + Var YX2 + Var XY 2 stating the properties of expectation that you use. Solution Write Var XY = XY 2 − XY 2 = X 2 Y 2 − X2 Y 2 and continue = Var X + X2 Var Y + Y 2 − X2 Y 2 = Var XVar Y + X2 Var Y + Y 2 Var X The facts used are: linearity of expectation, the equations Z = XY and Z2 = X 2 Y 2 that hold due to independence, and finiteness of all mean values because of the boundedness of random variables X and Y . Problem 1.35 Let a1 a2 an be yearly rainfalls in Cambridge over the past n years: assume a1 a2 an are IID RVs. Say that k is a record year if ak > ai for all i < k (thus the first-year is always a record year). Let Yi = 1 if i is a record year and 0 otherwise. Find the distribution of Yi and show that Y1 Y2 Yn are independent. Calculate the mean and variance of the number of record years in the next n years. Set N = j if j is the first record year after year 1 1 ≤ j < n, and N = n if a1 or an are maximal among a1 an (i.e. the first or the last year produced the absolute record). Show that N → as n → . Solution Ranking the ai s in a non-increasing order generates a random permutation of 1 2 n; by symmetry, all such permutations will be equiprobable. Ranking the first i rainfalls yields a random permutation of 1 2 i. Hence, 1 i−1 1 1 1 Yi = Var Yi = − 2 Yi = 1 = Yi = 0 = i i i i i Observe that RVs Y1 Yn are independent. In fact, set Xi = the ranking of year i among 1 i Discrete outcomes 46 with 1 Xi = l = 1 ≤ l ≤ i i Then Yi is a function of Xi only. So, it is enough to check that the Xi are independent. In fact, for any collection of pair-wise distinct values li i = 1 n, with li ≤ i, the event Xi = li 1 ≤ i ≤ n is realised for a unique permutation out of n!. Thus, 1 = Xi = xi 1 ≤ i ≤ n = Xi = xi n! 1≤i≤n Next, n 1 and Yi = n 1 1 i n n n 1 1 Var − 2 Yi = Var Yi = i i 1 i=1 1 Finally, for m = 2 n, the probability N ≥ m equals 2 m − 1 are not records = 1 × 1 2 m−2 1 × ···× = 2 3 m−1 m−1 Hence, N ≥ nm=2 1/m − 1 which tends to as n → . Observe, however, that with probability 1 there will be infinitely many record years if observations are continued indefinitely. Problem 1.36 An expedition is sent to the Himalayas with the objective of catching a pair of wild yaks for breeding. Assume yaks are loners and roam about the Himalayas at random. The probability p ∈ 0 1 that a given trapped yak is male is independent of prior outcomes. Let N be the number of yaks that must be caught until a pair is obtained. (i) Show that the expected value of N is 1 + p/q + q/p, where q = 1 − p. (ii) Find the variance