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%.
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.
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%.
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.