Assume a process that samples uniformly at random from the range $[1,\ldots,n]$. I am interested in the expected time to find a duplicate given only that the sampling process is pairwise independent. That is I would like to find the expected time until a sample matches one of the samples taken before.

One way to compute the expected time is $$E=\sum_{x=1}^\infty P(X \geq x).$$ Here $X$ is a random variable that represents the time at which the first duplicate is found.

If the samples were fully independent then we would have that $$\sum_{x=1}^\infty P(X \geq x) = \sum_{x=1}^\infty \prod_{i=1}^{x-1} (1-i/n).$$ We can bound this quantity using the fact that $e^{-2x} \leq 1-x \leq e^{-x}$ when $0 \leq x \leq 0.5$ and then bound the resulting sum using an integral. This gives an asymptotic bound of $\Theta(\sqrt{n})$ steps.

How would you perform a similar analysis where we only have pairwise independence and also preferably get an asymptotic result rather than just an upper bound?

EDIT: Following Henry's great reply, I would really like to know a lower bound as well as the upper bound he has given. In particular, does the lower bound for fully independent sampling of $\Omega(\sqrt{n})$ also apply to this pairwise independent case? Or alternatively, can anyone think of a pairwise independent process that has mean less than order $\sqrt{n}$?


The worst case is $O(n)$. Clearly by pigeonhole arguments the expectation cannot exceed $n+1$ but there are examples where it exceeds $n$.

Suppose the samples are $S_1, S_2, \ldots$ and

  • that $S_1$ has a uniform distribution on $\{1,2,\ldots,n\}$,

  • that with probability $\frac{1}{n}$ you have $S_1 = S_2 = \cdots = S_{n} $ and with probability $\frac{n-1}{n}$ you have $S_j$ having a uniform distribution on $\{1,2,\ldots,n\} - \{S_1,\ldots , S_{j-1} \}$ for $2 \le j \le n$ and

  • that $S_{n+1}$ has a uniform distribution on $\{1,2,\ldots,n\}$ independently of all the others,

then there is a probability $\frac{1}{n}$ that you need a sample size of $2$ and a probability $\frac{n-1}{n}$ you need a sample size of $n+1$ to find a duplicate value. This gives an expectation of $n+\frac{1}{n}$ which is $O(n)$.

  • $\begingroup$ That's great thanks. I would really like to know a lower bound as well as this interesting upper bound you have given. I will edit the question to explain that as well. $\endgroup$ – Raphael Jul 12 '12 at 17:24
  • $\begingroup$ If you have time, it might be worth adding a sentence on why the sampling process you describe is pairwise independent as I think this is a problem lots of people would be interested in. $\endgroup$ – Raphael Jul 12 '12 at 17:26
  • $\begingroup$ What's your view on a lower bound? $\endgroup$ – Raphael Jul 13 '12 at 17:06
  • $\begingroup$ @Arlo: I suspect the fully independent version may give the lower bound $\endgroup$ – Henry Jul 13 '12 at 17:49
  • $\begingroup$ Bounty awarded as this was the best answer received on math stackexchange. Thanks. $\endgroup$ – Raphael Jul 16 '12 at 23:23

A simple lower bound proof was given at https://mathoverflow.net/questions/102079/bounds-for-duplicate-finding-with-limited-independence by Douglas Zare. I include a slightly edited copy for completeness.

The expected number of duplicates among the first $m$ is an upper bound for the probability of a duplicate in the first $m$. For $m=c\sqrt{n}$ the expected number of duplicates is under $c/2$, so the probability that the first duplicate is greater than $\sqrt{n}$ is greater than $1/2$, which means the expected first duplicate is greater than $\sqrt{n}/2$.


This is the generalized birthday problem. Your $n$ is $d$ in the article.

  • $\begingroup$ The main difference is that my problem can only assume pairwise independence so those results don't seem to hold. Also I want to know the expected number of samples to get a duplicate not the number needed to get probability at least 1/2 of getting a duplicate. $\endgroup$ – Raphael Jul 11 '12 at 22:26
  • $\begingroup$ @Arlo: For your second point, try further down the same page $\endgroup$ – Henry Jul 12 '12 at 0:01
  • $\begingroup$ Good point, thanks. $\endgroup$ – Raphael Jul 13 '12 at 20:41

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.