# Bolzano–Weierstrass theorem for random variables?

I am wondering if there is something similar to the Bolzano–Weierstrass theorem for random sequences. Namely, let $\{x_n\}$ be a bounded random sequence. Is it true that, under some reasonable conditions (I cannot be specific), there exists a subsequence of it that converges almost surely to a constant (not random variable)?

• what type of convergence are we talking about, convergence of distribution, convergence almost surely, etc – Kamster Aug 14 '14 at 5:37
• thanks for the correction, I revised the question. I want an almost sure convergence. – ljl Aug 14 '14 at 5:41
• Though this may not exactly answer your question directly looking these lecture slides (bcamath.org/documentos_public/courses/…) we have if sequence converges in distribution to a constant that it converges in probability to constant (pg 28) which you can combine with fact that a sequence of rvs that converges in probability to an rv must have a subsequence that converges almost surely. All in all you would have: if $X_{1},X_{2},..$ converges in distribution to a.s rv constant $c$, then there exist a subsequence that converges almost surely to $c$ – Kamster Aug 14 '14 at 5:59
• I notice my answer doesn't really answer your question about bounded rv sequences, just thought I'd post it in case you found it interesting – Kamster Aug 14 '14 at 6:03
• @Kamster and ljl, here is a probabilistic Bolzano-Wierstrass theorem along these lines (see answer below), let me know if this makes sense. – Michael Dec 31 '14 at 1:58

In general, no. A standard counterexample is to take your probability space to be $\Omega = [0,1]$ with Lebesgue measure, and consider the complex-valued random variables $X_n(\omega) = e^{2 \pi i n \omega}$, which are all bounded in absolute value by 1. They are orthonormal in $L^2(\Omega)$, so by Bessel's inequality, they converge weakly to 0 in $L^2(\Omega)$. If a subsequence converges almost surely, then by dominated convergence it converges strongly in $L^2(\Omega)$, and the limit must be the same as the weak limit, i.e. 0. But all $X_n$ have $L^2$ norm equal to 1, so this is absurd.

You can modify this to get real-valued counterexamples if you prefer.

Also, there is no reason to expect to be able to get a subsequential limit that is constant. As a very trivial example, let $X$ be any non-constant random variable and consider the sequence $(X,X,X,X,\dots)$; every subsequence converges almost surely to $X$.

If you want to guarantee convergence of a subsequence (which is really a statement about compactness), the usual approach is to choose a weaker mode of convergence. For instance, it follows from Prohorov's theorem that a uniformly bounded sequence of random variables has a subsequence converging in distribution. If your probability space is standard Borel, the Banach-Alaoglu theorem will guarantee that for any $1 < p < \infty$, you have a subsequence converging weakly in $L^p$.

In another direction, the Tychonoff theorem guarantees that your sequence has a subnet converging everywhere. This subnet is typically not a subsequence.

• great explanation, thanks! – ljl Aug 14 '14 at 8:11
• If we assume independence and we allow the subsequence to be chosen after seeing the sample path, then we can prove the desired result (see answer below). Of course, your $(X,X,X,\ldots)$ example shows that we cannot remove independence. – Michael Dec 31 '14 at 1:50
• Let me know if you agree with the proof below. – Michael Dec 31 '14 at 2:00

After thinking about it some, here is a result in that direction that uses the methodology of the standard Bolzano-Wierstrass proof. I just made this up, let me know if this is an existing result:

Proposition: Let $\{X_n\}_{n=1}^{\infty}$ be an infinite sequence of mutually independent random variables that take values in a bounded subset of the reals. Then there is a (non-random) constant $c$ such that, with probability 1, $\{X_n\}_{n=1}^{\infty}$ contains a subsequence that converges to $c$.

The proof relies on the second Borel-Cantelli Lemma:

Lemma: (Second Borel-Cantelli) Let $\{X_1, X_2, \ldots\}$ be mutually independent random variables and let $\{A_1, A_2, \ldots\}$ be events such that $\sum_{n=1}^{\infty} Pr[X_n \in A_n] = \infty$. Then with probability 1, $X_n \in A_n$ infinitely often. (This is a standard result so I will skip the proof)

Proof of Proposition: Without loss of generality we can assume the random variables take values in the bounded interval $[-M,M]$ for some positive number $M$. Call $[-M,M]$ the interval $I_1$. Chop $[-M,M]$ into two sub-intervals $[-M,0]$ and $[0,M]$. Then $Pr[X_n\in I_1] = 1$ for all $n$ and so:

\begin{align} \infty &= \sum_{n=1}^{\infty} Pr[X_n \in I_1] \\ &\leq \sum_{n=1}^{\infty} \left(Pr\left[X_n \in [-M,0]\right] + Pr\left[X_n \in [0, M]\right]\right)\\ &=\sum_{n=1}^{\infty} Pr\left[X_n \in [-M,0]\right] + \sum_{n=1}^{\infty} Pr\left[X_n \in [0,M]\right] \end{align} Thus, either the left or right sub-interval must have an infinite sum. Choose the left-most sub-interval that has an infinite sum and call this interval $I_2$. Then $\sum_{n=1}^{\infty} Pr[X_n \in I_2] = \infty$ and so, by the second Borel-Cantelli lemma, we know (with prob 1) that $X_n \in I_2$ infinitely often. Now chop $I_2$ into two sub-intervals $Left_2$ and $Right_2$. Then: \begin{align} \infty &=\sum_{n=1}^{\infty} Pr[X_n \in I_2] \\ &\leq \sum_{n=1}^{\infty} Pr[X_n \in Left_2] + \sum_{n=1}^{\infty} Pr[X_n \in Right_2] \end{align} and so again one of the sub-intervals must have an infinite sum. Choose the left-most sub-interval that has an infinite sum and call this $I_3$. Then $\sum_{n=1}^{\infty} Pr[X_n \in I_3] = \infty$. By Borel-Cantelli, with prob 1 $X_n$ must be in $I_3$ infinitely often. Continuing this way, we get a sequence of nested closed sub-intervals $\{I_1, I_2, I_3, \ldots\}$ that have size that vanishes to 0. So the sub-intervals must converge to a single point $c$. Note that there is nothing random about the sub-intervals, or about the point $c$. So $c$ is a (non-random) constant. With probability 1, for each $k$ the sequence $\{X_n\}$ is in each sub-interval $I_k$ infinitely often. Now form a subsequence as follows: Choose $n = 1$. For each $k>1$, choose $n[k]$ as the smallest index $m$ such that $m>n[k-1]$ and $X_m \in I_k$. Such a sub-sequence can be constructed with probability 1. Then $\{X_{n[k]}\}_{k=1}^{\infty}$ converges to $c$.

The Nate Eldredge example $(X,X,X, \ldots)$ gives a simple counter-example if we try to remove the independence assumption in the above proposition.

• I guess an alternative proof of the proposition would use the Kolmogorov 0-1 law on the non-increasing binary-valued function $f(x) = Pr[\limsup_{n\rightarrow\infty} X_n \geq x]$, to show that the $\limsup$ is the (non-random) transition point (with prob 1). – Michael Jan 1 '15 at 3:22
• Not clear why there was an unexplained downvote (a few years after I posted this). Note that while $c$ is a nonrandom constant, the indices of the subsequence must be chosen after observing the sample path for $\{X_n\}_{n=1}^{\infty}$. An example is when $\{X_n\}_{n=1}^{\infty}$ is i.i.d. uniform over $[0,1]$. Define $n_1=1$. Define $n_2$ as the first index $i>n_1$ such that $X_i \in [0,1/2]$, define $n_3$ as the first index $i > n_2$ such that $X_i \in [0, 1/4]$, and so on. With probability 1, we can find such indices at each step, and the resulting subsequence converges to 0. – Michael May 25 '17 at 18:21