# Is it possible for a collection of independent $\{-1,1\}$-random variables whose sum equal to 0 is superexponentially small?

Suppose there is a collection of random variables $\{X_i\}_{i\ge 1}$ with $\mathbb{P}(X_i=1)=p_i$ and $\mathbb{P}(X_i=-1)=1-p_i$ for $p_i\in(0,1)$. Let $S_n=\sum_{i=1}^nX_i$. If we do not require $X_i$'s are independent, then it is easy to set $X_1=X_2=\dots$ with $\mathbb{P}(S_n=0)=0$. So if we require $X_i$'s are independent, does there exists such a collection with $\mathbb{P}(S_n=0)\le e^{-\omega(n)\cdot n}$, where $\omega(n)\to+\infty$ when $n\to \infty$?

My intuition is that if we allow $p_i$ equal to 0 or 1, and then we set $X_i$'s as constants and guarantee for any $n$, numbers of 1 and -1 are not equal, then the probability should be 0. I am wondering if $P(S_n=0)$ changes continuously as $p_i$ changes. If so, it is hopeful that the probability could be exponentially small.

• if you take $p_n=\frac{1}{n^2}$ then by Borel-Cantelli you have that $S_n\rightarrow -\infty$ almost surely – clark Sep 11 '17 at 21:24
• Yes, it implies infinitely many 1 occurs with probability 0, so $\mathbb{P}(S_n=0)\to 0$. But does it means $\mathbb{P}(S_n=0)$ is super exponentially small? – Connor Sep 11 '17 at 21:31

You can't have superexponential decay. Indeed take $n=2k$ for $k \in \mathbb{N}$ (for uneven $k$ there $S_n =0$ is not possible). Then we can find a lower bound for the probability that the sum vanishes. Indeed the sum vanishes if the first $k$ terms are 1 and the last are $-1.$
Thus we can bind $$\mathbb{P}(S_n = 0)\ge p^k(1-p)^k = \exp \bigg(\frac{n}{2} \log(p(1-p))\bigg)$$ So that you can have most linear exponential growth. But we can do better and completely compute the above probability. There are $\binom{2k}{k}$ dispositions which give us a zero sum. All of which have the same probability. So $$\mathbb{P}(S_n = 0) = \binom{2k}{k}\exp \bigg(\frac{n}{2} \log(p(1-p))\bigg)$$ And now an application of Stirling's approximation gives us that the last term behaves like $$\exp\big( k[\ln(4) +\ln(p(1-p))] + o(\ln(k)) \big)$$ which tells you that you have linear exponential growth unless $p = 1/2$ in which the regime turns out to be even polynomial.
## EDIT: For the case $p_i$ depending on $i$.
There are many possibilities. Let us choose the $p_i$'s according to some simple rules. We say that all $X^i$ should be $1$ with high probability and very seldom be zero. So let $$\epsilon_i =(1-p_i)$$ be a sequence decreasing to zero. Then we can find a bound for the probability of $S^n =0.$ Indeed any of the $2k$ choose $k$ dispositions that allow $S^n$ to be zero comes with a probability. Since the $\epsilon_i$ are decreasing we can bind this probability by the probability that the first $k$ elements are zero. Indeed all other dispositions are even more unlikely. So we find: $$\mathbb{P}(S^n = 0) \le \binom{2k}{k} \prod_{i = 1}^k \epsilon_i$$ So now we can lat our minds run wild in the choice of $\epsilon_i.$ Although tenacious people might want to try out $\epsilon_i = 1/i!$ I will stick to $\epsilon_i = 1/i.$ In this case the last formula reads: $$\frac{(2k)!}{(k!)^3} = \exp\big( {-}n\log(n) [ 1 + o(1)] \big).$$ This seems to be the decay you are looking for.
• Yes, in the i.i.d. case, it cannot. But what if they are not identical? Say $\mathbb{P}(X_i=1)=p_i$ depending on $i$? Is it possible to construct a sequence decay superexponentially? – Connor Sep 14 '17 at 2:39
• Ah, sorry I didn't see the index $i$. – Kore-N Sep 14 '17 at 12:34