# Convergence in probability, not almost surely

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.

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

$$\Pb(|X_n - 0| > \epsilon) = \Pb(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$.

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$.
• Ah! Your addition makes perfect sense. Such a wonderful $n$ you picked. If you are able to answer this question meaningfully at all, I might ask "How did you think of this $n$?" I worked it out for small values of $k$ and its very nice. Thanks again – Moderat Nov 10 '12 at 19:28
• @jmi4 The $n$ follows from the definition of $m$ – Henry Nov 10 '12 at 23:18