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}$?