Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let be $X_1, X_2,\; \ldots $ independent and identically distributed (i.i.d.) random variables with common distribution: $\mathbb{P}(X_k=1)=p,\; \mathbb{P}(X_k=0)=1-p $. We fix a $\lambda > 1$ parameter and let $A_k^{(\lambda)}$ denote the following events: $k=1, 2, 3, \dots $ $$ A_k^{(\lambda)}: = \{ \exists r \in [[\lambda^k], [\lambda^{k+1}]-1]\cap\mathbb{N}: X_r=X_{r+1}= \dots =X_{r+k-1}=1\} $$ where $[\lambda^k]$ denotes the floor. I.e.: $A_k^{(\lambda)} $ event means that between $[\lambda^k]$a and $[\lambda^{k+1}]-1$ exists a $k$ long run of ones. Let's prove:

a) If $\lambda < p^{-1}$ then $A_k^{(\lambda)} $ events occurs only for finitely many k with probability of 1.

b) If $\lambda > p^{-1}$ then $A_k^{(\lambda)} $ events occurs infinitely many times with probability of 1.

c) What happens when $\lambda=p^{-1}$?

Any help would be appreciated.

share|cite|improve this question
up vote 3 down vote accepted

The three parts are consequences of Borel-Cantelli lemmas hence we begin by controlling the probability of $A^{(\lambda)}_k$.

On the one hand, this event involves at most $\lambda^{k+1}-\lambda^k$ (non independent) events of probability $p^k$ hence, introducing $\mu=\lambda-1\gt0$, $$ \mathrm P(A^{(\lambda)}_k)\leqslant \mu\cdot(p\lambda)^k. $$ On the other hand, decomposing the interval $(\lambda^k,\lambda^{k+1})$ into disjoint intervals of length $k$, one gets at least $\mu\lambda^k/k$ (independent) events of probability $p^k$ hence $$ \mathrm P(A^{(\lambda)}_k)\geqslant 1-(1-p^k)^{\mu\lambda^k/k}. $$ These two estimates imply the following:

  • In case (a), $p\lambda\lt1$ hence $\sum\limits_k\mathrm P(A^{(\lambda)}_k)$ converges and the first Borel-Cantelli lemma yields the conclusion in your post.

  • In case (b), $p\lambda\gt1$ hence $(1-p^k)^{\mu\lambda^k/k}\to0$, $\mathrm P(A^{(\lambda)}_k)\to1$ and $\sum\limits_k\mathrm P(A^{(\lambda)}_k)$ diverges. Since the events $(A^{(\lambda)}_k)_k$ are independent, the second Borel-Cantelli lemma yields the conclusion in your post.

  • In case (c), $(1-p^k)^{\mu\lambda^k}=(1-p^k)^{\mu/p^k}\to\mathrm e^{-\mu}\gt0$ hence $\mathrm P(A^{(\lambda)}_k)\geqslant (\mu+o(1))/k$ and the second Borel-Cantelli lemma shows that, almost surely, infinitely many events $A^{(\lambda)}_k$ occur.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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