Complexity, Probability, pairwise independence Question:
$n$ coins are laid covered on a table, $k < n/3$
of which are pure gold and the rest copper, and
you are told to uncover and take $2n/3$
coins. You are allowed to use any algorithm, no matter
what its complexity is, but remember that the adversary knows your algorithm and places
the gold coins based on your algorithm.
• Show that if you use $n$ random coins you can almost certainly get $Ω(k)$ gold coins.
• Show that with $O(\log n)$ random coins, you can guarantee $Ω(k)$ gold coins with probability
at least $O(1-
1/
k
)$.
Hint: Use pair-wise independence
My thoughts:
For the $1$st bullet I've tried saying that if I randomly pick $2/3$ of the coins, then the probability for all the gold coins to be picked is $\frac{\frac {2n}3!}{\frac n3! n!}$ (using the hyper-geometric rv formula).
This has a limit of $0$ at infinity, so I don't see how this can prove what needs to be proven. 
About the second bullet, I don't know where to start - how can I use pairwise ind. here for this?
 A: Outline:


*

*First remark: Don't use hypergeometric (sampling without replacement). Since for high values of $n$ the two distributions will be statistically close, use sampling with replacement instead, this independence property will make things easier to analyse.

*Take $n$ coins, i.e. $n$ independent random bits $X_1,\dots, X_n$ with bias $2/3$, where you select coin $i$ iff $X_i=1$. The expected number of coins uncovered is $\frac{2n}{3}$, and by standard arguments this will be highly concentrated when $n$ is big (hence the possibility of switch hypergeometric/binomial).

*Now, the number of golden coins selected is, on expecteation, $\frac{2}{3}k.$ Provided $k=\omega(1)$, the same arguments (to be precise: Chernoff/Hoeffding bounds) will ensure you get at least say $\frac{k}{100}$ with very high probability.

*If you only have pairwise independence, do the same. But your $X_i$'s are only pairwise independent, so the second part of the analysis fails (you cannot use Chernoff/Hoeffding bounds to get an exponential small probability of error). Instead, use Chebyshev's inequality, since the variance will be additive (due to the pairwise independence). The error probablity you get for the same error threshold will not be as good, however -- only inverse polynomial. But there are known constructions of pseudorandom generators that guarantee pairwise independence of $n$ random bits using only $O(\log n)$ truly random bits.
You may want to read this summary of useful probabilistic facts (at least the corresponding parts of it: Chernoff, Chebyshev, pairwise sampling) by Oded Goldreich for more intuition and detail.
