Probability of substring occurring at the end of a string

Question

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()
   

Answer 1

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}$$