0
$\begingroup$

I am interested in characterising the probability for identifying a substring at the end of a string.

Consider a string of length $L$ that is based on a 4-letter alphabet. For example, for $L = 10$ we could have "CDACCACBBB". All letters are equally likely to occur.

I'd like to know the probability for finding a substring consisting of only identical letters of a pre-specified length $1 \leq d \leq L$ at the end of the string. So in above example, what is the probability of finding e.g. a "BBB" (for fixed $d = 3$), "BBBB" (for a fixed $d = 4$), "BBBBB" (for a fixed $d = 5$), and so on, at the end of the string?

I am unsure how to approach this. The number of possible strings is $4^L$. But what about the number of possible substrings? I know that a substring of length $d$ has to start at position $L - d + 1$.

Ultimately I'd like to get a probability as a function of substring length for a given string length $L$: $Pr(d | L)$.

I'd appreciate any help.


I am able to approach the problem through simulation (using R).

  1. First define some convenience functions that

    1. generate n random strings of length L based on the alphabet al

      generate_random_string <- function(L, n = 100, al = LETTERS[1:4]) {
          lapply(setNames(L, L), function(x)
              replicate(n, paste0(sample(al, x, replace = T), collapse = "")))
      }
      
    2. extract the maximal substring of identical Ds at the end of a vector of strings; NA if such a substring does not exist

      find_substring <- function(s)
          lapply(s, function(x) {
              m <- regexpr("(?<=[ABC])D{1,}$", x, perl = T)
              replace(rep(NA, length(s)), m > -1, regmatches(x, m))
          })
      
    3. count the number of (identical) Ds in that vector of substrings

      get_length <- function(s) lapply(s, nchar)
      
  2. Generate $10^6$ random strings of length L = 20, and extract the maximal length of terminating D-only substrings.

    set.seed(2018)
    ss <- generate_random_string(20, n = 10^6)
    ct <- stack(get_length(find_substring(ss)))
    
  3. Calculate the frequency of occurrence (amongst the $10^6$ strings) of terminating D-only substrings of length d.

    tbl.sim <- prop.table(table(ct$value))
    tbl.sim
    #
    #           1            2            3            4            5            6
    #7.502034e-01 1.873114e-01 4.674669e-02 1.168266e-02 3.077971e-03 7.254073e-04
    #           7            8            9           10           11
    #1.603110e-04 6.813218e-05 1.603110e-05 4.007775e-06 4.007775e-06
    

    Compare frequencies with those according to @JeremyDover's answer:

    prob <- function(d) 3 / 4 * (1/4) ^ (d - 1)
    tbl.th <- prob(setNames(as.numeric(names(tbl.sim)), names(tbl.sim)))
    tbl.th
    #           1            2            3            4            5            6
    #7.500000e-01 1.875000e-01 4.687500e-02 1.171875e-02 2.929688e-03 7.324219e-04
    #           7            8            9           10           11
    #1.831055e-04 4.577637e-05 1.144409e-05 2.861023e-06 7.152557e-07
    
  4. Plot simulated and theoretical frequencies of occurrence (amongst the $10^6$ strings) of D-only substrings of length d.

    library(tidyverse)
    merge(stack(tbl.sim), stack(tbl.th), by = "ind") %>%
        transmute(
            d = as.numeric(as.character(ind)),
            freq.sim = values.x,
            freq.th = values.y) %>%
        gather(key, freq, -d) %>%
        ggplot(aes(d, -log10(freq), colour = key)) +
        geom_line() +
        geom_point() +
        theme_bw()
    

enter image description here

$\endgroup$
  • 1
    $\begingroup$ You mean to find the substring of consecutive letters only at the end of the string? For, example, for $d=2$, would the string ACCBCC qualify or not? $\endgroup$ – leonbloy Feb 25 at 0:31
  • $\begingroup$ @leonbloy I'm interested in the probability for finding the substring of identical letters only at the end of the string. So in the example you give, I'd like to characterise the probability for finding "CC" at the end of string "ACCBCC" (which should be the same as the probability for finding "AA", "BB", or "DD" at the end of the same string). Ultimately, I'd like to know the probability for different lengths $d$, given a string length $L$. $\endgroup$ – Maurits Evers Feb 25 at 0:48
  • 1
    $\begingroup$ If I understand correctly, the probability should be $(1/4)^{d-1}$. For each of the $4$ letters, there is a $(1/4)^d$ probability that the last $d$ places in the string all have that letter. Multiplying $(1/4)^d$ by $4$ gives $(1/4)^{d-1}$. $\endgroup$ – Mike Earnest Feb 25 at 1:08
  • 1
    $\begingroup$ @MikeEarnest is correct as he has stated the problem, but he is finding the probability that the last $d$ places are identical, allowing the possibility that the number of identical places at the end of the string is larger than $d$. Multiplying the given probability by $\frac34$ ensures that the terminating string is exactly $d$ places long. $\endgroup$ – Jeremy Dover Feb 25 at 2:01
  • $\begingroup$ @JeremyDover That seems to be the correct answer. Somehow I had thought that the probability would depend on the length of the original string $L$. I've added a simulation-based approach (in R) that agrees with your theoretical probability of $\frac{3}{4} (\frac{1}{4})^{d-1}$. I might have a thick moment here, but would you mind elaborating on where the factor of $3/4$ comes from and perhaps post this as a full solution so I can upvote and close the question? Many thanks. $\endgroup$ – Maurits Evers Feb 25 at 3:43
2
$\begingroup$

Given a string of length $L$ over an alphabet of $a$ characters ($a=4$ is the case for the OP, but it's as easy to solve in general), the OP asks the probability that the last $d$ characters in the string are identical for $1 \le d \le L$, and the last $d+1$ characters are not identical, if $d < L$.

Our sample space is the set of all strings, which has size $a^L$, as we need to choose one of $a$ characters for each of $L$ positions in the string.

Suppose first that $d=L$. Then all characters in the string must be identical. There are exactly $a$ such strings: the first character can be picked arbitrarily, and then all others must match it. Therefore the probability of this occurring is $\left(\frac1a\right)^{L-1} = \left(\frac1a\right)^{d-1}$.

If $d < L$, then we pick the last character of the string first, which can be done in $a$ ways. Then the $d-1$ predecessors to this character must match it, which can be done in one way. Since $d < L$, there is a character immediately preceding this terminating run of $d$ identical characters, and this character must not match the last character, otherwise our terminating identical string would be longer than $d$. This can be chosen in $a-1$ ways. The remaining $L-d-1$ characters in the string can be chosen arbitrarily, for which there are $a^{L-d-1}$ choices.

Therefore the probability of our string ending with exactly $d$ identical characters with $d < L$ is $$\frac{a(a-1)a^{L-d-1}}{a^L} = \frac{a-1}{a^d}$$

$\endgroup$
  • $\begingroup$ Thank you very much for the detailed explanation @JeremyDover. $\endgroup$ – Maurits Evers Feb 25 at 22:40

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.