Tutorial 10:Limit Theorems Weiwen LIU wwliu@cse.cuhk.edu.hk April 3,2017 1
Tutorial 10: Limit Theorems Weiwen LIU wwliu@cse.cuhk.edu.hk April 3, 2017 1
Markov and Chebyshev Inequalities These inequalities use the mean and possibly the variance of a random variable to draw conclusions on the probabilities of certain events. primarily useful in situations exact values or bounds for the mean and variance of a random variable X are easily computable. but the distribution of X is either unavailable or hard to calculate. 2
Markov and Chebyshev Inequalities • These inequalities use the mean and possibly the variance of a random variable to draw conclusions on the probabilities of certain events. • primarily useful in situations • exact values or bounds for the mean and variance of a random variable 𝑋 are easily computable. • but the distribution of 𝑋 is either unavailable or hard to calculate. 2
Markov inequality If a random variable X can only take nonnegative values,then pX之)≤W,for all>0 Loosely speaking,it asserts that if a nonnegative random variable has a small mean,then the probability that it takes a large value must also be small. 3
Markov inequality • If a random variable 𝑋 can only take nonnegative values, then 𝑃 𝑋 ≥ 𝑎 ≤ 𝐸 𝑋 𝑎 , for all 𝑎 > 0 Loosely speaking, it asserts that • if a nonnegative random variable has a small mean, then the probability that it takes a large value must also be small. 3
Example 1 Let X be uniformly distributed in the interval0,4 and note that E[X]=2. Then,the Markov inequality asserts that 2 P(X之2)≤2=1 2 P(X≥3)≤5=0.67. PX≥4)≤4=0.5 4
Example 1 • Let 𝑋 be uniformly distributed in the interval [0,4] and note that 𝐸[𝑋] = 2. • Then, the Markov inequality asserts that 𝑃 𝑋 ≥ 2 ≤ 2 2 = 1. 𝑃 𝑋 ≥ 3 ≤ 2 3 = 0.67. 𝑃 𝑋 ≥ 4 ≤ 2 4 = 0.5. 4
Example 1 By comparing with the exact probabilities P(X≥2)=0.5. P(X≥3)=0.25. P(X≥4)=0. We see that the bounds provided by the Markov inequality can be quite loose
Example 1 • By comparing with the exact probabilities 𝑃 𝑋 ≥ 2 = 0.5. 𝑃 𝑋 ≥ 3 = 0.25. 𝑃 𝑋 ≥ 4 = 0. • We see that the bounds provided by the Markov inequality can be quite loose. 5