# Probability that 2 of t strings of length n are equal

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?

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.

• 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.
– Alex
May 16 '17 at 19:52
• @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$. May 16 '17 at 21:40
• 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)}$?
– Alex
May 18 '17 at 5:31
• 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. May 18 '17 at 5:46
• Could you have a look at my edit pls
– Alex
May 19 '17 at 15:47

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.

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?