3
$\begingroup$

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

$\endgroup$
12
  • $\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$ Jul 13, 2012 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, 2012 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$ Jul 13, 2012 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, 2012 at 18:40
  • $\begingroup$ Under independence, the expected time until the first duplicate is already $\Omega(\sqrt{n})$. $\endgroup$ Jul 13, 2012 at 20:55

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Jul 15, 2012 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$ Jul 29, 2012 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.