# Seeking an "intuitive" proof

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

• 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$.) Jul 31 at 10:37
• You can think of $y_1,\ldots,y_n$ as specifying a probability distribution, with respect to which $\mathbb{E}[a_i] = v$. Jul 31 at 10:38
• @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$ Jul 31 at 10:42
• 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). Jul 31 at 14:08
• Why is this in CS rather than Mathematics? Jul 31 at 17:26

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