benelliott comments on Can you recognize a random generator? - Less Wrong

2 Post author: uzalud 28 December 2011 01:59PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (55)

You are viewing a single comment's thread.

Comment author: benelliott 28 December 2011 02:29:40PM 19 points [-]

The biased random generator is also just as likely to output 0000000000 as it is 0010111101.

This is the mistake.

If you actually do the maths the biased generator is significantly more likely to output 0000000000 than 0010111101.

For a much simpler example, suppose we run on two times. The random generator outputs 00 25% of the time, 01 25% of the time, 10 25% of the time and 11 25% of the time.

For the biased generator, we need calculus. First suppose its p(0) = x. Then p(00 | p(0) = x ) = x^2. Since we have what is essentially a uniform distribution over [0,1] (the presence of absence of a single point makes no difference) we need to integrate f(x) = x^2 over the interval [0,1], which gives and answer of p(00) = 1/3. The same method gives p(11) = 1/3 and p(01) = p(10) = 1/6.

The general rule, is that if we run it n times, for any k between 0 and n the chance of it outputting k 1s is 1/(n+1), and that probability is shared out evenly among all possible different ways of outputing k 1s (also derivable from calculus). Thus p(0000000000) = 9.1% while p(0010111101) = 0.043%.

Comment author: uzalud 28 December 2011 04:14:21PM 1 point [-]

Thanks, this is a great answer. It didn't occur to me that stateless generator with unknown p(0) will have such a "preference" for all-digits-are-same-sequences. p(ten zeros) = 1/11 if p(0) can be any number; but p(ten zeros)=1/1024 if p(0)=1/2.