A question regarding next-bit predictors

Question

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 "gap" 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.

Answer 1

[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).

Answer 2

I think there is the use of intuition in the proof (Similar proof to statistical closeness implies computational indistinguishability). It uses the fact that a best case scenario for the adversary (even computationally unbounded ones) would be if it could efficiently and deterministically calculate the probability $Pr[X_k|X_1,X_2..X_{k-1}]$. The distinguisher then outputs $1$ if $p_{1}>p_{0}$, $0$ otherwise. You can now use basic probability calculation to show that the distinguisher still gets it correct with the probability only negligibly better than random guess if $|p_1 - p_0|$ is negligible. Another strategy would be more probabilistic, output 1 with probability equal to $p_{1}$ but since this is independent of whether $X_{k}$ is $0$ or $1$, advantage is still equal to one above.

Unfortunately, I don't have any mathematical proof that this is best an adversary can do but it is the fact that these probabilities are the best any computationally unbounded adversary can theoretically calculate given only $X_1,X_2..X_{k-1}$.

Answer 3

I am not sure this is correct but I'll give it a try... More specifically instead of relating the conditional probabilities, I will rather try and bound conditional entropies i.e $H(X_k | X_1^{k-1})$. I don't know yet if the bound on probabilities directly follows from this but I will try and argue it informally.

Notation $X_k^n = (X_k, X_{k+1},\ldots,X_n)$. For simplicity we write $X^n = X_1^n$.

Problem statement: We are given $X^n \sim \text{ } D$. We are also given an adversary $\mathcal A$ that produces a guess $\tilde X_{k} = \mathcal A(X^{k-1})$ and $P[\tilde X_k = X_k] \geq \frac{1}{2} + \frac{1}{\text{poly}(n)}$. We want to show that:

\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}

Attempt 1: We use Fano's inequality

---

Fano's inequality: Let $U$ and $\tilde U$ be random variables taking values in the set $\mathcal U$. We think of $\tilde U$ as a guess about $U$. Let the error probability defined as $P_e = Pr[U \neq \tilde U]$, then we have $$ H_b(Pe) + Pe \log(|\mathcal U| - 1) \geq H(U|\tilde U)$$ Where $H_b(p)$ is the binary entropy of a Bernoulli RV with $P(1) = p$

We apply this to $X_k$ and $\tilde X_k$: First the probability of error $P_e^{\mathcal A} = \frac{1}{2} - \frac{1}{\text{poly}(n)}$. We then obtain $ H(X_k | X_{k-1}) \leq H(X_k |\tilde X_k) \leq H_b(P_e^{\mathcal A}) = H_b(\frac{1}{2} - \frac{1}{\text{poly}(n)})$. The first inequality from $\tilde X_k = \mathcal A(X^{k-1})$.

Now if we assume towards contraction that \begin{equation} \underset{X \sim D}{\text{Pr}}[X_k~|~X_1,X_2,\ldots,X_{k-1}] - \underset{X \sim D}{\text{Pr}}[\overline{X_k}~|~X_1,X_2,\ldots,X_{k-1}] \approx \text{negl}(n), \end{equation}

Then (very informal): $H(X_k | X^{k-1})$ is the average of entropies of almost uniform Bernouilli distributions therefore $H(X_k | X_{k-1}) \leq H(X_k |\tilde X_k) \leq H_b(P_e^{\mathcal A}) = H_b(\frac{1}{2} - \frac{1}{\text{poly}(n)})$ would not hold.