Mathematics for Computer Science
19.2. Chebyshev’s Theorem 793 Definition 19.2.2.Thevariance, VarŒRç, of a random variable,R, is: VarŒRçWWDEx .RExŒRç/^2 : Va ...
Chapter 19 Deviation from the Mean794 We can compute the VarŒAçby working “from the inside out” as follows: AExŒAç D 1 with pr ...
19.2. Chebyshev’s Theorem 795 mean O.¢/ Figure 19.1 The standard deviation of a distribution indicates how wide the “main part” ...
Chapter 19 Deviation from the Mean796 The IQ Example Suppose that, in addition to the national average IQ being 100, we also kno ...
19.3. Properties of Variance 797 Here we use the notation Ex^2 ŒRças shorthand for.ExŒRç/^2. Proof. LetDExŒRç. Then VarŒRçDExŒ. ...
Chapter 19 Deviation from the Mean798 .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 ç ...
19.3. Properties of Variance 799 It’s even simpler to prove that adding a constant does not change the variance, as the reader ...
Chapter 19 Deviation from the Mean800 sinceRandSare independent: ExŒ.RCS/^2 çDExŒR^2 C2RSCS^2 ç DExŒR^2 çC 2 ExŒRSçCExŒS^2 ç DEx ...
19.4. Estimation by Random Sampling 801 19.4.1 A Voter Poll Suppose at some time before the election thatpwas the fraction of vo ...
Chapter 19 Deviation from the Mean802 gives VarŒSnçDn.p.1p//n 1 4 D n 4 : (19.18) Next, we bound the variance ofSn=n: Var Sn ...
19.4. Estimation by Random Sampling 803 calculate the expected number of pairs of students with matching birthdays. Then we can ...
Chapter 19 Deviation from the Mean804 In particular, for a class ofnD 95 students withdD 365 possible birthdays, we have ExŒMç1 ...
19.4. Estimation by Random Sampling 805 divided byn: Var Sn n D 1 n 2 VarŒSnç (Square Multiple Rule for Variance (19.9)) ...
Chapter 19 Deviation from the Mean806 19.5 Confidence versus Probability So Chebyshev’s Bound implies that sampling 3,125 voters ...
19.6. Sums of Random Variables 807 So confidence levels refer to the results of estimation procedures for real-world quantities. ...
Chapter 19 Deviation from the Mean808 randomly assigned posts to computers. Imagine their surprise when the system stayed up and ...
19.6. Sums of Random Variables 809 whereˇ.c/WWDclnccC 1. The Chernoff bound applies only to distributions of sums of independent ...
Chapter 19 Deviation from the Mean810 which is an inconceivably small number. Alternatively, the bound also becomes stronger for ...
19.6. Sums of Random Variables 811 19.6.5 Randomized Load Balancing Now let’s return to Fussbook and its load balancing problem. ...
Chapter 19 Deviation from the Mean812 that the first server is overloaded, by the Union Bound in Section 16.5.2. So PrŒsome serv ...
«
36
37
38
39
40
41
42
43
44
45
»
Free download pdf