Skip to main content
added 2 characters in body
Source Link
Iosif Pinelis
  • 127.8k
  • 8
  • 107
  • 229

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^{-n} $$$$ \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^{-n} \,. $$$$\Pr[|\sum_{i \in [n]} X_i| \ge t]=2^{1-n} \,. $$

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^{-n} $$ but $$\Pr[|\sum_{i \in [n]} X_i| \ge t]=2^{-n} \,. $$

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

Source Link
Yuval Peres
  • 14.2k
  • 1
  • 28
  • 49

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^{-n} $$ but $$\Pr[|\sum_{i \in [n]} X_i| \ge t]=2^{-n} \,. $$