Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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: i1131.photobucket.com/albums/m550/__dissonance_/typewriter.gif –  Giuseppe Negro Nov 9 '12 at 22:58
add comment

1 Answer 1

up vote 2 down vote accepted

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

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

share|improve this answer
    
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 –  Zvpunry Nov 10 '12 at 1:34
    
@jmi4: Just prove the suggestion in the question, as I have in my addition –  Henry Nov 10 '12 at 1:43
    
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 –  Zvpunry Nov 10 '12 at 19:28
    
@jmi4 The $n$ follows from the definition of $m$ –  Henry Nov 10 '12 at 23:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.