# Probability of a substring in two different strings

Say you have a 10 digit string, where A-Z and 0-9 are all allowed. Within that string, you have the substring "DAD." I'm trying to find the probability of getting a second randomized string with the same parameters as the first (10 digits, A-Z and 0-9 allowed) containing that same substring. In other words, I guess I'm wondering about the probability of that substring occurring twice in two randomized strings with the exact same parameters.

Not sure where to start with this really, can someone point me in the right direction?

• Do every A-Z and 0-9 values appear independently with the same probabilities for any character in your string? In the end you say that you want the probability of the two strings to contain the same substring. Do you know the substring? Or any substring of any size? Only 1 substring (consecutive characters) in common? You need to provide more details – Max Apr 4 '18 at 18:38
• @MaxFt The substring is "DAD." Or another substring that contains one character twice and another once. That's the only substring that needs to be in common. And yes, the values appear independently with the same probabilities for any character. – bkula Apr 4 '18 at 18:48
• Do you know the substring you are looking for in the two strings beforehand. Or does it just need to contains one character once and another twice in any order? – Max Apr 4 '18 at 18:51
• The characters in the substring need to be in the same order. So if the first substring is "DAD," the second one needs to be "DAD." If the first one is "DDA," the second one needs to be "DDA." – bkula Apr 4 '18 at 18:55
• Ok got it. Thanks for the clarification. Interesting problem indeed – Max Apr 4 '18 at 18:57

Number of possible string: $36^{10}$

The substring you look for have to start at the 1st,2nd,3rd,4th,5th,6th,7th or 8th character and the 7 other characters can be anything. Thus, $8\times 36^7$ favorable outcomes.

Note that with this method when the substring appears $n$-times in the string the outcome it will be counted $n$ times; once for each starting points of each instance of the substring.

On the other hand consider a string where the substring appears at least $n$-times in the string, this string also appears once in the set of string where the substring appears at least $n-1$-times. Call $n_i$ the number of strings containing at least i instances or the subtring:

#favorable outcomes = $n_1 - \sum_{i>1} n_i$

Now let's compute $(n_i)$ for the two possible structure of substrings (one allowing overlapping, the other does not):

Case with structure not allowing overlap (DDA,ADD):

$n_3=3*36$

3 Triplets of starting character possible: (1,4,7);(1,4,8);(2,5,8)

$n_2=10*36^4$

4+3+2+1 = 10 Couples of starting character possible: (1,4);(1,5);..(1,7);(2,5);...;(2,8);...;(5,8)

Probability = $\frac{8\times 36^{7} - 10*36^4 - 3*36}{36^{10}}$

Cases with structure allowing overlap (DAD):

$n_3=22*36$

4+3+2+1+3+2+1+2+1+1=22 Triplets of starting character possible: (1,3,5);(1,3,6);...;(1,3,8);(1,4,6);...;(4,6,8);

$n_2=21*36^4$

6+5+4+3+2+1 = 21 Couples of starting character possible: (1,3);(1,4);..(1,8);(2,4);...;(2,8);...;(5,8)

Probability = $\frac{8\times 36^{7} - 21*36^4 - 22*36}{36^{10}}$

• Double counting is a particularly problematic with this string because of overlaps. You could have DADADADADY which contains the substring 4 times. – saulspatz Apr 4 '18 at 19:26
• Arf you are right. And the overlapping possibilities depends on the structure of the substring... DDA or ADD VS DAD the 2 cases gives different overlap possibilities – Max Apr 4 '18 at 19:35
• Looks like you ended your comment prematurely. What is the rest of the sentence? – saulspatz Apr 4 '18 at 19:37
• I finished the sentence and edited my answer accordingly sorry. For structure like DAD I would to have to also add the overlapping scenario in the cases I substract. It is easily feasible as long as I am careful but I am even more interested in transforming the problem rather than brutally counting the cases now. – Max Apr 4 '18 at 19:46