Mathematics for Computer Science
17.5. Linearity of Expectation 613 (a)What is the expected number of true propositions? Hint:LetTibe an indicator for the event ...
Chapter 17 Random Variables614 H H T T D D D Figure 17.8 Sample space tree for coin toss until two consective heads. (b)Suppose ...
17.5. Linearity of Expectation 615 Proof. ExŒR 1 R 2 ç D X r 2 range.R 1 R 2 / rPrŒR 1 R 2 Drç D X ri 2 range.Ri/ r 1 r 2 P ...
Chapter 17 Random Variables616 Homework Problems Problem 17.17. A coin will be flipped repeatedly until the sequence tail/tail/h ...
18 Deviation from the Mean 18.1 Why the Mean? In the previous chapter we took it for granted that expectation is important, and ...
Chapter 18 Deviation from the Mean618 18.2 Markov’s Theorem Markov’s theorem gives a generally coarse estimate of the probabilit ...
18.2. Markov’s Theorem 619 Our focus is deviation from the mean, so it’s useful to rephrase Markov’s Theo- rem this way: Corolla ...
Chapter 18 Deviation from the Mean620 18.2.2 Markov’s Theorem for Bounded Variables Suppose we learn that the average IQ among M ...
18.3. Chebyshev’s Theorem 621 Rephrasing (18.3.1) in terms of the random variable,jRExŒRçj, that measures R’s deviation from its ...
Chapter 18 Deviation from the Mean622 The expected payoff is the same for both games, but they are obviously very different! Thi ...
18.3. Chebyshev’s Theorem 623 mean O.¢/ Figure 18.1 The standard deviation of a distribution indicates how wide the “main part” ...
Chapter 18 Deviation from the Mean624 Here we see explicitly how the “likely” values ofRare clustered in anO.R/- sized region a ...
18.4. Properties of Variance 625 Proof. LetDExŒRç. Then VarŒRçDExŒ.RExŒRç/^2 ç (Def 18.3.2 of variance) DExŒ.R/^2 ç (def of) ...
Chapter 18 Deviation from the Mean626 .CC1/^2. So ExŒC^2 çDp 12 C.1p/ExŒ.CC1/^2 ç DpC.1p/ ExŒC^2 çC 2 p C 1 DpC.1p/ExŒC^2 ç ...
18.4. Properties of Variance 627 It’s even simpler to prove that adding a constant does not change the variance, as the reader ...
Chapter 18 Deviation from the Mean628 An independence condition is necessary. If we ignored independence, then we would conclu ...
18.5. Estimation by Random Sampling 629 Now to estimatep, we take a large number,n, of random choices of voters^2 and count the ...
Chapter 18 Deviation from the Mean630 Next, we bound the variance ofSn=n: Var Sn n D 1 n 2 VarŒSnç (by (18.9)) 1 n ...
18.5. Estimation by Random Sampling 631 Unlike the situation with voter preferences, having matching birthdays for dif- ferent p ...
Chapter 18 Deviation from the Mean632 18.5.3 Pairwise Independent Sampling The reasoning we used above to analyze voter polling ...
«
26
27
28
29
30
31
32
33
34
35
»
Free download pdf
