# A confusion on the proof of Yao's theorem (Yao 82)

I'm reading the proof of Yao's theorem on Boaz Barak's lecture, the main part of the proof is the following claim:

My question is:

How can we say "without loss of generality" here? Since $H^i$ and $H^{i-1}$ are probability ensembles, hence for a fixed $D$, whether $\mathrm{Pr}[D(H^i_n)=1]\ge \mathrm{Pr}[D(H^{i-1}_n)=1]$ or not may not necessary the same for all $n$, where $H^i_n$ is the $n$th distribution in that ensemble. So, when one wants to design the algorithm $P$, one need to encode these relation information, how can we do this?

He's doing a pretty poor job of expressing a very simple idea here, which is that if there exists a distinguisher $D$ for which $Pr\lbrack D(H^{i-1})=1\rbrack$ > $Pr\lbrack D(H^{i})=1\rbrack$ (which means the advantage is negative before taking the absolute value), there also exists a distinguisher $\overline{D}$ for which $Pr\lbrack D(H^{i})=1\rbrack$ > $Pr\lbrack D(H^{i-1})=1\rbrack$ (i.e. the advantage is positive before taking the absolute value) by just defining $\overline{D}(H^*) = 1-D(H^*)$ for $H^* \in \{H^i,H^{i-1}\}$. Informally, this distinguisher runs $D$ on its input and just flips whatever $D$ outputs.
Thus, w.l.o.g. we can assume the distinguisher has a higher probability of outputting a 1 given a sample from $H^i$ than from $H^{i-1}$, which means we don't need the absolute value.
• Hi pg, I can understand this part, but my question is: how do we know the relation $\mathrm{Pr}[D(H^i_n)=1]>\mathrm{Pr}[D(H^{i-1}_n)=1]$ is "uniform" for all $n$, since when we say $|\mathrm{Pr}[D(H^i)=1]-\mathrm{Pr}[D(H^{i-1})=1]|\ge \epsilon$ we mean $|\mathrm{Pr}[D(H^i_n)=1]-\mathrm{Pr}[D(H^{i-1}_n)=1]|\ge \epsilon(n)$ for all $n$. – Paul Mar 31 '16 at 22:54
• Why does it matter? We fix a specific $n$ in the problem statement, and it holds for all $n$, and in fact the distinguishers are usually considered to be non-uniform Turing machines anyway so we can change the description of the program to make absolute values unnecessary for any $n$. – pg1989 Mar 31 '16 at 23:00