Take the 2-minute tour ×
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.

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|improve this question
3  
I think third question should be: "What happens if $\lambda=1/p$?" –  Norbert Apr 14 '12 at 17:51
1  
(+1) Is this homework? If so, kindly add the homework tag. :) –  cardinal Apr 14 '12 at 18:23
1  
Does $[\lambda^k]$ denote the nearest integer, or floor, or ceiling, or what? –  Quinn Culver Apr 14 '12 at 19:19
1  
Does "...among $A_{k}^{(\lambda)}$ events occurs only finitely many..." mean that $A_{k}^{(\lambda)}$ occurs for only finitely many $k$? –  Quinn Culver Apr 14 '12 at 19:35
1  
Thank you. I added the tag as you suggested and completed the text that $[\lambda^k]$ denotes the floor, plus I corrected the sentence that was not clear. –  Dawson Apr 14 '12 at 20:16
show 2 more comments

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.