# Calculating probability, given any word of length N?

Suppose I have 2,096,896 randomly generated letters (they were actually derived from pi). How can I calculate the probability that a word of length N will appear? I took discrete math a few years ago, but I am a bit rusty...could someone help me out here? Thanks! :)

-

Note: As @Henry noted below, this answer is wrong. I confused conditional independence with regular independence. The probability that you draw a word starting at index i is related to the probability that you draw a word starting at i+1.

Assuming you have $m$ different letters (with equal probability), the probability of generating a length $n$ word from the first letter is $p = \left(\frac{1}{m}\right)^n$. Each trial is independent, and you have to get the letters exactly right, so you can just multiply the probabilities.

You can then simplify your question by asking for each index, what is the probability that I will get my word from this index onwards? This is the same as above, of course, although it only works for $2,096,896 - n + 1$ places, because after that there's no more space for the full word.

So now you have $2,096,896 - n + 1$ independent trials. The easiest approach is to ask what the probability is that the word doesn't appear, which is $1-p$ for each index, and $(1-p)^{2,096,896 - n + 1}$. Subtract this from $1$ and you have the probability that your word appears once or more.

If you want to actually compute these values, you may want to take their logarithms, as they can go to zero very quickly.

-
Just to be clear, you are saying that if I have a length 2 word, "hi" for example, then the probability of getting that word is (1/26)^2*(1/26)^1? Isn't the probability related to how many numbers we have? Or I am I missing something? –  Mr_CryptoPrime Mar 15 '12 at 9:45
That's not what I'm saying. With twenty-six letters, the word "hi" would occur at least once with probability $1 - \left(1-\left(\frac{1}{26}\right)^2\right)^{(s-2+1)}$ where $s$ is how many numbers you generate. First you raise to the length of the word, then to the number of samples. –  Peter Mar 15 '12 at 9:55
Oh, ok! I was wondering why I kept getting lower probabilities for n=1 than for n>1?! :) Thanks! –  Mr_CryptoPrime Mar 15 '12 at 10:00
The trials are not independent: suppose you have a two letter alphabet A and B, and you are looking for a two letter word in a string of three. Your formula would give $1-(1-(1/2)^2)^{3-2+1} = 7/16$; if you were looking for AA the true value is $3/8$ [AAA, AAB or BAA] while if you were looking for AB the true value is $1/2$ [AAB, ABA, ABB, BAB]. –  Henry Mar 15 '12 at 11:29
You're absolutely right. I've edited my answer. –  Peter Mar 15 '12 at 11:57