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} \}. $$
  • $\begingroup$ Does "monotone increasing" = "nondecreasing"? $\endgroup$ – Michael Nov 24 '18 at 17:22
  • $\begingroup$ Yes, that's what I meant $\endgroup$ – Tki Deneb Nov 24 '18 at 17:28
  • 2
    $\begingroup$ Well after 2 false starts I'm starting to think it might not be measurable. Favorited $\endgroup$ – Matthew C Nov 24 '18 at 18:57
  • 1
    $\begingroup$ 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. $\endgroup$ – George Lowther Dec 5 '18 at 2:49
  • 1
    $\begingroup$ 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? $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – Shashi Dec 6 '18 at 6:27
  • $\begingroup$ 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}$. $\endgroup$ – George Lowther Dec 6 '18 at 8:42
  • $\begingroup$ 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?) $\endgroup$ – Tki Deneb Dec 6 '18 at 8:57
  • $\begingroup$ 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. $\endgroup$ – George Lowther Dec 6 '18 at 9:10
  • $\begingroup$ Oh now I get it. Thank you! $\endgroup$ – 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$.


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


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


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$

  • $\begingroup$ 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\}$. $\endgroup$ – Michael Nov 24 '18 at 23:47
  • $\begingroup$ 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. $\endgroup$ – Usermath Nov 25 '18 at 1:11
  • $\begingroup$ @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, ...\}$. $\endgroup$ – Michael Nov 25 '18 at 5:01
  • 1
    $\begingroup$ @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. $\endgroup$ – Michael Nov 25 '18 at 15:01
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.


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.