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, 2014 at 4:56
  • $\begingroup$ Yes, $X\stackrel{d}{=}-X$ $\endgroup$
    – Sayan
    Nov 11, 2014 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, 2014 at 18:31
  • 1
    $\begingroup$ Well, $n=2$ is straightforward if you deal with the four quadrants separately. $\endgroup$
    – copper.hat
    Nov 11, 2014 at 23:05
  • $\begingroup$ Is this an exercise from a book? If so which? $\endgroup$
    – user35546
    Nov 14, 2014 at 0:55

2 Answers 2


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


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, 2014 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, 2014 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, 2014 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, 2014 at 5:56

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.