A question regarding next-bit predictors Consider a probability distribution $D$ over $n$ bit strings. Consider a next bit predictor $A$ as follows.
\begin{equation}
\underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})=X_k] \geq \frac{1}{2} + \frac{1}{\text{poly}(n)}.
\end{equation}
Here, $X_i$ indicates the $i^{\text{th}}$ bit of $X$. Consider that this predictor exists. Intuitively, if I understand correctly, this means that there should be a &quot;gap&quot; between the bit $X_k$ and the bit $\overline{X_k}$ (complement of $X_k$); otherwise the algorithm $A$ should not exist. In other words, I think that the existence of an algorithm $A$ implies
\begin{equation}
\underset{X \sim D}{\text{Pr}}[X_k~|~X_1X_2.....X_{k-1}] - \underset{X \sim D}{\text{Pr}}[\overline{X_k}~|~X_1X_2.....X_{k-1}] \geq \frac{1}{\text{poly}(n)},
\end{equation}
or something similar to this, with respect to the statistical property of the $k^{\text{th}}$ bit. I couldn't prove this mathematically.
Is my intuition correct and can it be made mathematically rigorous?

I tried proving my intuition, but I am still stuck. Here is my attempt.
We can show that the fact that $A$ exists and acts as
\begin{equation}
\underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})=X_k] \geq \frac{1}{2} + \frac{1}{\text{poly}(n)}.
\end{equation}
implies
\begin{equation}
\underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1}) = X_k] - \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})= \overline{X_k}] \geq \frac{1}{\text{poly}(n)}.
\end{equation}
Now, I am trying to show
\begin{equation}
\underset{X \sim D}{\text{Pr}}[X_k~|~X_1X_2.....X_{k-1}] - \underset{X \sim D}{\text{Pr}}[\overline{X_k}~|~X_1X_2.....X_{k-1}] \\ \geq \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1}) = X_k] - \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})= \overline{X_k}].
\end{equation}
In other words, the proof reduces to proving
\begin{equation}
\underset{X \sim D}{\text{Pr}}[X_k~|~X_1X_2.....X_{k-1}] - \underset{X \sim D}{\text{Pr}}[\overline{X_k}~|~X_1X_2.....X_{k-1}] \\ = \max_{A}\left( \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1}) = X_k] - \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})= \overline{X_k}]\right).
\end{equation}
If I start with the contrapositive of the statement, I end up in the same place. I think I am missing something subtle. In spirit, the statement our proof reduces to is similar to a very similar-looking result relating total variation distance between two distributions with distinguishability bias of the best algorithm (like this answer). But also, it is not quite the same: as we only have one distribution now, not two, and retracing the same steps does not work.
[SEE UPDATE BELOW] This is a very interesting question. Basically what it means is that if there exists a next-bit predictor, then there is a canonical distinguisher $D$ that outputs the $k$th bit and does nothing else. This is a good distinguisher since the $k$th bit equals 1 with probability that is polynomially bounded away from a random bit. I find this intuitively appealing and was first surprised. However, it does make sense.
As a sanity check, let's see what would happen if on the extreme:
$$
Pr_{X\sim D}[X_k=1 \mid X_1X_2\ldots X_{k-1}] = Pr_{X\sim D}[X_k=0 \mid X_1X_2\ldots X_{k-1}].
$$
This would mean that $X_k$ is actually independent of $X_1,\ldots,X_{k-1}$ and is a random bit. In such a case, it is clear that $A$ could only predict the next bit with probability $\frac12$. As a result, I think that this could be proven in the contrapositive.
I won't do all of this here; there is good value in you working it out. In order to get the direction, I propose that you look at the proof of equivalence of next-bit unpredictability and pseudo randomness. One place to see this is Section 7.3.2 of this chapter on Pseudorandomness by Salil Vadhan.
Let me know if it doesn't work out from here.
==================================
I'm leaving the above for the didactic value, but I'm no longer sure that this is correct. The problem is the conditioning. In particular, once we condition on $X_1,\ldots,X_{k-1}$, then we are completely changing the probability space. (General recommendation - it's really easy to get conditioning wrong so stay away if you can. This was a recommendation given to me by my advisor. You can't always avoid it, but you need to be really careful.) In more detail, it could be that for \emph{many} given $X_1,\ldots,X_{k-1}$, the $k$th bit $X_k$ is polynomially biased away from $1/2$. The problem is that you don't know how to recognize the prefixes where this holds. Of course, this means that it can't happen with high probability (or a non-uniform distinguisher could hold some prefixes as advice). I think part of the confusion is what it even means to sample a full $X$ and then condition on $X_1,\ldots,X_{k-1}$. I think what you mean is that: for every $X_1,\ldots,X_{k-1}$, the probability of $X_k=1$ when the sample of $X$ has the given prefix of $X_1,\ldots,X_{k-1}$ is bounded away from $1/2$. I don't think this would be correct. If you mean something else, then it's worth thinking about.
I guess the important question is what you are trying to show and why, or possibly it's just understanding (which is good within itself).