9
$\begingroup$

This is a classic example of convergence in probability, but not almost surely, but I am trying to rigorously prove it as opposed to "arguing against" the almost sure convergence. $\DeclareMathOperator{\Pb}{\mathbf{P}}$ $\DeclareMathOperator{\Unif}{\mathsf{Uniform}}$

Definition 1

A sequence of random variables, $X_n$, is said to converge in probability if for any real number $\epsilon > 0$ $ \lim_{n \to \infty} \Pb(|X_n - X | > \epsilon ) \to 0$

Definition 2

A sequence of random variables $X_n$, is said to converge almost surely (a.s.) to a limit if $\Pb(\lim_{n \to \infty} X_n = X) = 1$

Recall also that a sequence of real numbers $a_n$ converges to a limit $a$ if for any $\epsilon > 0$ there exists a large enough value $N$ so that $|a_n - a| < \epsilon $ for all $n \geq N$. In other words, the difference between the sequence and the limit is uniformly small after some point in the sequence.


The Question

Let $U \sim \Unif(0,1)$. For $n = 2^k + m$ where $k \geq 0$ and $0 \leq m \leq 2^k - 1$ define the functions $f_n : [0, 1) \to \{0,1\}$ as follows $ f_n(x) = \begin{cases} 1 & \text{if } {m \over 2^k} \leq x < {m +1 \over 2^k} \\ 0 & \text{o.w.} \end{cases} $

  • What is the distribution of $f_n(U)$ for $n = 2^k + m$ for $k \geq 0$ and $ 0 \leq m \leq 2^k - 1$?

  • Using the previous part, show that $X_n := f_n(U)$ converges to $0$ in probability.

  • Show that for any fixed $x \in (0,1)$, $f_n(x) = 1$ for infinitely many values of $n$. Use this fact to reason why $X_n = f_n(U)$ does not converge to 0 almost surely.


My Work

$f_n(U)$ is equal to $1$ with probability ${1 \over 2^k}$ and $0$ otherwise. This takes care of the distribution, then to show that $X_n$ does not converge in probability, $\Pb(|X_n - 0| > \epsilon) = \Pb(X_n = 1) = {1 \over 2^k}$ As $n \to \infty$, for $k = \lfloor \log_2 n\rfloor $ we have that $k \to \infty$, hence ${1 \over 2^k} = \Pb(|X_n - 0| > \epsilon) \to 0$

This is the part that I have often seen slightly glossed over. It is also the part that I am unclear about. I want to fix an $x$, and show that there is an $N$ so that $X_n$ for all $n \geq N$ is uniformly close to $0$. However, I'm really not sure how to do this. I tried working with binary expansions of my fixed $x$.

Thanks for any help.

  • 0
    I don't know if this may be of help yo you, but here's an animated graph of the sequence $(f_n)$. Somebody calls it *typewriter sequence*: http://i1131.photobucket.com/albums/m550/__dissonance_/typewriter.gif2012-11-09

1 Answers 1

5

There does seem to be some confusion about in distribution or in probability or almost surely.

$$\mathbf{P}(|X_n - 0| > \epsilon) = \mathbf{P}(X_n = 1) = {1 \over 2^k}$$

implies $X_n \to 0$ in distribution or in probability as the right hand side can be made arbitrarily small: it will be less than any $\epsilon$ with $0 \lt \epsilon \lt 1$ if $n \gt N =\lceil 1 - \log_2(\epsilon)\rceil$.

It will not converge to $0$ almost surely as the pointwise failure to converge $X_n \not\to 0$ is the whole of $(0,1)$ which given the probability measure of $U$ has probability $1$ rather than $0$.

Added

For every $x \in (0,1)$ and and every positive integer $k$ there is an $n$ such that $f_n(x)=1$ namely $n=2^k + \lfloor x2^k\rfloor$.

So $f_n(x)=1$ infinitely often for all $x \in (0,1)$ and so $X_n$ does not converge almost surely to $0$.

  • 0
    @jmi4 The $n$ follows from the definition of $m$2012-11-10