4
$\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.

Improve this question
$\endgroup$
12
  • 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
    Commented May 20, 2016 at 11:17
  • 1
    $\begingroup$ @Bey: do I really need to explain what a "12-letter word" is??? $\endgroup$
    – Kelvin
    Commented May 20, 2016 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 ♦
    Commented May 20, 2016 at 15:38
  • 2
    $\begingroup$ Consider the real English word "tot". Does "tot" appear in the string "abtwetototnxwtot" twice or three times? $\endgroup$
    – user88719
    Commented May 20, 2016 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 ♦
    Commented May 20, 2016 at 20:16

1 Answer 1

Reset to default
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)}$

Improve this answer
$\endgroup$
8
  • 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 ♦
    Commented May 20, 2016 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
    Commented May 20, 2016 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
    Commented May 20, 2016 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 ♦
    Commented May 20, 2016 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
    Commented May 20, 2016 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.