Pseudo-Random Binary Sequence Prediction (Newbie)

Question

Hi, i know nothing about programming or C or windowing... nothing too deep about computers... but i'm very interested in: given a pseudo-random binary sequence (e.g.: 00101010010101) of finite values, predict how will the sequence continue. Can someone please tell me the easiest way to do it? Or in case it's too difficult for someone who can barely play solitaire on its computer, can someone tell me where to give my first steps...I'm pretty nerdy. PS: can this technique be used to precict the colour of the next electronic roulette number (e.g.: asigning 1 and 0 to red and black respectively)?

Thanks!

Sorry about my english...i know it sucks

Answer 1

To answer the PS first: No, because roulette spins are independent events so there's nothing predictive in the historical sequence of outcomes.

The general question is hard and interesting. This website can infer a surprising number of sequences from their initial values:

http://www.research.att.com/~njas/sequences/

Note that it's for arbitrary integer sequences.

I tried it on simple patterns like {0,0,1,1,0,0,1,1,...} and it says the right thing.

Answer 2

Well, for pseudo-random sequences, the only possibility is to keep count how many of each possibility has come before. If the 1s outweigh the 0s, it's more likely that the next one will be 0. How much more likely depends on the relative occurrences of each.

Note that this won't work for true randomness since the events are independent, despite what the statisticians tell you :-)

You'll find that out (painfully) the first time you get a run of 13 reds on the table when you're using the double-on-loss method of playing roulette. In any case, the house derives its advantage from 0 (and double-0 on some tables) which are neither red nor black.

Answer 3

This is a decent question but I think if "you can barely play solitaire" it might be out of your reach right now.

You should look into picking up a basic language, and most are going to say PHP but I'm wary of recommending that to a beginner (it's pretty easy to get working though, see:XAMPP). Java is probably an "easy-to-get-running-and-work-with" language but I'm sure there's better threads on here about which language to start with (Python or something probably wins because experienced programmers love it).

By the way, your English is fine (I didn't notice you were a non-native English speaker).

Now, as for your question, if you're looking at true pattern matching. I'd be inclined to convert this idea to code:

 "CURRENTPOINT" is end of first letter.
 LOOP: Pick letter(s) from Start to "CURRENTPOINT"
 Break the rest of your binary string into blocks of the same size.
 See if these blocks all equal your picked letters.
 If not, move "CURRENTPOINT" along and repeat the LOOP until you run out of letters.
 If so, you have your "repeating section."

If you're just guessing that the random generator is temporarily biased, and that this bias will re-establish a baseline (balanced 0s and 1s) in the reasonably short-term then you can compare the count of each 0s and 1s and say the other is more likely based on the deviation from your baseline. However, be careful of the Monte Carlo fallacy.

Answer 4

Cryptographically secure pseudorandom number generators are intended specifically to make what you want to do impossible. In particular, they satisfy the "next bit test": given k bits of their output, you cannot guess bit k+1 with probability greater than 1/2.

Plain pseudorandom number generators that do not satisfy the next bit test can be attacked and in fact security vulnerabilities have been discovered in real world systems due to the choice of PRNG. In particular, linear congruential generators are known to be somewhat (or completely) predictable, and some versions of Unix random may use this algorithm. This method is quite math intensive though. If you want to go down this path a search for "linear congruential generator prediction" is a place to start.

Another attack if you are aware of the PRNG implementation is to try to determine the seed used to generate the sequence you are analyzing. The seed is sometimes based on guessable information like time of day, process ID, etc.

Answer 5

Wow! this is an incredible site..i wasn't expecting so many answers in such a short time....thank you for all the information, i'll start to make deeper investigation on what you suggested as soon as i finish my exams.

By the way, i'm aware that with true randomness (like in real life roulettes) it's impossible to "guess bit k+1 with probability greater than 1/2", since events are independent. And that there might be effective ways to create binary sequences where, at least, is very difficult to predict next value. But there's this stupid addictive game on the Internet which i believe it must use a ver inefficient way of generating the series.

Anyway, thanks again for all the information.

PS: does anyone know software Weka?... couldn't be useful for my proposes? and what about mathlab?