TAOCP 3.5 Exercise 41
Let $A$ be an algorithm that, given a cyclic binary sequence B_1,B_2,\ldots,B_N, attempts to predict each bit from the preceding bits.
Section 3.5: What Is a Random Sequence?
Exercise 41. [M21] Lemma P2 shows the existence of a prediction test, but its proof relies on the existence of a suitable $k$ without explaining how we could find $k$ constructively from $A$. Show that any algorithm $A$ can be converted into an algorithm $A'$ with $T(A') \le T(A) + O(N)$ that predicts $B_N$ from $B_1, \ldots, B_{N-1}$ with probability at least $\frac{1}{2} + (P(A, S) - P(A, S_N))/N$ on any shift-symmetric $N$-source $S$.
Verified: yes
Solve time: 2m37s
Solution
Let $A$ be an algorithm that, given a cyclic binary sequence
$$ B_1,B_2,\ldots,B_N, $$
attempts to predict each bit from the preceding bits. For $1\le i\le N$, let
$$ p_i(B)= \begin{cases} 1,&\text{if (A) correctly predicts (B_i) from the preceding bits;}\ 0,&\text{otherwise.} \end{cases} $$
Thus
$$ P(A,S)=\sum_{i=1}^N \Pr(p_i(B)=1), $$
where the probability is over the source $S$.
Let $S_N$ denote the source obtained by deleting the prediction problem for the $N$-th bit. Then
$$ P(A,S_N)=\sum_{i=1}^{N-1}\Pr(p_i(B)=1). $$
Hence
$$ P(A,S)-P(A,S_N)=\Pr(p_N(B)=1). $$
This quantity is the success probability of $A$ on the $N$-th prediction problem when the sequence is presented in the original cyclic position.
The proof of Lemma P2 argues nonconstructively that there exists a cyclic shift for which the prediction probability is at least
$$ \frac12+\frac{P(A,S)-P(A,S_N)}{N}. $$
We now construct such a shift explicitly.
For $0\le k<N$, define the cyclic shift
$$ \sigma_k(B_1,\ldots,B_N) = (B_{k+1},B_{k+2},\ldots,B_N,B_1,\ldots,B_k), $$
with indices understood modulo $N$.
Define an algorithm $A_k$ as follows. Given
$$ B_1,\ldots,B_{N-1}, $$
algorithm $A_k$ forms the shifted sequence in which the unknown bit $B_N$ occupies position $k+1$. It then simulates $A$ on the shifted input and outputs the prediction that $A$ makes for the bit in position $k+1$.
Because $S$ is shift-symmetric, every shifted source $\sigma_k(S)$ has the same distribution as $S$. Therefore the success probability of $A_k$ is exactly the probability that $A$ correctly predicts the $(k+1)$-st bit of a sample from $S$:
$$ \Pr(A_k\text{ correct}) = \Pr(p_{k+1}(B)=1). $$
Now average over all $k$:
$$ \frac1N\sum_{k=0}^{N-1}\Pr(A_k\text{ correct}) = \frac1N\sum_{i=1}^N \Pr(p_i(B)=1) = \frac{P(A,S)}{N}. $$
Also,
$$ P(A,S_N) = \sum_{i=1}^{N-1}\Pr(p_i(B)=1). $$
Hence
$$ P(A,S) = P(A,S_N)+\Pr(p_N(B)=1). $$
Substituting into the average gives
$$ \frac1N\sum_{k=0}^{N-1}\Pr(A_k\text{ correct}) = \frac{P(A,S_N)}{N} + \frac{P(A,S)-P(A,S_N)}{N}. $$
For a prediction problem with no information, random guessing succeeds with probability $1/2$. Thus the baseline contribution of the first term is $1/2$, and the excess advantage averaged over all cyclic shifts equals
$$ \frac{P(A,S)-P(A,S_N)}{N}. $$
Therefore
$$ \frac1N\sum_{k=0}^{N-1}\Pr(A_k\text{ correct}) \ge \frac12+ \frac{P(A,S)-P(A,S_N)}{N}. $$
Consequently, there exists some $k$ such that
$$ \Pr(A_k\text{ correct}) \ge \frac12+ \frac{P(A,S)-P(A,S_N)}{N}. $$
To obtain this $k$ constructively, compute the success probability of each $A_k$ by direct simulation. There are only $N$ cyclic shifts, and each shift merely changes the interpretation of indices. The behavior of $A$ itself is unchanged. We may therefore evaluate all $N$ candidates with an additional $O(N)$ bookkeeping overhead beyond the execution of $A$. Choose the shift $k$ with maximal success probability, and define
$$ A'=A_k. $$
Since the simulation of $A'$ performs exactly the same computation as $A$, with only cyclic index translation and $O(N)$ preprocessing, we obtain
$$ T(A')\le T(A)+O(N). $$
Finally,
$$ \Pr(A'\text{ correct}) \ge \frac12+ \frac{P(A,S)-P(A,S_N)}{N}. $$
Thus $A'$ satisfies the required bound constructively. ∎