Need to use Markov\'s Inequality + Union Bound and reference the below https://b

Question

Need to use Markov's Inequality + Union Bound and reference the below

https://bb.au.dk/bbcswebdav/pid-193771-dt-content-rid-370754_1/courses/BB-Cou-STADS-UUVA-40277/basicProbInequalities.pdf

-if site asks for credentials, just refresh

Exercise 4 (Hard). Modify the above construction to yield a data structure that simultaneously has worst case query time O(lgn/lg lg n), space o(n), erpected construction time O(n) AND ma-1 List (Ali)P 10n, no matter what set S of n elements from Ul that is given as input. Hint: Use the wnion bound in combination with Erercise 3.

Explanation / Answer

Markov and Chebyshev Inequalities

Let XX be any positive continuous random variable, we can write

EXEX   =xfX(x)dx=xfX(x)dx
=0xfX(x)dx=0xfX(x)dx   (since X is positive-valued)(since X is positive-valued)
axfX(x)dxaxfX(x)dx   (for any a>0)(for any a>0)
aafX(x)dxaafX(x)dx   (since x>a in the integrated region)(since x>a in the integrated region)
=aafX(x)dx=aafX(x)dx
=aP(Xa).=aP(Xa).

Thus, we conclude
P(Xa)EXa,for any a>0.
P(Xa)EXa,for any a>0.
We can prove the above inequality for discrete or mixed random variables similarly (using the generalized PDF), so we have the following result, called Markov's inequality.
Markov's Inequality

If XX is any nonnegative random variable, then

P(Xa)EXa,P(Xa)EXa,   for any a>0.for any a>0.

Example
Prove the union bound using Markov's inequality.

Solution

Example
Let XBinomial(n,p)XBinomial(n,p). Using Markov's inequality, find an upper bound on P(Xn)P(Xn), where p<<1p<<1. Evaluate the bound for p=12p=12 and =34=34.

Solution

Chebyshev's Inequality:

Let XX be any random variable. If you define Y=(XEX)2Y=(XEX)2, then YY is a nonnegative random variable, so we can apply Markov's inequality to YY. In particular, for any positive real number bb, we have
P(Yb2)EYb2.
P(Yb2)EYb2.
But note that
EY=E(XEX)2=Var(X),P(Yb2)=P((XEX)2b2)=P(|XEX|b).
EY=E(XEX)2=Var(X),P(Yb2)=P((XEX)2b2)=P(|XEX|b).
Thus, we conclude that
P(|XEX|b)Var(X)b2.
P(|XEX|b)Var(X)b2.
This is Chebyshev's inequality.

Chebyshev's Inequality

If XX is any random variable, then for any b>0b>0 we have
P(|XEX|b)Var(X)b2.
P(|XEX|b)Var(X)b2.

Chebyshev's inequality states that the difference between XX and EXEX is somehow limited by Var(X)Var(X). This is intuitively expected as variance shows on average how far we are from the mean.

Example
Let XBinomial(n,p)XBinomial(n,p). Using Chebyshev's inequality, find an upper bound on P(Xn)P(Xn), where p<<1p<<1. Evaluate the bound for p=12p=12 and =34=34.

Solution
One way to obtain a bound is to write
P(Xn)P(Xn)   =P(Xnpnnp)=P(Xnpnnp)
P(|Xnp|nnp)P(|Xnp|nnp)
Var(X)(nnp)2Var(X)(nnp)2
=p(1p)n(p)2.=p(1p)n(p)2.

For p=12p=12 and =34=34, we obtain
P(X3n4)4n.
P(X3n4)4n.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.