Skip to main content
MathOverflow

Return to Answer

simplified some notation and included the shorter proof of Lemma 2 as pointed out by Fedor
Source Link
Steve
Steve
  • 1.1k
  • 6
  • 16

I think I found an elementary proof of Question 2/3 for arbitrary probability distributions. In fact, it is not required that the components in the sums are squares, but general i.i.d. non-negative random variables work. Further, the requirement that both sums have an even number of terms ($2k$ and $2(n-k)$ in the question) is not required.

Let $X_1, ..., X_N$ be i.i.d. non-negative, integrable random variables. Let $T_k := \mathbb{E}[|\sum_{i=1}^k X_i - \sum_{i=k+1}^N X_i|]$.

Lemma 1: For $k \geq \lfloor N/2\rfloor$ it holds $T_{k+1} \geq T_k$.

By symmetry (for $k \leq \lfloor N/2\rfloor$) this Lemma yields the question. To prove Lemma 1, we require the two following supplementary statements

Lemma 2: Let $C$ be a symmetric, integrable random variable, and $a, b\in\mathbb{R}$, $|b| \geq |a|$. Then $\mathbb{E}[|C+b|] \geq \mathbb{E}[|C+a|]$.

Hereby, $C$ being symmetric means that $C = C^+ + C^-$, where $C^+ \geq 0 \geq C^-$ and $C^+$$C$ and $-C^-$$-C$ have the same distribution.

Lemma 3: Let $C$ be a symmetric, integrable random variable and $A$, $B$ non-negative and integrable random variables and assume that $A, B, C$ are independent. Then $\mathbb{E}[|C+A-B|] \leq \mathbb{E}[|C+A+B|]$.

Proof of Lemma 2: Without loss of generality, by symmetry of $C$, let $0\leq a\leq b$. Then one calculates $$ \mathbb{E}[|C+a|] = \mathbb{E}[\mathbb{1}_{a \geq |C|} (C+a) + \mathbb{1}_{a < |C|} (\mathbb{1}_{C > 0} + \mathbb{1}_{C < 0}) |C+a|]\\ = \mathbb{P}(|C| \leq a) a + \mathbb{E}[\mathbb{1}_{a < |C|} (\mathbb{1}_{C > 0} (C+a) + \mathbb{1}_{C < 0} (-C-a)]\\ =\mathbb{P}(|C| \leq a) a + \mathbb{E}[\mathbb{1}_{|C| > a} |C|] \\ =\mathbb{E}[\max\{a, |C|\}] $$\begin{align*} \mathbb{E}[|C+a|] &= \mathbb{E}[\mathbb{1}_{a \geq |C|} (C+a) + \mathbb{1}_{a < |C|} (\mathbb{1}_{C > 0} + \mathbb{1}_{C < 0}) |C+a|]\\ &= \mathbb{P}(|C| \leq a) a + \mathbb{E}[\mathbb{1}_{a < |C|} (\mathbb{1}_{C > 0} (C+a) + \mathbb{1}_{C < 0} (-C-a)]\\ &=\mathbb{P}(|C| \leq a) a + \mathbb{E}[\mathbb{1}_{|C| > a} |C|] \\ &=\mathbb{E}[\max\{a, |C|\}] \end{align*} and this term is obviously increasing in $a$. (in general, it simply holds $\mathbb{E}[|C+a|] = \mathbb{E}[\max\{|C|, |a|\}]$, which can also be proved via the identity $|C+a| + |-C+a| = 2\max\{|C|, |a|\}$ as pointed out by Fedor.)

Proof of Lemma 3: Let $C \sim \mu, A \sim \nu, B \sim \theta$. Then $$ \mathbb{E}[|C+A-B| - |C+A+B|] = \int \int \Big(\int |c+a-b| - |c+a+b| \mu(dc)\Big)\nu(da)\theta(db) \leq 0 $$ since the term inbetween the large brackets is non-positive since $|a+b| \geq |a-b|$ (since $a, b \geq 0$) and by Lemma 2.

Proof of Lemma 1: Let $C := \sum_{i=1}^{N-k-1} X_i - \sum_{i=k+1}^N X_i$ and note that $C$ is symmetric, $A := \sum_{i=N-k}^k X_i$ (where the sum is understood to be 0 if $k < N-k$), and $B := X_{k+1}$. Note that, for $k \geq \lfloor \frac{N}{2}\rfloor$, it holds $T_k = \mathbb{E}[|C+A-B|]$ and $T_{k+1} = \mathbb{E}[|C+A+B|]$. The claim now follows from Lemma 3.

I think I found an elementary proof of Question 2/3 for arbitrary probability distributions. In fact, it is not required that the components in the sums are squares, but general i.i.d. non-negative random variables work. Further, the requirement that both sums have an even number of terms ($2k$ and $2(n-k)$ in the question) is not required.

Let $X_1, ..., X_N$ be i.i.d. non-negative, integrable random variables. Let $T_k := \mathbb{E}[|\sum_{i=1}^k X_i - \sum_{i=k+1}^N X_i|]$.

Lemma 1: For $k \geq \lfloor N/2\rfloor$ it holds $T_{k+1} \geq T_k$.

By symmetry (for $k \leq \lfloor N/2\rfloor$) this Lemma yields the question. To prove Lemma 1, we require the two following supplementary statements

Lemma 2: Let $C$ be a symmetric, integrable random variable, and $a, b\in\mathbb{R}$, $|b| \geq |a|$. Then $\mathbb{E}[|C+b|] \geq \mathbb{E}[|C+a|]$.

Hereby, $C$ being symmetric means that $C = C^+ + C^-$, where $C^+ \geq 0 \geq C^-$ and $C^+$ and $-C^-$ have the same distribution.

Lemma 3: Let $C$ be a symmetric, integrable random variable and $A$, $B$ non-negative and integrable random variables and assume that $A, B, C$ are independent. Then $\mathbb{E}[|C+A-B|] \leq \mathbb{E}[|C+A+B|]$.

Proof of Lemma 2: Without loss of generality, by symmetry of $C$, let $0\leq a\leq b$. Then one calculates $$ \mathbb{E}[|C+a|] = \mathbb{E}[\mathbb{1}_{a \geq |C|} (C+a) + \mathbb{1}_{a < |C|} (\mathbb{1}_{C > 0} + \mathbb{1}_{C < 0}) |C+a|]\\ = \mathbb{P}(|C| \leq a) a + \mathbb{E}[\mathbb{1}_{a < |C|} (\mathbb{1}_{C > 0} (C+a) + \mathbb{1}_{C < 0} (-C-a)]\\ =\mathbb{P}(|C| \leq a) a + \mathbb{E}[\mathbb{1}_{|C| > a} |C|] \\ =\mathbb{E}[\max\{a, |C|\}] $$ and this term is obviously increasing in $a$. (in general, it simply holds $\mathbb{E}[|C+a|] = \mathbb{E}[\max\{|C|, |a|\}]$.)

Proof of Lemma 3: Let $C \sim \mu, A \sim \nu, B \sim \theta$. Then $$ \mathbb{E}[|C+A-B| - |C+A+B|] = \int \int \Big(\int |c+a-b| - |c+a+b| \mu(dc)\Big)\nu(da)\theta(db) \leq 0 $$ since the term inbetween the large brackets is non-positive since $|a+b| \geq |a-b|$ (since $a, b \geq 0$) and by Lemma 2.

Proof of Lemma 1: Let $C := \sum_{i=1}^{N-k-1} X_i - \sum_{i=k+1}^N X_i$ and note that $C$ is symmetric, $A := \sum_{i=N-k}^k X_i$ (where the sum is understood to be 0 if $k < N-k$), and $B := X_{k+1}$. Note that, for $k \geq \lfloor \frac{N}{2}\rfloor$, it holds $T_k = \mathbb{E}[|C+A-B|]$ and $T_{k+1} = \mathbb{E}[|C+A+B|]$. The claim now follows from Lemma 3.

I think I found an elementary proof of Question 2/3 for arbitrary probability distributions. In fact, it is not required that the components in the sums are squares, but general i.i.d. non-negative random variables work. Further, the requirement that both sums have an even number of terms ($2k$ and $2(n-k)$ in the question) is not required.

Let $X_1, ..., X_N$ be i.i.d. non-negative, integrable random variables. Let $T_k := \mathbb{E}[|\sum_{i=1}^k X_i - \sum_{i=k+1}^N X_i|]$.

Lemma 1: For $k \geq \lfloor N/2\rfloor$ it holds $T_{k+1} \geq T_k$.

By symmetry (for $k \leq \lfloor N/2\rfloor$) this Lemma yields the question. To prove Lemma 1, we require the two following supplementary statements

Lemma 2: Let $C$ be a symmetric, integrable random variable, and $a, b\in\mathbb{R}$, $|b| \geq |a|$. Then $\mathbb{E}[|C+b|] \geq \mathbb{E}[|C+a|]$.

Hereby, $C$ being symmetric means that $C$ and $-C$ have the same distribution.

Lemma 3: Let $C$ be a symmetric, integrable random variable and $A$, $B$ non-negative and integrable random variables and assume that $A, B, C$ are independent. Then $\mathbb{E}[|C+A-B|] \leq \mathbb{E}[|C+A+B|]$.

Proof of Lemma 2: Without loss of generality, by symmetry of $C$, let $0\leq a\leq b$. Then one calculates \begin{align*} \mathbb{E}[|C+a|] &= \mathbb{E}[\mathbb{1}_{a \geq |C|} (C+a) + \mathbb{1}_{a < |C|} (\mathbb{1}_{C > 0} + \mathbb{1}_{C < 0}) |C+a|]\\ &= \mathbb{P}(|C| \leq a) a + \mathbb{E}[\mathbb{1}_{a < |C|} (\mathbb{1}_{C > 0} (C+a) + \mathbb{1}_{C < 0} (-C-a)]\\ &=\mathbb{P}(|C| \leq a) a + \mathbb{E}[\mathbb{1}_{|C| > a} |C|] \\ &=\mathbb{E}[\max\{a, |C|\}] \end{align*} and this term is obviously increasing in $a$. (in general, it simply holds $\mathbb{E}[|C+a|] = \mathbb{E}[\max\{|C|, |a|\}]$, which can also be proved via the identity $|C+a| + |-C+a| = 2\max\{|C|, |a|\}$ as pointed out by Fedor.)

Proof of Lemma 3: Let $C \sim \mu, A \sim \nu, B \sim \theta$. Then $$ \mathbb{E}[|C+A-B| - |C+A+B|] = \int \int \Big(\int |c+a-b| - |c+a+b| \mu(dc)\Big)\nu(da)\theta(db) \leq 0 $$ since the term inbetween the large brackets is non-positive since $|a+b| \geq |a-b|$ (since $a, b \geq 0$) and by Lemma 2.

Proof of Lemma 1: Let $C := \sum_{i=1}^{N-k-1} X_i - \sum_{i=k+1}^N X_i$ and note that $C$ is symmetric, $A := \sum_{i=N-k}^k X_i$ (where the sum is understood to be 0 if $k < N-k$), and $B := X_{k+1}$. Note that, for $k \geq \lfloor \frac{N}{2}\rfloor$, it holds $T_k = \mathbb{E}[|C+A-B|]$ and $T_{k+1} = \mathbb{E}[|C+A+B|]$. The claim now follows from Lemma 3.

Source Link
Steve
Steve
  • 1.1k
  • 6
  • 16

I think I found an elementary proof of Question 2/3 for arbitrary probability distributions. In fact, it is not required that the components in the sums are squares, but general i.i.d. non-negative random variables work. Further, the requirement that both sums have an even number of terms ($2k$ and $2(n-k)$ in the question) is not required.

Let $X_1, ..., X_N$ be i.i.d. non-negative, integrable random variables. Let $T_k := \mathbb{E}[|\sum_{i=1}^k X_i - \sum_{i=k+1}^N X_i|]$.

Lemma 1: For $k \geq \lfloor N/2\rfloor$ it holds $T_{k+1} \geq T_k$.

By symmetry (for $k \leq \lfloor N/2\rfloor$) this Lemma yields the question. To prove Lemma 1, we require the two following supplementary statements

Lemma 2: Let $C$ be a symmetric, integrable random variable, and $a, b\in\mathbb{R}$, $|b| \geq |a|$. Then $\mathbb{E}[|C+b|] \geq \mathbb{E}[|C+a|]$.

Hereby, $C$ being symmetric means that $C = C^+ + C^-$, where $C^+ \geq 0 \geq C^-$ and $C^+$ and $-C^-$ have the same distribution.

Lemma 3: Let $C$ be a symmetric, integrable random variable and $A$, $B$ non-negative and integrable random variables and assume that $A, B, C$ are independent. Then $\mathbb{E}[|C+A-B|] \leq \mathbb{E}[|C+A+B|]$.

Proof of Lemma 2: Without loss of generality, by symmetry of $C$, let $0\leq a\leq b$. Then one calculates $$ \mathbb{E}[|C+a|] = \mathbb{E}[\mathbb{1}_{a \geq |C|} (C+a) + \mathbb{1}_{a < |C|} (\mathbb{1}_{C > 0} + \mathbb{1}_{C < 0}) |C+a|]\\ = \mathbb{P}(|C| \leq a) a + \mathbb{E}[\mathbb{1}_{a < |C|} (\mathbb{1}_{C > 0} (C+a) + \mathbb{1}_{C < 0} (-C-a)]\\ =\mathbb{P}(|C| \leq a) a + \mathbb{E}[\mathbb{1}_{|C| > a} |C|] \\ =\mathbb{E}[\max\{a, |C|\}] $$ and this term is obviously increasing in $a$. (in general, it simply holds $\mathbb{E}[|C+a|] = \mathbb{E}[\max\{|C|, |a|\}]$.)

Proof of Lemma 3: Let $C \sim \mu, A \sim \nu, B \sim \theta$. Then $$ \mathbb{E}[|C+A-B| - |C+A+B|] = \int \int \Big(\int |c+a-b| - |c+a+b| \mu(dc)\Big)\nu(da)\theta(db) \leq 0 $$ since the term inbetween the large brackets is non-positive since $|a+b| \geq |a-b|$ (since $a, b \geq 0$) and by Lemma 2.

Proof of Lemma 1: Let $C := \sum_{i=1}^{N-k-1} X_i - \sum_{i=k+1}^N X_i$ and note that $C$ is symmetric, $A := \sum_{i=N-k}^k X_i$ (where the sum is understood to be 0 if $k < N-k$), and $B := X_{k+1}$. Note that, for $k \geq \lfloor \frac{N}{2}\rfloor$, it holds $T_k = \mathbb{E}[|C+A-B|]$ and $T_{k+1} = \mathbb{E}[|C+A+B|]$. The claim now follows from Lemma 3.