How to explain a particular property of the second-to-last bits of primes?

Question

Assuming that $i \geq 0$, let $p_i$ denote an $i$-th prime: $p_0 = 2, p_1 = 3, \ldots$ Then $b_i$ denotes the second-to-last bit of $p_i$, i.e. $b_i = \left\lfloor p_i/2 \right\rfloor \bmod 2.$

The sequences $B_0$ and $B_1$ are constructed by the following algorithm: if $b_i$ is equal to $i \bmod 2$, append $b_i$ to $B_0$; otherwise (i.e. if $b_i$ is not equal to $i \bmod 2$), append $b_i$ to $B_1$. Thus $$\begin{array}{l} B_0 = 1010101101010101010101101010101010011001001111001101001011001010\ldots,\\ B_1 = 1101010101011001011010101100101010101010010101011101010101010101\ldots \end{array}$$

Basically, both of these sequences are $\ldots1010\ldots$, slightly interspersed with runs of two or more identical bits. For example, the first $10^6$ bits of $B_1$ do not even contain ten consecutive zeros. What is the explanation of this phenomenon?

Answer 1

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.

---

More generally, if we replace $b_i$ with a Markov chain with probability of taking the same value on adjacent steps $p$, then the probability that $B_0$ takes the same value on adjacent steps should be $$p^2 + p^2(1-p)^2 + p^2 (1-p)^4 + \dots = \frac{ p^2}{ 1- (1-p)^2} = \frac{p^2 }{ 2p -p^2} = \frac{p}{ 2-p}$$ since to get two of the same bit in $B_0$, $b_i$ must be same-same or same-different-different-same or same-different-different-different-different-same.

To explain $\frac{ p}{2-p} = \frac{1}{2} - .28 = .22$ as in dvitek's analysis, we need $p= \frac{2}{ 1/.22 +1} =.361$, i.e. there is a discrepancy of about $.14$ to explain in the more natural statistic of how often two adjacent primes have distinct second-to-last bits.

Answer 2

I don't think this is all that unexpected given work of Lemke Oliver and Soundararajan on residues of consecutive primes. (I realize that the first word of that paper's title is "Unexpected", but I don't care.) Note that John Omielan's first link in the comments points (eventually) to this paper.

---

Let's look at the run statistics of the first 49,981 bits of $B_0$, corresponding to about half of the first 100,000 primes. There are runs of equal consecutive bits of lengths 1 through 7, and the counts of these runs are, respectively, $$(27261, 7710, 1771, 390, 67, 13, 2).$$

Now consider a Markov process with states {0,1} and transition matrix \begin{pmatrix}\frac{1}{2}-d & \frac{1}{2}+d \\ \frac{1}{2}+d & \frac{1}{2}-d\end{pmatrix} for some parameter $d \in [-1/2, 1/2]$. We should expect shorter runs for larger $d$, and longer runs for smaller $d$. If we take $d = 0.28$, we get the following counts for runs of length 1 through 11, averaged over 100 samples: $$(30378.2, 6700.82, 1472.6, 324.16, 71.42, 16.01, 3.7, 0.75, 0.15, 0.02, 0.01).$$ This looks like a decent fit to the observed values, if perhaps a bit too low on medium-length runs and too high elsewhere.

---

I'm not sure what value of $d$ is realistic here: Lemke Oliver and Soundararajan have (conjecturally) asymptotically correct expressions, but they're studying a slightly different problem. More specifically, if we look at mod 4 residues of the first $10^6$ primes, their data suggest $d \approx 0.07$ is a reasonable guess for their problem. For smaller primes $d$ should be larger, but your $B_0$/$B_1$ setup is artificial enough so as to make their methods significantly harder to apply. (EDIT: it seems like the bulk of this $d$ term is due to the definitions of $B_0$ and $B_1$; see Will Sawin's answer.)

More broadly, the shape mismatch in the data suggests (unsurprisingly) that there are longer-range effects going on than those captured by the Markov process modelling. I expect spending some quality time with Lemke Oliver and Soundararajan and thinking about the prime tuples conjecture should give you better explanations here.