From Expected Crossings to an Oscillation Diagnostic
A sequence can fail to settle near a fixed value by repeatedly moving from below a level \(a\) to above a higher level \(b\). Counting these completed moves gives a precise way to discuss one form of oscillation. For a submartingale, the expected-upcrossing inequality turns that count into a bound involving the positive part of the process at the final time. The key diagnostic is whether the resulting bound stays finite uniformly over time: if it does, infinitely many upcrossings of the fixed interval have probability zero. If it grows with the time horizon, the bound alone may not decide whether repeated oscillation occurs.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\) with a filtration \((\mathcal{F}_n)_{n\ge0}\). A real-valued process \((X_n)_{n\ge0}\) is a submartingale if each \(X_n\) is integrable and \(\mathcal{F}_n\)-measurable, and \(\mathbb{E}[X_{n+1}\mid\mathcal{F}_n]\ge X_n\) almost surely for every \(n\). Fix real numbers \(a<b\). An upcrossing of \([a,b]\) is completed when the process has been at or below \(a\) and subsequently reaches or exceeds \(b\). Write \(U_N(a,b)\) for the number of completed upcrossings by time \(N\). The endpoints are included: the lower test is \(X_n\le a\), and the upper test is \(X_n\ge b\).
The inequality is an upper bound, not an estimate of the exact number of crossings. In particular, its right-hand side depends on the terminal positive part and the initial negative part relative to \(a\), not simply on \(\mathbb{E}[X_N]\). Once the bound is available, Markov's inequality gives, for every positive integer \(r\),
This converts an expectation bound into a probability bound for at least \(r\) completed crossings. It is useful even when the exact distribution of \(U_N(a,b)\) is hard to calculate.
Why Uniformity in the Time Horizon Matters
Proof. For each positive integer \(r\), let \(A_r=\bigcup_{N\ge0}\{U_N(a,b)\ge r\}\). Since \(U_N(a,b)\) is nondecreasing in \(N\), the events inside this union increase with \(N\). The expected-upcrossing inequality and Markov's inequality give \(\mathbb{P}(U_N(a,b)\ge r)\le C/(r(b-a))\) for every \(N\). Taking the increasing union over \(N\) preserves this bound, so \(\mathbb{P}(A_r)\le C/(r(b-a))\). The event of infinitely many completed upcrossings is \(\bigcap_{r\ge1}A_r\). It is contained in every \(A_r\), and therefore its probability is at most \(C/(r(b-a))\) for every positive integer \(r\). Letting \(r\) increase without bound shows that this probability is zero. \(\square\)
The condition is uniform in \(N\): the same finite \(C\) must work at every time horizon. A finite bound for each separate \(N\) is not enough by itself. For example, a sequence of upper bounds that grows with \(N\) does not give a single estimate tending to zero as \(r\) increases after taking the union over all horizons.
A convenient sufficient condition is a common almost-sure bound \(|X_n|\le K\) for every \(n\), where \(K\) is a fixed nonnegative constant. Then \(\mathbb{E}[(X_N-a)^+]\le(K-a)^+\) and \(\mathbb{E}[(X_0-a)^-]\le(K+a)^+\). The sum is bounded independently of \(N\), so the proposition applies. This conclusion concerns upcrossings of the chosen interval; by itself it does not establish every other property one might mean by convergence.
Worked Example: A Uniform Bound for a Bounded Submartingale
Suppose \((X_n)\) is a submartingale with \(X_0=0\) and \(|X_n|\le2\) almost surely for every \(n\). Find a uniform bound for the probability of at least two upcrossings of \([-1,1]\) by time \(N\), and determine what the bound implies about infinitely many such upcrossings.
Here \(a=-1\), \(b=1\), so \(b-a=1-(-1)=2\). Since \(X_N\le2\), we have \((X_N-a)^+=(X_N+1)^+\le3\). Also \((X_0-a)^-=(0+1)^-=0\). Thus the expected-upcrossing inequality gives \(\mathbb{E}[U_N(-1,1)]\le3/2\) for every \(N\). Applying Markov's inequality with \(r=2\),
The bound is the same for every finite horizon. More generally, \(\mathbb{P}(U_N(-1,1)\ge r)\le3/(2r)\) for every positive integer \(r\). The proposition therefore shows that infinitely many completed upcrossings of \([-1,1]\) have probability zero. These are upper bounds; they need not be attained by the particular submartingale.
An Unbounded Example: Bounds That Grow with Time
Worked Example: Upcrossing Bounds for a Simple Random Walk
Let \(S_0=0\) and \(S_n=\xi_1+\cdots+\xi_n\), where the increments are independent and satisfy \(\mathbb{P}(\xi_k=1)=\mathbb{P}(\xi_k=-1)=1/2\). Take \(\mathcal{F}_n=\sigma(\xi_1,\ldots,\xi_n)\). The two increment probabilities sum to \(1/2+1/2=1\), and independence gives \(\mathbb{E}[S_{n+1}\mid\mathcal{F}_n]=S_n\), so this is a martingale and hence a submartingale. Calculate the bound for upcrossings of \([0,1]\) at time \(N=4\).
For the four increments, the number of \(+1\) steps has probabilities \(1/16,4/16,6/16,4/16,1/16\) for \(0,1,2,3,4\) positive steps. The corresponding values of \(S_4\) are \(-4,-2,0,2,4\). Consequently, \(\mathbb{E}[(S_4-0)^+]=0(6/16)+2(4/16)+4(1/16)=12/16=3/4\). Since \(S_0=0\), \((S_0-0)^-=0\), and \(b-a=1-0=1\). The expected-upcrossing inequality yields \(\mathbb{E}[U_4(0,1)]\le3/4\), and hence \(\mathbb{P}(U_4(0,1)\ge1)\le3/4\).
This example also shows why a bound that grows with the horizon may be inconclusive rather than contradictory. By time \(3\), the specific increment pattern \(+1,-1,+1\) has probability \((1/2)(1/2)(1/2)=1/8\) and produces the path \(0,1,0,1\), with two completed upcrossings of \([0,1]\). At \(N=3\), the distribution of \(S_3\) has values \(-3,-1,1,3\) with probabilities \(1/8,3/8,3/8,1/8\), so \(\mathbb{E}[S_3^+]=1(3/8)+3(1/8)=6/8=3/4\). The inequality gives \(\mathbb{P}(U_3(0,1)\ge2)\le(3/4)/2=3/8\), consistent with the event of probability \(1/8\). This finite-horizon calculation shows that repeated crossings can occur; it does not, on its own, prove that infinitely many occur.
Worked Example: An Unbounded Process with No Repeated Upcrossings
On a one-point probability space with the trivial filtration, let \(X_n=2^n\). This deterministic process is an integrable submartingale: \(X_{n+1}=2^{n+1}\ge2^n=X_n\) at every time. For the interval \([1,2]\), calculate the actual number of upcrossings by time \(3\) and the bound at that horizon.
The values through time \(3\) are \(1,2,4,8\). The process starts at the lower endpoint and reaches the upper endpoint at time \(1\), completing one upcrossing. It never returns to a value at or below \(1\), so \(U_3(1,2)=1\). In the expected-upcrossing inequality, \(b-a=2-1=1\), \((X_3-1)^+=(8-1)^+=7\), and \((X_0-1)^-=(1-1)^-=0\). The resulting bound is \(\mathbb{E}[U_3(1,2)]\le7\), while the actual expectation is \(1\).
The process is unbounded over time, but it does not oscillate across this interval repeatedly. Its growing terminal positive part makes the bound increasingly weak. Thus failure to obtain a uniform upper bound does not show that oscillation occurs; it only means this particular diagnostic does not rule it out.
Reading the Bound Correctly
For a fixed interval, first calculate the right-hand side at the same horizon as the crossing count. Then ask whether those values can be bounded by one finite constant for all horizons. If so, the proposition rules out infinitely many completed upcrossings of that interval. If not, inspect what the examples actually show: the inequality remains a valid finite-time upper bound, but it may be too loose to distinguish oscillatory behavior from monotone growth or other behavior.
Common mistake. For the random walk at \(N=4\), it is wrong to replace \(\mathbb{E}[(S_4-0)^+]\) by \(\mathbb{E}[S_4]=0\) and conclude that the expected number of upcrossings is zero. The inequality uses the positive part, not the untruncated terminal value. The correct calculation is \(\mathbb{E}[S_4^+]=2(4/16)+4(1/16)=3/4\), giving \(\mathbb{E}[U_4(0,1)]\le3/4\). A zero mean can result from cancellation between positive and negative values and does not make the positive part vanish.
Keep the direction of the conclusion in view. A finite uniform upper bound on expected upcrossings rules out infinitely many such crossings; a bound that increases with time does not prove they happen. The interval, endpoint conventions, and uniformity in the time horizon are all essential to interpreting the diagnostic.
Check Your Understanding
For each question, identify the horizon and the fixed interval before applying an inequality.
- For a submartingale with \(X_0=0\) and \(|X_n|\le3\) almost surely, give a uniform expected-upcrossing bound for the interval \([0,2]\).
- If \(\mathbb{E}[U_N(a,b)]\le5\) for every \(N\), what bound follows for \(\mathbb{P}(U_N(a,b)\ge r)\)? What does it imply about infinitely many upcrossings?
- Why does \(\mathbb{E}[X_N]=0\) fail to determine the right-hand side of the expected-upcrossing inequality for \(a=0\)?
- For the deterministic process \(X_n=2^n\), how many upcrossings of \([1,2]\) have been completed by time \(N\ge1\)? Why can the terminal-value bound still grow?
- If the expected-upcrossing bound is finite for each \(N\) but grows without bound as \(N\) increases, which step in the uniform argument is unavailable?