(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.

  • $\begingroup$ 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. $\endgroup$ – Douglas Zare Jul 13 '12 at 1:42
  • $\begingroup$ @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. $\endgroup$ – Raphael Jul 13 '12 at 17:10
  • $\begingroup$ 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})$. $\endgroup$ – Douglas Zare Jul 13 '12 at 18:24
  • $\begingroup$ @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? $\endgroup$ – Raphael Jul 13 '12 at 18:40
  • $\begingroup$ Under independence, the expected time until the first duplicate is already $\Omega(\sqrt{n})$. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Douglas Zare Jul 15 '12 at 8:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Douglas Zare Jul 29 '12 at 0:39

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.