Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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! :)

share|improve this question
add comment

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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