2
$\begingroup$

enter image description here

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. enter image description here

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, the technical problem can be easily solved by taking [ ] to the r_n's. $\endgroup$ – Keith May 5 '15 at 8:32
  • $\begingroup$ Here [r_n] is the largest of the integers smaller than r_n $\endgroup$ – Keith May 5 '15 at 8:33
  • $\begingroup$ 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. $\endgroup$ – GenericNickname May 5 '15 at 8:40

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.