5
$\begingroup$

Let $X_1, \ldots, X_n$ be independent symmetric variables. Now I would like to know whether there exists a constant $C$, such that $$ \Pr[\max_{k \in [n]} |\sum_{i \in [n] \setminus \{k\}} X_i| \ge t] \le C\Pr[|\sum_{i \in [n]} X_i| \ge t] $$ Now similar inequalities are Levy's inequalities \begin{align} \label{eq:levy-sum} \Pr[\max_{1 \le l \le n} |\sum_{i = 1}^l X_i| \ge t] &\le 2 \Pr[|\sum_{i = 1}^n X_i| \ge t] \\ \label{eq:levy-individual} \Pr[\max_{1 \le l \le n} |X_l| \ge t] &\le 2 \Pr[|\sum_{i = 1}^n X_i| \ge t] \end{align} Unfortunately, I am unable to use the techniques used to prove Levy's inequality in my case.

The best result I have been able to prove is the following \begin{align*} \Pr[\max_{k \in [n]} |\sum_{i \in [n] \setminus \{k\}} X_i| \ge t] &\le \Pr[\max_{k \in [n]} |X_k| + |\sum_{i \in [n]} X_i| \ge t] \\&\le \Pr[\max_{k \in [n]} |X_k| \ge t/2] + \Pr[|\sum_{i \in [n]} X_i| \ge t/2] \\&\le 3\Pr[|\sum_{i \in [n]} X_i| \ge t/2] \end{align*} The last inequality follows from using the second of Levy's inequalities. But here we lose a factor of 2 on $t$, which I would like to avoid.

$\endgroup$
1
  • 1
    $\begingroup$ When citing Levy's inequalities you did not complete the RHS $\endgroup$ Commented Feb 2, 2021 at 3:40

1 Answer 1

6
$\begingroup$

Alas, no such inequality can hold. Suppose that the symmetric $X_i$ take values $\pm 1$ and $t=n-1$. Then $$ \Pr[\max_{k \in [n]} |\sum_{i \in [n] \setminus \{k\}} X_i| \ge t] =(n+1)2^{1-n} $$ but $$\Pr[|\sum_{i \in [n]} X_i| \ge t]=2^{1-n} \,. $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .