3
$\begingroup$

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:
      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

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

For an alphabet with $Q$ symbols the answer is $$Q^N - N![z^N] \sum_{q=1}^Q {Q\choose q} \left(\sum_{p=1}^{k-1} \frac{z^p}{p!}\right)^q.$$

This is based on the observation that it is easier to count strings where no symbol appears $k$ or more times.

Observe that a string of length $N$ in an alphabet of $Q$ symbols is a partition into sets of the interval $[1,N]$ where we can have one set, two sets, etc. up to $Q$ sets. Let the number of sets be indexed by the variable $q.$ Then we have the combinatorial species

$$\mathfrak{P}_{=q} \left(\mathfrak{P}_{1\le \cdot\lt k }(\mathcal{Z}) \right).$$

This gives the generating function $$\frac{1}{q!}\left(\sum_{p=1}^{k-1} \frac{z^p}{p!}\right)^q.$$

Note however that we must choose the $q$ letters from the set of $Q$ available ones. Once these are chosen we assign them to the sets which are distinct, containing values from $1$ to $N$. This yields a factor of $${Q\choose q} \times q!$$

for a species of $$\sum_{q=1}^Q {Q\choose q} \times q! \times \mathfrak{P}_{=q} \left(\mathfrak{P}_{1\le \cdot\lt k }(\mathcal{Z}) \right).$$

Translating to generating functions we finally have $$\sum_{q=1}^Q {Q\choose q} \times q! \times \frac{1}{q!} \left(\sum_{p=1}^{k-1} \frac{z^p}{p!}\right)^q$$

which simplifies to the term given in the introduction.

Observe that when we remove the restriction on the size of the sets that make up the partition this technique will produce the generating function $$\sum_{q=1}^Q {Q\choose q} \left(\sum_{p=1}^{\infty} \frac{z^p}{p!}\right)^q \\ = \sum_{q=1}^Q {Q\choose q} (\exp(z)-1)^q = -1 + (\exp(z)-1+1)^Q = -1 + \exp(Qz).$$

Upon inspection this reveals the coefficient $$N! [z^N] (-1+\exp(Qz))= N! \times \frac{Q^N}{N!} = Q^N$$ which means we definitely have the right answer.

The formula from the introduction simplifies to $$Q^N - N![z^N] \left(-1 + \left(1+\sum_{p=1}^{k-1} \frac{z^p}{p!}\right)^Q\right).$$

which for $N\ge 1$ becomes $$Q^N - N![z^N] \left(\sum_{p=0}^{k-1} \frac{z^p}{p!}\right)^Q.$$

We observe that we have an alternate species equation here which is $$\mathfrak{S}_{=Q}(\mathfrak{P}_{\lt k}(\mathcal{Z})).$$

This corresponds to the following alternate model: instantiate a row of slots one for each of the $Q$ symbols of the alphabet. From $N$ distinct items (labeled) distribute these into the slots available on the row, where slots may be empty. The item labeled with $m$ represents the position $m$ on the string and the slot represents the letter at that position.

This is the Maple code that was used to verify the formula by computing the count in two ways, the first being total enumeration and the second using the generating function.

F :=
proc(Q, N,k)
    option remember;
    local ind, d, mset, p, res;

    res := 0;

    for ind from Q^N to 2*Q^N-1 do
        d := convert(ind, base, Q);

        mset := convert([seq(d[q], q=1..N)], multiset);

        for p in mset do
            if p[2] >= k then
                res := res+1;
                break;
            fi;
        od;
    od;

    res;
end;

EX2 :=
proc(Q, N, k)
    option remember;
    local gfA, gf;

    gfA := add(z^p/p!, p=0..k-1);

    Q^N-N!*coeftayl(gfA^Q, z=0, N);
end;

$\endgroup$
1
  • $\begingroup$ Very nice, +1.. $\endgroup$
    – Zain Patel
    Jul 22, 2015 at 22:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .