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.


1 Answer 1


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$.


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$.

  • $\begingroup$ But that is exactly what I want to prove: that it does not converge a.s. My question is how to do rigorously prove this $\endgroup$
    – Moderat
    Nov 10, 2012 at 1:34
  • $\begingroup$ @jmi4: Just prove the suggestion in the question, as I have in my addition $\endgroup$
    – Henry
    Nov 10, 2012 at 1:43
  • $\begingroup$ 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 $\endgroup$
    – Moderat
    Nov 10, 2012 at 19:28
  • $\begingroup$ @jmi4 The $n$ follows from the definition of $m$ $\endgroup$
    – Henry
    Nov 10, 2012 at 23:18

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.