Probability distribution of a pretty-good measurement Let $\rho_{XE}$ be a classical-quantum state. That is,
$$
\rho_{XE} = \sum_{x}\Pr[X=x] \cdot |x\rangle \langle x | \otimes \rho_{x}
$$ 
where every $\rho_{x}$ is a density matrix with $\mathrm{Tr}(\rho_{x})=1$.
Define the POVM $\{F_{x}\}_{x}$ to be the pretty-good measurement (PGM) on $E$, trying to predict $X$, defined by
$$F_{x} = \Pr[X=x]\rho^{-1/2}\rho_{x}\rho^{-1/2}$$ 
where $\rho = \sum_{x}\Pr[X=x]\rho_{x}$ is the average encoding.
Question: Given a specific $x$, is it true that for every $y$, $\mathrm{Tr}(F_{x}\rho_{x}) \ge \mathrm{Tr}(F_{x}\rho_{y})$? 
It seems like it should be true, but I can't figure out the proof. Moreover, a proof for $\mathrm{Tr}(F_{x}\rho_{x}) \ge (\mathrm{Tr}(F_{x}\rho_{y}))^2$ will be good as well.
 A: Edit: I still don't know if the first inequality you seek really holds, but the following does get pretty darn close :D 
For every $x$ define
$$
{\hat u}_x = \rho^{-1/4}\rho_x\;\rho^{-1/4}
$$
and rewrite the quantities of interest as
$$
Tr(F_x\rho_x) =  \text{Pr}(X=x)Tr\left(\rho^{-1/2}\rho_x\rho^{-1/2}\rho_x\right) = \text{Pr}(X=x)Tr \left[ \left(\rho^{-1/4}\rho_x\rho^{-1/4}\right)\left( \rho^{-1/4}\rho_x\rho^{-1/4} \right)\right] = \text{Pr}(X=x)Tr\left( {\hat u}_x^\dagger {\hat u}_x \right) \equiv \text{Pr}(X=x)\left( {\hat u}_x | {\hat u}_x \right)
$$
$$
Tr(F_x\rho_y) =  \text{Pr}(X=x)Tr\left( \rho^{-1/2}\rho_x\rho^{-1/2}\rho_y\right) = \text{Pr}(X=x)Tr\left( {\hat u}_x^\dagger {\hat u}_y \right) \equiv \text{Pr}(X=x) \left( {\hat u}_x | {\hat u}_y \right)
$$
Now play with the scalar products and get first a Cauchy-Schwartz inequality,
$$
 \left( {\hat u}_x | {\hat u}_y \right) \le \sqrt{ \left( {\hat u}_x | {\hat u}_x \right) \left( {\hat u}_y | {\hat u}_y \right)} 
$$
This is not quite what we want, but notice now two things:
1) From $\rho = \sum_x{\text{Pr}[X=x]\;\rho_x}$ we have 
$$
\rho^{-1/4} \rho\; \rho^{-1/4} \equiv \rho^{1/2} = \sum_x{\text{Pr}[X=x] \;{\hat u}_x}
$$
wherefrom
$$
\rho = \sum_{x,y}{\text{Pr}[X=x]\;\text{Pr}[X=y]\;{\hat u}_x^\dagger {\hat u}_y}
$$
and 
$$
Tr\rho \equiv 1 = \sum_{x,y}{\text{Pr}[X=x]\;\text{Pr}[X=y]\;\left({\hat u}_x |{\hat u}_y\right)}
$$
2) For any $x, y$ let $\rho_x = {\hat \gamma}_x {\hat \gamma}_x^\dagger$, $\rho_y = {\hat\gamma}_y {\hat\gamma}_y^\dagger$. We then have
$$
\left({\hat u}_x |{\hat u}_y\right) \equiv Tr\left( \rho^{-1/2}\rho_x\rho^{-1/2}\rho_y\right) = Tr\left( \rho^{-1/2}{\hat\gamma}_x {\hat\gamma}_x^\dagger\rho^{-1/2}{\hat\gamma}_y {\hat\gamma}_y^\dagger\right) = Tr \left({\hat\gamma}_x^\dagger \rho^{-1/2} {\hat\gamma}_y {\hat\gamma}_y^\dagger \rho^{-1/2}{\hat\gamma}_x \right) =\\
= Tr \left[\left({\hat\gamma}_y^\dagger \rho^{-1/2}{\hat\gamma}_x \right)^\dagger \left({\hat\gamma}_y^\dagger \rho^{-1/2}{\hat\gamma}_x \right)\right] \ge 0
$$
From (1) and (2) it follows necessarily that 
$$
0 \le \left({\hat u}_x |{\hat u}_y\right) \le 1\;\;\; \forall \;x,y
$$
and in particular
$$
0 \le \left({\hat u}_y |{\hat u}_y\right) \le 1\;\;\; \forall \;y
$$
Taking this back into the Cauchy-Schwartz inequality we are left with
$$
 \left( {\hat u}_x | {\hat u}_y \right) \le \sqrt{ \left( {\hat u}_x | {\hat u}_x \right) \left( {\hat u}_y | {\hat u}_y \right)} \le \sqrt{ \left( {\hat u}_x | {\hat u}_x \right)}
$$
and then
$$
\left(Pr[X=x] \left( {\hat u}_x | {\hat u}_y \right) \right)^2 \le Pr[X=x] \left( {\hat u}_x | {\hat u}_y \right)^2 \le Pr[X=x] \left( {\hat u}_x | {\hat u}_x \right)
$$
So finally we arrive at 
$$
\left[ Tr\left(F_x\rho_y\right) \right]^2 \le Tr\left(F_x \rho_x\right)
$$
as desired.
Would be nice to figure out if indeed $Tr\left(F_x\rho_y\right) \le Tr\left(F_x \rho_x\right)$, maybe somebody else can chip in? 
A: The inequality $\mathrm{tr}[F_x\rho_y]
\le
\mathrm{tr}[F_x\rho_x]
$ is true for the case of case of two outcomes, however generally wrong for the case of three or more outcomes.  
(I.e., the bottomline is that a pretty good measurement will have a higher succeed probability on the correct codeword than on the average of all other codewords, but there might be (rare) codewords which have a higher success probability.)

Let us first provide a counterexample for the case of three outcomes. To this end,  let $p_1=p_2=\tfrac12$ and $p_3=0$, and let
\begin{align}
\rho_1 &= \left(\begin{matrix}\tfrac13\\&\tfrac23\end{matrix}\right)\ , 
\\
\rho_2 &= \left(\begin{matrix}\tfrac23\\&\tfrac13\end{matrix}\right)\ ,
\\
\rho_3 &= \left(\begin{matrix}0\\&1\end{matrix}\right)\ .
\end{align}
Then, $\rho=\tfrac121\!\!1$, which yields
$$
F_1 = \left(\begin{matrix}\tfrac1{3}\\&\tfrac2{3}\end{matrix}\right)\ , 
$$
and thus $\mathrm{tr}[F_1\rho_1]=\tfrac1{3}\tfrac13+\tfrac2{3}\tfrac23=\tfrac{5}{9}$,
while $\mathrm{tr}[F_1\rho_3]=\tfrac2{3}=\tfrac{6}{9}>\tfrac{5}{9}$.
Note that the fact that $p_3=0$ bears no relevance, since the example is robust under perturbations.

Let us now prove the inequality for the case of two outcomes. To this end,
let $\sigma_x\le 1\!\!1$. It holds that
$$\mathrm{tr}[\sigma_x\rho]^2 = \mathrm{tr}[(\rho^{1/4}\sigma_x \rho^{1/4})(\rho^{1/2})]
\stackrel{(*)}{\le} \mathrm{tr}[\rho]\,\mathrm{tr}[\sigma_x\sqrt{\rho}\sigma_x\sqrt{\rho}]\ ,
$$
where in $(*)$ we have used Cauchy-Schwarz, and also repeatedly the cyclicity of the trace. 
It is now straightforward to check that the above inequality is equivalent to
$$
\frac{\mathrm{tr}[\sigma_x\sqrt{\rho}(1\!\!1-\sigma_x)\sqrt{\rho}]}{
    \mathrm{tr}[\rho]-\mathrm{tr}[\rho\sigma_x]} 
\le
\frac{\mathrm{tr}[\sigma_x\sqrt{\rho}\sigma_x\sqrt{\rho}]}{
    \mathrm{tr}[\rho\sigma_x]}\ .
$$
By choosing $\sigma_x = p_x\rho^{-1/2}\rho_x\rho^{-1/2}\equiv F_x$, this immediately yields the inequality 
$$
\mathrm{tr}\left[F_x\frac{\rho-p_x\rho_x}{1-p_x}
\right]\le
\mathrm{tr}\left[F_x\rho_x\right]\ ,
$$
where we have used that $\mathrm{tr}[\rho]=\mathrm{tr}[\rho_x]=1$, and thus
$\mathrm{tr}[\rho\sigma_x]=\mathrm{tr}[p_x\rho_x]=p_x$.
In the case where $p_x\rho_x+p_y\rho_y = \rho$ (i.e., with only two outcomes), this immediately yields
$$
\mathrm{tr}[F_x\rho_y]
\le
\mathrm{tr}[F_x\rho_x]
$$
and thus completes the proof.
