6
$\begingroup$

Let $X_n$ be the outcome of a Bernoulli trial where the probability of getting 1 is $p_n$ and the probability of getting 0 is $1-p_n$, and let $S_n = \sum_{i=1}^n \left(X_i - \textrm{E} X_i \right)$. In general, $p_i \neq p_j$, so $S_n$ is Poisson binomial distributed, but with the mean subtracted. Since $S_n$ has finite variance and expectation value 0, I would assume that $S_n$ is recurrent and that this should be a fairly well-known result. However, I have been browsing the literature and asking around, and despite the problem being apparently rather simple, I have not yet been able to find a proof.

QUESTION: Does anyone have a proof that $S_n$ is recurrent, alternatively, references to relevant literature where I could find proof(s) and discussion(s) of this problem?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

$S_n$ is a martingale with bounded jumps, and there is a result that it should either converge to a finite limit, or fluctuate, in the sense that $\limsup S_n=+\infty$, $\liminf S_n=-\infty$ (this, I guess, should be understood as "recurrence"). See e.g. Theorem (3.1) of Chapter 4 of [Durrett, "Probability, Theory and Examples" (2004)]. If $\sum p_n = \sum (1-p_n) = \infty$, this should rule out the first possibility, so the walk will have to be recurrent.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Just to be sure, do you mean Theorem 4.1.2 in the 2013 version? (It can be found here: math.duke.edu/~rtd/PTE/PTE4_1.pdf) This theorem holds only when $Y_i := X_i - \textrm{E}X_i$ are iid. However, while $\textrm{E}Y_i= \textrm{E}Y_j = 0$, in general $Y_i$ and $Y_j$ do not have the same variance and hence are not iid, so the theorem does not apply. Do you know if the theorem generalizes so that your argument holds? $\endgroup$
    – user45947
    Commented Oct 19, 2015 at 20:58
  • $\begingroup$ Ah, seems that he changed chapters' order. In that version, it's Theorem 5.3.1. $\endgroup$
    – Serguei Popov
    Commented Oct 19, 2015 at 21:08
  • $\begingroup$ Great! That seems to be exactly what I'm looking for. I'm just wondering: I get intuitively why $\sum p_n = \sum (1-p_n) = \infty$ would lead to recurrence. But how would you argue more strictly that this statement rules out convergence to a finite limit of $S_n$? Perhaps the answer is obvious, but I'd be grateful for some help along the way. $\endgroup$
    – user45947
    Commented Oct 19, 2015 at 21:32
  • $\begingroup$ For example, if $\sum p_n<\infty$, then a.s. there will be only a finite number of 1's (so that $\sum X_n$ converges), and (since $E X_n=p_n$) $\sum E X_n$ converges as well. The other case is analogous (or consider $Y_n=1-X_n$, and observe that $X_n-EX_n=-(Y_n-EY_n)$). $\endgroup$
    – Serguei Popov
    Commented Oct 19, 2015 at 21:41
  • $\begingroup$ To add a bit to @SergueiPopov's last comment, the condition for a.s. convergence is given by the Kolmogorov three-series theorem, which in this situation reduces to the condition $\sum_n \textrm{Var}(X_n) = \sum_n p_n(1-p_n)<\infty$. $\endgroup$
    – Dan Romik
    Commented Oct 19, 2015 at 22:14
9
$\begingroup$

The result is not true for a general sequence of probabilities $p_n$. For example, if $p_n=1/n^2$ then $\sum_n p_n <\infty$ and therefore by the Borel-Cantelli lemma, almost surely $X_k=0$ (and therefore $X_k-EX_k=-p_k$) for all but a finite number of $k$'s. In particular, $S_n$ will converge almost surely to some random limit so will not be recurrent.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks. I didn't think of extreme cases like that. Is it the case that any sequence of probabilities $p_n$ that satisfies $\lim_{n \to \infty} \sum_n p_n = \infty$ would yield $S_n$ recurrent? It certainly is true for $p_n = 1/2$, but would it be true for example for $p_n = 1/n$? $\endgroup$
    – user45947
    Commented Oct 19, 2015 at 8:21
  • $\begingroup$ You will need a more subtle condition, since if the $p_n$'s are very close to 1 rather than 0 then you won't get recurrence for similar reasons, and if many of them are close to 0 and many are close to 1, you can arrange to have or not have recurrence by choosing how you alternate the near-zeros with the near-ones. Also for a full analysis you may need to separate the case when $S_n$ takes values on a lattice (e.g. when $p_n=c$ for some rational constant $c$) from the non-lattice case, since those two cases involve different definitions of recurrence. So it's not an obvious question. $\endgroup$
    – Dan Romik
    Commented Oct 19, 2015 at 8:46
  • $\begingroup$ I'm obviously interested in what this subtle condition would be. You say it's not an obvious question, but do you anyhow happen to know some references that at least partly addresses it? $\endgroup$
    – user45947
    Commented Oct 19, 2015 at 9:06
  • $\begingroup$ No, sorry... :-( $\endgroup$
    – Dan Romik
    Commented Oct 19, 2015 at 9:17
  • $\begingroup$ A valuable answer anyway. Thanks for chipping in. $\endgroup$
    – user45947
    Commented Oct 19, 2015 at 9:20

You must log in to answer this question.

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