Interlacing stopping times

Question

This question is posed on a measurable space $(\Omega,\mathscr{F}$) equipped with a filtration $\{\mathscr{F}_t\}$. Recall that a random time $\tau\colon\Omega\rightarrow[0,\infty]$ is said to be a stopping time if $\{\tau \leq t\}\in\mathscr{F}_t$ for every $t\geq 0$.

I seek a proof of the following:

Lemma: If $a_{1}\leq a_{2}\leq\cdots$ and $b_{1}\leq b_{2}\leq\cdots$ are nondecreasing sequences of stopping times, there exists a nondecreasing sequence of stopping times $\tau_{1}\leq\tau_{2}\leq\cdots$ such that for each $j$ and sample $\omega$, $\tau_{j}(\omega)$ is the $j$-th smallest element in (with repetition) $$(a_{1}(\omega),a_{2}(\omega),\ldots,b_{1}(\omega),b_{2}(\omega),\ldots).$$

The above states, intuitively, given two sequences of nondecreasing stopping times, we can "combine" or "interlace" them without losing the stopping-time property.

---

Addendum: Below is an explicit construction that exhibits the property above.

\begin{align*} \tau_{1} & =a_{1}\wedge b_{1}\\ \tau_{2} & =\mathbf{1}_{\left\{ a_{1}\leq b_{1}\right\} }\left(a_{2}\wedge b_{1}\right)+\mathbf{1}_{\left\{ a_{1}>b_{1}\right\} }\left(a_{1}\wedge b_{2}\right)\\ \tau_{3} & =\mathbf{1}_{\left\{ a_{1}\leq b_{1}\right\} }\left(\mathbf{1}_{\left\{ a_{2}\leq b_{1}\right\} }\left(a_{3}\wedge b_{1}\right)+\mathbf{1}_{\left\{ a_{2}>b_{1}\right\} }\left(a_{2}\wedge b_{2}\right)\right)\\ & \qquad+\mathbf{1}_{\left\{ a_{1}>b_{1}\right\} }\left(\mathbf{1}_{\left\{ a_{1}\leq b_{2}\right\} }\left(a_{2}\wedge b_{2}\right)+\mathbf{1}_{\left\{ a_{1}>b_{2}\right\} }\left(a_{1}\wedge b_{3}\right)\right)\\ & \phantom{(\,}\vdots \end{align*}

Formally, one would build $\tau_j$ by induction and establish that if $\tau_{j-1}$ is a stopping time, so too is $\tau_j$.

---

I would be interested in seeing any of the following: (i) a critique of the sketch above, (ii) a clever and/or short formalization of this sketch, or (iii) a different proof (perhaps a non-constructive one?) altogether. All comments are very welcome.

Answer 1

Go for $\tau_1=a_1 \wedge{} b_1$. (Does the job. - This begins the induction!)

Induction: Assume $\tau_1,...,\tau_{n-1}$ did the job.

Then define $a^{\bullet}_n=\min_{i \leq n}\{a_i|\forall j < n: a_i > \tau_j \}$ and $b^{\bullet}_n$ alike, they are stopping times because $\tau_1,...,\tau_{n-1}$ were.

Then set $\tau_n=a^{\bullet}_n \wedge b^{\bullet}_n$.

Why will $\tau_n$ finish the job?

Well, both $a^{\bullet}_n$ and $b^{\bullet}_n$ are by construction bigger than the first smallest "stopp" $\tau_1$, the second smallest "stopp" $\tau_2$ (if $n \geq 3$, of course) and so forth to the $n-1$th smallest "stop" $\tau_{n-1}$.

Now we see that if for some $j \leq n$ there would be $a_j > a^{\bullet}_n$ then $a_j$ could not be the $n$th smallest item, since this would imply $a^{\bullet}_n=\tau_k$ for some $k<n$ which contradicts the definition of $a^{\bullet}_n$. The same argument applies for all $b_j$ and $b^{\bullet}_n$. So we are left with $a^{\bullet}_n$ and $b^{\bullet}_n$ as candidates for the $n$th smallest item. Logically taking the minimum is satisfying.

Hope this is sufficient, best regards.

EDIT: This requires strict inequalities between the $a_i$ and $b_i$ still I think one can fix it...

This is how I would fix it:

I define the number of $\tau_k$ equal to $\max_{k \leq n-1} \tau_k = \tau_{n-1}$:

$\xi_n=\sum^{n-1}_{k=1}\mathbf{1}_{\tau_k=\tau_{n-1}}$ Now the $a_k$ and $b_k$: $\zeta_n=\sum^{n-1}_{k=1}(\mathbf{1}_{a_k=\tau_{n-1}}+\mathbf{1}_{b_k=\tau_{n-1}})$

Now set $a^{*}_n=\mathbf{1}_{\xi_n \geq \zeta_n}a^{\bullet}_n+\mathbf{1}_{\xi_n < \zeta_n}\tau_{n-1}$, $b^{*}_n$ the same. This works, because if $\xi_n \geq \zeta_n$ (this means $\xi_n = \zeta_n$, but why bother showing it? ;) )there is no other item in the $a_k$ or $b_k$ that was not counted and equals $\tau_{n-1}$, so we go for the next biggest in the two lists. And in the other case there is a small value left to assign and thus we should have $\tau_n = \tau_{n-1}$, which is just what is going to happen if you set $\tau_n=a^{*}_n \wedge b^{*}_n$.