My Solution for Randomized Algorithms for the Fall 2015 semester, Problem Set 3. Keep your Academic Integrity plz.

Try Firefox if your web browser (e.g. Chrome, IE) does not support MathML, a part of HTML5.

Randomized Algorithms: Problem Set 3


1 Problem 1

Suppose there are two parameters k,l to be determined. Our algorithm runs as follows:

Input set S of n elements over totally ordered domain.

  1. 1.

    Pick a multi-set R of nk elements in S, chosen independently and uniformly at random with replacement, and sort R;

  2. 2.

    Let d be the 12nknl-th smallest element in R, and let u be the 12nk+nl-th smallest element in R;

  3. 3.

    Construct C={xS|dxu} and compute the ranks rd=|{xS|xd}| and ru=|{xS|xu}|;

  4. 4.

    If rd>n2 or ru<n2 or |C|>4n1k+l then return FAIL;

  5. 5.

    Sort C and return the (n2rd+1)-th element in the sorted order of C.

We now bound the probability that the algorithm returns a FAIL. Let mS be the meadian of s. By Line 4, we know that the algorithm returns a FAIL if and only if at least one of the following events occur:

  • 1: Y=|{xR|xm}|<12nknl;(which is equivalent to rd>n2)

  • 2: Z=|{xR|xm}|<12nknl;(which is equivalent to ru<n2)

  • 3: |C|>4n1k+l.

1.1 Bound 1 and 2

Let Xi be the i-th sampled element in Line 1 of the algorithm. Let Yi be an indicator random variable such that

Yi={1 if Xim,0 otherwise.

Clearly Y=i=1kYi. Note that


Recall a form of the Chernoff bound: For a sequence of m independent random variables on {0,1} such that for all i, Pr[Yi=1]=p for some p, Pr[Yi(p+τ)m]exp(2mτ2) and similarly Pr[Yi(pτ)m]exp(2mτ2). Let m=nk, τ=nlk.

Pr[1] =Pr[Y<12nknl]

By similar analysis, we can bound


1.2 Bound 3

By the Pigeonhole Principle, 3 happens only when at least one of these two events happen:

  • 3: at least 2n1k+l elements of C is smaller than m;

  • 3′′: at least 2n1k+l elemetns of C is greater than m.

Note that 3 implies that the rank of d is at most 12n2n1k+l, and thus there are at least 12nknl elements in R whose rank are at most 12n2n1k+l. Let Xi be an indicator random variables to indicate whether the i-th sample’s rank is at most 12n2n1k+l. Let X=i=1nkXi. Hence


Recall a form of the Chernoff bound: For a sequence of m independent random variables on {0,1} such that for all i, Pr[Xi=1]=p for some p, Pr[Xi(p+τ)m]exp(2mτ2) and similarly Pr[Xi(pτ)m]exp(2mτ2). Let m=nk, τ=nlk.

Pr[3] =Pr[X12nknl]

The probability that 3′′ occurs will have the same bound by symmetry. By the union bound,


1.3 Combine Together

By the union bound, the probability our algorithm fails is at most


which will be less than 4/e2 if 2lk.

To make our algorithm efficient, we let |C|nk. Thus we have 1k+lkk(1+l)/2. Recall that 2lk, it holds that 2l(1+l)/2l1/3. Therefore k(1+l)/22/3, we can sample n2/3 elements in R.

2 Problem 2



Pr[Xt] =Pr[λXλt] (λ>0)
?[eλX]eλt (Markov’s Inequality)


We define f(λ):=λtΨX(λ). Since λt is a line and ΨX(λ) is strictly convex, f(λ) should be a strict concave function over λ0, and ΨX*(λ) is achieved at the unique point where f(λ)=0.

With the assumption that ΨX(λ) is continuously differentiable, we have


Therefore, ΨX*(t) is achieved at the unique λ0 satisfying ΨX(λ)=t.

2.2 Normal random variables.


?(eλX)=exp(λ2σ22+λμ) (Computed by WolfarmAlpha)

ΨX*(t) is achieved at λ=tμσ2

Ψx*(t) =tμσ2t((tμσ2)2σ22+tμσ2μ)



2.3 Poisson random variables.


?(eλX)=exp(ν(eλ1)) (Computed by WolfarmAlpha)

ΨX*(t) is achieved at λ=lntν

Ψx*(t) =tlntν(tν1)ν



2.4 Bernoulli random variables.

let ΨX(λ)=peλpeλ+1p=t, we get λ=ln(1p)t(1t)p.

ΨX*(t) =tln(1p)t(1t)pln[(1p)t1t+(1p)]

2.5 Sum of independent random variables.


ΨXi(λ) =ln?(eλXi)
ΨX(λ) =ln?(eλi=1nXi)
=lni=1n?(eλXi) (independent!)


X1,X2,,Xn are i.i.d. random variables
ΨX(λ)=nΨXi(λ), for some i
Assuming the unique λ=λ0 makes ΨX(λ0)=nΨXi(λ0)=t

ΨXi*(tn) =tnλ0ΨXi(λ0)
nΨXi*(tn) =tλ0nΨXi(λ0)



We consider Binomial random X as sum of n i.i.d. Bernoulli random variables X1,X2,,Xn. Then Pr[Xt]exp(ΨX*(t))=exp(nΨXi*(tn)). Let Y{0,1} is a Bernoulli random variable with parameter tn and X{0,1} is a Bernoulli random variable with parameter p, we can conclude that Pr[Xt]exp(nD(YX)).


Let ΨXi(λ)=tn, then λ=lnntt(p1).

ΨXi*(tn) =tnλΨXi(λ)
Pr[Xt] exp(ΨX*(t))

3 Problem 3


3.1.1 Union Bound

We constuct a mapping uniformly at random. Let X1,,Xn be independent Poisson trials and X=Xi, ?[X]=n/2. Let δ=8rln2,d=(n/2)(1δ). We have

Pr[the distance between any 2 codewords is at most d] =Pr[Xd]
<exp(δ2n/22) (Chernoff bound)

Due to the union bound,

Pr[x,y{0,1}k s.t. d(C(x),C(y))d] (2k2)Pr[Xd]

Therefore there exists a boolean code of code rate r=k/n and distance (122ln2r)n.

3.1.2 Lovász Local Lemma

Consider arbitrary a pair of points a,b{0,1}k, a’s coordinates are smaller than b in lexicographic order. We define a bad event (a,b) as d(C(a),C(b))<d. Observe that in the dependency graph of bad events, a bad event is adjacent to at most 2(2k2) other bad events. Thus, due to the Lovász Local Lemma, the probability that all the bad events do not happen will be larger than 0 if the probability that a single bad event happen is at most 1/(e2(2k2))>1/(2e2k)>exp(k2).

Let δ=cr, d=(n/2)(1δ). Due to the Chernoff bound as previous section, a bad event happens with probability at most exp(δ2n4). The target mapping exists if (δ2n)/4k+2. In another word,


Therefore there exists a boolean code of code rate r=k/n and distance (121+12kr)n.


We construct the boolean matrix A uniformly at random. For each entry of A, let the entry be 0 or 1 with probability of 1/2 respectively.

Consider arbitrary two different messages a and b, and some 1×k vector v in A. Let xi denote the i-th entry of vector x. Let c=a+mod2b, i.e. ci,ci=ai+mod2bi. Observe that


Since a and b are different messages, c0. Observe that for all i[1,k], only the i’s such that vi=ci=1 will influence the value of vc. Let S={i[1,k]|vi=ci=1}. Clearly, vc=1|S| is odd, and Pr[|S| is odd]=1/2. Let A=[v1T,v2T,,vnT]T,


By coupling vic with Xi, we have

Pr[d(Aa,Ab)d] =Pr[Xd]
<exp(δ2n/22) (Chernoff bound)

Due to the union bound,

Pr[a,b{0,1}k s.t. d(Aa,Ab)d] (2k2)Pr[Xd]

Therefore there exists a linear boolean code of code rate r=k/n and distance (122ln2r)n.

4 Problem 4


For each position i{1,2,,n} of the binary string, we define an indicator random variable Yi to indicator whether there is a run which has length at least k and starts from i. Obviously Xk=Yi. Let T[i] denote i-th value of the binary string. Observe that

  • Y1=1i[1,k],T[i]=1,

  • i[2,nk+1],(Yi=1T[i1]=0j[i,i+k1],T[j]=1),

  • i[nk+2,n],Yi=0.

Due to the linearity of expection,

?[Xk] =i=1n?[Yi]


Let Zi be an indicator random variable to indicate whether the i-th element in the string is 1. Let ?=(Z1,,Zn), Xk=f(Z1,,Zn), where f is a function of random variables and Xk denote the number of runs in S of length k or more. Observe that for any x1,,xn{0,1} and any w{0,1},


f satisfying the Lipschitz condition with constant 1. Then due to the Method of Bounded Differences,

Pr[|Xk?[Xk]|t] =Pr[|f(?)?[f(?)]|t]

5 Problem 5


Without lost of generality, we assume there exists c0 s.t.


Note that due to the Taylor series of exponential function and the linearity of expectation,

?[exp(c|X|)]exp(cδ) =exp(cδ)i=0?[(c|X|)i]i!

Recall that for some XPois(λ),Pr[X=k]=exp(λ)λk/k!. This implies if we sample K which follows a Poisson distribution with parameter of cδ at random, the expected Kth-moment bound will be as good as the Chernoff bound.

For k=0, the moment bound will be 1. Observe that unless i(?[|X|i]=δi), there is another moment bound which is strictly different with 1. Due to the Pigeonhole Principle, there exists an integer k which is strictly less than the expected value. In another word, there exists a choice of k such that the kth-moment bound is strictly stronger than the Chernoff bound.

If i(?[|X|i]=δi), then |X| will be a constant δ. The moment bound and Chernoff bound will be trivial 1.


Because it it difficult to such a k such that kth-moment bound is strictly stronger than the Chernoff bound.

CC BY-SA 4.0 RA.PS3 by himemeizhi is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.