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} \}. $$

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.

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$