4
$\begingroup$

I'm trying to find the probability that two randomly-selected letters from "average" text in a language will be the same.

For example, if my hypothetical language contains four letters which each occur on average with the following frequency:

A = 60%
B = 25%
C = 10%
D = 5%

What is the probability that selecting any two letters from a representational text will be the same?

My intuition for solving this is first to find the chance that they're different, so the sum over the probabilities that a letter is chosen and then some other letter is chosen next, over each letter in the alphabet:

(0.6  * (1 - 0.6)  + 
 0.25 * (1 - 0.25) + 
 0.1  * (1 - 0.1)  + 
 0.05 * (1 - 0.05)) = 0.565

Then the chance that they are the same:

1 - 0.565 = 0.435

Is this reasoning sound? It seems like a very basic probability problem, but I always seem to be thinking about these things in the wrong way and would appreciate a sanity check (and any pointers to materials which would help me be more confident about this kind of thing in the future!)

$\endgroup$
  • $\begingroup$ A derivative question: What frequency distribution minimizes this probability that two randomly-selected letters from "average" text in a language will be the same? Is it all letters equally common distribution? $\endgroup$ – curious_cat Mar 21 '13 at 6:49
  • 1
    $\begingroup$ @curious_cat yes a discrete uniform minimizes the probability. (This is related to the birthday problem - if you assume anything but uniform births, the probability goes up.) $\endgroup$ – Glen_b -Reinstate Monica Mar 21 '13 at 7:26
  • 1
    $\begingroup$ @curious_cat Based on Glen_b's answer, you may interpret the chance that the two letters are the same as the squared distance to the origin of the "probability vector" $(p_1, p_2, \ldots, p_n)$. The restriction that $p_1+p_2+\cdots+p_n=1$ confines this vector to a plane, yielding a geometric interpretation of your question: what point on this plane is nearest the origin? At any such point, the vector to the origin must be perpendicular to the plane. Obviously such a point is unique and just as obviously $(1,1,\ldots,1)$ is perpendicular: thus all the $p_i$ must equal one another, QED. $\endgroup$ – whuber Mar 21 '13 at 20:52
12
$\begingroup$

You got the right answer but you kind of did it the hard way.

If $L_1$ is the first letter and $L_2$ is the second letter, then

the probability is $\sum_x P(L_1=x) \times P(L_2=x|L_1=x)$.

If you assume independence (which would be the case if you were selecting from the whole population at random for each letter, for example), that's

$\sum_x P(L_1=x) \times P(L_2=x)$.

But of course then the two probability distributions will be the same. Let's call the probability that a random letter has the value $x$ "$p_x$".

That is, the overall probability = $\sum_x p_x^2$

In your case, that's 0.6*0.6 + 0.25*0.25 + 0.1*0.1 + 0.05*0.05 which comes to 0.435.

--

generalization to $k$ letters:

To find the probability that $k$ letters selected from the population are all identical:

If $L_1$ is the first letter, $L_2$ is the second letter, ..., and $L_k$ is the $k^\mathrm{th}$ then

the probability is $\sum_x P(L_1=x) \times P(L_2=x|L_1=x)\times P(L_3=x|L_1=x,L2=x)\times ... \times P(L_k=x|L_1=x,L2=x, ...,L_k=x)$.

If you assume independence (which would be the case if you were selecting from the whole population at random for each letter, for example), that's

$\sum_x P(L_1=x) \times P(L_2=x)\times ... \times P(L_k=x)$.

But of course then all the probability distributions will be the same. Let's call the probability that a random letter has the value $x$ "$p_x$".

That is, the overall probability = $\sum_x p_x^k$

$\endgroup$
  • 1
    $\begingroup$ Thanks, this is exactly the sort of answer I was hoping for. It seems that if I wanted to extrapolate to 3 letters, I would just sum over $p_x^3$ then? $\endgroup$ – Arne Roomann-Kurrik Mar 21 '13 at 17:19
  • $\begingroup$ Updated answer to cover this case. Short answer: yes. $\endgroup$ – Glen_b -Reinstate Monica Mar 21 '13 at 20:16
3
$\begingroup$

I think you can compute it by $A^2+B^2+C^2+D^2=0.6^2+0.25^2+0.1^2+0.05^2=0.435$ And $A^2$ means you will get $2A$s, $B^2$ means you will get $2B$s and so on.

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