# $\{X_n\}$ are iid random variables with symmetric distribution

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.

• By symmetric do you mean $P \{X_k \le \alpha\} = P \{ -X_k \le \alpha \}$? – copper.hat Nov 11 '14 at 4:56
• Yes, $X\stackrel{d}{=}-X$ – Sayan Nov 11 '14 at 4:57
• 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. – user35546 Nov 11 '14 at 18:31
• Well, $n=2$ is straightforward if you deal with the four quadrants separately. – copper.hat Nov 11 '14 at 23:05
• Is this an exercise from a book? If so which? – 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.

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:

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*}

• 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... – copper.hat Nov 15 '14 at 4:11
• 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)$. – user35546 Nov 15 '14 at 5:31
• 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. – user35546 Nov 15 '14 at 5:44
• 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. – 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}$.