2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ if you take $p_n=\frac{1}{n^2}$ then by Borel-Cantelli you have that $S_n\rightarrow -\infty$ almost surely $\endgroup$ – clark Sep 11 '17 at 21:24
  • $\begingroup$ 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? $\endgroup$ – Connor Sep 11 '17 at 21:31
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Connor Sep 14 '17 at 2:39
  • $\begingroup$ Ah, sorry I didn't see the index $i$. $\endgroup$ – Kore-N Sep 14 '17 at 12:34
  • $\begingroup$ @Connor I edited the answer for this case. Hope it's correct (and satisfactory) :) $\endgroup$ – Kore-N Sep 14 '17 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.