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$
  • $\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$
  • $\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$
  • $\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$ – James Bender Mar 27 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 at 15:04
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$
  • $\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

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.