Probability of a given string being a substring of another string

Question

I am in interested into the following problem. We are given an alphabet $\Sigma$ of $k$ letters and a fixed string $S_1$ of length $l$ defined over $\Sigma$. Given a probability distribution $D$ over $\Sigma$, we sample another string $S_2$ with length $n$. Each letter is $S_2$ is sampled independently. We consider that $S_1$ is a substring of $S_2$ if there exists two strings $p$ and $q$ such that: $S_2 = p S_1 q$. What is the probability that $S_1$ is a substring of $S_2$? Additional assumptions could be made about D.

For a uniform distribution, it is a combinatoric problem which solution has been studied for example in: https://stackoverflow.com/questions/6790620/probability-of-3-character-string-appearing-in-a-randomly-generated-password

Would you please have any insight about how it generalizes to any distribution $D$ over $\Sigma$?

Answer 1

Let $A_t$ be the event that $S_1$ is a substring of $S_2$, $S_2=pS_1q$, where the length of $p$ is $t$. Then the probability of $\cup_t A_t$ can be found by inclusion-exclusion as $$\sum P(A_t)-\sum P(A_{t_1}\cap A_{t_2}) + \sum_{t_1,t_2,t_3} P(A_{t_1}\cap A_{t_2}\cap A_{t_3})-\dots$$ Terms like $P(A_{t_1}\cap A_{t_2})$ have probabilities that depend on how far apart the $t_i$ are, and on the structure of $S_1$. For instance,

• the probability that $01$ is a substring of a 3-letter string $xyz$ is $$P(x=0,y=1)+P(y=0,z=1)$$ which by your independence assumption is $2p_0p_1$.
• The probability that $01$ is a substring of $xyzw$ is $$P(x=0,y=1)+P(y=0,z=1)+P(z=0,w=1)-P(x=0,y=1,z=0,w=1)$$ $$=3p_0p_1-p_0^2p_1^2.$$
• A further complication arises from the cases where $S_1$ is 111 or 0101 or in general any string that is a power of another string. The probability that 111 is a substring of $xyzw$ is $$P(x=y=z=1)+P(y=z=w=1)-P(x=y=z=w=1)=2p_1^3-p_1^4.$$

Answer 2

I'm going to give complete solutions for the case when $T$, the target word (which OP calls $S_1$), has $1$ or $2$ letters in it. These should suggest the difficulties involved in finding a solution for $T$ of length $3$ or more, both because of the number of different patterns I can have for $T$, and the proliferation of recursion which is needed.

Without loss of generality, I may assume $\Sigma$ is either equal to the number of unique letters which appear in $T$ (that is, every randomly generated letter could potentially form part of $T$) or $\Sigma$ is the number of unique letters in $T$, plus $1$ (there is a random letter that can only block $T$ from forming, and never aid in forming $T$). We don't need more than one additional letter, as which irrelevant letter is picked doesn't matter to our analysis; we can lump them all together into a single irrelevant letter. So in our analysis, $T$ will be (WLOG) one of $a$, $aa$, or $ab$; and $\Sigma$ will be either $\{a, x \},$ $\{a, b \}$, or $\{a, b, x\}$, where $x$ stands for the irrelevant letter.

We will also have a probability distribution $\Bbb{P}: \Sigma \rightarrow [0, 1]$, and denote $\Bbb{P}(L) = p_L$ when $L = a, b,$ or $x$.

Finally, our $n$-letter word $S_n$ (which OP calls $S_2$) will be randomly chosen as $S_n = L_1 L_2 ... L_n$, where $L_1, L_2, L_3, ...$ are independent, identically $\Bbb{P}$-distributed, $\Sigma$-valued discrete random variables. We will also abuse the notation $S_k = L_1 L_2 ... L_k$ to refer to the first $k$ letters of $S_n$, that is, consider $S_k$ as a substring of $S_n$ when $k < n$.

1. The case $T = a$: In this case, clearly $\Sigma = \{ a, x \}$ and either we get $a$ at the very beginning of $S_n$, or we get a string of $x$'s terminating in an $a$ as the first few letters of $S_n$. If there are $n$ letters in my word, then this gives me $$p_a + p_x p_a + ... + p_x^{n-1} p_a = p_a \frac{1 - p_x^n}{1 - p_x} = 1 - p_x^n,$$ since $p_a + p_x = 1$. This makes sense; the only way I can avoid having an $a$ in my word $S_n$ is by using an $x$ for every letter.

2. The case $T = aa$: Once again, $\Sigma = \{a, x \}$. Call $q_n$ the probability that an $n$-letter string $S$ does not contain $T = aa$ (so the probability we want is $1 - q_n$). Then this string either ends in $x$ or in $xa$, so we have the recurrence $$q_n = p_x q_{n-1} + p_a p_x q_{n-2},$$ with initial conditions $q_1 = 1$, $q_2 = 1 - p_a^2$. This is a linear homogeneous recurrence relation, and unfortunately the solutions to the characteristic equation $\lambda^2 - p_x \lambda - p_x p_a = 0$ are rather messy: $$\lambda = \frac{p_x \pm \sqrt{p_x^2 + 4p_x p_a}}{2} = \frac{p_x \pm \sqrt{4p_x - 3p_x^2}}{2},$$ which are, in general, not rational. If we let $\lambda_+$ denote the root with the plus sign and $\lambda_-$ denote the root with the minus sign, then $$q_n = c_+ \lambda_+^n + c_- \lambda_-^n,$$ where $c_+, c_-$ are the solutions to the system of linear equations $c_+ + c_- = 1$, $c_+ \lambda_+ + c_- \lambda_- = 1 - p_a^2$. Then $$\Bbb{P}(S_n = pTq) = 1 - q_n = 1 - (c_+ \lambda_+^n + c_- \lambda_-^n).$$

3. The case $T = ab$, $\Sigma = \{a, b\}$: As before, let $q_n$ be the probability that $S_n$ does not contain $ab$. The only way $S_n$ ends with $b$ and does not contain $ab$ is if $S_n$ is a string of all $b$'s; otherwise, $S_n$ ends in $a$. So we get $q_n = p_a q_{n-1} + p_b^n$, and expanding out we find $$q_n = p_a^n + p_a^{n-1} p_b + ... + p_a p_b^{n-1} + p_b^n,$$ so $q_n = n p_a^n$ if the letters $a, b$ are equally likely and $$q_n = \frac{p_a^{n+1} - p_b^{n+1}}{p_a - p_b}$$ when they are not. The probability that $S_n$ contains $T$ is then $1 - q_n$, as before.

4. The case $T = ab$, $\Sigma = \{a, b, x\}$: This is as close as we get to the general case, and we are going to see some really obnoxious recursion for $q_n$, which is as in Cases 2 and 3. If $S_n$ does not contain $T$, then either $S_n$ ends in $a$ or $x$, $S_n$ ends in $xbb...bb$, or $S_n = bbbbbbb...bbbb$ is a string of $n$ $b$'s. So our recurrence is now $$q_n = (p_a + p_x) q_{n-1} + p_b p_x q_{n-2} + p_b^2 p_x q_{n-3} + ... + p_b^{n-2} p_x q_1 + p_b^{n-1} p_x + p_b^n,$$ which can be solved by similar techniques as before, but is rather messy.

From reading this account the complexity of giving a general answer for $T$ of arbitrary length and structure should, I hope, be clear.

Answer 3

In the most generic setting, the problem may be solved with Knuth-Morris-Pratt algorithm.

Consider a graph $G$ on $l+1$ vertices numbered from $0$ to $l$, such that the vertex $k$ corresponds to the prefix of $S_1$ of size $k$. Each such vertex has $\Sigma$ outgoing arcs from it, each marked by some alphabet letter. Essentially, this graph is a deterministic finite automaton, such that after going with the string $S_2$ through its arcs you end up in a vertex that corresponds to the largest suffix of $S_2$ that is also a prefix of $S_1$.

This automaton could as well be perceived as a Markov chain, that is transition with the letter $c$ has a fixed known probability to happen. Then, the problem is equivalent to finding the probability of not ever getting into the last vertex after having a walk that starts in the vertex $0$ and has a length $n$.

Let $A$ be the stochastic matrix of this chain. Then the $j$-th element of the $i$-th row of $A^n$ equates to the probability of ending up in $j$-th state after making $n$ steps starting in the state $i$. If we redirect all transitions from the state $l$ into itself, we will turn it into "devil state" which forever traps you once you get there.

Now, the question essentially asks to compute the probability of not getting into the devil state after $n$ steps. This probability is equal $1-p$, where $p$ is the $l$-th element of the $0$-th row of $A^n$.

It's not really a formula, but it's a universal and somewhat efficient way to computationally solve these kind of problems for any specific string.

P.S. I know that there is an explicit formula for the expected time of finding $S_1$ to be a substring of $S_2$ for the first time. Unfortunately, I'm not sure whether it can be used for probabilities.