# Extension to Bolzano–Weierstrass theorem (required property of a convergent subsequence)

According to Bolzano–Weierstrass theorem, it says that any bounded sequence in $\mathbb{R}^n$ has a convergent subsequence.

Assume that $\{\mathbf{x}_\nu\}$ is a given bounded sequence and $\{\nu_k\}$ is the index set of a convergent subsequence. Can we assume that $\lim_{k\rightarrow \infty}\nu_k-\nu_{k-1}<\infty$? (i.e. subsequent iterates are in finite distance of each other.)

If yes, why do you claim that?

If not, is there any requirement on the sequence $\{\mathbf{x}_\nu\}$ by which, existence of such a convergent subsequence can be guaranteed?

Thank you very much in advance.

• You can consider $\{x_v\}_{v=1}^{\infty}=\{0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, ...\}$. The only possible values a subsequence can converge to are $0$ or $1$, but either way, we need to skip a progressively large number of indices to converge there. – Michael Feb 29 '16 at 6:05
• @Michael yes , you're right. So how can I guarantee that property? is there any assumption I can make on the whole sequence to have that property? – vulture Feb 29 '16 at 6:08
• Hmm...if we want to enforce that property...right now I find it hard to give a meaningful characteristic for the sequence to have that is not just a trivial restatement of the desired property itself. – Michael Feb 29 '16 at 6:11
• @Michael OK, yes. However thanks for the answer. Anyway if you know a good source that I might be able study that and find something, let me know. Thanks again – vulture Feb 29 '16 at 6:13
• For intuition: Consider an iid sequence of random variables $\{X_1, X_2, X_3, ...\}$, each uniform over $[0,1]$. I believe I can show that, with probability 1, there does not exist a convergent subsequence that satisfies your property. So, your property is rare, at least if the sequence is sufficiently "random." I might write that up as an answer if I have time. – Michael Feb 29 '16 at 6:17

Four miscellaneous observations:

1) Consider $\{x_k\}=\{0, 1, 1, 0,0, 0, 1,1,1, 1, 0,0,0,0, 0, …\}$. The only values a convergent subsequence could converge to are 0 or 1, but either way we would need to skip a progressively growing number of indices.

2) Let $\{X_1, X_2, X_3, …\}$ be a sequence of iid random variables with a continuous CDF function $F_X(x) = P[X\leq x]$ for all $x \in \mathbb{R}$.

### Claim:

With probability 1, $\{X_1, X_2, X_3, …\}$ does not contain a convergent subsequence $X_{n[k]}$ that satisfies $\limsup_{k \rightarrow\infty} (n[k+1]-n[k]) < \infty$.

### Proof:

For any rational numbers $a,b$ such that $a<b$, the law of large numbers tells us that: $$\lim_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^n1\{X_i \in [a,b]\} = F_X(b)-F_X(a) \quad (w.p.1)$$ where $1\{X_i \in [a,b]\}$ is an indicator function that is 1 if $X_i \in [a,b]$, and $0$ else. There are only a countably infinite number of rational intervals $[a,b]$. Hence, with probability 1, the above holds for all rational intervals.

Now suppose $\{X_n\}_{n=1}^{\infty}$ contains a convergent subsequence of the desired form. So there is a real number $c \in \mathbb{R}$, an integer $M>0$, and a subsequence $n[k]$ such that $\lim_{k\rightarrow\infty} X_{n[k]} = c$ and $\limsup_{k\rightarrow\infty} (n[k+1]-n[k]) \leq M$. The latter implies that $n[k+1]-n[k]\leq M$ for all sufficiently large $k$ (since $n[k+1]-n[k]$ is integer-valued). Fix $\delta>0$ such that $$F_X(c+\delta) - F_X(c-\delta) \leq 1/(2M)$$ This is possible because the $F_X$ function is continuous. Fix rational numbers $a,b$ such that $a<c<b$ and $$c-\delta \leq a < c < b \leq c + \delta$$ Since $F_X$ is nondecreasing, we get: $$F_X(b) - F_X(a) \leq F_X(c+\delta)-F_X(c-\delta) \leq 1/(2M) < 1/M \quad (*)$$
The subsequence $\{X_{n[k]}\}$ converges to $c$ and so it is in the interval $[a,b]$ for all sufficiently large $k$. Hence, eventually the sequence $\{X_n\}_{n=1}^{\infty}$ will fall into the interval $[a,b]$ at least once every $M$ steps, and so: $$\liminf_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^n 1\{X_i \in [a,b]\} \geq 1/M > F_X(b)-F_X(a)$$ where the final inequality holds by (*). Thus: $$\lim_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^n 1\{X_i \in [a,b]\} \neq F_X(b)-F_X(a)$$ Hence, $[a,b]$ is a rational interval over which the law of large numbers result does not work. This occurs with probability 0. $\Box$

3) Take the iteration: $$x[k+1]=(1-\gamma[k])x[k] + \gamma[k]r[k]$$ where $x[0]$ is a given real number, $\gamma[k]$ is a given square-summable sequence, and $r[k]$ is random.

Suppose that $E[(x[k]-r[k])^2] \leq B$ for all $k$, for some constant $B$. Suppose that $$E[r[k]|x[0],x[1],...,x[k]]=x[k]$$ Then $x[k]$ is a martingale. Further, we have for all $k$: $$x[k+1]-x[k] = \gamma[k](r[k]-x[k])$$ Summing over $k\in\{0, ..., n-1\}$ gives: $$x[n] - x[0] = \sum_{k=0}^{n-1} \gamma[k](r[k]-x[k])$$ Hence: $$E[(x[n]-x[0])^2] = \sum_{k=0}^{n-1}\gamma[k]^2E[(r[k]-x[k])^2] \leq B\sum_{k=0}^{\infty}\gamma[k]^2$$ where we have used the fact that $E[(r[k]-x[k])(r[i]-x[i])]=0$ for $i\neq k$. So $\sup_n E[x[n]^2]$ is bounded. By the $L^2$-bounded martingale convergence theorem, we know $x[n]$ converges with probability 1.

4) Consider $\{X_n\}_{n=1}^{\infty}$ iid uniform over $[0,1]$.

### Claim:

With prob 1, we can find a convergent subsequence $\{X_{n[k]}\}$ that converges to $0.5$ and that satisfies $n[k+1]-n[k] \leq k^{1/2}$ for all sufficiently large $k$.

Proof: Define the subsequence as follows: Define $n[1]=1$. For $k\in\{2, 3, 4, ...\}$, greedily select $n[k]$ as the first integer $n>n[k-1]$ for which:
$$X_n \in \left[.5-\frac{1}{2k^{1/4}}, .5+\frac{1}{2k^{1/4}}\right]$$ By construction, the $\{X_{n[k]}\}_{k=1}^{\infty}$ subsequence will converge to $0.5$. We just need to show the distances between $n[k]$ grow sublinearly. Notice that at stage $k$, the probability of a sample $X_n$ falling in the above interval is $1/k^{1/4}$.

Define $Wait[k] = n[k+1]-n[k]$. Fix $k \in \{1, 2, 3, \ldots\}$. For simplicity, treat $k^{1/2}$ as an integer. Then:
$$P[Wait[k] > k^{1/2}] = (1-1/k^{1/4})^{k^{1/2}} = \left((1-1/k^{1/4})^{k^{1/4}}\right)^{k^{1/4}} \approx (1/e)^{k^{1/4}}$$ This decays rapidly. Notice that: $$\sum_{k=1}^{\infty} P[Wait[k]>k^{1/2}] < \infty$$ It follows by Borel-Cantelli that, with prob 1, at most a finite number of the events $\{Wait[k]>k^{1/2}\}$ occur. In particular, $Wait[k] \leq k^{1/2}$ for all sufficiently large $k$. $\Box$

• Thanks a lot for this descriptive answer. Now it's so much clearer to me. I liked how you proved the second observation. In the third observation, actually assumption $E[(r[k]-x[k])(r[i]-x[i])]=0$ doesn't hold and that is the main problem I have for proving convergence of the sequence. If I could somewhow show that $r[k]-x[k]$ decays with rate of at least $\mathcal{O}(\sqrt{\gamma[k]})$, then we could remove that assumption and convergence could be proved. For proving this fact, one needs to deal with the optimization problem that we solve for calculating $r[k]$ which it's quite tough to show. – vulture Feb 29 '16 at 17:24
• Another proof of observation 2 in a more general scenario: Suppose $\{X_n\}_{n=1}^{\infty}$ is iid and there are two real numbers $x,y$ with $x<y$ such that $$P[X_n \leq x]>0, P[X_n\geq y]>0$$ Then with prob 1 there is no convergent subsequence with the desired property. This is because, with prob 1, there are arbitrarily large run lengths of the event $\{X_n\leq x\}$, and also arbitrarily large run lengths of the event $\{X_n\geq y\}$. Under these conditions, any convergent subsequence must have arbitrarily large run lengths of skipped indices. – Michael Feb 29 '16 at 18:00
• Great thanks for the proof, but as you know, I need to use, somehow, some property of my problem in order to show the existence of such a subsequence. So your second observation is eye-opening but I think that its claim about the fact that such a sequence is rare is due to our general assumption on the sequence of variates and hopefully it might not apply to my case. – vulture Feb 29 '16 at 18:28
• I know. I just found the general Bolzano-Wierstrass question interesting and wanted to give an alternative proof. If you can formulate a more precise question for your specific problem, you might want to do that, perhaps linking to this question for background. It was not clear to me what your $\hat{x}$ really is, or what the $f$ function is, so more details on that would likely be needed. You might also want to consider relaxed versions of your subsequence condition, like $n[k+1]-n[k]$ grows at most linearly (rather than being bounded). – Michael Feb 29 '16 at 19:38
• The intuition is this: Even if $\{X_i\}$ are iid, I think you can still find convergent subsequences (with prob 1) with $n[k+1]-n[k]$ that grows at most linearly, even though this is impossible when we require $n[k+1]-n[k]$ to be bounded. – Michael Feb 29 '16 at 19:53