Mathematics for Computer Science
18.6. Confidence versus Probability 633 This is enough to apply Chebyshev’s Theorem and conclude: Pr ˇˇ ˇ ˇ Sn n ˇˇ ˇ ˇx ...
Chapter 18 Deviation from the Mean634 Now suppose a pollster actually takes a sample of 3,125 random voters to esti- mate the fr ...
18.7. Sums of Random Variables 635 more —for example, that the random variable has a binomial distribution —and then it is possi ...
Chapter 18 Deviation from the Mean636 load balance. But how many is enough? 11? 15? 20? 100? We’ll answer that question with a n ...
18.7. Sums of Random Variables 637 expectation by 20% or more? LetTibe an indicator variable for the event that the ith coin is ...
Chapter 18 Deviation from the Mean638 $5 million of the $10 million paid for tickets. The lottery operator’s nightmare is that t ...
18.7. Sums of Random Variables 639 and otherwiseTiis the length of the task. SoT D Pn iD 1 Tiis the total length of tasks assign ...
Chapter 18 Deviation from the Mean640 18.7.5 Proof of the Chernoff Bound The proof of the Chernoff bound is somewhat involved. H ...
18.7. Sums of Random Variables 641 Proof. Ex h cT i DEx h cT^1 CCTn i (def ofT) DEx h cT^1 cTn i DEx h cT^1 i ExŒcTnç ( ...
Chapter 18 Deviation from the Mean642 18.7.6 Comparing the Bounds Suppose that we have a collection of mutually independent even ...
18.7. Sums of Random Variables 643 In this case, the probability of exceeding the mean bycExŒTçdecreases as an exponentially sma ...
Chapter 18 Deviation from the Mean644 For example, given any set of mutually independent events, if you expect 10 of them to hap ...
18.8. Really Great Expectations 645 you’ve won, and I’ll pay you generously —how does 25 cents sound? Maybe you’d rather have $1 ...
Chapter 18 Deviation from the Mean646 Suppose you had the good fortune to gamble against a fair roulette wheel. Then whatever yo ...
18.8. Really Great Expectations 647 So sure enough, ExŒCçWWDExŒ X i 2 ZC CiçD10: (18.25) But since ExŒCiçD 0 , X i 2 ZC ExŒCiçD ...
Chapter 18 Deviation from the Mean648 By Total Expectation, ExŒLçD X i 2 ZC ExŒLj1st red inith spinçPrŒ1st red inith spinç D X ...
18.8. Really Great Expectations 649 (b)What value ofb 0 in part (a) gives the best bound? Problems for Section 18.4 Practice Pr ...
Chapter 18 Deviation from the Mean650 (d)What actually is PrŒH > a=pç‹ Conclude that for any fixedp > 0, the probability t ...
18.8. Really Great Expectations 651 Homework Problems Problem 18.7. There is a “one-sided” version of Chebyshev’s bound for devi ...
Chapter 18 Deviation from the Mean652 The probability that some voter is chosen more than once in the sequence goes to zero asn ...
«
26
27
28
29
30
31
32
33
34
35
»
Free download pdf
