# Bounds for duplicate finding with limited independence

(This is a follow up to this previous question on math.stackexchange.com.)

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

If the sampling process is fully independent then it is well known that the expected time is $\Theta(\sqrt{n})$. Further you can compute upper and lower bounds for $P(X \geq x)$ fairly straightforwardly giving you good tail bounds on the probability that you need many more than the expected value. Here $X$ is the r.v. which represents the number of samples to get a duplicate.

My question is how to analyse the problem if the sampling process is only $k$-independent. What are upper and lower bounds for the expected time to get a duplicate and can we get good tail bounds?

The link at the top shows that for pairwise independence the mean can be greater than $n$. Is this true for $k >2$? For an arbitrary fixed $k$, does the $\Omega(\sqrt{n})$ lower bound we get for full independence still hold? This is clearly not true for $k=1$ (see comment below) but is it true for all $k \geq 2$? Alternatively, does anyone know of a $k$-independent process that takes less than order $\sqrt{n}$ steps to find a duplicate on average?

EDIT 1: Added reference request tag and final sentence. Maybe someone has worked on similar problems before?

EDIT 2: Lower bound question answered in the affirmative by Douglas Zare.

-
If $k \ge 4$ then you can compute the second moment of the number of duplicates among the first $m$. The Chebyshev inequality is not quite good enough to give $O(\sqrt{n})$ from this. –  Douglas Zare Jul 13 '12 at 1:42
@Douglas Zare, blog.computationalcomplexity.org/2009/11/… has a related bound using the 2nd moment when $k=4$. I will a reference request to the question too as maybe someone has worked on this before. –  Raphael Jul 13 '12 at 17:10
That blog covered part of the calculations I did. Chebyshev's inequality is usually far from sharp, and perhaps replacing it with something stronger would provide slightly better estimates on the probability that there are no duplicates among the first $m$, which may be enough to prove $O(\sqrt{n})$. –  Douglas Zare Jul 13 '12 at 18:24
@Douglas Zare, That would be very interesting as it would imply that there is a dramatic difference between $2$ and $4$-independence. Does this approach have any chance of showing an $\Omega(\sqrt{n})$ lower bound as well? –  Raphael Jul 13 '12 at 18:40
Under independence, the expected time until the first duplicate is already $\Omega(\sqrt{n})$. –  Douglas Zare Jul 13 '12 at 20:55

For $k \ge 4$, the expected time until the first duplicate is $O(\sqrt{n})$. This leaves the case $k=3$ [Edit: The case of $k=3$ is resolved below with a construction with expected first duplicate at about $n/4$].

Let $D_i$ be the number of duplicates in the first $i$ values. The expected time until the first duplicate equals $\sum_{i=0}^n P(D_i = 0)$. We can use the second moment method to estimate these probabilities well enough when $k\ge 4$.

$E(D_i) = {i \choose 2}/n$.

$E(D_i^2) = {i \choose 2}^2/n^2 + {i \choose 2}(1/n - 1/n^2)$.

$\text{Var}(D_i) = E(D_i^2) -E(D_i)^2 = {i \choose 2}(1/n - 1/n^2) \le {i \choose 2}/n$.

So, $0$ is at least $\sqrt{{i \choose 2}/n}$ standard deviations away from the mean of $D_i$. By Chebyshev's inequality, $P(D_i =0)$ is at most $n/{i \choose 2} \le \frac{2n}{(i-1)^2}$. As a probability, it is also at most $1$, and we'll use that estimate for small $i$.

$$\sum_{i=0}^n P(D_i = 0)$$

$$\le \sum_{i=0}^{\lceil \sqrt{2n}\rceil} 1 + \sum_{i=\lceil \sqrt{2n}\rceil+1}^n \frac{2n}{(i-1)^2}$$

$$\le 3 + \sqrt{2n} + \int_{\sqrt{2n}}^n \frac {2n}{x^2}dx$$

$$= 1 + 2\sqrt{2n}.$$

This is about a factor of $4\sqrt{2}$ off of the lower bound in the comments.

To solve the $k=3$ case, we'll construct some processes which are not $3$-independent, then take a mixture which is $3$-independent and which has an expected first duplicate of about $n/4$.

For simplicity, we'll ignore times beyond $n$. Any random prefix on the first $n$ can be extended by appending an independent uniform sequence, and the choice of extension has no effect on the expected first duplicate.

Consider random functions $f$ which are symmetric both on the domain $\lbrace 1,...,n \rbrace$ and range $\lbrace 1,...,n \rbrace$. Such a function corresponds to a $3$-independent process if and only if $P(f(1) = f(2) = f(3)) = 1/n^2$ and $P(f(1)=f(2)\ne f(3))=(n-1)/n^2.$

Let $f_0$ denote random bijections between the domain and range. $P(f_0(1) = f_0(2) = f_0(3))=0.$ $P(f_0(1)=f_0(2)\ne f_0(3))=0.$

Let $f_1$ denote random constant maps. $P(f_1(1) = f_1(2) = f_1(3))=1.$ $P(f_1(1)=f_1(2)\ne f_1(3))=0.$

Suppose $n = 9m$. Choose a random set partition of $\lbrace 1,...,n \rbrace$ into $3m$ pairs and $m$ triplets. Choose $4m$ distinct values for the parts, and let $f_2$ take these values on the parts. $P(f_2(1) = f_2(2) = f_2(3)) = m/{n \choose 3} \approx \frac 2{3n^2} \lt 1/n^2.$ $P(f_2(1)=f_2(2)\ne f_2(3)) = \frac{2}{3} \frac{1}{n}+ \frac{1}{3} \frac{2}{n-1} \frac {n-3}{n-2} = \frac{4(n^2-3n+1)}{3 n(n^2-3n+2)}\approx \frac{4}{3n} \gt (n-1)/n^2.$ The first term, $\frac{2}{3n},$ corresponds to the possibility that $1$ is part of a pair and $2$ is the second point in the pair. The second term corresponds to the possibility that $1$ and $2$ are part of a triplet and $3$ is not the third point of the triplet.

$(1/n^2, (n-1)/n^2)$ is in the convex hull of $(0,0)$, $(1,0)$, and $(m/{n \choose 3},\frac{2}{3} \frac{1}{n}+ \frac{1}{3} \frac{2}{n-1} \frac {n-3}{n-2})$. So, some mixture of $f_0$, $f_1$, and $f_2$ is $3$-independent. Specifically,

$$\frac{n^4-13n^2+16n-4}{4n^4-12n^3+4n}f_0 + \frac{n^2-5n+2}{2n^4-6n^3+2n^2}f_1 + \frac{3n^3 - 12n^2+15n-6}{4n^3-12n^2+4n}f_2$$

is $3$-independent. This mixture gives a weight of $1/4 + o(1)$ to $f_0$, which has expected first duplicate time of $n+1$, so the expected first duplicate of the mixture is at least $(1/4+o(1))n$.

We can use slightly different set partitions when $n$ is not a multiple of $9$. The $2/3:1/3$ split into pairs and triplets was not optimized, so perhaps some other ratio would give a better proportion of $f_0$ in the mixture, hence a better coefficient of $n$ in the expected time of the first duplicate.

-
Earlier I had overlooked that you only need the sum from about $\sqrt{2n}$ to $n$, which is why I didn't obtain the $O(\sqrt{n})$ result from this technique. –  Douglas Zare Jul 15 '12 at 8:36
Thanks very much. –  Raphael Jul 19 '12 at 17:29
For $k=3$, it looks like $(1/3 + o(1))n$ is the limit of this technique, with about $n/4$ pairs and $n/6$ triplets. –  Douglas Zare Jul 29 '12 at 0:39