Variance of sum Theorem: For independent X and Y,Cov(X,Y)=0. Theorem: For pairwise independent X1,X2,...,Xn, n n Var ∑Var[Xl. 1 i=1
Variance of sum Theorem: For independent X and Y , Cov(X,Y ) = 0. Theorem: For pairwise independent X1,X2,...,Xn, Var ⇤ n i=1 Xi ⇥ = ⇤ n i=1 Var[Xi]
Variance of Binomial Distribution Binomial distribution:number of successes in n i.i.d.Bernoulli trials. .X follows binomial distribution with parameter n and p n X=∑X, with probability p i=l with probabir Var[Xi]E[X?]-E[Xi]2=p-p2=p(1-p) Var[X]=>Var[Xil=p(1-p)n (independence) i=1
Variance of Binomial Distribution • Binomial distribution: number of successes in n i.i.d. Bernoulli trials. • X follows binomial distribution with parameter n and p Xi = 1 with probability p 0 with probability 1 p X = n i=1 Xi Var[Xi] = E[X2 i ]E[Xi] 2 = p p2 = p(1 p) Var[X] = n i=1 Var[Xi] = p(1 p)n (independence)
Chebyshev's Inequality Chebyshev's Inequality: For any t >0, Var[X] Pr[IX-E[X]川≥t]≤ t2 Proof: Apply Markov's inequality to (X-E[X])2 Pr[(X-E[X)2≥t2]≤ E[(X-E[X)2] 2
Chebyshev’s Inequality Chebyshev’s Inequality: Pr[|X ⇥E[X]| ⌅ t] ⇤ Var[X] t 2 . For any t > 0, Proof: Apply Markov’s inequality to (X E[X])2 Pr (X E[X])2 ⇤ t 2⇥ ⇥ E (X E[X])2⇥ t 2
Selection Problem Input:a set of n elements Output:median straightforward alg: sorting,(nlogn)time sophisticated deterministic alg: median of medians,(n)time simple randomized alg: LazySelect,(n)time,find the median w.h.p
Input: a set of n elements Output: median Selection Problem simple randomized alg: sophisticated deterministic alg: median of medians,(n) time straightforward alg: sorting, (n logn) time LazySelect, (n) time, find the median w.h.p
Selection by Sampling distribution: Naive sampling: uniformly choose an random element make a wish it is the median
Selection by Sampling Naive sampling: uniformly choose an random element distribution: make a wish it is the median