MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Help prove a maximal inequality

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

-
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 2011 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 2011 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 2011 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 2011 at 18:00
The motivation: math.stackexchange.com/questions/94948/… – Byron Schmuland Dec 31 2011 at 19:11

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

-