7
$\begingroup$
  • I have an alphabet: {A, B, C}.
  • I'm randomly generating strings of length N from that alphabet.

    Examples: Examples: N=5, AACBC, AAAAA, BBCAA

  • What is the likelihood that exactly k characters of that string are the same? (k <= N)
    (k corresponds to the maximum number of similar characters...
    Example: With string AABCAAA: N=7, k=5 because there are 5 A's.
    String AABBCC: N=6, k=2 because there are equally-sized groups of A's, B's, and C's.)

Initially, my solution looked like this:
P(k characters are the same) = $(\frac{1}{3})^k * (\frac{2}{3})^{n-k}$
Until I realized that this solution wasn't robust enough-- it doesn't matter WHICH characters are the same, only that k characters are the same.

Thanks so much in advance for your help.

$\endgroup$
  • $\begingroup$ Not only that, you will have to consider permutations of each string. Hint: Since there are three categories instead of two, you can't use the binomial coefficient. $\endgroup$ – true blue anil Jul 22 '15 at 3:49
  • $\begingroup$ Did you mean $N=6$ for AABBCC? $\endgroup$ – user940 Jul 22 '15 at 3:51
  • $\begingroup$ @ByronSchmuland yes I meant N = 6! Thanks for pointing that out. $\endgroup$ – jdmcpeek Jul 22 '15 at 7:10
  • $\begingroup$ Do you mean "at least $k$ characters of the string will be the same"? $\endgroup$ – DanielV Jul 22 '15 at 8:04
  • $\begingroup$ @DanielV I mean exactly k characters. $\endgroup$ – jdmcpeek Jul 22 '15 at 8:13
1
$\begingroup$

Let k, l, m be the # of occurrences for different letters in decreasing order.

Using the multinomial distribution formula, to illustrate,

for string AAABBC, Pr = $\frac{6!}{3!2!1!}\cdot\left(\frac{1}{3}\right)^6$

and for string AABBCC, Pr = $\frac{6!}{2!2!2!}\cdot\left(\frac{1}{3}\right)^6$

In general, Pr = $\frac{N!}{k!l!m!}\cdot\left(\frac{1}{3}\right)^N$, k+l+m = N

continued...

I have taken that you want probabilities for particular values of k. For k = 3 and N = 6, for example, you will need to sum up probabilities for permutations of 3-3-0 (3#s) & 3-2-1 (6#s)

edited by the questioner...
The final solution comes down to this. Imagine that we have three bins, each representing the number of times each character appears in a string. For AAABC, the bins would be {A:3, B:1, C:1} For:

  • N = the length of the string,
  • k = the maximum bin value (there can be ties),
  • l = the next bin value,
  • m = the last bin value,
  • d = the number of bin values that are different from k's bin value (max 2)
    • Examples:
      1. ABC: bins = {A: 1, B: 1, C: 1}. d = 0
      2. AAA: bins = {A: 3, B: 0, C: 0}. d = 1
      3. AAC: bins = {A: 2, B: 0, C: 1}. d = 2
  • C = the number of letters in our alphabet (always 3),

Pr = $\frac{N!}{k!l!m!}\cdot\left(\frac{1}{3}\right)^N \cdot\frac{C!}{(C - d)!}$, k+l+m = N

$\endgroup$
  • $\begingroup$ I'm not sure if this works for a few cases I've been using to test on. For example, if I generate a three-letter string (N=3), the probability that two of them are the same (k = 2) is $\frac{6}{9}$. I know this because I counted it out by hand. When I apply the multinomial distribution formula: $\frac{3!}{2!*1!*0!} * (\frac{1}{3})^3 = 1/9$ $\endgroup$ – jdmcpeek Jul 22 '15 at 7:24
  • $\begingroup$ Read my "continued" portion. Since 2-1-0 has 6 permutations, you will need to multiply by 6, and you will get the correct answer. $\endgroup$ – true blue anil Jul 22 '15 at 8:00
  • $\begingroup$ Do you mean that I multiply by the number of permutations of k? Like: Pr = **$\frac{N!}{k!l!m!}\cdot\left(\frac{1}{3}\right)^N * k!$ $\endgroup$ – jdmcpeek Jul 22 '15 at 8:08
  • $\begingroup$ Also, what about in the case of 2 cards that are both different? $\frac{2!}{1!*1!*0!} * (\frac{1}{3})^2 * 2! = 4/9$, which isn't the correct probability. $\endgroup$ – jdmcpeek Jul 22 '15 at 8:10
  • $\begingroup$ Not multiply by k!, there can only be 3 patterns for N = 3: all identical (1 permutation), 2 identical (3 permutations) and all different (6 permutations). Thus for the 1-1-0 case, you need to multiply by 3,(which arises as 3!/2!) not 2! $\endgroup$ – true blue anil Jul 22 '15 at 8:39

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.