Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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."

share|improve this question
add comment

3 Answers

up vote 19 down vote accepted
+500

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$.

share|improve this answer
    
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). –  joriki Mar 14 '12 at 22:34
    
@joriki: I saw the comment, thanks. –  George Lowther Mar 14 '12 at 22:39
    
Great, unexpected proof! –  Yuval Filmus Mar 14 '12 at 23:06
    
@GeorgeLowther Thanks very much for this, George! I was starting to lose hope. –  Byron Schmuland Mar 15 '12 at 0:56
add comment

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.

share|improve this answer
1  
Why is it intuitive that the maximum is attained at $z_i=\rm const$? –  George Lowther Mar 12 '12 at 0:33
    
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. –  Yuval Filmus Mar 12 '12 at 4:47
add comment

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)$.

share|improve this answer
    
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. –  Ewan Delanoy Mar 12 '12 at 18:23
    
@EwanDelanoy, it cannot be extended, since the function is not concave on such sections for $n > 2$. –  WimC Mar 12 '12 at 18:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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