1
$\begingroup$

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}

$\endgroup$
2
  • 1
    $\begingroup$ What is $p$ here? What is $y$? $\endgroup$ Jan 24, 2023 at 15:20
  • $\begingroup$ $p(x|y)$ is a conditional distribution. You can replace it with any function of $x$. $\endgroup$
    – Math_Y
    Jan 24, 2023 at 15:39

1 Answer 1

1
$\begingroup$

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\}$".)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.