關於下一位預測器的問題
考慮機率分佈 $ D $ 超過 $ n $ 位串。考慮下一位預測器 $ A $ 如下。 $$ \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} $$ 這裡， $ X_i $ 表示 $ i^{\text{th}} $ 一點 $ X $ . 考慮到這個預測器存在。直覺地說，如果我理解正確，這意味著位之間應該存在“間隙” $ X_k $ 和位 $ \overline{X_k} $ （補充 $ X_k $ ); 否則算法 $ A $ 不應該存在。換句話說，我認為算法的存在 $ A $ 暗示 $$ \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} $$ 或類似的東西，關於 $ k^{\text{th}} $ 少量。我無法在數學上證明這一點。
我的直覺是正確的嗎？它可以在數學上變得嚴謹嗎？
我試圖證明我的直覺，但我仍然卡住了。這是我的嘗試。
我們可以證明 $ A $ 存在並充當 $$ \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} $$ 暗示 $$ \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} $$
現在，我試圖展示 $$ \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} $$
換句話說，證明簡化為證明 $$ \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} $$
如果我從陳述的對立面開始，我最終會在同一個地方。我想我錯過了一些微妙的東西。從本質上講，我們的證明簡化為的陳述類似於看起來非常相似的結果，該結果將兩個分佈之間的總變異距離與最佳算法的可區分性偏差相關聯（如這個答案）。但是，它也不完全相同：因為我們現在只有一個分佈，而不是兩個，並且追溯相同的步驟是行不通的。
$$ SEE UPDATE BELOW $$這是一個非常有趣的問題。基本上它的意思是，如果存在下一位預測器，那麼就有一個規範的區分器 $ D $ 輸出 $ k $ 位並且什麼都不做。這是一個很好的區分，因為 $ k $ th 位等於 1，機率是多項式地遠離隨機位。我發現這在直覺上很有吸引力，並且首先感到驚訝。然而，這確實是有道理的。 作為健全性檢查，讓我們看看極端情況下會發生什麼： $$ 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}]. $$ 這將意味著 $ X_k $ 實際上是獨立於 $ X_1,\ldots,X_{k-1} $ 並且是一個隨機位。在這種情況下，很明顯 $ A $ 只能用機率預測下一位 $ \frac12 $ . 因此，我認為這可以用反證法來證明。
我不會在這裡做所有這些；你解決它有很好的價值。為了找到方向，我建議您查看下一位不可預測性和偽隨機性的等價證明。看到這一點的一個地方是Salil Vadhan的關於Pseudorandomness的本章第 7.3.2 節。
讓我知道它是否從這裡無法解決。
==================================
我將上述內容保留為教學價值，但我不再確定這是正確的。問題是空調。特別是，一旦我們條件 $ X_1,\ldots,X_{k-1} $ ，那麼我們就是在徹底改變機率空間。（一般建議——條件反射很容易出錯，所以盡可能遠離。這是我的顧問給我的建議。你不能總是避免它，但你需要非常小心。）更詳細地說，可能是給定的 \emph{many} $ X_1,\ldots,X_{k-1} $ ， 這 $ k $ 位 $ X_k $ 是多項式偏離 $ 1/2 $ . 問題是你不知道如何辨識它所在的前綴。當然，這意味著它不可能以高機率發生（或者非統一的區分器可能會持有一些前綴作為建議）。我認為部分困惑是對完整樣本進行採樣甚至意味著什麼 $ X $ 然後條件 $ X_1,\ldots,X_{k-1} $ . 我認為你的意思是：對於每個 $ X_1,\ldots,X_{k-1} $ , 的機率 $ X_k=1 $ 當樣本 $ X $ 具有給定的前綴 $ X_1,\ldots,X_{k-1} $ 有界遠離 $ 1/2 $ . 我不認為這是正確的。如果你的意思是別的，那麼值得考慮。
我想重要的問題是您要展示什麼以及為什麼，或者可能只是理解（這本身就很好）。