Let $\mathcal{F}$ be the space of all functions that uniformly and independently map the alphabet $\mathcal{X}$ to the set $\{1,2,\ldots,A\}$. Let $p(x|y)$ be an arbitrary conditional probability distribution. Does the following inequality hold?
\begin{align}
\mathbb{E}\_\mathcal{F}\left[\sqrt{\sum\_{x\in\mathcal{X}}p^2(x|y)\mathbf{1}[\mathcal{F}(x)=1]}\right]&\overset{?}{\le}\sqrt{\sum\_{x\in\mathcal{X}}p^2(x|y)}\mathbb{E}\_\mathcal{F}\left[\mathbf{1}[\mathcal{F}(x)=1]\right]\\
&=\frac{1}{A}\sqrt{\sum\_{x\in\mathcal{X}}p^2(x|y)},
\end{align}
where $\mathbf{1}[\cdot]$ is the indicator function.


I know that using Jensen's inequality for $\sqrt{x}$ we have:
\begin{align}
\mathbb{E}\_\mathcal{F}\left[\sqrt{\sum\_{x\in\mathcal{X}}p^2(x|y)\mathbf{1}[\mathcal{F}(x)=1]}\right]&\leq\sqrt{\sum\_{x\in\mathcal{X}}p^2(x|y)\mathbb{E}\_\mathcal{F}\left[\mathbf{1}[\mathcal{F}(x)=1]\right]}\\
&=\frac{1}{\sqrt{A}}\sqrt{\sum\_{x\in\mathcal{X}}p^2(x|y)}.
\end{align}



Does the following expectation-based inequality hold?
No, the factor $\frac1{\sqrt A}$ is the best you can get.


Indeed, letting $\mathcal X=[n]:=\{1,\dots,n\}$ and $a\_x:=p^2(x|y)$, we have


$$R\_n:=\frac{E\sqrt{\sum\_{x\in\mathcal{X}}p^2(x|y)1[\mathcal{F}(x)=1]}}{\sqrt{\sum\_{x\in\mathcal{X}}p^2(x|y)}}
=E\sqrt{\frac
{\sum\_{i\in[n]} a\_i Y\_i}
{\sum\_{i\in[n]} a\_i} },$$
where the $Y\_i$'s are iid Bernoulli random variables such that $P(Y\_1=1)=\frac1A=1-P(Y\_1=0)$.


If now, say, $a\_i=a>0$ for all $i\in[n]$, then, by the law of large numbers and the Fatou lemma,
$$\liminf\_{n\to\infty}R\_n=\liminf\_{n\to\infty}E\sqrt{\frac
{\sum\_{i\in[n]} Y\_i}n }\ge\sqrt{EY\_1}=\frac1{\sqrt A}.$$
Thus, the factor $\frac1{\sqrt A}$ is the best you can get, as claimed.




---


(Of course, for your question to make sense, you should have said "Let $\mathcal{F}$ be a uniformly distributed random element of the space of all functions that map the alphabet $\mathcal{X}$ to the set $\{1,2,\ldots,A\}$" instead of "Let $\mathcal{F}$ be the space of all functions that uniformly and independently map the alphabet $\mathcal{X}$ to the set $\{1,2,\ldots,A\}$".)


