Let $X_1,X_2,\ldots,X_n$ be iid random variables with symmetric distribution. Show that $$P\left(|X_1+X_2+\cdots+X_n|\ge \max_{1\le i\le n}|X_i|\right)\ge \frac12.$$

I was trying it for $n=2$. Let $I=P(|X+Y|\ge |X| \cap |X+Y| \ge |Y|)$. It is equivalent to $$1-P(|X+Y|<|X| \cup |X+Y|<|Y|)=1-2P(|X+Y|<|X|)=1-2P(Y^2<-2XY)$$ Now $P(Y^2<-2XY)=P(Y^2<-2XY\mid XY\le 0)P(XY\le 0)=\frac12(P(Y^2<-2XY\mid XY\le 0)$. But could not proceed further.

  • $\begingroup$ By symmetric do you mean $P \{X_k \le \alpha\} = P \{ -X_k \le \alpha \}$? $\endgroup$ – copper.hat Nov 11 '14 at 4:56
  • $\begingroup$ Yes, $X\stackrel{d}{=}-X$ $\endgroup$ – Sayan Nov 11 '14 at 4:57
  • $\begingroup$ For $n=2$ you can try a brute force cases argument. Set $f(X,Y) := |X+Y| - max(|X|,|Y|)$. If $0 \le X \le Y, f(X,Y) = X$. If $X \le 0 \le Y$ and $|X| \le |Y|$ then $f(X,Y) = X$. If $X \le Y \le 0$ then $f(X,Y) = -Y$. In each case $P(f(X,Y) \ge 0) = \frac{1}{2}$ by symmetry of the distribution. The other cases should follow since $X$ and $Y$ are identically distributed. $\endgroup$ – user35546 Nov 11 '14 at 18:31
  • 1
    $\begingroup$ Well, $n=2$ is straightforward if you deal with the four quadrants separately. $\endgroup$ – copper.hat Nov 11 '14 at 23:05
  • $\begingroup$ Is this an exercise from a book? If so which? $\endgroup$ – user35546 Nov 14 '14 at 0:55

Define $E_n$ to be the event that $|X_1 + \dots + X_n| \ge \max_{1 \le i \le n} |X_i|$. With $P(E_2) \ge \frac{1}{2}$ established, we proceed by induction. Assuming that $P(E_n) \ge \frac{1}{2}$, we will argue that $P(E_{n+1}) \ge \frac{1}{2}$.

The proof begins by conditioning $P(E_{n+1})$ on whether the maximum is achieved at $X_{n+1}$. Letting $A$ be the event that $\max_{1\le i\le n+1}|X_i| = |X_{n+1}|$ we have the decomposition:

$$ P(E_{n+1}) = P(E_{n+1}|A)P(A) + P(E_{n+1}|A^c)P(A^c) $$

The goal will be to show that $P(E_{n+1}|A)$ and $P(E_{n+1}|A^c)$ are both greater than $\frac{1}{2}$. This will imply that $P(E_{n+1}) \ge \frac{1}{2}$.

Before proceeding we need to introduce some notation. For convenience let $S_n := X_1 + \dots + X_n$. In order to simplify the proof, I will assume that neither $S_n$ nor $X_{n+1}$ are equal to zero. Under this assumption, define $F$ to be the event that $S_n$ and $X_{n+1}$ have the same sign. Note that $P(F) = \frac{1}{2}$ by symmetry of the distribution. Note further and that $E_n$ and $F$ are independent and conditionally independent given $A$.

We consider the cases of $A$ and $A^c$ separately. In each case we will have to condition into further subcases.

Case 1: $P(E_{n+1}|A)$

In this case we have

$$ \begin{align*} P(E_{n+1}|A) &= P\left(|S_n + X_{n+1}| \ge \max_{1\le i \le n+1}|X_i| \Big| A\right)\\ &= P\Bigl(|S_n + X_{n+1}| \ge |X_{n+1}|\Bigr)\\ &= P\Bigl(|S_n + X_{n+1}| \ge |X_{n+1}|\Bigr | F\Bigr)P(F) + P\Bigl(|S_n + X_{n+1}| \ge |X_{n+1}|\Bigr | F^c\Bigr)P(F^c) \end{align*} $$

It is clear that $P\Bigl(|S_n + X_{n+1}| \ge |X_{n+1}| \Bigr| F\Bigr) = 1$. Since $P(F) = \frac{1}{2}$, we conclude that $P(E_{n+1}|A) \ge \frac{1}{2}$.

Case 2: $P(E_{n+1}|A^c)$

Suppose the maximum is achieved at some index $m < n+1$ so that $$\max_{1\le i \le n+1}|X_i| = |X_m|$$

The quantity of interest is now

$$ P(E_{n+1}|A^c) = P(|S_n + X_{n+1}|\ge |X_m|) $$ Now we will break Case 2 into four sub-subcases and then combine them at the end to show that $P(E_{n+1}|A^c) \ge \frac{1}{2}$. The first subcase to consider is whether $|S_n| \ge |X_m|$. Using previously defined notation this is the event $E_n$.

Subcase 2a: $P(E_{n+1}|A^c,E_n)$

$S_n$ can be positive or negative as depicted on the graph below.

Relative positions of $S_n$ and $X_{n+1}$ on the event $E_n$

We consider sub-subcases defined by looking at whether $S_n$ and $X_{n+1}$ have the same sign. That is, we further condition on the event $F$.

Sub-subcase 2a(i): $P(E_{n+1}|A^c,E_n,F)$

It's clear that in this sub-subcase $P(E_{n+1}|A^c,E_n,F) = 1$

Sub-subcase 2a(ii): $P(E_{n+1}|A^c,E_n,F^c)$

In this sub-subcase, we still have some hope that $|S_n + X_{n+1}| \ge |X_m|$. This will happen if $X_{n+1}$ is not too big in absolute value. To be precise the desired inequality holds if $|X_{n+1}| \le \Bigl||X_m| - |S_n|\Bigr|$. And so in this sub-subcase we have

$$ P(E_{n+1}|A^c,E_n,F^c) = P\Bigl(|X_{n+1}| \le \Bigl||X_m| - |S_n|\Bigr|\Bigr) $$

Define $G$ to be the event that $|X_{n+1}| \le \Bigl||X_m| - |S_n|\Bigr|$. We will need this later.

Subcase 2b: $P(E_{n+1}|A^c,E_n^c)$

Now the relative positions are reversed:

Relative positions of $S_n$ and $X_{n+1}$ on the event $E_n^c$

We break into sub-subcases by conditioning on $F$ as before.

Sub-subcase 2b(i): $P(E_{n+1}|A^c,E_n^c,F)$

In this sub-subcase, in order to have $|S_n + X_{n+1}| \ge |X_m|$, we need $|X_{n+1}|$ to be large. To be exact $|S_n + X_{n+1}| \ge |X_m|$ if $|X_{n+1}| \ge \Bigl||X_m| - |S_n|\Bigr|$. And we note that this is event is precisely $G^c$. So in this sub-subcase we have

$$ P(E_{n+1}|A^c,E_n^c,F) = P(G^c) $$

Sub-subcase 2b(ii): $P(E_{n+1}|A^c,E_n^c,F^c)$

There is no hope here. In this sub-subcase we have $P(E_{n+1}|A^c,E_n^c,F^c)= 0$.

There are no more sub-cases (or sub-subcases) to consider.

It is left to actually do the calculation to show that $P(E_{n+1}|A^c) \ge \frac{1}{2}$. We have:

$$ \begin{align*} P(E_{n+1}|A^c) &= P(E_{n+1}|A^c,E_n,F)P(E_n)P(F) + P(E_{n+1}|A^c,E_n,F^c)P(E_n)P(F^c) \\ &+ P(E_{n+1}|A^c,E_n^c,F)P(E_n^c)P(F) + P(E_{n+1}|A^c,E_n^c,F^c)P(E_n^c)P(F^c)\\ &= \frac{1}{2}P(E_n) + \frac{1}{2}P(E_n)P(G) + \frac{1}{2}P(E_n^c)P(G^c) + 0\\ &= \frac{1}{2}\Bigl[ P(E_n) + P(E_n)P(G) + P(E_n^c)\bigl(1 - P(G)\bigr)\Bigr]\\ &= \frac{1}{2}\Bigl[1 + P(E_n)P(G) - P(E_n^c)P(G) \Bigr] \\ &\ge \frac{1}{2} \quad \text{by the induction hypothesis } \square\\ \end{align*} $$

  • $\begingroup$ I am having difficulty following your proof. For example, the 3rd paragraph. You have if some condition then $P(E_{n+1}) = ...$, but the probability of the event $E_{n+1}$ cannot depend on the condition? I am missing something... $\endgroup$ – copper.hat Nov 15 '14 at 4:11
  • $\begingroup$ The entire proof is an exhaustive case analysis. The first case I'd like to consider is whether $\max_{1\le i \le n+1}|X_i| = |X_{n+1}|$. Call this event $A$. The third paragraph argues that on $A, \quad P(E_{n+1}) \ge \frac{1}{2}$. Then the rest of the proof is a calculation that $P(E_{n+1}) \ge \frac{1}{2}$ on $A^c$ as well. So technically, whenever I write $P(E_{n+1})$ after the 3rd paragraph I really mean $P(E_{n+1}|A^c)$. $\endgroup$ – user35546 Nov 15 '14 at 5:31
  • $\begingroup$ The argument that $P(E_{n+1}|A) \ge \frac{1}{2}$ proceeds by considering the subcases defined by the event $F_n$. The result follows by noting that $|S_n + X_{n+1}| \ge |X_{n+1}|$ is always true on the event $F_n$. But, yes, the proof is not so easy to follow. I will think about an edit to clarify. $\endgroup$ – user35546 Nov 15 '14 at 5:44
  • $\begingroup$ Thanks Joe. I think two things are throwing me, one is notation, and the other (bigger one) is that I am not getting the general idea of the proof. I will try again tomorrow. $\endgroup$ – copper.hat Nov 15 '14 at 5:56

Here is an answer for $n=2$. Let $A=\{x | |x_1+\cdots x_n| \ge \|x\|_\infty \}$. Also note that if $x\in A$, then $-x \in A$. Let $B=\{ x | x_1 = 0 \text{ or } x_2 = 0 \}$, we see that $B \subset A$. Let $Q_k^\circ$ be the interior of the four quadrants, we see that $Q_1^\circ \subset A$ and hence $Q_3^\circ \subset A$. Note that $B,Q_k^\circ$ form a partition of $\mathbb{R}^2$. Since the distributions are symmetric, we see that $P Q_1^\circ = \cdots =P Q_4^\circ$, and since $PB + 4 P Q_1^\circ =1$, we see that $P A \ge PB + 2 P Q_1^\circ \ge {1 \over 2} (PB + 4 P Q_1^\circ) = {1 \over 2}$.


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.