Upcrossings of a Real-Valued Sequence

What Counts as a Completed Upcrossing?

When a real-valued sequence moves around a fixed interval, it may repeatedly go from below the interval to above it. The number of such completed upward passages is a useful way to describe how a sequence oscillates. Counting them requires care: a sequence can start partway through a passage, end partway through one, or visit a threshold more than once. A precise definition settles which observations count and gives a reliable procedure for finite sequences.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \((X_n)_{n\ge0}\) be a real-valued sequence of random variables on it. Fix a finite observation horizon \(N\) and real numbers \(a<b\). For each outcome \(\omega\), the observed finite sequence is \(X_0(\omega),\ldots,X_N(\omega)\). The count is defined separately for each such sequence; no assumptions about independence, a Markov property, or a filtration are needed.

The ordered indices make the pairs disjoint: an observation used to finish one upcrossing cannot also be used to finish another, and the next lower-threshold observation must occur after the previous upper-threshold observation. Since the interval is closed, equality counts: \(x_s=a\) is a qualifying lower observation and \(x_t=b\) is a qualifying upper observation. The requirement \(a<b\) ensures that one observation cannot satisfy both threshold conditions.

This definition counts completed passages, not partial ones. A sequence that starts with \(x_0>a\) has not yet supplied a lower observation for an upcrossing. Similarly, a sequence that reaches \(x_s\le a\) but has no later observation at least \(b\) has an unfinished attempt, not a completed upcrossing.

A Greedy Counting Rule

To count the upcrossings, scan the observations from left to right. Initially, wait for the first value at most \(a\). After finding one, wait for the first later value at least \(b\); that completes a crossing. Then start waiting for a new lower observation. Repeated upper observations do not count again unless a new lower observation has occurred after the last completed crossing.

Proof. Let the greedy procedure produce pairs \((s_1,t_1),\ldots,(s_g,t_g)\), in order. Each pair meets the threshold conditions, and after \(t_r\) the procedure waits for a new lower observation before choosing \(s_{r+1}\). Thus \(t_r<s_{r+1}\), so these pairs are admissible in the definition and \(g\le U_N[a,b]\). To show that no admissible collection has more pairs, consider any collection \((u_1,v_1),\ldots,(u_k,v_k)\) with \(u_1<v_1<\cdots<u_k<v_k\), \(x_{u_r}\le a\), and \(x_{v_r}\ge b\). The first greedy lower index \(s_1\) is no later than \(u_1\), since \(u_1\) is itself a qualifying lower index. The greedy upper index \(t_1\) is the first qualifying upper index after \(s_1\); since \(v_1>u_1\ge s_1\), it satisfies \(t_1\le v_1\). Suppose for some \(r<k\) that the greedy procedure has produced its \(r\)-th pair and \(t_r\le v_r\). The next admissible lower index satisfies \(u_{r+1}>v_r\ge t_r\), so it is available after the greedy procedure resumes. Therefore the next greedy lower index satisfies \(s_{r+1}\le u_{r+1}\); its next upper index satisfies \(t_{r+1}\le v_{r+1}\), by the same first-upper argument. By induction, the greedy procedure produces at least \(k\) pairs. This holds for every admissible collection, so \(g\ge U_N[a,b]\). Combining the inequalities gives \(g=U_N[a,b]\). \(\square\)

The earliest available lower and upper observations are convenient, but the theorem says more than that they are easy to find: their number of completed pairs is maximal. This matters when a sequence offers several possible choices of indices. Choosing a later lower observation cannot create extra room for additional completed pairs, because it cannot make the next upper observation occur earlier.

Proof. Start before \(x_0\) in the waiting-for-a-lower-observation status, with count zero. Suppose the status is waiting when \(x_n\) is read. The new observation can start a qualifying pair exactly when \(x_n\le a\); it cannot complete a pair that has not started, and if \(x_n>a\) it does not change the available information. Suppose instead the status is holding a lower observation. The new observation completes the current pair exactly when \(x_n\ge b\). In that case the count increases by one and the procedure waits for a fresh lower observation. If \(x_n<b\), the pair is not yet complete, so the count and status remain unchanged. Because \(a<b\), the two threshold conditions cannot hold at the same observation. These updates implement the greedy rule at every index, and the theorem shows that its final count is \(U_N[a,b]\). \(\square\)

Worked Counts

Common Mistakes and Why the Count Is Useful

A common error is to count every visit to the upper threshold as a new completion, or to reuse one observation in multiple pairs. For example, in the sequence \((-1,0,2,2,0,1,2)\) with thresholds \(0\) and \(2\), one might count \((0,2)\), \((1,2)\), and \((4,6)\), obtaining \(3\). This is invalid: the first two proposed pairs both use the upper observation at index \(2\), and their indices are not strictly ordered as required. The correct disjoint pairs are \((0,2)\) and \((4,6)\), so the count is \(2\). The greedy rule prevents this error by resetting only after a completed pair and requiring a new lower observation before another completion.

Another mistake is to treat a start or finish inside the interval as if it were a completed passage. An observation strictly between \(a\) and \(b\) is neither a qualifying lower endpoint nor a qualifying upper endpoint. It may occur during an unfinished attempt, but it does not itself start or finish a pair. Likewise, a sequence that begins at or above \(b\) does not count that initial value as a completion: no qualifying lower observation precedes it within the observed sequence.

Upcrossing counts turn a visual description of oscillation into a precise quantity. For a finite observed path, the count records how many times the path has made a complete move from at most \(a\) to at least \(b\), without reusing observations. In the study of stochastic sequences, this pathwise definition is the basic object used before asking how many upcrossings one should expect or what a bound on that number implies. Those questions require additional probabilistic arguments; the finite-sequence count itself depends only on the observed values and the two thresholds.