2
$\begingroup$

Consider the following claim.

Let $a_i$'s and $y_i$'s be positive real numbers such that: \begin{gather*} y_1 \leq y_2 \leq y_3 \ldots \leq y_n \\ a_1 y_1 + a_2 y_2 + a_3 y_3 + \dots + a_n y_n = v \\ y_1 + y_2 + y_3 + \dots + y_n = 1 \end{gather*} Show that there exists an $i$ such that: $$AVG(a_i, a_{i+1}, a_{i+2}, \ldots, a_n) \geq v.$$

I do have a proof for the above claim (assume the contrary; get $n$ equations; multiply $i^{th}$ equation by $y_{i+1} - y_i$). But, I'm looking for a more intuitive explanation — perhaps, a more "visual" or more insightful proof. Or even insights into why the above is true (without actually proving it).

$\endgroup$
6
  • 2
    $\begingroup$ What if $y_{i+1} - y_i$ is negative? Or are you assuming that $y_1 \leq \cdots \leq y_n$? Indeed, if $n = 2$, $y_1 = 1$, $y_2 = 0$, $a_1 = v = 3$ and $a_2 = 1$ then $a_2 < v$ and $(a_1 + a_2)/2 < v$. (If you don't like zeroes, change it to $y_1 = 1-\epsilon$ and $y_2 = \epsilon$.) $\endgroup$ Jul 31 at 10:37
  • 1
    $\begingroup$ You can think of $y_1,\ldots,y_n$ as specifying a probability distribution, with respect to which $\mathbb{E}[a_i] = v$. $\endgroup$ Jul 31 at 10:38
  • $\begingroup$ @Brian The claim is incorrect if you allow for $y$'s and $a$'s to be $0$. So your proof will have to somehow use the fact $a_i,y_i>0$ $\endgroup$
    – nir shahar
    Jul 31 at 10:42
  • $\begingroup$ Yes, $y_1 \leq y_2 \leq y_3 \ldots \leq y_n$ is indeed true. I didn't realize that the proof was using it (it is) -- that's why hadn't added to the problem description. The $a_i$'s and $y_i$'s can be zero -- in fact, $a_n$ is actually zero (in the context where the above claim is coming from). $\endgroup$
    – Brian
    Jul 31 at 14:08
  • $\begingroup$ Why is this in CS rather than Mathematics? $\endgroup$
    – Barmar
    Jul 31 at 17:26
4
$\begingroup$

Since the $y_i$ are non-negative, you can think of $y_1,\ldots,y_n$ as specifying a probability distribution. One way to sample from this distribution is via the partition $$ [0,1) = [0,y_1) \cup [y_1,y_1+y_2) \cup [y_1+y_2,y_1+y_2+y_3) \cup \cdots: $$ sample a uniform point in $[0,1]$, and if it falls into the $i$'th interval, output $i$.

We now further decompose these intervals, assuming that $y_1 \leq \cdots \leq y_n$:

  • The interval $[0,y_1)$ is decomposed into one subinterval of length $y_1$.
  • The interval $[y_1,y_1+y_2)$ is decomposed into subintervals of length $y_1$ and $y_2-y_1$.
  • The interval $[y_1+y_2,y_1+y_2+y_3)$ is decomposed into subintervals of length $y_1,y_2-y_1,y_3-y_2$.
  • And so on. The $i$'th interval is decomposed into subintervals of length $y_1,y_2-y_1,\ldots,y_i-y_{i+1}$.

Altogether, we obtain:

  • $n$ subintervals of length $y_1$, appearing in intervals $1,\ldots,n$.
  • $n-1$ subintervals of length $y_2-y_1$, appearing in intervals $2,\ldots,n$.
  • $n-2$ subintervals of length $y_3-y_2$, appearing in intervals $3,\ldots,n$.
  • And so on, until a single subinterval of length $y_n-y_{n-1}$, appearing in the $n$'th interval.

By assumption, if we sample $i$ according to this distribution, then the expected value of $a_i$ is exactly $v$. In particular, there must exist a subinterval length $y_j - y_{j-1}$ (where $y_0 = 0$) such that the expected value of $a_i$, subject to the uniform point in $[0,1]$ falling inside a subinterval of this length, is at least $v$. This expected value is exactly the average of $a_j,\ldots,a_n$.

$\endgroup$
0

Your Answer

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

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