2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Michael Feb 29 '16 at 6:05
  • $\begingroup$ @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? $\endgroup$ – vulture Feb 29 '16 at 6:08
  • $\begingroup$ 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. $\endgroup$ – Michael Feb 29 '16 at 6:11
  • $\begingroup$ @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 $\endgroup$ – vulture Feb 29 '16 at 6:13
  • $\begingroup$ 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. $\endgroup$ – Michael Feb 29 '16 at 6:17
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – vulture Feb 29 '16 at 17:24
  • $\begingroup$ 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. $\endgroup$ – Michael Feb 29 '16 at 18:00
  • $\begingroup$ 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. $\endgroup$ – vulture Feb 29 '16 at 18:28
  • $\begingroup$ 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). $\endgroup$ – Michael Feb 29 '16 at 19:38
  • $\begingroup$ 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. $\endgroup$ – Michael Feb 29 '16 at 19:53

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.