Random Variables random variable X X indicates the evenness a function defined over the sample space X:→R event“X=x” PrX=x =Pr({s∈2|X(s)=x})
X indicates the evenness 0 1 random variable X a function defined over the sample space X : R event “X=x ” Pr[X = x] = Pr ({s | X(s) = x}) Random Variables
Expectation Definition: The expectation of a discrete random variable X is EX]=∑x·Pr[X= ℃ where the sum is over all values x in the range of X. Linearity of expectations: 区e刘-店E E i=1 Works for arbitrary dependency!
Expectation Definition: The expectation of a discrete random variable X is where the sum is over all values x in the range of X. E[X] = x x · Pr[X = x] Linearity of expectations: E ⇤ n i=1 aiXi ⇥ = ⇤ n i=1 ai · E[Xi]. Works for arbitrary dependency!
Linearity of Expectations “pr0of A monkey randomly types in 1 billion letters. Expected number of "proof's. Xi indicates a "proof'started at position i linearity indicator counter 109-4 109-4 E = EX]=(109-4)Pr(“proof")= 109-4 ≈84 265 i=1
“proof” A monkey randomly types in 1 billion letters. Expected number of “proof”s. Xi indicates a “proof” started at position i linearity + indicator 㱺 counter Linearity of Expectations E 10 94 i=1 Xi = 10 94 i=1 E[Xi] = (109 4) Pr(“proof”) = 109 4 265 84
Coin Flipping flip a biased coin: distribution of one flipping Bernoulli of flips until HEADs occurs geometric ●#of HEADs in n flips binomial
Coin Flipping flip a biased coin: • distribution of one flipping • # of flips until HEADs occurs • # of HEADs in n flips Bernoulli geometric binomial
Geometric distribution (hitting time) of coin flips until a HEAD occurs. Run i.i.d.Bernoulli trials until succeeded. K (Independently and Identically Distributed) X is the number of trials coin flips. Pr[X=对=(1-p)k-1p X follows the geometric distribution with parameter p
Geometric distribution (hitting time) • Run i.i.d. Bernoulli trials until succeeded. • X is the number of trials / coin flips. X follows the geometric distribution with parameter p. (Independently and Identically Distributed) Pr[X = k] = (1 p) k1p # of coin flips until a HEAD occurs