Scribd
Upload
6 views

2019 Randomized Algorithm Design Assignment 1

Uploaded by

captainamericabio1980
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views

2019 Randomized Algorithm Design Assignment 1

Uploaded by

captainamericabio1980
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Assignment 1: Randomized Algorithm Design

Palash Dey
Indian Institute of Technology, Kharagpur
January 18, 2019

Assume that the random variables are either continuous or discrete if not explicitly mentioned.

1. Let Xi , i ∈ [n] be n random variables each with finite support. Then prove the following.

X X X
 
n n

var  Xi  = var (Xi ) + 2 cov(Xi , Xj )


i=1 i=1 16i<j6n

where for any two random variables X and Y, we define cov(X, Y) = E[XY] − E[X]E[Y].
2. Let X and Y be two independent random variables. Then prove that E[XY] = E[X]E[Y]. From this
conclude that, for n pairwise random variables Xi , i ∈ [n], we have the following.

X X
 
n n

var  Xi  = var(Xi )
i=1 i=1

3. Fix any input sequence of n integers to the quick sort algorithm. Let X be the random variable denoting
the number of comparisons the the quick sort algorithm makes on the input sequence. Then prove that
var(X) = O(n2 ).
4. Let Ai , i ∈ [n] be n objects each having two attributes Axi and Ayi . The attribute y is 0 for every Ai .
Suppose we have a deterministic quick sort algorithm that can sort Ai , i ∈ [n] on the attribute x or on
the attribute y. Can you use this deterministic quick sort algorithm to design a randomized algorithm
to sort Ai , i ∈ [n] on the attribute x which makes an expected O(n log n) comparisons? Please prove
that your algorithm indeed makes O(n log n) comparisons on expectation.
5. Let Xi , i ∈ P
[n] be n pairwise independent random variables each taking values in {0, 1} with expectation
µ and S = n i=1 Xi . Then for any positive real number δ we have the following.
µ
h i  e−δ
Pr S 6 (1 − δ)µ 6
(1 − δ)1−δ

6. Show that the expected number of balls one needs to through randomly into m bins to have every bin
at least one ball is O(m log m).

7. Give an example of a random variable whose expectation exists but variance does not exist.
8. Find the expectation and variance of the number of swaps that the bubble sort algorithm performs on
a uniformly random permutation of n distinct integers.

1
9. Prove the weak law of large numbers using Chebyshev inequality. The weak law of large number states
that, for random variables Xi , i ∈ N which are distributes independently and identically with mean µ
and variance σ2 , we have the following for any constant ε > 0
 
X1 + X2 + · · · + Xn
lim Pr −µ >ε =0
n→∞ n

10. Let Xi , i ∈ [n]


P be n pairwise independent random variables each taking values in {0, 2} with expectation
µ and S = n i=1 Xi . Use standard Chernoff bound proved in class to upper bound the probability that
S takes value more than (1 + δ)µ.

11. Let X be a random variable with expectation µ and variance σ2 . Then for any t ∈ R>0 , prove the
following.
h i 1 h i 2
Pr X − µ > tσ 6 2
and Pr |X − µ| > tσ 6
1+t 1 + t2
12. Let X be a non-negative integer valued random variable with positive expectation. Then prove the
following.
 E[X2 ] − E[X]2 E[X]2
Pr X = 0 6

and 6 Pr[X 6= 0] 6 E[X]
E[X]2 E[X2 ]

You might also like