(This is a follow up to this [previous question on math.stackexchange.com.](https://math.stackexchange.com/questions/169649/average-time-to-find-a-duplicate-with-pairwise-independence))


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](http://en.wikipedia.org/wiki/Birthday_problem#Average_number_of_people) 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.



Bounds for duplicate finding with limited independence
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.


