3
$\begingroup$

Given t bit-strings of length n that are generated randomly. What is the probability that at least 2 of these strings are equal. I've seen someone who wrote that the probability is $ \le \frac{t^2}{2^n}$

The reasoning is that you have $t$ options to choose the first string. The $t$ options to choose the second string, and given a string chosen at the first stage, the probability that the other chosen string is equal to the first one is $\frac{1}{2^n}$. The you sum all these options of choosing 2 equal string ($t^2$) and you get $ \frac{t^2}{2^n}$ This just seems wrong because for each such choice of 2 strings there are many other options to the other strings, but I can't find a proof to show that it is wrong.

Does this reasoning make sense?

$\endgroup$
2
$\begingroup$

We can actually be more precise and say that the probability is at most $\frac{\binom t2}{2^n}$.

For $1 \le i < j \le n$, let $A_{ij}$ be the event that the $i^{\text{th}}$ string is equal to the $j^{\text{th}}$ string. Then $\Pr[A_{ij}] = \frac{1}{2^n}$, because the $j^{\text{th}}$ string is equally likely to be any of $2^n$ possibilities, one of which is equal to the $i^{\text{th}}$ string.

We have two equal strings if any of the $\binom t2$ events $$A_{12}, A_{13}, A_{14}, \dots, A_{t-1,t}$$ occur. If these events were all disjoint - no two could happen at the same time - the probability that any of them occur would be exactly $\binom t2 \cdot \frac1{2^n}$. They're not all disjoint; if the $1^{\text{st}}$ string is equal to the $2^{\text{nd}}$, and the $3^{\text{rd}}$ string is equal to the $4^{\text{th}}$, then $A_{12}$ and $A_{34}$ both occur. So this is not the actual probability we want.

However, it's still an upper bound. For any two events $A$ and $B$, we have \begin{align} \Pr[A \text{ or } B] &= \Pr[A] + \Pr[B] - \Pr[A \text{ and }B] \\ &\le \Pr[A] + \Pr[B] \end{align} and by induction, we can show that for any $m$ events $A_1, A_2, \dots, A_m$, we have $$\Pr[A_1 \text{ or } A_2 \text{ or } \dots \text{ or } A_m] \le \Pr[A_1] + \Pr[A_2] + \dots + \Pr[A_m].$$ This is known as the union bound. In our case, it says that \begin{align} \Pr[A_{12} \text{ or } A_{13} \text{ or } \dots \text{ or } A_{t-1,t}] &\le \Pr[A_{12}] + \Pr[A_{13}] + \dots + \Pr[A_{t-1,t}] \\ &= \binom t2 \frac1{2^n}. \end{align}

We can find the exact probability by first finding the probability that all $t$ strings are different. This is $$\frac{(2^n-1)(2^n-2) \cdots (2^n-t+1)}{(2^n)^{t-1}}.$$ (If all strings must be different, there are $2^n-1$ possibilities for the second string, $2^n-2$ for the third, and so on.) So the exact answer is $1 - \frac{(2^n-1)(2^n-2) \cdots (2^n-t+1)}{(2^n)^{t-1}}$.

But the union bound is often useful when the exact answer cannot be found: for example, if the dependence between the events is very hard to describe. Even here, the bound $\binom t2 \frac1{2^n}$ may be more useful than an exact answer: it makes it much easier to see that if $t$ is much smaller than $2^{n/2}$, then $\binom t2$ is much smaller than $2^n$, and so the probability that any two strings are equal is very small.

$\endgroup$
6
  • $\begingroup$ I only have concern about the order - since the denominator, $\binom{2^n -1 +t }{t}$ does not consider the order of selected strings, and I'm not sure how to account for it. Though the problem seems to imply that order does not matter. $\endgroup$
    – Alex
    May 16 '17 at 19:52
  • $\begingroup$ @Alex - I've edited my answer to have the correct exact answer. Indeed, $\binom{2^n-1+t}{t}$ cannot possibly be the correct denominator, since the total number of possibilities for the $t$ strings is $2^{nt}$, so the correct denominator must be a divisor of $2^{nt}$: a power of $2$. $\endgroup$ May 16 '17 at 21:40
  • $\begingroup$ The question says 'generated randomly', so it's not quite clear if the order matters; my answer holds if the order doesn't matter. Could you explain how you got $2^{n(t-1)}$? $\endgroup$
    – Alex
    May 18 '17 at 5:31
  • $\begingroup$ For each of the $t-1$ remaining strings after the first, we get a factor of $2^t$ in the denominator. I'm assuming "generated randomly" to mean "each string is uniformly and independently chosen from all $2^n$ strings" and don't see what other distribution we could reasonably take. $\endgroup$ May 18 '17 at 5:46
  • $\begingroup$ Could you have a look at my edit pls $\endgroup$
    – Alex
    May 19 '17 at 15:47
2
$\begingroup$

This reminds of the Birthday Problem!

In a room with $n$ students, what is the probability that at least two students share the same birthday? The probability that two students share a birthday is $\frac{1}{365}$, but you have to compare all pairs of n students.

To make an analogy, the probability that two strings are equal is $\frac{1}{2^n}$, but you have to compare all pairs of t strings.

$\endgroup$
1
$\begingroup$

I think this probability is $1-\frac{\binom{2^n}{t}}{\binom{2^n -1 +t}{2^n -1}}$. Essentially this means 1- probability to have all strings different. The numerator is all different strings. The denominator is all cases of selecting t out of $2^n$ with repetitions.

EDIT:

OK @MishaLavrov's solution $\frac{\binom{2^n}{t} t!}{2^{nt}}$ is better. What my solution gives is $\frac{\text{number of ways to get $t$ unique strings length $n$ from a set of $2^n$ strings, order does not matter}}{\text{number of ways to get $t$ strings length $n$ from a set of $2^n$ strings, order does not matter}}$.

For example, if $t=3$, one possible denominator would be $aba, aab, baa$ counted as one. In the numerator we can have $abc,bac,...,cba$ all counted as one outcome.

My confusion is that, even if strings are 'generated randomly', do we account for repeated sets or not?

$\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.