Randomized Algorithms 2022 Coursework 1

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Randomized Algorithms 2022

Coursework 1

1. Imagine that we have a fair coin and want to generate a stream of (uniform) random bits. Instead of using the natural process for generating (say) the N needed bits (flip the coin N times), we have decided to attempt to “reuse” the randomness and generate the N bits using only n =「2^N│ coin flips.

To do this, we first generate n =「2^N│ fair random bits Z1, . . . , Z「2^N」  with the fair coin. Next, we consider the index set of pairs P = {{i, j} : 1 < i < j < n} and for every p e P we define Yp  as the exclusive-or Zi o Zj  of the particular variables of the pair p = {i, j} (o being the exclusive-or operator).

This will give rise to |P| different Yp  random variables.

We will also consider the “total” random variable Y = 渥1 Yp .

(a)  Show that for every p e P , Yp  is 0 with probability 1/2 and 1 with probability 1/2. So despite the unusual definition with o, each Yi,j  is a fair coin flip.

(b)  Show that the number of different Yp  variables  (the cardinality of the set P) will be greater than N.

(c)  Show that every pair of the Yp  variables satisfy the definition of pairwise independence,

and hence that E[YpYq] = E[Yp]E[Yq].

(you will need to consider 2 cases to show this)

(d)  Show that the collection of {Yp  : p e P} variables do not satisfy the definition of mutual independence.

(e) What is the expected value E[Y]?

(f)  It is a known fact that if we have a collection of random variables {Xi  : 1 < i < k} such

that the Xi  are pairwise independent, that Var[渥1 Xi] =渥1 Var[Xi]. Use this fact to calculate Var[Y] for Y = 渥1 Yp .

(g) Using Chebyshev’s inequality, prove an upper bound on Pr[|Y — E[Y]| > n].

2.  Consider a variation on the coupon collector problem where the goal is to collect n/2 coupons   [15 marks]

instead of all n.  What is the expected number of coupons one would have to purchase to collect n/2 coupons.  (An expression for this in terms of n will suffice.)

Asymptotically, what is the order of the expected number of coupon purchases of coupons required to collect n/2 coupons? Recall that the asymptotic order of purchases required for the original coupon collector problem is Θ(n ln n).

3.  Suppose that a certain real-valued random variable X has a (continuous) distribution D which   [10 marks]

has support only in the unit interval  [0, 1].   Suppose we we can obtain any number m of independent samples X1, ..., Xm from the same distribution D. We want to use as few samples as possible in order to estimate E[X] to within an additive error at most ±e, and with failure probability at most δ, for some desired chosen e e (0, 1) and δ e (0, 1). Give an algorithm for this problem, such that your algorithm is as efficient as you can make it in terms of “sample complexity”, meaning in terms of the total number m of random samples used.  Specify the number of samples your algorithm uses, as a function of (1/δ) and (1/e). Justify correctness of your claims using a result stated in lectures (quoting the specific result you are using).

4.  Consider a undirected graph G = (V, E), which has n = |V| vertices.  For v e V, let N(v) =   [25 marks]

{u e V | {u, v} e E} denote the set of neighbors of the vertex v in the graph.  Suppose the degree of every vertex in the graph G is > d. In other words, suppose |N(v)| > d for all v e V.

Let us call a subset S  C V of vertices  Good if for every vertex v  e V either v  e S or N(v) n S  0, or both. In other words, S is Good if for every vertex v, either v itself or one of its neighbors, or both, is in S.  Show that in any undirected graph with minimum degree at least d, there exists a Good set of size at most:

|n . | .                                                      (1)

[Hint:  use the probabilistic method.  Start by choosing a random subset S C V, by placing each vertex v in S, independently, with probability p (where the probability p is to be deter- mined later). Then make the chosen S Good, by adding to it every vertex that isn’t already “covered” . Finally, figure out what the best p is for giving you the upper bound in (1).]

 



2022-10-26