# Using R and hidden Markov models to predict pseudorandom binary sequences better than P > .5?

I would to predict a pseudo-random binary sequence of 0's and 1's. I am thinking of using the HMM package in R.

I have a binary sequence like ... 0 1 0 0 1 1 0 1 x(n+1)? with thousands of values. What I would like is to get automatic estimation for x(n+1), computing their prob.matrix automatically every time.

The question is to know, if a HMM (or any other algorithm) can provide P > .5 for binary events that pass random tests, BUT are generated by deterministic algorithms, like LCG.

Something like that; http://www.stanford.edu/class/stats366/hmmR2.html BUT using a data file with the binary sequence, so prob.matrix can't be estimated before. thank you

• It depends on which "random tests" the PRG passes. Nowadays most batteries of tests include various runs tests and sequential correlation tests, sometimes extending for 8, 32, or even longer windows. In principle, then, an algorithm that uses larger neighborhoods to make predictions has a chance of improving over $0.5$, but--by the same lights--it would be hopeless to try an algorithm based on shorter windows. Now consider how many states a longer window would contain and how long the sequence would have to be to estimate transition probabilities... .
– whuber
Nov 13 '13 at 17:17
• Well, but would be possible to algorithmically (auto)estimate how many states, windows for a given ie; sequence of length n=1000?. Nov 13 '13 at 17:27
• I've upload a PRBSquence of n=1000 to estimate for a HMM: link Nov 13 '13 at 17:59
• No way. Suppose you use a (tiny) window of four, for example: that comprises $2^4=16$ states, requiring estimation of $16\times 16=256$ transitions. A sequence of $1000$ gives an average of just four occurrences of each transition: the standard error of estimate of the probability would be an order of magnitude larger than the probability itself! You would need a sequence of billions (and likely many more) to have any hope of detecting fairly large deviations from perfect randomness and quadrillions to detect the tiny ones that might exist.
– whuber
Nov 13 '13 at 18:47