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.

I have a signal generator, which each second generates one of the letters 'a', 'b' or 'c'.

I don't know anything else about this signal generator, but I suspect that there are some patterns to it.

The signal generator is started at time 0. Given output of the signal from time 0 to time n, I need to forecast its output at time n+1.

I suspect that there are some patterns to the signal, so I create a frequency table:

For each sub-string(up to length 7) of the first n symbols of the signal generated data, I calculate three values: the number of occurrences of 'a','b', and 'c' after that sub-string.

So, for example for sub-string "abc"(if it exists in the data), I store:

  • the number of cases when symbol 'a' comes after string "abc"
  • the number of cases when symbol 'b' comes after string "abc"
  • the number of cases when symbol 'c' comes after string "abc"

Now that I have all these data, I have 7 predictions as to what the next symbol could be. If for example the last 7 characters of the signal are "acbccba", then:

If I look just at the one-character frequency table, then I will have a certain prediction, which would look like: "Since the last character of the string is 'a', and since coming directly after character 'a' there were 40 cases of letter 'a', 25 cases of letter 'b', and 130 cases of letter 'c', I predict that the next character will be letter 'c'"

Similarly for the last 2-letter("ba"), 3-letter("cba"), ... , 7-letter("acbccba"). So in the end I have 7 predictions.

The question is, how do I find which next character is actually the most probable for this signal generator? Different predictions are based on different sample sizes, so how do I combine them effectively?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

What you have can be modeled as a Markov information source. The probability parameters of the model can be estimated by a variety of methods. Probably the best approach is to use a variable-order Markov model or VOM. An article by Begleiter et al, 2004 reviews half a dozen algorithms for finding parameters of VOM's and some software at vocrf.net treats VOM's.

For methods other than VOM's, see eg www.cs.ucf.edu/~zhou/pmpm_cbp2.pdf which presents a prediction method based on combining multiple partial matches like you have, and also acl.ldc.upenn.edu/W/W97/W97-0309.pdf, which talks about "aggregate and mixed-order Markov models for statistical language processing".

share|improve this answer

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.