4
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – mhdadk
    Jan 23, 2021 at 10:14
  • $\begingroup$ Possible approach to computing how many such strings do not contain a consecutive B and C: dynamic programming. $\endgroup$
    – fblundun
    Jan 23, 2021 at 10:37
  • $\begingroup$ @mhdadk Yes, all letters occur independently. $\endgroup$
    – MTP
    Jan 23, 2021 at 10:40
  • $\begingroup$ @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. $\endgroup$
    – Fiodor1234
    Jan 23, 2021 at 13:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – whuber
    Jan 23, 2021 at 21:58

1 Answer 1

6
$\begingroup$

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.

Figure

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")
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.