2
$\begingroup$

The following question (in two parts) comes from a homework sheet of the fall 2019 semester cs170 course taught at UC Berkely taught by professors Vazerani and Tal.

Design an algorithm that takes in a stream $z_{1}, . . . , z_{M}$ of $M$ integers in $\mathbb{Z_{n}}$ and at any time $t$ can output a uniformly random element in $z_{1}, . . . , z_{t}$ . Your algorithm may use at most polynomial in $\lg(n)$ and $\lg(M)$ space.

This is an instance of Reservoir Sampling with reservoir size of $1$.

For a stream $S = z_{1}, . . . , z_{2n}$ of $2n$ integers in $[n]$, we call $j ∈ [n]$ a duplicate element if it occurs more than once. Design an algorithm that takes in $S$ as input and with probability at least $1 − \frac{1}{n}$ outputs a duplicate element. Your algorithm may use at most polynomial in $\lg(n)$ space.

Attempts

Consider the naive approach of consuming the entire stream and sampling. At least $n$ elements in the stream have duplicates. Since each of the $2n$ elements in the stream is equally likely to be sampled, the probability of sampling a duplicate element is at least $\frac{n}{2n} = \frac{1}{2}$, which is not nearly as tight a bound as $1 - \frac{1}{n}$.

On the other hand, Reservoir sampling produces a simple random sample, so maybe we could model the reservoir as sampling from a multiset and compute the probability of there being a duplicate using multinomial distribution? Although, the multinomial requires independent trials.

I don't see a path forward for part $b$ of the problem yet. Any hints?

$\endgroup$
0
1
$\begingroup$

Since I realized too late you only asked for a hint, I spoilered my full answer. The hint is: use reservoir sampling with $\log n$ integers and check for duplicates during the sampling.

Perform your reservoir sampling algorithm with $\log n$ integers. This takes $O\left(\log{\left(n\right)}^2\right)$ bits of space and is thus allowed. However, at each step, before (potentially) replacing your reservoir, check if the new element from the stream equals one in the reservoir. If yes, return the found duplicate immediately.

Let's assume we face an adversary that does not output a duplicate unless it has to. So we assume the first $n$ integers do not contain any duplicate. After those first $n$ integers at any point we store a completely uniform random sample of $\log n$ distinct integers from the first $k$ elements from the stream. Thus the probability that the next element of the stream is a duplicate of a currently stored one is $\frac{\log n}{n}$, and the adversary can do nothing to decrease these odds. So overall the probability that we fail to find a duplicate this way is at most ${\left(1 - \frac{\log n}{n}\right)}^n$.

Now using the inequality $(1-x)^r \leq e^{-xr}$ we have $${\left(1 - \frac{\log n}{n}\right)}^{n} \leq e^{-\log n} = 1/n.$$

$\endgroup$
2
  • $\begingroup$ I wonder, did you start with the inequality and fit the adversary story to it, or did you have another thought process when coming up with the solution? $\endgroup$
    – heckeop
    Jul 1 at 23:05
  • $\begingroup$ @heckeop Check the edit history for my first, flawed attempt :) $\endgroup$
    – orlp
    Jul 1 at 23:18
1
$\begingroup$

Let us denote by $S(m,c,\epsilon)$ the space (number of words) needed to find a duplicate in an array of size $cm$ which contains at most $m$ distinct integers, with error probability at most $\epsilon$. We assume that $c > 1$.

Let $\delta > 0$. We consider two possibilities:

  • Both halves of the array contain at least $(1 + \delta)(m/2)$ distinct integers.

  • One of the halves of the array contains at most $(1+\delta)(m/2)$ distinct integers.

In the first case, the two halves have at least $\delta m$ elements in common. If we sample an element from the first half, the probability that we sample one of these common elements is $\frac{\delta m}{c(m/2)} = 2\delta/c$. If we sample $k$ elements from the first half (using reservoir sampling), we hit one of these elements with probability $1 - (1-2\delta/c)^k$. Choosing $k = \log_{1-2\delta/c} \epsilon \approx \frac{c}{2\delta} \log (1/\epsilon)$, the failure probability is at most $\epsilon$.

In the second case, we simply run the same algorithm on each of the halves. Each of these halves is of size $cm/2$ and contains at most $(1+\delta)(m/2)$ distinct integers. Since $$ \frac{cm/2}{(1+\delta)(m/2)} = \frac{c}{1+\delta}, $$ we run the algorithm with $c \gets \frac{c}{1+\delta}$.

Since we don't know which of the two cases holds, we run the two strategies in parallel. In total, we obtain $$ S(m,c,\epsilon) \leq \frac{c}{2\delta} \log(1/\epsilon) + S\bigl(m/2,\frac{c}{1+\delta},\epsilon\bigr). $$

We are interested in $S(n,2,1/n)$. We choose $\delta = \gamma/\log n$ to ensure that the value of $c$ along the process is always at least $$ \frac{2}{(1 + \gamma/\log n)^{\log n}} \approx \frac{2}{e^\gamma}, $$ which will be larger than $1$ for an appropriate constant $\gamma$. The total space is $$ \frac{1}{\delta} \log(1/\epsilon) \cdot \log n = O(\log^3 n). $$ (We take as base case $m = 1$, which requires no memory.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.