A probability inequality: probability that the normalized sum of i.i.d. random variables is bounded below, is bounded below

probabilityprobability theoryprobability-limit-theoremsreal-analysisstatistics

I have been told that the following fact is true. Let $X_1,X_2,X_3,\dots$ be i.i.d. random variables. Then there exists $\epsilon$ such that for all $n$,
$$\mathbb{P}\left(\frac{|X_1+\dots+X_n|}{\sqrt{n}}\geq \epsilon\right)\geq \delta.$$

Observe that $\epsilon$ does not depend on $n$. Both $\epsilon$ and $\delta$ are $>0$.

However, I am struggling to prove this, or find any reference. The kicker is that the $X_i$'s need not have finite mean or variance. In fact, I am interested in applying this "fact" to a situation where the $X_i$'s must have infinite variance (but possibly zero mean), so elementary things like Markov or Chebyshev's inequality won't help. I am unsure on how to proceed. Any hint would be greatly appreciated!

Update on progress: For the $X_i$ that I am interested in, I have deduced the condition
$$X_1+X_2+\dots+X_{2^k} \sim2^{k/4}X_i.$$
I also have proved the inequality
$$\mathbb{P}(|S_n|>t) \geq \frac{1}{2}\mathbb{P}(\max_j|X_j|>t)\geq\frac{1}{2}(1-e^{-n(1-F(t)+F(-t))}),$$
where $F$ is the c.d.f. of $X_i$. By $S_n$, I mean the $S_n=X_1+\dots+X_n$. Thus it seems like the issue boils down to analyzing the distribution of $X_i$.

Best Answer

Let me give a direct proof using characteristic functions. The setting is as follows:

$(X_n)$ and $(X'_n)$ are i.i.d.
$\tilde{X}_n = X_n - X'_n$ are symmetrized variables.
$S_n = X_1 + \cdots + X_n$ and $\tilde{S}_n = \tilde{X}_1 + \cdots + \tilde{X}_n$.

Under this setting, we want to prove that

Claim. If the law of $X_1$ is not degenerate, then there exists $\epsilon > 0$ such that $$ \inf_{n\geq 1} \mathbb{P}\left( |S_n| \geq \epsilon\sqrt{n} \right) > 0. $$

We prove the contraposition. To this end, assume that $\inf_n \mathbb{P}\left(|S_n|\geq \epsilon \sqrt{n}\right) = 0$ for any $\epsilon > 0$. Then exists $(n_k)$ such that $S_{n_k}/\sqrt{n_k} \to 0$ in probability. This implies that $\tilde{S}_{n_k}/\sqrt{n_k} \to 0$ in probability as well. So, if $\varphi(t) = \mathbb{E}[\cos(t\tilde{X}_1)] $ denotes the characteristic funtion of $\tilde{X}_1$, then

$$ \varphi\left( \frac{t}{\sqrt{n_k}} \right)^{n_k} = \mathbb{E}[\exp\{\mathrm{i}t \tilde{S}_{n_k}/\sqrt{n_k}\}] \xrightarrow[k\to\infty]{} 1 $$

by the Portmanteau theorem. By taking $\log|\cdot|$, we have $n_k \log\left| \varphi\left( \frac{t}{\sqrt{n_k}} \right) \right| \to 0$. But since

$ \varphi\left( \frac{t}{\sqrt{n_k}} \right) = 1 - 2 \mathbb{E}\left[ \sin^2\left( \frac{t\tilde{X}_1}{2\sqrt{n_k}}\right) \right] $ by the double-angle identity;
$\mathbb{E}\left[ \sin^2\left( \frac{t\tilde{X}_1}{2\sqrt{n_k}}\right) \right] \to 0$ by the dominated convergence theorem;

it follows that

$$ n_k \mathbb{E}\left[ \sin^2\left( \frac{t\tilde{X}_1}{2\sqrt{n_k}}\right) \right] \xrightarrow[k\to\infty]{} 0. $$

Plugging $t = 2$ and applying the monotone convergence theorem and the squeezing lemma,

$$ \mathbb{E}[\tilde{X}_1^2] = \lim_{k\to\infty} \mathbb{E}\left[ n_k \sin^2\left( \frac{\tilde{X}_1}{\sqrt{n_k}}\right) \mathbf{1}_{\{ |\tilde{X}_1| \leq \frac{\pi}{2}\sqrt{n_k} \}} \right] = 0, $$

and therefore $X_1$ is degenerate.

Related Solutions

Finding upper bounds on probability that a sum of random variables exceeds some value

Use Chernoff or Hoeffding here, they will be tighter than Chebyshev. And things are symmetric, so $\mathbb{P}\{ S_n \geq x\} = \mathbb{P}\{ S_n \leq -x\}$: $$ \forall x\in [0,1], \qquad \mathbb{P}\{ S_n \geq x\} = \frac{1}{2}\mathbb{P}\{ \lvert S_n\rvert \geq x\} $$

Probability – Non-i.i.d. Bernoulli Random Variables

Your calculated upper bound is an upper bound and your argument looks reasonable, but it is not the tightest possible.

If the $X_i$ can have any dependency, with large enough $n$ you can construct $\bar X$ to approximate any distribution on $[0,1]$ which has expectation $p$. There are three ranges of values of $\epsilon$ to consider:

$0< \epsilon < \min(p, 1-p)$: you can concentrate the distribution of $\bar X$ outside the interval $(p - \epsilon, p+\epsilon)$ so you can only say (as with any probability) $$\mathbb{P}(|\bar{X}-p| > \epsilon) \le 1$$
$\max(p, 1-p) < \epsilon$: in which case $p - \epsilon < 0$ and $p + \epsilon > 1$ and so you can say $$\mathbb{P}(|\bar{X}-p| > \epsilon) =0$$
$\min(p, 1-p) < \epsilon < \max(p, 1-p)$: you are only interested in one tail and if $0 < p< \frac12$ then $\mathbb{P}(|\bar{X}-p| > \epsilon) = \mathbb{P}(\bar{X}>p +\epsilon) \le \frac{\mathbb E[\bar X]}{p+\epsilon}= \frac{p}{p+\epsilon}$ using Markov's inequality, and similarly by symmetry if $\frac12 < p < 1$ then $\mathbb{P}(|\bar{X}-p| > \epsilon) = \mathbb{P}(\bar{X}< 1-p -\epsilon) \le \frac{1-p}{1-p+\epsilon}$, which you can combine to say $$\mathbb{P}(|\bar{X}-p| > \epsilon) \le \frac{1}{1+\frac{\epsilon}{\min(p,1-p)}}$$

As an illustration, here are the two upper bounds shown for $p=\frac13$, with yours in red and mine in blue.

Jessie asked for the code to draw this. Using R:

boundA <- function(p,epsilon){
  ifelse(epsilon < p & epsilon < 1-p, 1, 
  ifelse(epsilon > p & epsilon > 1-p, 0, 
  1 / (1 + epsilon / ifelse(p < 1-p, p, 1-p))))  
  }   
boundB <- function(p,epsilon){
  p*(1-p) / epsilon^2
  }   

pstring <- "1/3"
p <- eval(parse(text=pstring))
curve(boundA(p,x), from=0, to=1.15, ylim=c(0,2), col="blue", 
      n=50001, xlab="epsilon", ylab="upper bound on probability",
      main=paste(c("p = ", pstring), collapse=""))
curve(boundB(p,x), from=0, to=1.15, col="red", add=TRUE)

Best Answer

Related Solutions

Finding upper bounds on probability that a sum of random variables exceeds some value

Probability – Non-i.i.d. Bernoulli Random Variables

Related Question