Probability of subsequence occuring in a sequence

Imagine you have an alphabet available with three letters denoted by 'A', 'B', and 'C'.

You are allowed to form a sequence (or word) with $$n_A\in\mathbf{N}$$ 'A's, $$n_B\in\mathbf{N}$$ 'B's, and $$n_C\in\mathbf{N}$$ 'C's. Each sample sequence is considered to be equally probable.

For example, set $$n_A=6$$, $$n_B=2$$, and $$n_C=2$$. Thus, the resulting sequences all have length $$n_A+n_B+n_C=10$$. An example for a sequence is then 'ABAACBACAA'.

Question: Depending on $$n_A,n_B,n_C$$, what is the probability that letters 'B' and 'C' occur (at least once) next to each other in a sample sequence, i.e., 'BC' or 'CB' occurs?

Approaches or keywords for further searches are very welcome.

• Is the occurrence of a letter at any position in the sequence independent of the occurrence of all other letters in the rest of the sequence? Jan 23, 2021 at 10:14
• Possible approach to computing how many such strings do not contain a consecutive B and C: dynamic programming. Jan 23, 2021 at 10:37
• @mhdadk Yes, all letters occur independently.
– MTP
Jan 23, 2021 at 10:40
• @MTP Do you know what the result should be ?? I found that the anwser should be $2/6$ but I'm not quite sure. I could share my attempt and check it. Jan 23, 2021 at 13:08
• You seem to ask several different questions: are the letters drawn "uniformly at random" from the alphabet or are they simply a random rearrangement of six A's, 2 B's, and 2 C's?? In the former case the answer is $2173551/(2^5\cdot3^2\cdot5^3\cdot 7)\approx 0.862504$ and in the latter case the answer is $133/210\approx 0.633.$ Neither is at all close to $2/6,$ making it likely @Fiodor1234 has found yet a third way to interpret the question.
– whuber
Jan 23, 2021 at 21:58

Simplify the notation: let there be $$b$$ copies of B, $$c$$ copies of C, and $$n\ge b+c$$ letters altogether (entailing $$a=n-b-c$$ copies of A). Switch the roles of B and C if necessary and suppose there exist some of each of those letters to ensure $$b\ge c\ge 1.$$

There are $$\binom{n}{n-b-c;\,b;\,c} = \frac{n!}{(n-b-c)!\,b!\,c!}$$ distinct, equally probable configurations $$\omega$$ of these letters ("words"). We can therefore find the chance that BC or CB is a substring of $$\omega$$ by counting the number of words in which neither BC nor CB is a substring. Let's call these the "separated" words, because no B is adjacent to a C.

Let $$\omega$$ be a separated word. Its "places" are $$n$$ in number, corresponding to the locations of the $$n$$ letters. Erasing all A's in $$\omega$$ produces a word $$\omega_{\hat A}$$ of length $$b+c$$ in the alphabet $$\{\text{B},\text{C}\}.$$ Scanning from the beginning, reinsert a single A every time a B and C are adjacent. Suppose $$k$$ such insertions are made. The possible words corresponding to any such value of $$k$$ are determined by the positions of the $$n-b-c-k$$ reinserted A's relative to the string of B's and C's, which number $$\binom{n-b-c-k + (b+c)}{b+c} = \binom{n-k}{b+c} = \frac{(n-k)!}{(b+c)!\,(n-b-c-k)!}.$$ Therefore they contribute a probability

$$p(k;n,b,c) = \frac{\binom{n-k}{b+c}}{\binom{n}{n-b-c;\,b;\,c}}= \frac{\binom{n-k}{b+c}}{\binom{n}{a;\,b;\,c}}.$$

We need to consider four similar cases depending on (a) whether B or C is the first letter in $$\{\text{B},\text{C}\}$$ that appears in $$\omega$$ and (b) whether $$k$$ is odd or even. The analysis is similar in each case.

1. Let's take the first combination, where B appears first and $$k=2m$$ is even. (Equivalently, $$\omega_{\hat A}$$ contains $$2m+1$$ runs of B's and C's.) To count the possibilities, index the B's from $$1$$ through $$b$$ in the order in which they appear and index the C's in the same manner from $$1$$ through $$c.$$ Let the first run of B's end at $$b_1,$$ the first run of C's end at $$c_1,$$ the second run of B's end at $$b_2,$$ and so on. The last run of B's is the $$m+1^\text{st}$$ run, ending at $$b_{m+1}=b,$$ and the last run of C's is the $$m^\text{th}$$ run, ending at $$c_n=c.$$

The word $$\omega_{\hat A}$$ is determined by the sequences $$(b_1,b_2,\ldots, b_m)$$ and $$(c_1,c_2,\ldots, c_{m-1}).$$ These correspond to subsets of sizes $$m$$ and $$m-1$$ within the index sets $$\{1,2,\ldots,b-1\}$$ and $$\{1,2,\ldots,c-1\},$$ respectively. Since they can be independently chosen, the total number of possibilities is $$\binom{b-1}{m}\,\binom{c-1}{m-1}.$$

2. When C appears first, the roles of B and C are switched, giving $$\binom{c-1}{m}\,\binom{b-1}{m-1}$$ for the total number of possible such words $$\omega_{\hat A}$$.

3. When $$k=2m-1$$ is odd and B is the first letter in $$\omega_{\hat A},$$ there are $$m$$ runs of each letter. The formula in (1) is now $$\binom{b-1}{m-1}\,\binom{c-1}{m-1}.$$

4. When $$k=2m-1$$ is odd and C is the first letter, switching B and C in (3) yields the same count, $$\binom{b-1}{m-1}\,\binom{c-1}{m-1}.$$

Because the word $$\omega$$ determines $$k,$$ we find the probability of separated words by summing over $$k,$$ which can be done by summing over the values of $$m$$ appearing in (1) through (4):

\begin{aligned} \Pr(\omega\text{ separated}) &= \sum_{m\ge 1} p(2m;n,b,c)\left(\binom{b-1}{m}\,\binom{c-1}{m-1} + \binom{b-1}{m-1}\,\binom{c-1}{m}\right)\\ &+ 2 \sum_{m\ge 1} p(2m-1;n,b,c)\binom{b-1}{m-1}\,\binom{c-1}{m-1}. \end{aligned}

(The sums terminate at $$c$$ or $$c-1$$ because (by definition) the Binomial coefficients $$\binom{c}{i}$$ for negative values of $$i$$ are zero.) Subtract this from $$1$$ to find the chance that $$\omega$$ is not separated: that is, that it contains at least one BC or CB.

Note that when $$n=b+c$$ there are no A's. A minor alteration of this analysis shows how to determine the null distribution of the number of runs ($$k+1$$) in the Wald-Wolfowitz Runs Test. (Surprisingly, it is hard to find a derivation of this result on the Web: all the references I find only quote it.)

Example

In the question, $$b=c=2$$ and $$n=2+2+6=10.$$ There are $$\binom{10}{6;\,2\,2}=1260$$ distinct words. The first sum in the formula (for $$k=2m$$) covers the case $$k=2$$ and contributes $$70+70.$$ The second sum in the formula (for $$k=2m-1$$) covers the cases $$k=1$$ and $$k=3,$$ contributing the terms $$252+70.$$ The total number of separated words therefore is $$462$$ and the chance of not being separated--of BC or CB occurring--therefore is $$1 - 462/1260=0.6\bar3.$$

An exhaustive listing of all $$1260$$ cases confirms this.

Computing

To avoid double precision overflow, it is essential to use logarithms in computing these values whenever $$a,$$ $$b,$$ or $$c$$ grows into three (decimal) digits. Here is an illustration in R.

#
# Chance that all B's and C's are separated.  Need n >= b+c and b, c >= 1.
#
p <- function(n, b, c) {
lp <- function(k,n,b,c)
suppressWarnings(lchoose(n-k, b+c) - lfactorial(n) +
lfactorial(n-b-c) + lfactorial(b) + lfactorial(c))

m <- c(seq_len(min(b, c)))
lp.2m <- lp(2*m, n, b, c)
sum(exp(lp.2m + lchoose(b-1,m) + lchoose(c-1,m-1)) +
exp(lp.2m + lchoose(b-1,m-1) + lchoose(c-1,m)) +
2 * exp(lp(2*m-1,n,b,c) + lchoose(b-1,m-1) + lchoose(c-1,m-1)))
}

For example, here is a plot of the separation probability as a function of $$n$$ for medium values of $$b$$ and $$c.$$ Beneath it is the code to produce it.

f <- Vectorize(function(x) p(x,200,100), "x")
curve(f(x), 1e3, 1e7, ylim=c(0,1), n=1001, log="x", lwd=2,
xlab="n", ylab=expression(paste("Pr(", omega, " separated)")),
main="Separation Probability for b=200, c=100")