0
$\begingroup$

I was asked this question today, and my initial thought was - let's check a numeric example.

So $m$ is obviously a multiple of $3$, and the smallest possible value is $m=3$.

I divided the sample space into disjoint events, and then calculated the probability for collision:

1st element is in entry #1, 2nd element is in entry 1; probability for collision is 1/3
1st element is in entry #1, 2nd element is in entry 2; probability for collision is 2/3
1st element is in entry #1, 2nd element is in entry 3; probability for collision is 2/3
1st element is in entry #2, 2nd element is in entry 1; probability for collision is 2/3
1st element is in entry #2, 2nd element is in entry 2; probability for collision is 1/3
1st element is in entry #2, 2nd element is in entry 3; probability for collision is 2/3
1st element is in entry #3, 2nd element is in entry 1; probability for collision is 2/3
1st element is in entry #3, 2nd element is in entry 2; probability for collision is 2/3
1st element is in entry #3, 2nd element is in entry 3; probability for collision is 1/3

Hence the overall probability is $(15/3)/9$, or simply $5/9$, which is of course larger than $1/2$.

I was hoping to get a counter-example, but damn...

Then, for $m=6$, the computation becomes much more complicated, and isince I had a good feeling that it would surpass $1/2$ as well, I've figured I may as well look for a proof rather than a counterexample (though calculating the probability for different values of $m$ may help in understanding the problem and perhaps finding a reason for why this statement is true).

However, it then struck me that this may well be a logical problem, or more precisely - a linguistic problem, where one has to fully understand what is being asked.

For example, I can interpret the question above as:

True or False: After inserting $(2/3)m$ elements into a hash table of size $m$, the probability of a collision upon the next insertion is at least $1/2$, regardless of what hash function was used and what elements were inserted.

Then, it is obvious that this statement is false, since there are cases where those $(2/3)m$ elements were inserted into a single entry, or more generally, into at most $(1/2)m$ entries.

In other words, if I show a single example where the probability of a collision is not larger than $0.5$, then the statement is false.

But it's really hard to tell what the intention of the author in this case, because if we ask "what is the probability?" instead of "is it true that the probability is always larger than $1/2$?", then the answer may well be some value larger than $1/2$.

My questions are:

  1. Am I correct in my argument for why this statement is false?
  2. Is there a way to determine a unilateral interpretation for this statement?

Thank you!!!

$\endgroup$
  • 1
    $\begingroup$ The probability depends on what elements did you insert before so it doesn't depend only on $m$. $\endgroup$ – enedil Feb 9 at 17:12
0
$\begingroup$

If the first $2m/3$ entries collide among themselves enough s.t. they occupy $<1/2$ the table, then the next insertion clearly collides with prob $<1/2$. This is uninteresting, and so the original author cannot possibly mean "For any possible first $2m/3$ entries..." If the first $2m/3$ entries don't collide, and fill up $2/3$ of the table, then the next insertion clearly collides with prob $=2/3 > 1/2$. This is also uninteresting.

The interesting interpretation (IMHO) is what if the first $2m/3$ entries are also random and independent. In this case, the next insertion collides with the $i$th previous entry with probability $1/m$, for $i \in \{1, 2, ..., 2m/3\}$, and all such potential collusions are independent (because the previous entries are independent). Therefore, probability that the next insertion does NOT collide $= p_m = (1 - {1\over m})^{2m/3}$, and the claim is $p_m < 1/2$.

BTW for $m=3, p_m = (1 - 1/3)^2 = 4/9$ which agrees with your result (since my $p_m$ is prob of NOT colliding).

I dont know for what values of $m$ it is true that $p_m < 1/2$, but in the large $m$ limit this reduces to $p_m = ((1 - {1 \over m})^m)^{2/3} \approx (1/e)^{2/3} = e^{-2/3} \approx 0.513$. Since this is the prob of NOT colliding, this interpretation of the claim is false for large $m$.

$\endgroup$

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.