# Is the set $\{ (X_n)_{n \in \mathbb{N}} \text{ has a nondecreasing subsequence} \}$ measurable?

Given a measurable space $$(\Omega, \mathcal{A})$$ and $$\mathcal{A}/\mathcal{B}(\mathbb{R})$$-measurable maps $$X_n : \Omega \to \mathbb{R}$$, $$n \in \mathbb{N}$$, is the set $$A:= \{\omega \in \Omega | (X_n(\omega))_{n \in \mathbb{N}} \text{ has a nondecreasing subsequence} \}$$ in $$\mathcal{A}$$?

My intuitive answer was yes. But I have been struggling to show this. Basically, the problem is that there are uncountably many subsequences.

To clarify: A sequence of real numbers $$(a_n)_{n \in \mathbb{N}}$$ is nondecreasing if $$a_n \leq a_{n+1}$$ for all $$n \in \mathbb{N}$$.

Here are some ways of trying to show the measurability that don't work.

1. Trying to write $$A$$ as $$B:= \bigcap_{n \in \mathbb{N}}\bigcup_{k \geq n}\bigcup_{l > k}\{X_k \leq X_l\}$$ doesn't work, because $$B$$ doesn't have to be in $$A$$, see the sequence $$-1,-1,-2,-2,-3,-3,\dots$$

2. Defining, for all $$k \in \mathbb{N}$$, the random variables $$T_0^k := k$$, and then recursively $$T_{j+1}^k := \inf\{n \geq T_j^k|X_n \geq X_{T_j^k}\}$$ and then considering the set $$C:= \bigcup_{k \in \mathbb{N}}\bigcap_{j \in \mathbb{N}}\{T_j^k < \infty\}$$ doesn't work, because $$A$$ doesn't have to be in $$C$$, see the sequence $$0,\frac12,0,\frac13,0,\frac14,0,\dots$$

3. Considering the sets $$S_k = \{(X_n)_{n \in \mathbb{N}} \text{ has a nondecreasing subsequence of length } k \}$$ and arguing that $$A = \bigcap S_k$$. In fact the reverse inclusion does not hold as can be seen by the sequence: $$1,1+1/2,$$ $$0,0+\frac{1}{2}, \; 0+\frac{3}{4},$$ $$-1,-1+\frac{1}{2},-1+\frac{3}{4},-1+\frac{7}{8},$$ $$-2,-2+\frac{1}{2},-2+\frac{3}{4},-2+\frac{7}{8}, -2+\frac{15}{16}, \ldots$$

Update: I still don't know the answer to this question. However, I feel like if $$A$$ was always measurable, it shouldn't be so difficult to find a proof.

For showing non-measurability, I have tried the following. Let $$X_n$$ be iid $$U([0,1])$$ distributed. Now if we assume that $$A$$ is measurable, then $$A$$ is also in the terminal $$\sigma$$-algebra $$\mathcal{T}_\infty$$ of the $$X_n$$. Now if we define $$B := \{\omega \in \Omega | (X_n(\omega))_{n \in \mathbb{N}} \text{ has a nonincreasing subsequence} \},$$ then we have $$P(A \cup B) = 1$$ because every sequence of real numbers has a monotone subsequence, and $$P(A) = P(B)$$ because the $$X_n$$ are $$U([0,1])$$-distributed. This gives us $$P(A) > 0$$, and thus $$P(A) = 1$$ because $$A \in \mathcal{T}_\infty$$. So all you would have to do to find a contradiction is to find a set of strictly positive measure where $$(X_n)$$ doesn't have a nondecreasing subsequence.

Update: George Lowther has given an extensive answer. To sum up: We can use the lemma in his answer to show that our set $$A$$ need not be in $$\mathcal{A}$$, but is always analytic which means in particular that, given any probability measure $$P$$ on $$(\Omega, \mathcal{A})$$, we can always assign a meaningful measure to $$A$$ because $$A$$ is in the completion of $$\mathcal{A}$$ w.r.t. $$P$$. Here is how we use the lemma:

1. Given any measurable space $$(\Omega,\mathcal{A})$$ and $$A$$ as above, the first implication of the lemma directly implies that $$A$$ is analytic.
2. To show that $$A$$ need not be in $$\mathcal{A}$$, we construct a counterexample. Let $$(\Omega,\mathcal{A}) = (\mathbb{R},\mathcal{B}(\mathbb{R}))$$. Then there exists a set $$A \subseteq \Omega$$ that is analytic but is not in $$\mathcal{A}$$. Now the second implication of the lemma tells us that we can construct a sequence $$(X_n)_{n \in \mathbb{N}}$$ of random variables such that $$A = \{\omega \in \Omega | (X_n(\omega))_{n \in \mathbb{N}} \text{ has a nondecreasing subsequence} \}.$$
• Does "monotone increasing" = "nondecreasing"? – Michael Nov 24 '18 at 17:22
• Yes, that's what I meant – Tki Deneb Nov 24 '18 at 17:28
• Well after 2 false starts I'm starting to think it might not be measurable. Favorited – Matthew C Nov 24 '18 at 18:57
• The set you mention need not be measurable, without additional constraints on $\mathcal{A}$ such as completeness. I know this as it can be re-stated in terms of measurability of hitting times (en.wikipedia.org/wiki/Hitting_time) of cadlag stochastic processes, and hitting times are not in general measurable, which is why completeness of the underlying probability space is usually assumed. That argument is a bit convoluted though. – George Lowther Dec 5 '18 at 2:49
• Thank you for the comment. However, I'm not sure how I would rewrite my set with a càdlàg process and hitting times. Can you elaborate on that? – Tki Deneb Dec 5 '18 at 10:56

In general, the set described need not be measurable, but it will always be universally measurable. Universally measurable sets are those subsets of $$\Omega$$ which lie in the completion of $$\mathcal{A}$$ with respect to every sigma-finite measure. That is, for a sigma-finite measure $$\mu$$ on $$(\Omega,\mathcal{A})$$, let $$\mathcal{A}_\mu$$ be the completion. This is the sigma-algebra of sets of the form $$B\cup C$$ where $$B\in\mathcal{A}$$ and $$C$$ is contained in a set in $$\mathcal{A}$$ of zero $$\mu$$-measure. The universal completion of $$\mathcal{A}$$ is $$\overline{\mathcal{A}}=\bigcap_\mu\mathcal{A}_\mu$$ where the intersection is over all sigma-finite measures on $$(\Omega,\mathcal{A})$$. The set $$A$$ in the question can be shown to be in $$\mathcal{A}_\mu$$ for each such $$\mu$$ and, in particular, is in $$\overline{\mathcal{A}}$$. This means that it has a well-defined measure with respect to any sigma-finite measure $$\mu$$. However, it need not be in $$\mathcal{A}$$.

We can exactly classify the possible sets $$A$$ in terms of analytic sets. There are many equivalent definitions of analytic sets, but I will take the following for now (which makes sense for any sigma-algebra $$\mathcal{A}$$).

A set $$A\subseteq\Omega$$ is $$\mathcal{A}$$-analytic if and only if it is the projection of an $$\mathcal{A}\otimes\mathcal{B}(\mathbb{R})$$ measurable subset of $$\Omega\times\mathbb{R}$$ onto $$\Omega$$. i.e., $$A = \left\{x\in\Omega\colon(x,y)\in S{\rm\ for\ some\ }y\in\mathbb{R}\right\}$$ for some $$S\in\mathcal{A}\otimes\mathcal{B}(\mathbb{R}).$$

The definition given by Wikipedia is for the case where $$\Omega$$ is a Polish space and $$\mathcal{A}$$ its Borel sigma-algebra, but this definition can be applied to any measurable space $$(\Omega,\mathcal{A})$$. A nice introduction to analytic sets is given in appendix A5 of Stochastic Integration with Jumps by Klaus Bichteler, available free online on his homepage.

Useful well-known properties of analytic sets are the following.

• Every $$\mathcal{A}$$-analytic set is in the universal completion $$\overline{\mathcal{A}}$$.
• If $$\Omega$$ is an uncountable Polish space with Borel sigma-algebra $$\mathcal{A}$$, (for example, $$\Omega=\mathbb{R}$$, $$\mathcal{A}=\mathcal{B}(\mathbb{R})$$) then there exists $$\mathcal{A}$$-analytic sets which are not in $$\mathcal{A}$$.

The following classifies the sets $$A$$ in the question in terms of analytic sets.

Lemma: The following are equivalent.

• There is a sequence of real-valued random variables $$X_n$$ on $$(\Omega,\mathcal{A})$$ such that $$A=\left\{\omega\in\Omega\colon n\mapsto X_n(\omega){\rm\ has\ a\ nondecreasing\ subsequence}\right\}\qquad{\rm(1)}$$
• $$A$$ is $$\mathcal{A}$$-analytic.

Once we have proven this lemma, then the statements above about the measurability of $$A$$ follow.

To prove that the first statement of the lemma implies the second, consider $$A$$ given by (1). Define $$S\subseteq\Omega\times(0,\infty]$$ by $$S=\left\{(\omega,x)\colon X_n(\omega){\rm\ has\ a\ nondecreasing\ subsequence\ tending\ to\ }x\right\}.$$ This can be shown to be in $$\mathcal{A}\otimes\mathcal{B}((0,\infty])$$ and its projection onto $$\Omega$$ is $$A$$. So, $$A$$ is analytic.

It just remains to prove that the second statement of the lemma implies the first. For this, I will use the alternative definition of an analytic set $$A$$ as given by the Suslin operation. This can be shown to be equivalent to the definition above. Let $$\omega=\{0,1,2,\ldots\}$$ denote the natural numbers, $$\omega^{\lt\omega}=\bigcup_{n=1}^\infty\omega^n$$ denote the nonempty finite sequences in $$\omega$$, and $$\omega^\omega$$ denote the infinite sequences in $$\omega$$. For each $$x\in\omega^\omega$$ and positive integer $$n$$, write $$x\vert_n\in\omega^{\lt\omega}$$ for the initial sequence of length $$n$$ from $$x$$, $$x\vert_n = (x_0,x_1,\ldots,x_{n-1}).$$ A Suslin scheme $$P$$ is a collection of sets $$P_x\in\mathcal{A}$$ over $$x\in\omega^{<\omega}$$ and the Suslin operation maps this to $$A=\bigcup_{x\in\omega^\omega}\bigcap_{n=1}^\infty P_{x\vert_n}.$$ Every $$\mathcal{A}$$-analytic set can be expressed in this form. We can express $$A$$ as a projection of a reasonably nice subset of $$\Omega\times\mathbb{R}$$. Start by choosing a collection of intervals $$U_x=[a_x,b_x)\subseteq[0,1)$$ over $$x\in\omega^{\lt\omega}$$ satisfying the properties

• $$\bigcap_{n=1}^\infty U_{x\vert_n}\not=\emptyset$$ for all $$x\in\omega^\omega$$.
• $$U_x\cap U_y=\emptyset$$ unless $$x=z\vert_m$$ and $$y=z\vert_n$$ for some $$z\in\omega^\omega$$ and positive integers $$m,n$$.

For example, we can take $$a_{x_0,\ldots,x_n}=\sum_{k=0}^n2^{-k-x_0-\ldots-x_{k-1}}(1-2^{-x_k})$$ and $$b_{x_0,\ldots,x_n}=a_{x_0,\ldots,x_n+1}$$.

Define $$S\subseteq\Omega\times\mathbb{R}$$ by $$S=\bigcap_{n=1}^\infty\bigcup_{x\in\omega^n}P_x\times U_x.$$ Then, $$A$$ is the projection of $$S$$ onto $$\Omega$$. Set $$S_n=\bigcap_{k=1}^n\bigcup_{x\in\omega^k}P_x\times U_x.$$ Then, $$S_n$$ decreases to $$S$$ and the paths $$X_n(\omega,t)=1_{\{(\omega,t)\in S_n\}}$$ are right-continuous. The set $$A$$ is precisely the set of $$\omega\in\Omega$$ such that the process $$\sum_{n=1}^\infty 2^{-n}X_n(\omega,t)$$ hits $$1$$. This relates the question to measurability of hitting times of right-continuous processes as mentioned in my comment to the original question.

For each positive integer $$n$$, define a sequence $$Y_{n,m}$$ of random variables over $$m=0,1,2,\ldots$$ by \begin{align} Y_{n,0}(\omega)&=1.\\ Y_{n,m+1}(\omega)&=\sup\{x\in[0,Y_{n,m}(\omega)-1/n]\colon (\{\omega\}\times[x,Y_{n,m}(\omega)])\cap S_n\not=\emptyset\} \end{align}

Then $$m\mapsto Y_{n,m}$$ are decreasing sequences of random variables and, using the convention $$\sup\emptyset=-\infty$$, each sequence is constant at $$-\infty$$ after a finite number of steps. It can be seen that a point $$(\omega,t)\in S$$ if and only if there is a subsequence $$Y_{n_k,m_k}(\omega)$$ strictly decreasing to $$t$$.

Finally, let $$X_k(\omega)$$ be the sequence of random variables $$Y_{n,m}(\omega)$$ in order of increasing $$m$$ and then increasing $$n$$, after each value of $$-\infty$$ and each repeated value is removed. In case this terminates, we can set $$X_k(\omega)=k$$ once there are no remaining values left in the sequence. Then, a point $$(\omega,t)$$ is in $$S$$ if and only if $$X_k(\omega)$$ has a subsequence decreasing to $$t$$, and $$A$$ is precisely the set of $$\omega\in\Omega$$ for which $$-X_k(\omega)$$ has a nondecreasing subsequence.

Finally, I'll point out that although I showed above that there are cases where $$A$$ is not in $$\mathcal{A}$$, the construction above would give rather contrived examples. However, the existence of any single counterexample implies that any sufficiently `generic' construction of the space $$(\Omega,\mathcal{A})$$ will also give $$A\not\in\mathcal{A}$$.

For example, consider the following standard construction of a space with an infinite sequence of random variables. Let $$\Omega=\mathbb{R}^{\mathbb{N}}$$ be the space of infinite sequences $$\omega=(\omega_1,\omega_2,\ldots)$$ of real numbers. Then, for each positive integer $$n\in\mathbb{N}$$, define $$X_n\colon\Omega\to\mathbb{R}$$ by $$X_n(\omega)=\omega_n$$. Finally, let $$\mathcal{A}$$ be the sigma-algebra generated by the $$X_n$$. i.e., $$\mathcal{A}$$ is generated by the sets $$X_n^{-1}(S)$$ for $$n\in\mathbb{N}$$ and $$S\in\mathcal{B}(\mathbb{R})$$. Then, $$A = \left\{\omega\in\Omega\colon X_n(\omega){\rm\ has\ a\ nondecreasing\ subsequence}\right\}$$ is not in $$\mathcal{A}$$.

To see this, consider any counterexample $$(\tilde\Omega,\mathcal{\tilde A})$$ with random variables $$\tilde X_n\colon\tilde\Omega\to\mathbb{R}$$ such that the set $$\tilde A$$ on which $$\tilde X_n$$ has a nondecreasing subsequence is not measurable. Define the map $$f\colon\tilde\Omega\to\Omega$$ by $$f(\tilde\omega)=\omega$$ where $$\omega_n=\tilde X_n(\tilde\omega)$$. Then, $$f$$ is measurable and $$\tilde A=f^{-1}(A)$$. If $$A$$ was in $$\mathcal{A}$$ then this implies that $$\tilde A\in\mathcal{\tilde A}$$, a contradiction.

• To be honest, this is completely out my league, but I have a small question though: in the lemma you say there is a sequence of random variables, how does that prove for all random variables? – Shashi Dec 6 '18 at 6:27
• Think you misunderstood something, but in the original question we are given that there is a sequence of random variables such that A is given by (1). The Lemma then tells you that A is analytic. Stating the Lemma in this way (two equivalent statements) is useful because, in the other direction, you can take an analytic but non-measurable set and use it to construct a counterexample showing that A need not be in $\mathcal{A}$. – George Lowther Dec 6 '18 at 8:42
• Thank you very much for your answer. I've only ever seen analytic sets on polish spaces, so I've never thought of them here. I will need some more time to read and understand the whole proof ;) but after a first read it all makes sense and I will accept your answer. Do you have a good source on analytical sets in this general context? Also one specific question: For the first statement of the lemma, you show $S \in \mathcal{A} \otimes \mathcal{B}((0,\infty])$. Do we have a problem because $\infty$ is included? How is $(0,\infty]$ a Polish space? (It has to be so that $A$ is analytic, right?) – Tki Deneb Dec 6 '18 at 8:57
• including $\infty$ is not a problem as $(0,\infty]$ is homeomorphic to $(0,1]\subseteq R$. Alternatively you could remove this by first mapping your sequence to a bounded one, replacing $X_n$ by $X_n/(1+\lvert X_n\rvert)$, if you prefer. I'll have to come back later with further references. – George Lowther Dec 6 '18 at 9:10
• Oh now I get it. Thank you! – Shashi Dec 6 '18 at 9:36

Some minor observations: Let $$\{a_n\}_{n=1}^{\infty}$$ be a real-valued sequence.

### Claim 1:

$$\{a_n\}_{n=1}^{\infty}$$ has no nondecreasing subsequence if and only if the following two properties hold:

(i) $$\sup_{n \in \{1, 2, 3,...\}} a_n < \infty$$

(ii) For each $$x \in \mathbb{R}$$ there is an $$\epsilon_x>0$$ such that $$a_n \in [x-\epsilon_x,x]$$ for at most finitely many positive integers $$n$$.

### Proof:

($$\impliedby$$) Suppose $$\{a_n\}$$ has a nondecreasing subsequence $$\{a_{n[k]}\}_{k=1}^{\infty}$$ (where $$n[k]$$ are positive integers that increase with $$k$$). We show at least one of the two properties are violated. If $$\sup_{n \in \{1, 2, 3, ....\}} a_n = \infty$$ we are done. Assume $$\sup_{n \in \{1, 2, 3, ....\}} a_n <\infty$$. Then $$\{a_{n[k]}\}_{k=1}^{\infty}$$ is upper bounded and nondecreasing, it approaches a finite limit $$x \in \mathbb{R}$$ from below, which violates property (ii).

($$\implies$$) Suppose $$\{a_n\}$$ violates one of the two properties. We show it must have a nondecreasing subsequence. If it violates the first property then $$\sup_{n \in \{1, 2, 3, ...\}} a_n = \infty$$ and clearly there is a subsequence that increases to $$\infty$$, so $$\{a_n\}$$ has a nondecreasing subsequence.

Now suppose the second property is violated. So there must exist an $$x \in \mathbb{R}$$ such that for every $$\epsilon>0$$ we have $$a_n \in [x-\epsilon, x]$$ for an infinite number of positive integers $$n$$. If there are an infinite number of positive integers $$n$$ for which $$a_n=x$$ then this forms a constant subsequence, which is nondecreasing and we are done. Else, for each $$\epsilon>0$$, we have $$a_n \in [x-\epsilon, x)$$ for an infinite number of positive integers $$n$$, and we can easily construct a nondecreasing subsequence (pick $$a_{n[1]} \in [x-1, x)$$, pick $$n[2]>n[1]$$ such that $$a_{n[2]} \in [a_{n[1]}, x)$$, and so on). $$\Box$$

Now let $$\mathcal{L}$$ be the set of all limiting values that can be achieved over infinite subsequences of $$\{a_n\}_{n=1}^{\infty}$$ (considering all subsequences that have well defined limits, allowing $$\infty$$ and $$-\infty$$). So $$\mathcal{L} \subseteq \mathbb{R} \cup \{\infty \} \cup \{-\infty\}$$.

### Claim 2:

If $$\{a_n\}_{n=1}^{\infty}$$ has no nondecreasing subsequence, then $$\mathcal{L}$$ has an at-most countably infinite number of values and $$\sup \mathcal{L} < \infty$$. In particular, $$\infty \notin \mathcal{L}$$.

Proof: Claim 1 implies that $$\sup_{n \in \{1, 2, 3, ...\}} a_n < \infty$$ and so $$\sup \mathcal{L} < \infty$$.

Claim 1 implies that for each real-valued $$x \in \mathcal{L}$$ there is a gap of size $$\epsilon_x>0$$, so that there are no elements of $$\mathcal{L}$$ in the interval $$(x-\epsilon_x,x)$$. It follows that there are an at-most countably infinite number of elements of $$\mathcal{L}$$ in any finite interval of $$\mathbb{R}$$ (*see details about summing positive numbers below). Since $$\mathbb{R}$$ can be represented as a countable union of finite intervals, the result holds. $$\Box$$

*Details on summing positive numbers: Let $$I$$ be the finite interval of $$\mathbb{R}$$ in question, with size $$|I|$$. Suppose $$\mathcal{L} \cap I$$ is uncountably infinite (we reach a contradiction). Note that $$\epsilon_x>0$$ for all $$x \in \mathcal{L} \cap I$$. Let $$\mathcal{M}$$ be the set $$\mathcal{L} \cap I$$ with the smallest element removed (if there is no smallest element then let $$\mathcal{M} = \mathcal{L} \cap I$$). Then $$\mathcal{M}$$ is uncountably infinite and every point $$x \in \mathcal{M}$$ has another point in $$\mathcal{L} \cap I$$ beneath it (so $$x-\epsilon_x$$ does not fall below the bottom of interval $$I$$). For any countably infinite subset $$\mathcal{A}\subseteq \mathcal{M}$$ we know $$\sum_{x \in \mathcal{A}} \epsilon_x \leq |I|$$, meaning that the sum of the gaps is less than or equal to the interval size. The next lemma shows that, because $$\mathcal{M}$$ is uncountably infinite, there must exist a countably infinite subset $$\mathcal{A}\subseteq\mathcal{M}$$ for which $$\sum_{x \in \mathcal{A}} \epsilon_x=\infty$$, a contradiction.

### Lemma:

If $$\mathcal{X}$$ is an uncountably infinite set and $$f:\mathcal{X}\rightarrow\mathbb{R}$$ is a function such that $$f(x)>0$$ for all $$x \in \mathcal{X}$$, then there exists a countably infinite subset $$\mathcal{A}\subseteq \mathcal{X}$$ such that $$\sum_{x \in \mathcal{A}} f(x) = \infty$$.

### Proof:

Let $$M$$ be the supremum of $$\sum_{x \in \mathcal{B}} f(x)$$ over all finite subsets $$\mathcal{B} \subseteq \mathcal{X}$$. Then there is a sequence of finite subsets $$\{\mathcal{B}_k\}_{k=1}^{\infty}$$ with $$\mathcal{B}_k \subseteq \mathcal{X}$$ for all $$k\in \{1, 2, 3, ...\}$$ such that $$\lim_{k\rightarrow\infty} \sum_{x \in \mathcal{B}_k} f(x) = M$$ Since $$f(x)>0$$ for all $$x \in \mathcal{X}$$, for all positive integers $$k$$ we have $$\sum_{x \in \cup_{i=1}^{\infty}\mathcal{B}_i} f(x) \geq \sum_{x \in \mathcal{B}_k} f(x)$$ Taking a limit as $$k\rightarrow \infty$$ gives $$\sum_{x \in \cup_{i=1}^{\infty}\mathcal{B}_i}f(x) \geq M$$ If $$M=\infty$$ it follows that $$\cup_{i=1}^{\infty} \mathcal{B}_i$$ is a countably infinite set over which $$f(x)$$ sums to infinity and we are done.

Now suppose $$M<\infty$$ (we reach a contradiction). The set $$\cup_{k=1}^{\infty} \mathcal{B}_k$$ is either finite or countably infinite, so (since $$\mathcal{X}$$ is uncountably infinite) there is a point $$x^* \in \mathcal{X}$$ that is not in $$\cup_{k=1}^{\infty} \mathcal{B}_k$$. Choose $$k$$ such that $$|\sum_{x \in \mathcal{B}_k} f(x) - M| < f(x^*)/2$$. Then $$\mathcal{B}_k \cup \{x^*\}$$ is a finite set but $$\sum_{x \in \mathcal{B}_k \cup \{x^*\}} f(x) > M$$ contradicting the definition of $$M$$. $$\Box$$

• An example sequence $\{a_n\}_{n=1}^{\infty}$ that has no nondecreasing subsequence and such that $|\mathcal{L}|=2$ is $\{b_1, b_1 + 100, b_2, b_2 + 100, b_3, b_3 + 100, ...\}$ where $b_k = 1/k$ for all $k \in \{1, 2, 3, ...\}$. So $\mathcal{L} = \{0, 100\}$. – Michael Nov 24 '18 at 23:47
• That's a great answer! One comment: If $\{a_n\}$ does not have any non-decreasing subsequence, then in fact, $\mathcal{L}$ is finite. This is very easy to show by contradiction. – Usermath Nov 25 '18 at 1:11
• @Usermath : Thanks! At first I thought $\mathcal{L}$ must be finite but I realized I could only show that every element of $\mathcal{L}$ can have an at most finite number of other elements in $\mathcal{L}$ that are larger. A case when $\mathcal{L}$ is infinite is when we form $\{a_n\}$ by inter-mixing sequences $\{b_k\}, \{b_k-100\}, \{b_k-200\}, \{b_k-300\}, ...$, with $b_k = 1/k$ (as in my first comment), so $\mathcal{L} = \{0, -100, -200, -300, ...\}$. – Michael Nov 25 '18 at 5:01
• @TkiDeneb : Yes, I was implicitly using a non-obvious fact there that says if we sum an uncountably infinite number of positive gaps, the result is infinity. I have given the full details now. – Michael Nov 25 '18 at 15:01
• Thanks, I understand it now. The lemma could also be seen faster by noting that there must be an $n \in \mathbb{N}$ such that $\{x \in \mathcal{X}|f(x) > \frac1n \}$ is infinite, even uncountably infininte. – Tki Deneb Nov 25 '18 at 15:39

Here is a proof of a (lesser) result that shows the set of all $$\omega \in \Omega$$ for which $$\{X_n(\omega)\}_{n=1}^{\infty}$$ contains arbitrarily long finite nondecreasing subsequences is measurable.

For each $$k\in \mathbb{N}$$, define $$B_k(\omega)\subseteq\mathbb{N}$$ as the set of all indices $$i \in \mathbb{N}$$ for which $$\{X_n(\omega)\}_{n=1}^{\infty}$$ has a length-$$k$$ nondecreasing subsequence that starts at index $$i$$. So $$B_k$$ is a random set. For example $$\{5 \in B_{12}\}$$ is the subset of all $$\omega \in \Omega$$ for which $$\{X_n(\omega)\}$$ has a length-12 non-decreasing subsequence that starts at index 5.

Notice that $$B_1 = \mathbb{N}$$ and so for all positive integers $$i$$ we have $$\{i \in B_1\}= \Omega$$, which is measurable.

Induction: Fix $$n \in \mathbb{N}$$. Suppose that for all $$i \in \mathbb{N}$$ we have $$\{i \in B_n\}$$ is measurable (it holds for $$n=1$$). We show it holds for $$n+1$$: For each $$i \in \mathbb{N}$$ we have: $$\{i \in B_{n+1}\} = \cup_{j=i+1}^{\infty}\{ \{X_i\leq X_j\} \cap\{j \in B_n\}\} = \mbox{measurable}$$ $$\Box$$

Thus the following sets are measurable: \begin{align} &\cup_{i=1}^{\infty} \cap_{n=1}^{\infty} \{i \in B_n\} \\ & \cap_{n=1}^{\infty} \cup_{i=1}^{\infty} \{i \in B_n\} \end{align} In particular the event that $$\{X_n(\omega)\}$$ contains arbitrarily long finite-length nondecreasing subsequences is measurable.