Jian's inequality

From Samirrg
Jump to: navigation, search

The following inequality is needed in the proof of correctness of Chudak's facility location algorithm, which was presented on 2008-07-25.

<math>\sum_{i=1}^n \left( c_i y_i \prod_{j=1}^{i-1}(1-y_j) \right) \le \left( \sum_{i=1}^n c_i y_i \right)\left( 1 - \prod_{j=1}^n(1 - y_j) \right)</math>

(Assuming that <math>c_1 \le \cdots \le c_n</math>.)

Here's the proof Jian gave me (Matt) on 2008-08-01:

Lemma: Let <math>(a_i)_{i=1}^n</math> and <math>(b_i)_{i=1}^n</math> be two sequences of real numbers. Suppose <math>\sum_{i=1}^n a_i \ge 0</math>, <math>(a_i)_{i=1}^n</math> consists of nonpositive terms followed by nonnegative terms, and <math>0 \le b_1 \le \cdots \le b_n</math>. Then <math>\sum_{i=1}^n a_i b_i \ge 0</math>.

Proof: Observe that, for every <math>j = 1,\ \ldots,\ n</math>, <math>\sum_{i=j}^n a_i \ge 0</math> because <math>\sum_{i=j}^n a_i</math> either consists entirely of nonnegative terms or can be obtained from the nonnegative <math>\sum_{i=1}^n a_i</math> by removing nonpositive terms. Now, letting <math>b_0 = 0</math>, we have:

<math>\sum_{i=1}^n a_i b_i = \sum_{i=1}^n \left( a_i \sum_{j=1}^i (b_j - b_{j-1}) \right) = \sum_{j=1}^n \left( (b_j - b_{j-1}) \bigg( \sum_{i=j}^n a_i \bigg) \right) \ge 0</math>

as desired.

Main proof: Subtracting the left side of the inequality from the right gives the following equivalent inequality:

<math>\sum_{i=1}^n \left( c_i y_i \bigg( 1 - \prod_{j=1}^{i-1} (1 - y_j) - \prod_{j=1}^n (1 - y_j) \bigg) \right) \ge 0</math>

To prove this, we apply the lemma with <math>b_i = c_i</math> and <math>a_i = y_i \bigg( 1 - \prod_{j=1}^{i-1} (1 - y_j) - \prod_{j=1}^n (1 - y_j) \bigg)</math>. Clearly the <math>b_i</math> are increasing. The values <math>\bigg( 1 - \prod_{j=1}^{i-1} (1 - y_j) - \prod_{j=1}^n (1 - y_j) \bigg)</math> are increasing because increasing <math>i</math> adds factors to the second term, making it less negative; multiplying them by the positive <math>y_i</math> gives a sequence of nonpositive terms followed by nonnegative ones. We only have to show that <math>\sum_{i=1}^n a_i \ge 0</math>:

<math>\sum_{i=1}^n y_i \bigg( 1 - \prod_{j=1}^{i-1} (1 - y_j) - \prod_{j=1}^n (1 - y_j) \bigg) = \left( \sum_{i=1}^n y_i \right) \left( 1 - \prod_{j=1}^n (1 - y_j) \right) - \sum_{i=1}^n \left( y_i \prod_{j=1}^{i-1} (1 - y_j) \right)</math> <math>= 1 - \sum_{i=1}^n \left( y_i \prod_{j=1}^{i-1} (1 - y_j) \right) - \prod_{j=1}^n (1 - y_j) = 0.</math>

The last equality holds because the second term is the sum of each facility's probability that it is the closest one open and the third term is the probability that all facilities are closed, so together these account for all the possibilities. Q.E.D.