42
$\begingroup$

A colleague popped into my office this afternoon and asked me the following question. He told me there is a clever proof when $n=2$. I couldn't do anything with it, so I thought I'd post it here and see what happens.

Prove or find a counterexample

For positive, i.i.d. random variables $Z_1,\dots, Z_n$ with finite mean, and positive constants $a_1,\dots, a_n$, we have $$\mathbb{E}\left({\sum_{i=1}^n a_i^2 Z_i\over\sum_{i=1}^n a_i Z_i}\right) \leq {\sum_{i=1}^n a_i^2\over\sum_{i=1}^n a_i}.$$


Added: This problem originates from the thesis of a student in Computer and Electrical Engineering at the University of Alberta. Here is the response from his supervisor: "Many thanks for this! It is a nice result in addition to being useful in a practical problem of antenna placement."

$\endgroup$
23
+500
$\begingroup$

Yes, the inequality always holds for i.i.d. random variables $Z_1,\ldots,Z_n$. In fact, as suggested by Yuval and joriki, it is enough to suppose that the joint distribution is invariant under permuting the $Z_i$. Rearranging the inequality slightly, we just need to show that the following is nonnegative (here, I am using $\bar a\equiv\sum_ia_i^2/\sum_ia_i$) $$ \bar a-\mathbb{E}\left[\frac{\sum_ia_i^2Z_i}{\sum_ia_iZ_i}\right]=\sum_ia_i(\bar a-a_i)\mathbb{E}\left[\frac{Z_i}{\sum_ja_jZ_j}\right]. $$ I'll write $c_i\equiv\mathbb{E}[Z_i/\sum_ja_jZ_j]$ for brevity. Then, noting that $\sum_ia_i(\bar a-a_i)=0$, choosing any constant $\bar c$ that we like, $$ \bar a-\mathbb{E}\left[\frac{\sum_ia_i^2Z_i}{\sum_ia_iZ_i}\right]=\sum_ia_i(\bar a-a_i)(c_i-\bar c). $$ To show that this is nonnegative, it is enough to show that $c_i$ is a decreasing function of $a_i$ (that is, $c_i\le c_j$ whenever $a_i\ge a_j$). In that case, we can choose $\bar c$ so that $\bar c\ge c_i$ whenever $a_i\ge\bar a$ and $\bar c\le c_i$ whenever $a_i\le\bar a$. This makes each term in the final summation above positive and completes the proof.

Choosing $i\not=j$ such that $a_i \ge a_j$, $$ c_i-c_j=\mathbb{E}\left[\frac{Z_i-Z_j}{\sum_ka_kZ_k}\right] $$ Let $\pi$ be the permutation of $\{1,\ldots,n\}$ which exchanges $i,j$ and leaves everything else fixed. Using invariance under permuting $Z_i,Z_j$, $$ \begin{align} 2(c_i-c_j)&=\mathbb{E}\left[\frac{Z_i-Z_j}{\sum_ka_kZ_k}\right]-\mathbb{E}\left[\frac{Z_i-Z_j}{\sum_ka_kZ_{\pi(k)}}\right]\cr &=\mathbb{E}\left[\frac{(a_j-a_i)(Z_i-Z_j)^2}{\sum_ka_kZ_k\sum_ka_kZ_{\pi(k)}}\right]\cr &\le0. \end{align} $$ So $c_i$ is decreasing in $a_i$ as claimed.


Note: In the special case of $n=2$, we can always make the choice $\bar c=(c_1+c_2)/2$. Then, both terms of the summation on the right hand side of the second displayed equation above are the same, giving $$ \bar a-\mathbb{E}\left[\frac{\sum_ia_i^2Z_i}{\sum_ia_iZ_i}\right]=\frac{a_1a_2(a_2-a_1)(c_1-c_2)}{a_1+a_2}. $$ Plugging in my expression above for $2(c_1-c_2)$ gives the identity $$ \bar a-\mathbb{E}\left[\frac{\sum_ia_i^2Z_i}{\sum_ia_iZ_i}\right]=\frac{a_1a_2(a_1-a_2)^2}{2(a_1+a_2)}\mathbb{E}\left[\frac{(Z_1-Z_2)^2}{(a_1Z_1+a_2Z_2)(a_1Z_2+a_2Z_1)}\right], $$ which is manifestly nonnegative. I'm guessing this could be the "clever" proof mentioned in the question.

Note 2: The proof above relies on $\mathbb{E}[Z_i/\sum_ja_jZ_j]$ being a decreasing function of $a_i$. More generally, for any decreasing $f\colon\mathbb{R}^+\to\mathbb{R}^+$, then $\mathbb{E}[Z_if(\sum_ja_jZ_j)]$ is a decreasing function of $a_i$. Choosing positive $b_i$ and setting $\bar a=\sum_ia_ib_i/\sum_ib_i$ then $\sum_ib_i(\bar a-a_i)=0$. Applying the argument above gives the inequality $$ \mathbb{E}\left[f\left(\sum_ia_iZ_i\right)\sum_ia_ib_iZ_i\right] \le \mathbb{E}\left[f\left(\sum_ia_iZ_i\right)\sum_ib_iZ_i\right]\frac{\sum_ia_ib_i}{\sum_ib_i} $$ The inequality in the question is the special case with $b_i=a_i$ and $f(x)=1/x$.

$\endgroup$
  • $\begingroup$ This is a nice proof. I replied to your comment under my answer (I don't know whether you still got notified of that since I deleted it because it was wrong, as you suspected). $\endgroup$ – joriki Mar 14 '12 at 22:34
  • $\begingroup$ @joriki: I saw the comment, thanks. $\endgroup$ – George Lowther Mar 14 '12 at 22:39
  • $\begingroup$ Great, unexpected proof! $\endgroup$ – Yuval Filmus Mar 14 '12 at 23:06
  • $\begingroup$ @GeorgeLowther Thanks very much for this, George! I was starting to lose hope. $\endgroup$ – user940 Mar 15 '12 at 0:56
3
$\begingroup$

Since the $Z_i$ are i.i.d., the expectation is the same if we rename the variables. Taking all permutations, your inequality is equivalent to $$ \mathbb{E} \left[ \frac{1}{n!} \sum_{\pi \in S_n} \frac{\sum_{i=1}^n a_i^2 Z_{\pi(i)}}{\sum_{i=1}^n a_i Z_{\pi(i)}} \right] \leq \frac{\sum_{i=1}^n a_i^2}{\sum_{i=1}^n a_i}. $$ Going over all possible values of $Z_1,\ldots,Z_n$, this is the same as the following inequality for positive real numbers: $$ \frac{1}{n!} \sum_{\pi \in S_n} \frac{\sum_{i=1}^n a_i^2 z_{\pi(i)}}{\sum_{i=1}^n a_i z_{\pi(i)}} \leq \frac{\sum_{i=1}^n a_i^2}{\sum_{i=1}^n a_i}. $$ Intuitively, the maximum is attained at $z_i = \text{const}$, which is why we get the right-hand side. This is indeed true for $n = 2$, which is easy to check directly.

$\endgroup$
  • 1
    $\begingroup$ Why is it intuitive that the maximum is attained at $z_i=\rm const$? $\endgroup$ – George Lowther Mar 12 '12 at 0:33
  • $\begingroup$ Since the new inequality is equivalent to the old one, and if it were true, then it would indeed be maximized at $z_i = \text{const}$. If I knew a better reason, I'd complete the proof. $\endgroup$ – Yuval Filmus Mar 12 '12 at 4:47
2
$\begingroup$

I've been toying with a concavity argument and Jensen's theorem. For $n=2$ I think this works, as shown below. Unfortunately it falls flat for $n > 2$. In fact for $n > 2$ the restriction to any convex set $x_1 + \dotsc + x_n = \lambda$ can be shown to be not concave. So, here goes the partial result.

Let

$$ f(x_1, x_2) = \frac{a_1^2x_1 + a_2^2x_2}{a_1x_1+a_2x_2}. $$

Then $f$ restricted to the convex segment $I=\{(x_1,x_2) \mid x_1,x_2 \geq 0 \textrm{ and } x_1+x_2=1\}$ is a concave function. This can be checked in multiple ways, for example by explicitly computing the second derivative

$$ \frac{\partial^2}{\partial x^2} f(x, 1-x) = \frac{-2a_1a_2(a_1-a_2)^2}{(a_1x+a_2(1-x))^3} $$

and noting that it is non-positive for $x \in [0,1]$. Assume that the joint distribution of $(Z_1,Z_2)$ induces a probability distribution on $I$, then it is symmetric under $(x_1,x_2) \mapsto (x_2, x_1)$. In particular the expected values for the coordinates on $I$ are equal and therefore $\mathbb{E}(x_1) = \mathbb{E}(x_2) = \tfrac{1}{2}$. Then by Jensen's theorem for concave functions on $I$:

$$ \mathbb{E}(f(x_1,x_2)) \leq f(\mathbb{E}(x_1),\mathbb{E}(x_2)) = f(\tfrac{1}{2},\tfrac{1}{2}) = \frac{a_1^2+a_2^2}{a_1+a_2}. $$

Now $f$ is a radial function and the same reasoning applies to all segments $x_1+x_2 = \lambda$ for $\lambda > 0$. And even though the induced distribution depends on the parameter $\lambda$, the inequality above will hold for each such segment and hence also for the joint distribution $(Z_1,Z_2)$.

$\endgroup$
  • $\begingroup$ In fact, in this argument $a_1^2$ and $a_2^2$ can be replaced by any positive $b_1$ and $b_2$ such that (say) $a_1<a_2, \frac{b_2}{a_2}>\frac{b_1}{a_1}$. It is not clear how this can be extended to the $n>2$ case. $\endgroup$ – Ewan Delanoy Mar 12 '12 at 18:23
  • $\begingroup$ @EwanDelanoy, it cannot be extended, since the function is not concave on such sections for $n > 2$. $\endgroup$ – WimC Mar 12 '12 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy