MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $X_1,…,X_n$ are exchangeable of random variables, and $n$ is an even number. $S_k=X_1+\dots+X_k$. $M_k=X_{n/2}+\dots+X_{n/2+k}$.

I want to prove:

$$\Pr(\max_{1 \le k \le n}{|S_k|>\epsilon}) \le \\Pr(\max_{1 \le k \le n/2}{|S_k|>\epsilon/2}) + \Pr(\max_{1 \le k \le n/2}{|M_k|>\epsilon/2})$$

[added by YC] for background context to this question, see this MSE question

share|cite|improve this question
If $X_1,\dots, X_n$ are exchangeable, then doesn't $(S_1,\dots, S_{n/2})$ have the same distribution as $(M_1,\dots, M_{n/2})$? – Yemon Choi Dec 31 '11 at 9:04
Well, it isn't true in general. Take $X_i=1/n$ for all $i$ and $\epsilon=2/3$. – Brendan McKay Dec 31 '11 at 14:19
@BrendanMcKay, It is still right, the LHS is $\Pr(1>2/3)=1$, the RHS is $\Pr(1/2>1/3)+\Pr(1/2>1/3)=2$ – Fan Zhang Dec 31 '11 at 15:51
I think the summation for $M_k$ should start at $n/2 + 1$ so that it is the sum of $k$ terms. With this modification, as Yemon Choi pointed out, $M_k$ has the same distribution as $S_k$ so both probabilities on the right hand side are equal. – Pablo Lessa Dec 31 '11 at 18:00
The motivation:… – Byron Schmuland Dec 31 '11 at 19:11
up vote 4 down vote accepted

You can prove it by using the fact that the following holds always:

$\max_{1 \le k \le n}|S_k| \le \max_{1 \le k \le n/2}|S_k| + \max_{1 \le k \le n/2}|M_k|$

If the left hand side is larger than $\epsilon$ then one of the right hand terms is larger than $\epsilon/2$.

This also shows that the inequality is valid under absolutely no assumptions on the joint distribution of the variables $X_1,\ldots,X_n$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.