1
$\begingroup$

I brought more precision into the way I ask this question to make it investigatable:

Assume that everyone has a First name, a Family name, a Street name and a Suburb name. If you make a four-letter acronym made of the first letters of each of those names, each following the same order, how likely is it that you will get a duplicate in a list of N such acronyms, taken at random from a population?

I am looking for a general formula in terms of the frequency distribution of the first letter of each type of name. Without loss of generality, I will assume that each type of name is strictly made up of any of the 26 characters of the usual english alphabet "A" to "Z", and that the frequency distribution of the first letter of each type of name is non-uniform (meaning that names starting with the letter "D" might be more common than those starting with the letter "Y", for example).

My question is what can you tell me about this problem? What are other assumptions that you need to devise a solution? Or what approximations, or lower or upper bounds, can you find out?

For reference, an example of a frequency distribution for the first letter of a name can be seen in the following website (it shows the top first letter for baby names in the United-States over the year 2017): http://www.nancy.cc/2018/05/14/top-first-letters-us-baby-names-2017

$\endgroup$
  • 4
    $\begingroup$ This question is unanswerable for two reasons. The first is that such data don't exist anywhere (most people don't live in any place that has a "suburb name"). But taking it as an abstract question and assuming such data, the answer depends on the full multivariate distribution of the acronyms, not just on the four univariate distributions of the initial letters. That reduces the problem to finding the chance of a duplicate when sampling (without replacement) from an arbitrary discrete distribution. Is that really the question you want answered? $\endgroup$ – whuber Nov 14 '19 at 23:46
  • $\begingroup$ Similar to the famous birthday problem, with acronyms replacing birthdays. However, much more difficult to give a formula because it is unrealistic to assume acronyms are equally likely. (Birthdays in the US are "almost" uniform across the year, ignoring Feb 29; but about 7% more common in Summer and December, and about 7% less common in late Winter/early Spring. Roughly speaking, comparing simulations based on actual birthday frequencies with a formula based on equally likely birthdays shows differences in the 2nd decimal place. In some cases, Poisson approximation gives useful results.) $\endgroup$ – BruceET Nov 15 '19 at 2:38
  • 1
    $\begingroup$ @whuber Thank you for your contribution. Yes please, take it as an abstract question where people do have a suburb name. For your second point, suffice it to assume that each type of names are independent from each other, so that their univariate distribution is sufficient to answer the question, and can we generate a formula, in terms of these univariate distribution? $\endgroup$ – Xavier Nov 15 '19 at 2:49
  • $\begingroup$ @whuber I have amended the question for better clarity. $\endgroup$ – Xavier Nov 15 '19 at 4:42
  • $\begingroup$ It is intractable, as @BruceET indicates. See stats.stackexchange.com/questions/22009/… for a simulation solution. The reduction to independent variables changes nothing, because a duplicate occurs only when each of the four letters is duplicated and we're back to the case of an arbitrary discrete distribution. $\endgroup$ – whuber Nov 15 '19 at 13:26
0
$\begingroup$

I will attempt an answer for the case where:

  • There is total independence between each type of names, so that we can ignore the multivariate components of the frequency distributions of first letters. (Meaning that, for example, we can ignore any effects whereby suburbs starting with specific letters will be made of people with predominently other specific letters, compared to others, etc...)
  • We are sampling the population with replacement.

So this answer will strictly be made in terms of the four distinct univariate distributions that describes the distribution of the first letter of each types of names.

Since the probability of obtaining a duplicate with replacement is larger than the probability of obtaining a duplicate without replacement, this gives us an upper bound. However, this approximation tends towards the exact answer as the population from which you sample tends towards infinity, or I could even say (although I am not sure how to determine this) that the approximation becomes very good as the population from which you sample becomes sufficiently large compared to $N$, or in other words, $\text{Population}>>N$.

So we have a list of $N$ acronyms. Let $A_i$ be the $i^\text{th}$ acronym, where $1 \leqslant i \leqslant N$. Let $A_{i,j}$ be the $j^\text{th}$ letter of the $i^\text{th}$ acronym, where $1 \leqslant j \leqslant 4$ (in our case anyway) and let $A_{i,j,k}$ be the probability that $A_{i,j}$ is the $k^\text{th}$ letter of the alphabet, where $1 \leqslant k \leqslant 26$.

Now (assuming that we do have replacement during our sampling, as stated above) all acronyms are taken from the same four discrete frequency distributions, so that we can write $A_{i,j,k} = \operatorname{P} \left( j,k \right)$, the common probability that the $j^\text{th}$ type of name has the $k^\text{th}$ letter of the alphabet as its first letter.

The probability that two distinct acronyms ($i_1 \neq i_2$) are the same is: \begin{equation*} \begin{split} \operatorname{P} \left( A_{i_1} = A_{i_2} \right) & = \prod_{j=1}^{4} \operatorname{P} \left( A_{i_1,j} = A_{i_2,j} \right) \text{ (assuming independence, as discussed)} \\ & = \prod_{j=1}^{4} \sum_{k=1}^{26} A_{i_1,j,k} \times A_{i_2,j,k} \\ & = \prod_{j=1}^{4} \sum_{k=1}^{26} \operatorname{P} \left( j,k \right)^2 \end{split} \end{equation*}

Taking one step further, the probability that $S$ distinct acronyms ($i_1 \neq i_2 \neq \dots \neq i_S$) are all the same is: \begin{equation*} \begin{split} \operatorname{P} \left( A_{i_1} = \dots = A_{i_S} \right) & = \prod_{j=1}^{4} \operatorname{P} \left( A_{i_1,j} = \dots = A_{i_S,j} \right) \\ & = \prod_{j=1}^{4} \sum_{k=1}^{26} A_{i_1,j,k} \times \dots \times A_{i_S,j,k} \\ & = \prod_{j=1}^{4} \sum_{k=1}^{26} \operatorname{P} \left( j,k \right)^S \end{split} \end{equation*}

Now, the probability of a duplicate in our sample is the union of the probabilities of any two pairs of acronyms within the sample being equal to each other. These are clearly not mutually exclusive, so the inclusion-exclusion formula applies: \begin{equation*} \begin{split} \operatorname{P} \Big( \bigcup_{1 \leqslant i_1 < i_2 \leqslant N} A_{i_1} = A_{i_2} \Big) & = \sum_{i_1 < i_2} \operatorname{P} \left( A_{i_1} = A_{i_2} \right) - \sum_{i_1 < i_2 < i_3} \operatorname{P} \left( A_{i_1} = A_{i_2} = A_{i_3} \right) \\ & + \dots + \left( -1 \right)^N \sum_{i_1 < \dots < i_N} \operatorname{P} \left( A_{i_1} = \dots = A_{i_N} \right) \\ & = \binom{N}{2} \underset{i_1 \neq i_2}{\operatorname{P}} \left( A_{i_1} = A_{i_2} \right) - \binom{N}{3} \underset{i_1 \neq i_2 \neq i_3}{\operatorname{P}} \left( A_{i_1} = A_{i_2} = A_{i_3} \right) \\ & + \dots + \left( -1 \right)^N \binom{N}{N} \underset{i_1 \neq \dots \neq i_N}{\operatorname{P}} \left( A_{i_1} = \dots = A_{i_N} \right) \\ & = \sum_{S=2}^{N} \left( -1 \right)^S \binom{N}{S} \underset{i_1 \neq \dots \neq i_S}{\operatorname{P}} \left( A_{i_1} = \dots = A_{i_S} \right) \\ & = \sum_{S=2}^{N} \left( -1 \right)^S \binom{N}{S} \prod_{j=1}^{4} \sum_{k=1}^{26} \operatorname{P} \left( j,k \right)^S \end{split} \end{equation*}

I have not originally thought about the implications of having replacement or not, so I suppose my question is only partially answered with the following statement:

$\displaystyle \operatorname{P} \Big( \textrm{having a duplicate among $N$ acronyms} \Big) \leqslant \sum_{S=2}^{N} \left( -1 \right)^S \binom{N}{S} \prod_{j=1}^{4} \sum_{k=1}^{26} \operatorname{P} \left( j,k \right)^S$

Does anyone have any comments about this? Did I make any mistakes in my reasoning? What about a lower bound?

| cite | improve this answer | |
$\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.