Csdrhrt

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 $Bcup C$ where $Binmathcal{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_mumathcal{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 $AsubseteqOmega$ is $mathcal{A}$-analytic if and only if it is the projection of an $mathcal{A}otimesmathcal{B}(mathbb{R})$ measurable subset of $Omegatimesmathbb{R}$ onto $Omega$. i.e.,
$$
A = left{xinOmegacolon(x,y)in S{rm for some }yinmathbb{R}right}
$$
for some $Sinmathcal{A}otimesmathcal{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{omegainOmegacolon nmapsto 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 $SsubseteqOmegatimes(0,infty]$ by
$$
S=left{(omega,x)colon X_n(omega){rm has a nondecreasing subsequence tending to }xright}.
$$
This can be shown to be in $mathcal{A}otimesmathcal{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^{ltomega}=bigcup_{n=1}^inftyomega^n$ denote the nonempty finite sequences in $omega$, and $omega^omega$ denote the infinite sequences in $omega$. For each $xinomega^omega$ and positive integer $n$, write $xvert_ninomega^{ltomega}$ for the initial sequence of length $n$ from $x$,
$$
xvert_n = (x_0,x_1,ldots,x_{n-1}).
$$
A Suslin scheme $P$ is a collection of sets $P_xinmathcal{A}$ over $xinomega^{<omega}$ and the Suslin operation maps this to
$$
A=bigcup_{xinomega^omega}bigcap_{n=1}^infty P_{xvert_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 $Omegatimesmathbb{R}$. Start by choosing a collection of intervals $U_x=[a_x,b_x)subseteq[0,1)$ over $xinomega^{ltomega}$ satisfying the properties

• 
  $bigcap_{n=1}^infty U_{xvert_n}not=emptyset$ for all $xinomega^omega$.


• 
  $U_xcap U_y=emptyset$ unless $x=zvert_m$ and $y=zvert_n$ for some $zinomega^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 $SsubseteqOmegatimesmathbb{R}$ by
$$
S=bigcap_{n=1}^inftybigcup_{xinomega^n}P_xtimes U_x.
$$
Then, $A$ is the projection of $S$ onto $Omega$. Set
$$
S_n=bigcap_{k=1}^nbigcup_{xinomega^k}P_xtimes 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 $omegainOmega$ 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{xin[0,Y_{n,m}(omega)-1/n]colon ({omega}times[x,Y_{n,m}(omega)])cap S_nnot=emptyset}
end{align}

Then $mmapsto Y_{n,m}$ are decreasing sequences of random variables and, using the convention $supemptyset=-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 $omegainOmega$ 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 $Anotinmathcal{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 $ninmathbb{N}$, define $X_ncolonOmegatomathbb{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 $ninmathbb{N}$ and $Sinmathcal{B}(mathbb{R})$. Then,
$$
A = left{omegainOmegacolon X_n(omega){rm has a nondecreasing subsequence}right}
$$
is not in $mathcal{A}$.

To see this, consider any counterexample $(tildeOmega,mathcal{tilde A})$ with random variables $tilde X_ncolontildeOmegatomathbb{R}$ such that the set $tilde A$ on which $tilde X_n$ has a nondecreasing subsequence is not measurable. Define the map $fcolontildeOmegatoOmega$ by $f(tildeomega)=omega$ where $omega_n=tilde X_n(tildeomega)$. Then, $f$ is measurable and $tilde A=f^{-1}(A)$. If $A$ was in $mathcal{A}$ then this implies that $tilde Ainmathcal{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}subseteqmathcal{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}rightarrowmathbb{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 $kin {1, 2, 3, ...}$ such that
$$ lim_{krightarrowinfty} 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 $krightarrow 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$