2
$\begingroup$

I know this is easy, but my high school maths has failed me.

Question: I generate an 8 letter random string. What is the probability that within these 8 letters I will find a particular 4 letter word?

Each letter is A-Z. Repeats are allowed. What are the chances my string will contain the word "ABCD" for example?

EDIT: To clarify.. I do care about ordering. I want to know if "ABCD" occurs within my randomly generated string. But I don't care if "ABDC" occurs. In other words I want to know the probability of A followed by B followed by C followed by D occurring.

If it helps to understand why I am asking this. Our software generates 8 letter random strings which are used for logins to a web site. Very occasionally, these 8 letter random strings contain swear words. I want to know how to calculate the probability of a particular swear word occurring in a randomly generated 8 letter string.

$\endgroup$
2
  • $\begingroup$ Your question is not very clear. Should the sentence string just contain an A,B,C and D or should they be together in the right order? $\endgroup$
    – Marc
    May 31 '14 at 8:54
  • 1
    $\begingroup$ Marc I thought it was pretty clear. In my world the word "ABCD" means A followed by B followed by C followed by D. $\endgroup$
    – richb
    May 31 '14 at 10:16
1
$\begingroup$

The specific word in the 8 letter string can be found starting on places 1,2,3,4,5. The other letters in each combination can be chosen freely. Since there is a total of $26^8$ different combinations we get $$ 5\frac{26^4}{26^8} = \frac{5}{26^4}. $$

$\endgroup$
2
  • $\begingroup$ Isn't this giving me the probability of the four letters in any order? $\endgroup$
    – richb
    Jun 1 '14 at 7:25
  • $\begingroup$ Duh. Nope. This seems right.. thank-you. $\endgroup$
    – richb
    Jun 1 '14 at 7:42
3
$\begingroup$

Marc's answer is almost correct, but for one point; the numerator counts the occurrence of ABCDABCD twice. (As Graham Kemp pointed out. )


To elaborate: if I let $n(i)$ be the number of string patterns with ABCD starting at the $i$-th letter, then

$n(1) = n(2) = n(3) = n(4) = n(5) = 26^4$

(and $n(6) = n(7) = n(8) = 0$ )

but as ABCDABCD is counted in both $n(1)$ and $n(5)$, we must subtract by 1 to compensate.

So the end result would be

$$\frac{\left(\sum\limits_{i=1}^8{n(i)}\right)-1}{26^8}=\frac{5\times26^4-1}{26^8}$$ which is almost, but not quite, equal to the aforementioned answer. (Albeit probably close enough for realistic purposes...)


On the other hand, if we were looking for the expected value of the occurrence of ABCD, then we shouldn't need to subtract to compensate. (I think)


For longer strings, we would need to subtract duplicates, then add back to compensate for triplets, and so on, and the general formula I'm not sure how to write...

$\endgroup$
2
  • $\begingroup$ Doesn't this still triple count strings "MAMA", and quintuple count strings like "AAAA"? It seems like a general formula should be dependent on the nature of the string itself as well. $\endgroup$ Mar 27 '19 at 13:24
  • $\begingroup$ As mentioned in Graham Kemp's answer about double pairs, and as I tried to mention for longer strings--yes, higher multiplicities would require additional care. My guess is that transition matrices may be the way to go for generalization, but can't see the way off hand... $\endgroup$
    – yybtcbk
    Apr 1 '19 at 15:04
1
$\begingroup$

The answer is 2284879/208827064576 if no letters are repeated. This is roughly $5\times 10^{-12}$ less than Marc's answer 5/456976. It is also yybtcbk's answer.

To solve variants of this problem you may use this python code.

######## compile word to dfa

alphabet = 'abcdefghijklmnopqrstuvwxyz'

def bitstoint(bs):
    n = 0
    for b in reversed(bs):
        n = 2*n + b
    return n

def compile_word_to_dfa_that_matches_it_as_substring(word):
    """
    The state of the automaton must tell, for each i, whether the
    input so far ends in word[:i].

    If the input so far ends in word[:i], and the next character is
    indeed word[i], then the input so far ends in word[:i+1];
    otherwise it doesn't.

    As an exception to this rule, if the input so far ends in word,
    then this will forever be the state of the automaton.
    """
    assert set(word) <= set(alphabet)
    N = 2**(len(word) + 1)  # all states are 0 <= s < N; (s & (1 << i)) is valid for 0 <= i <= len(word)
    def transition(s, c):
        if s == N-1:
            return N-1  # accepting state
        if s & (1 << (len(word)-1)) and word[-1] == c:
            return N-1
        return 1 + 2*bitstoint([
            int(s & (1 << i) and word[i] == c)
            for i in range(len(word))
        ])
            
    transition_matrices = {
        c: [[int(transition(i, c) == j) for j in range(N)] for i in range(N)]
        for c in alphabet
    }
    initial_state = 1
    final_state = N-1
    return (transition_matrices, initial_state, final_state)

######## (optional: optimize the dfa)


######## probability calculation

import numpy as np

def calculate_acceptance_probability(dfa, q, t):
    transition_matrices, initial_state, final_state = dfa
    Aq = sum([np.array(transition_matrices[c])*q[c] for c in alphabet]).transpose()
    N = Aq.shape[0]
    v = np.array([int(i == initial_state) for i in range(N)])
    for _ in range(t):
        v = np.dot(Aq, v)
    return v[final_state]

######## demo

word = 'joel'  # the 4 letter word
t = 8          # the total number of letters

#number_type = float
import fractions
number_type = fractions.Fraction


dfa = compile_word_to_dfa_that_matches_it_as_substring(word)
q = {c: number_type(1)/len(alphabet) for c in alphabet}
answer = calculate_acceptance_probability(dfa, q, t)

print(f"The accepted stackexchange answer: {number_type(5)/26**4}")
print(f"The exact answer with automaton: {answer}")


""" demo output

box% python -i main.py 
The accepted stackexchange answer: 1.094149364518049e-05
The exact answer with automaton: 1.094148885652915e-05
>>>

box% python -i main.py
The accepted stackexchange answer: 5/456976
The exact answer with automaton: 2284879/208827064576
>>>

"""
$\endgroup$
7
  • $\begingroup$ Thank-you for your time looking at this. Your criteria "if no letters are repeated" doesn't answer the question which states repeats are allowed. Does it change your approach substantially? $\endgroup$
    – richb
    Nov 20 '20 at 0:23
  • $\begingroup$ Just replace 'joel' by e.g. 'aaba'. $\endgroup$ Nov 20 '20 at 8:23
  • $\begingroup$ When I said "if no letters are repeated", I was referring to the string 'joel' here, not the random string. $\endgroup$ Nov 20 '20 at 8:25
  • $\begingroup$ Hi joel sorry for my ignorance. I'm interested in your solution. I don't understand your reply. I don't know what you mean by just replace 'joel' by 'aaba'. Repeats are allowed? Or not? Probably my misunderstanding of your solution. $\endgroup$
    – richb
    Nov 20 '20 at 8:48
  • $\begingroup$ Repeats in the random string are allowed. $\endgroup$ Nov 20 '20 at 9:00
0
$\begingroup$

For the numerator: Count how many places the word can start, multiplied by the count how many values the remaining $4$ letters can take on. Exclude the one case where you've double counted (the word appearing twice.)

For the denominator: just count how many possible strings there are in total. $8$ places each able to take on $26$ values.


Note: this assumes the word is not a double pair, like DODO, in which case you would have to exclude the second counts of the strings containing DODODO.

$\endgroup$
0
$\begingroup$

Let's consider all the possible blocks ABCD in that order that could appear in an 8-letter word: this is the same as the number of ordered blocks of 4 digits out of 8 digits, i.e. $8C4$. For each of these blocks you can combine the other 4 letters in $26^4$ ways, for a total of $$8C4 \times 26^4 $$. If you don't care about the ordering of the letters $ABCD$ , then you want the number of permutations of 4 letters, for a total of $$8P4\times 26^4 $$

$\endgroup$
8
  • $\begingroup$ It is not that simple. You could also have a string of 8 letters which only contains 3 of the letters in the specified word for example. $\endgroup$
    – Marc
    May 31 '14 at 8:42
  • $\begingroup$ But I assume the OP wants to have exactly the 4 letters A,B,C,D. $\endgroup$
    – user99680
    May 31 '14 at 8:45
  • 1
    $\begingroup$ Yes, but then in the complement you should also include combinations that contain for example only three of the four specified letters and not only the combinations that contain none of the four letters. Moreover, if you use this approach, what happens if the specified word contains the same letter multiple times? $\endgroup$
    – Marc
    May 31 '14 at 8:48
  • $\begingroup$ O.K, I jumped in too quickly without reading carefully; let me see. $\endgroup$
    – user99680
    May 31 '14 at 8:51
  • 1
    $\begingroup$ @marc: I just rewrote a direct (and I think easier) approach. $\endgroup$
    – user99680
    May 31 '14 at 8:56
0
$\begingroup$

ABCD is not really a particular word as it is not in the English dictionary, it is a particular sequence of letters. One thing is, calculating what is the chance of hitting a particular n length letter sequence inside an m length random letter sequence, entirely different matter is calculating what is the chance of containing an n letter word inside an m length random character sequence. The latter would also depend on how many n letter words are in the English dictionary.

Something like what Marc suggests multiplied by the number of 4 letter words in the English dictionary.

$\endgroup$

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.