This is an addendum to a previous question found here.
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 k OR MORE 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.)
The solution for exactly k similar characters was found as follows:
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:
- ABC: bins = {A: 1, B: 1, C: 1}. d = 0
- AAA: bins = {A: 3, B: 0, C: 0}. d = 1
- AAC: bins = {A: 2, B: 0, C: 1}. d = 2
- Examples:
- 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
Now I'm wondering how you add up the probabilities of getting k similar characters or better, as in
P(k) + P(k + 1) + ... P(k = N)
My confusion arises because this isn't as simple as recalculating with an incremented k until k=N... in the example string AAABC, k = 3, if you increment k to k = 4, you either swallow a B or a C to make AAAAC or AAAAB.
I'm unsure how to factor this in to the final solution.
Thanks so much in advance for your help.