# An extremely frustrating problem using Borel-Cantelli lemma…

This is a problem that I am totally stuck at.... For (i), I used the hint to construct a sequence of independent events. But, I have to show that the sum of their probabilities go to infinity in order to apply Borel Cantelli Lemma.

I think I have to apply the (ii) of Borel Cantelli lemma to E_{nk}(r_{nk})'s. But, I have thought for more than 3 hours and have kept failing to show that the sum of P(E_{nk}(r_{nk}))'s go to infinity and am now just frustrated to extreme.....

Could anyone "please" help me how to prove the (i) of the problem? I in fact solved (ii) assuming (i) holds. I'm quite desperate now.

p.s. Here a fair coin is assumed for the infinitely many coin tosses.

## 1 Answer

While writing down my answer, I just realized that this exercise does not make sense for arbitrary positive real numbers $r_1,r_2,\ldots$ since $r_{n_{k+1}}$ isn't necessarily defined if e.g. $r_1 = 1/2$ because then $n_2 = 3/2$ and there is no $r_{3/2}$.... However, aside from this technical issue this is a very nice exercise and my solution looks like this:

I assume you already showed that the $E_{n_k}(r_{n_k})$ are independent. We can quickly verify that
\begin{align*} \limsup_{k \to \infty} E_{n_k}(r_{n_k}) & = \{ (x_m) : (x_m) \in E_{n_k}(r_{n_k}) \text{ for infinitely many } k \in \mathbb{N} \}\\ & \subseteq \{ (x_m) : (x_m) \in E_n(r_n) \text{ for infinitely many } k \in \mathbb{N} \} = \limsup_{n \to \infty} E_n(r_n) \end{align*} since $(n_k)$ is a strictly increasing sequence ($r_n > 0 ~ \forall n$). Hence, if we can apply - as you already suspected - part (ii) of the Borel-Cantelli-Lemma to the sequence $(E_{n_k}(r_{n_k}))$, we immediately obtain $$1 = P(\limsup_k E_{n_k}(r_{n_k})) \leq P(\limsup_n E_n(r_n)) \leq 1$$ which gives the desired result. This means we have to show that $$\sum_{k=1}^{\infty} P(E_{n_k}(r_{n_k})) = \infty.$$ To do so, we initially compute $$P(E_{n_k}(r_{n_k})) = P(\{x = (x_m) : l_{n_k}(x)\geq r_{n_k}\}) = P(x_{n_k} = 1, \ldots , x_{n_k + r_{n_k} - 1} = 1) = 2^{-r_{n_k}}$$ because we are talking about a fair coin.

Now, note that $n_{k+1} - n_k = r_{n_k}$ and that for every $n$ such that $n_k \leq n \leq n_{k+1}$, we have $$r_{n_k} \leq r_n \text{ and } 2^{-r_{n_k}} \geq 2^{-r_n}.$$ Hence, $$2^{-r_{n_k}} = \frac{n_{k+1}-n_k}{n_{k+1}-n_k} 2^{-r_{n_k}} = (n_{k+1} - n_k) \frac{2^{-r_{n_k}}}{r_{n_k}} = \sum_{n=n_k}^{n_{k+1}-1} \frac{2^{-r_{n_k}}}{r_{n_k}} \geq \sum_{n=n_k}^{n_{k+1}-1} \frac{2^{-r_n}}{r_n}.$$ Using all this, we get $$\sum_{k=1}^{\infty} P(E_{n_k}(r_{n_k})) = \sum_{k=1}^{\infty} 2^{-r_{n_k}} \geq \sum_{k=1}^{\infty} \sum_{n=n_k}^{n_{k+1}-1} \frac{2^{-r_n}}{r_n} = \sum_{n\geq 1} \frac{2^{-n}}{r_n} = \infty$$ Hence, we can apply part (ii) of Borel-Cantelli and we are done.

• Yes, the technical problem can be easily solved by taking [ ] to the r_n's. – Keith May 5 '15 at 8:32
• Here [r_n] is the largest of the integers smaller than r_n – Keith May 5 '15 at 8:33
• Yes, you are correct. One also has to use that $n_{k+1} > n_k + 1$ in order to make this work, but this is given in the exercise. – GenericNickname May 5 '15 at 8:40