Skip to main content
1 of 2
Will Sawin
  • 148.4k
  • 9
  • 324
  • 563

I think the phenomena you observe are explained more by the way you construct $B_0$ and $B_1$ than by the properties of primes (though properties of primes seem to play a role). If we suppose instead that $b_i$ were random, obtained by a coin flip, it's easy to see that for each bit of $B_0$ or $B_1$, the probability that the next bit is the same is $\frac{1}{3}$, and the probability that the next bit is different is $2/3$.

Indeed, say $b_i \equiv i \mod 2$ for some $i$, so at time $i$ we have just added $b_i$ to $B_0$.

Then if the next $k-1$ bits are not congruent to their position mod $2$, followed by the $k$th bit congruent to its position, $i+k$, mod $2$, we next append the bit $i+k \mod 2$ to $B_0$. This occurs with probability $\frac{1}{2^k}$, and in each sequence this occurs for exactly one value of $k$.

So we get a different bit with probability $\frac{1}{2} + \frac{1}{2^3} + \frac{1}{2^5} + \dots = \frac{2}{3}$, and the same bit with probability $\frac{1}{2^2} + \frac{1}{2^4} + \frac{1}{2^6} + \dots = \frac{1}{3}$. The $B_1$ case is identical.

So the probability of getting $10$ consecutive zeroes starting at any given point is $\frac{1}{2} \cdot \frac{1}{3^9}$. However, the length of time we expect to take before seeing the first run of $10$ consecutive zeroes is a little longer than the inverse of that, $3^{10}-1=59048$, by a classical argument.

So we waited about 17 times longer than one would expect to find a run of ten zeroes. (But you had 4 choices to pick to find such a long run without zeroes). That's not completely surprising, but it's a lot less strange than in the naive random model, where the expected wait time is $2^{11}-1$, so you would have waited about $489$ times longer than expected.

Will Sawin
  • 148.4k
  • 9
  • 324
  • 563