2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Platonix
    Dec 20, 2013 at 3:06
  • $\begingroup$ 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. $\endgroup$ Dec 20, 2013 at 3:19
  • $\begingroup$ 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$}) $\endgroup$
    – Platonix
    Dec 22, 2013 at 5:11

1 Answer 1

3
$\begingroup$

The answer is it depends in the sequence. Suppose we want to find the probability that the word 11 is inside a 3-letter word in an alphabet of 3 letters.There are 5 such words that contain it. Now lets look at the probability the word 12 is inside a 3-letter word. there are 6 words that contain it. Not all words have the same probability.

Now for a fixed word:

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?

$\endgroup$
2
  • $\begingroup$ Maths is amazing! I thought this was going to be a simple problem when I first started! What characteristic of a word makes it different, its symmetry? $\endgroup$
    – Platonix
    Dec 21, 2013 at 17:56
  • $\begingroup$ I've tried multiple examples, and the more complications I think I've dealt with, the more that arise. I also found a formula (non-recursive) that seemed to solve the problem, but again, didn't take into account double counting. It is the step of dealing with double counting where the specifics of the word come into play as well. $\endgroup$
    – Platonix
    Dec 22, 2013 at 5:00

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.