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).
First define some convenience functions that
generate
n
random strings of lengthL
based on the alphabetal
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 = ""))) }
extract the maximal substring of identical
D
s at the end of a vector of strings;NA
if such a substring does not existfind_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)) })
count the number of (identical)
D
s in that vector of substringsget_length <- function(s) lapply(s, nchar)
Generate $10^6$ random strings of length
L = 20
, and extract the maximal length of terminatingD
-only substrings.set.seed(2018) ss <- generate_random_string(20, n = 10^6) ct <- stack(get_length(find_substring(ss)))
Calculate the frequency of occurrence (amongst the $10^6$ strings) of terminating
D
-only substrings of lengthd
.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
Plot simulated and theoretical frequencies of occurrence (amongst the $10^6$ strings) of
D
-only substrings of lengthd
.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()
ACCBCC
qualify or not? $\endgroup$ – leonbloy Feb 25 '19 at 0:31