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)?

thanks in advance.

  • $\begingroup$ what type of convergence are we talking about, convergence of distribution, convergence almost surely, etc $\endgroup$ – Kamster Aug 14 '14 at 5:37
  • $\begingroup$ thanks for the correction, I revised the question. I want an almost sure convergence. $\endgroup$ – ljl Aug 14 '14 at 5:41
  • $\begingroup$ 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$ $\endgroup$ – Kamster Aug 14 '14 at 5:59
  • $\begingroup$ 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 $\endgroup$ – Kamster Aug 14 '14 at 6:03
  • $\begingroup$ @Kamster and ljl, here is a probabilistic Bolzano-Wierstrass theorem along these lines (see answer below), let me know if this makes sense. $\endgroup$ – 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.

  • $\begingroup$ great explanation, thanks! $\endgroup$ – ljl Aug 14 '14 at 8:11
  • $\begingroup$ 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. $\endgroup$ – Michael Dec 31 '14 at 1:50
  • $\begingroup$ Let me know if you agree with the proof below. $\endgroup$ – 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] = 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.

  • $\begingroup$ 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). $\endgroup$ – Michael Jan 1 '15 at 3:22
  • $\begingroup$ 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. $\endgroup$ – Michael May 25 '17 at 18:21

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.