3
$\begingroup$

Let's say we think of a specific $12$ letter word. How many times on average will that particular word appear in a string of $1$ quintillion ($10^{18}$) completely random letters (i.e., uniform/equal probability for each letter A-Z at each position, with no preference for vowels or any other letter)?

Also, what will the actual frequency distribution look like? What would be the formula for that PDF (probability density function) distribution?

For simplicity, we should consider that each incidence is non-overlapping, as most words do not start with the sam letter(s) they end with.

$\endgroup$
  • 1
    $\begingroup$ I think you need to define a "word" a little more precisely: is "aaa" a three-letter word or three one-letter words? $\endgroup$ – user75138 May 20 '16 at 11:17
  • 1
    $\begingroup$ @Bey: do I really need to explain what a "12-letter word" is??? $\endgroup$ – Kelvin May 20 '16 at 15:20
  • 2
    $\begingroup$ Kelvin, to appreciate @Bey's comment, consider a smaller version of your question where the word has just two letters and the string is just ten letters long. If the word is "aa" and the string happens to be "baaacqxdia", then does "aa" appear once or twice? Your answer matters because (a) it affects the solution and (b) it affects how one finds a solution. BTW, in the US one quintillion is $10^{18}$, not $10^{21}$ (and it's $10^{30}$ in the UK). Although clearly the solution method won't depend on the exact value of this number, you ought to remove the inconsistency. $\endgroup$ – whuber May 20 '16 at 15:38
  • 2
    $\begingroup$ Consider the real English word "tot". Does "tot" appear in the string "abtwetototnxwtot" twice or three times? $\endgroup$ – David Kent May 20 '16 at 16:54
  • 2
    $\begingroup$ FWIW, a word does not have to start and end with the same letter to create overlaps: it is only necessary that some suffix of the word match some prefix, as in "ionization" or "tergiversater." $\endgroup$ – whuber May 20 '16 at 20:16
1
$\begingroup$

For any 12 letter group, the odds of being the specific word of interest is $p={\frac{1}{26}}^{12}$.

The odds of finding exactly 1 in $N=10^{21}$ random letters is $(N-12)\cdot p^1 \cdot (1-p)^{N-12}$, as there are N-11 possible starting locations.

The odds of finding exactly 2, assuming the last n letters overlap the first n (n may obviously be 0), is $\frac{(N-11) \cdot (N-23+n)}{2} \cdot p^2 \cdot (1-p)^{N-24+n}$.

In general for z instances of g-letter length word, the discrete pmf is $p(z)=\frac{1}{z!} \cdot \prod_{i=1..z}\left({N-(g-n) \cdot i+1}\right)\cdot p^z \cdot (1-p)^{(N-(z+1) \cdot g+z \cdot n)}$.

Also $p(0)=(1-p)^{(N-g)}$

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ Something looks wrong. To check, let's apply your formula to the tractable case of $2$ letters $a$ and $b$, the two-letter word $aa$, and $N=4$. I compute $p=(1/2)^4$ and, for finding exactly one occurrence (not allowing overlaps), I compute $$(N-2)p^1(1-p)^{N-2}=2(1/16)(15/16)^2\approx 0.11.$$ However, exhaustive enumeration gives $$aabb,aaba,baab,abaa,bbaa,$$ each with probability $1/2^4$, for a total chance of $5/16\approx 0.3125$. (It's unclear whether you count instances like $aaab$ as one or two occurrences: they would only add to the chances.) I get an even larger value for $ab$. $\endgroup$ – whuber May 20 '16 at 19:13
  • 3
    $\begingroup$ @whuber one thing that's wrong is that he's assuming that the probability of finding a word of interest at each position is independent of every other position. I think we both answered a similar question that appropriately takes that into account? $\endgroup$ – Neil G May 20 '16 at 19:35
  • 1
    $\begingroup$ @whuber, thanks for looking at my answer! I believe that p should be (1/2)^2 for a 2-letter word, which gives us 0.4219, still above 0.3125 (I'll try to track down the issue!) but not so bad as 0.11! In any case, I believe that setting n=0 gets rid of the overlap cases. $\endgroup$ – MikeP May 20 '16 at 20:20
  • 1
    $\begingroup$ Sorry--you're right about $p$. I wouldn't expect your solution to be perfect, because it doesn't model the possibility of overlaps correctly, but the idea nevertheless ought to lead to an excellent approximation. It would nevertheless be nice to understand the discrepancies that crop up in small examples. $\endgroup$ – whuber May 20 '16 at 20:23
  • 1
    $\begingroup$ @whuber Here it is! stats.stackexchange.com/questions/202132/… and this one stats.stackexchange.com/questions/21825/… $\endgroup$ – Neil G May 20 '16 at 23:12

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.