# probability of a word in a string

What is the probability of a word n characters long appearing in a string of m characters, in an alphabet of x characters? A word here is simply a string of characters contained in another string of characters. A string of characters of length L is an ordered L-tuple of characters, where characters are members of a set A called an alphabet. An alphabet contains n characters if it has n members that are all mutually not equal.IMPORTANT: If the alphabet in question has x characters, each character in a string has exactly 1/x probability of being a given character.

• n is necessarily less than m, so if n=m, then we have P= 1/(x^n). If n+1=m then we have x ways the given word can appear in our string if our word occupies the "leftmost" n characters, and x ways with our word occupying the "rightmost" n characters, each with a probability of occurring of P= 1/(x^m), so we have a total probability of P= 2x/(x^m). Once we have n+2=m, all methods I have tried start double counting, and this is where I need help. Dec 20, 2013 at 3:06
• I think you might want to try working some explicit examples. What if $x=2$? Try listing the possibilities for small $m$ and $n$ so that you'll have some reliable examples to check the formulas you come up with. Maybe try a few with $x=3$, too. Dec 20, 2013 at 3:19
• I have tried many explicit examples and cannot solve the problem of double counting. I also was informed that the answer depends on the specific sequence and I'm wondering if a word can be characterized in terms of the range of characters it uses (the subset of the alphabet whose members are included in the word), and the symmetries of a word (the subsets of a word that are equal to their reverse: the reverse of an L-tuple {$x_1$,$x_2$,...,x$_L$}being an L-tuple equal to {x$_L$,x$_{L-1}$,...,$x_1$}) Dec 22, 2013 at 5:11

let w be your m-letter string in a k letter alphabet. Let $x_n$ be the number of words of lenth $n$ (also in x letter alphabet) containing w.
At first sight we would consider the following recurrence relation: $x_n=kx_{n-1}+k^{n-m}-x_{n-m}$ Since every word of length n can be created in the following way: for a n-1 word that contains w just add any of the k letters at the end $kx_{n-1}$. For a $k-n$length word just add w at the end to get one that does work. This seems really great. There's just one problem:
Sometimes when you add w at the end of a n-k word that doesn't contain w you get a word that contains w even if you remove some of the last digits. Let me explain: for example consider $w=1,2,1$ then the word $3,1,2$ clearly doesn't contain $w$ so we add w to this letter to get $3,1,2,1,2,1$ notice that this word is obtained through both the process of taking an (n-1) word that contains w and taking and n-k word that does not. Thus we are counting it twice? Can you refine the recursion so it works?