Expected Upcrossings of a Submartingale

From a Pathwise Count to an Expected Count

A pathwise upcrossing inequality describes how many times one realized sequence can travel from below a level $a$ to above a higher level $b$. Taking expectations turns that accounting identity into a bound for a random process. The key is not to assume that the gain from buying low and selling high has a particular sign: for a submartingale, its expected gain is nonnegative. Instead, compare that strategy with the complementary periods when it is not holding the asset.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $(\mathcal{F}_k)_{k\ge0}$ be a filtration, and let $(X_k)_{k\ge0}$ be a real-valued, adapted process. Fix a finite integer $n\ge0$, and assume $\mathbb{E}|X_k|<\infty$ for $0\le k\le n$. The submartingale condition means that for $0\le k<n$, $\mathbb{E}[X_{k+1}\mid\mathcal{F}_k]\ge X_k$ almost surely. Fix real numbers $a<b$.

Definition: A completed upcrossing of $[a,b]$ by $X_0,\ldots,X_n$ begins at an index $r$ with $X_r\le a$, and ends at a later index $s$ with $X_s\ge b$. After that completion, the next upcrossing begins at the first subsequent index at which the process is at most $a$. The number of completed upcrossings selected in this successive, non-overlapping way is $U_n(a,b)$. The inequalities at the endpoints are inclusive: values equal to $a$ can start a crossing, and values equal to $b$ can complete one.

For each step $k$, let $H_{k-1}$ equal $1$ if the process is being held over the step from $k-1$ to $k$, and $0$ otherwise. The rule is to begin holding upon reaching a value at most $a$, and to stop holding when a value at least $b$ completes an upcrossing. Thus $H_{k-1}$ is determined by $X_0,\ldots,X_{k-1}$, so it is $\mathcal{F}_{k-1}$-measurable. Define the cumulative gain through time $n$ by $G_n=\sum_{k=1}^n H_{k-1}(X_k-X_{k-1})$, with an empty sum equal to zero when $n=0$.

Theorem (Expected upcrossing bound): Under the assumptions above, for every finite $n$ and every $a<b$, $$ (b-a)\mathbb{E}[U_n(a,b)] \le \mathbb{E}[(X_n-a)^+]+a-\mathbb{E}[X_0] \le \mathbb{E}[(X_n-a)^+]+\mathbb{E}[(a-X_0)^+], $$ where $x^+=\max(x,0)$. In particular, the expected number of completed upcrossings is finite.

Proof: Account for the Strategy and Its Complement

Proof. We first establish the pathwise accounting inequality used in the expectation argument. Every completed holding period begins at some value $X_r\le a$ and ends at a value $X_s\ge b$, so its contribution to $G_n$ is $X_s-X_r\ge b-a$. If a holding period remains unfinished at time $n$, its contribution is $X_n-X_r\ge X_n-a$. Consequently, whether or not there is an unfinished holding period, $$ (b-a)U_n(a,b)\le G_n+(a-X_n)^+. $$ Indeed, with no unfinished period, completed gains alone are at least $(b-a)U_n(a,b)$. With an unfinished period, its contribution is at least $X_n-a$; if $X_n<a$, adding $(a-X_n)^+$ compensates for this possible shortfall, while if $X_n\ge a$, the unfinished contribution is nonnegative.

We next take expectations. All terms are integrable: $H_{k-1}$ is bounded, and each $X_k$ is integrable. From the submartingale property and the measurability of $H_{k-1}$, $$ \mathbb{E}[H_{k-1}(X_k-X_{k-1})] = \mathbb{E}\!\left[H_{k-1}\mathbb{E}[X_k-X_{k-1}\mid\mathcal{F}_{k-1}]\right]\ge0. $$ The complementary holding amount $1-H_{k-1}$ is also bounded, nonnegative, and $\mathcal{F}_{k-1}$-measurable. The same calculation gives $\mathbb{E}[(1-H_{k-1})(X_k-X_{k-1})]\ge0$. Since $H_{k-1}+(1-H_{k-1})=1$, summing over the steps shows $$ 0\le\mathbb{E}[G_n]\le\mathbb{E}\!\left[\sum_{k=1}^n(X_k-X_{k-1})\right] =\mathbb{E}[X_n-X_0]. $$ Taking expectations in the pathwise inequality therefore yields $$ (b-a)\mathbb{E}[U_n(a,b)] \le \mathbb{E}[X_n-X_0]+\mathbb{E}[(a-X_n)^+]. $$ For every real $x$, $x-a+(a-x)^+=(x-a)^+$. Applying this identity with $x=X_n$ gives the first bound in the theorem. Also, pointwise, $$ a-X_0\le(a-X_0)^+, $$ so the first bound implies the second. Since the right side of the second bound is finite and $b-a>0$, $\mathbb{E}[U_n(a,b)]<\infty$. $\square$

The first bound retains more information about the initial value than the second: it uses $a-\mathbb{E}[X_0]$, whereas the second uses the nonnegative part $\mathbb{E}[(a-X_0)^+]$. The second form is often convenient when only a nonnegative bound is needed. Neither form requires stationarity, independence of increments, or a martingale equality; the conditional submartingale inequality is the condition that drives the argument.

Worked Applications

Worked Example: A Two-Step Symmetric Random Walk

Let $\varepsilon_1,\varepsilon_2$ be independent, each equal to $1$ or $-1$ with probability $\tfrac12$. On their four equally likely outcomes, set $X_0=0$, $X_1=\varepsilon_1$, and $X_2=\varepsilon_1+\varepsilon_2$, with the filtration generated by the increments observed so far. The conditional mean of each next increment is $0$, so this is a martingale and hence a submartingale. Find $\mathbb{E}[U_2(0,1)]$ and check the bound.

List the four paths, each with probability $\tfrac14$. For $(\varepsilon_1,\varepsilon_2)=(1,1)$, the sequence is $0,1,2$, giving one completed upcrossing. For $(1,-1)$, it is $0,1,0$, again giving one. For $(-1,1)$, it is $0,-1,0$, giving none because the path never reaches $1$. For $(-1,-1)$, it is $0,-1,-2$, also giving none. Therefore $\mathbb{E}[U_2(0,1)]=(\tfrac14+\tfrac14)=\tfrac12$.

The endpoint values $X_2$ are $2,0,0,-2$, each with probability $\tfrac14$. Thus $\mathbb{E}[(X_2-0)^+]=\tfrac14(2+0+0+0)=\tfrac12$, and $(0-X_0)^+=0$. The theorem gives $\mathbb{E}[U_2(0,1)]\le\tfrac12$, which is attained. Check: the direct path count gives $\tfrac12$, and the bound's right side also equals $\tfrac12$.

Worked Example: A Two-Step Positively Drifting Walk

Let $X_0=0$ and let each of two independent increments be $1$ with probability $\tfrac34$ and $-1$ with probability $\tfrac14$. Use the filtration generated by the increments observed so far. Each increment has conditional mean $\tfrac34-\tfrac14=\tfrac12$, so $X$ is a submartingale. Compute the expected number of upcrossings of $[0,1]$ and compare it with the bound.

The path with two upward increments, of probability $\tfrac34\cdot\tfrac34=\tfrac9{16}$, is $0,1,2$ and has one upcrossing. The path with an upward increment followed by a downward increment, of probability $\tfrac34\cdot\tfrac14=\tfrac3{16}$, is $0,1,0$ and also has one. The path with a downward increment followed by an upward increment, of probability $\tfrac14\cdot\tfrac34=\tfrac3{16}$, is $0,-1,0$ and has none. The path with two downward increments, of probability $\tfrac14\cdot\tfrac14=\tfrac1{16}$, is $0,-1,-2$ and has none. Hence $\mathbb{E}[U_2(0,1)]=\tfrac9{16}+\tfrac3{16}=\tfrac{12}{16}=\tfrac34$.

The endpoint $X_2$ equals $2$ with probability $\tfrac9{16}$, $0$ with probability $\tfrac6{16}$, and $-2$ with probability $\tfrac1{16}$. Therefore $\mathbb{E}[(X_2-0)^+]=2\cdot\tfrac9{16}+0\cdot\tfrac6{16}+0\cdot\tfrac1{16}=\tfrac{18}{16}=\tfrac98$. Since $X_0=0$, the initial positive-part term is zero. The bound reads $\tfrac34\le\tfrac98$. Check: $\tfrac34=\tfrac{12}{16}\le\tfrac{18}{16}=\tfrac98$, as required.

Worked Example: A Random Initial Value

Let $X_0=-1$ or $2$, each with probability $\tfrac12$, and set $X_1=X_0+2$ when $X_0=-1$, while $X_1=X_0+1$ when $X_0=2$. Take $\mathcal{F}_0$ to contain $X_0$ and $\mathcal{F}_1=\mathcal{F}_0$. The increment is known at time $0$ and is either $2$ or $1$, so its conditional expectation is nonnegative and the process is a submartingale. For $a=0,b=1,n=1$, find the expected crossing count and evaluate both bounds.

On the first outcome, the path is $-1,1$, which starts at or below $0$ and reaches $1$, so $U_1(0,1)=1$. On the second outcome, the path is $2,3$; it starts above $0$, so it does not begin an upcrossing, and $U_1(0,1)=0$. Thus $\mathbb{E}[U_1(0,1)]=\tfrac12$.

The endpoint is $1$ or $3$, so $\mathbb{E}[(X_1-0)^+]=\tfrac12(1)+\tfrac12(3)=2$. The initial value is $-1$ or $2$, so $\mathbb{E}[(0-X_0)^+]=\tfrac12(1)+\tfrac12(0)=\tfrac12$. The second form of the theorem gives $\tfrac12\le2+\tfrac12=\tfrac52$. For the sharper form, the increments are $2$ and $1$, so $\mathbb{E}[X_1-X_0]=\tfrac12(2)+\tfrac12(1)=\tfrac32$; also $(0-X_1)^+=0$ on both outcomes. It gives $\tfrac12\le\tfrac32$. Check: both bounds hold, and the first is sharper here.

From an Expected Count to a Probability Bound

The expected-count result also controls the chance of seeing many crossings by a fixed time. If $r$ is a positive integer, then $U_n(a,b)\ge r$ on the event $\{U_n(a,b)\ge r\}$. Since $U_n(a,b)\ge0$, it follows that $$ r\,\mathbb{P}(U_n(a,b)\ge r) \le \mathbb{E}[U_n(a,b)]. $$ Combining this inequality with the theorem gives $$ \mathbb{P}(U_n(a,b)\ge r) \le \frac{\mathbb{E}[(X_n-a)^+]+\mathbb{E}[(a-X_0)^+]}{r(b-a)}. $$ This is a finite-time statement: its assumptions concern the process only through the specified horizon $n$. It does not by itself assert that the process converges or that its total number of crossings over an infinite horizon is finite.

Proof. On $\{U_n(a,b)\ge r\}$, the nonnegative random variable $U_n(a,b)$ is at least $r$, and outside that event it is at least $0$. Hence $U_n(a,b)\ge r\mathbf{1}_{\{U_n(a,b)\ge r\}}$ pointwise. Taking expectations gives the first inequality. Substituting the expected upcrossing bound and dividing by the positive number $r(b-a)$ gives the displayed probability bound. $\square$

A Sign Error to Avoid

A common mistake is to treat the gain from holding during a submartingale's upward moves as though it had nonpositive expectation. The biased-walk example shows why that reverses the argument. There, $a=0$, $b=1$, and $\mathbb{E}[U_2(0,1)]=\tfrac34$. The terminal negative part has expectation $\mathbb{E}[(0-X_2)^+]=2\cdot\tfrac1{16}=\tfrac18$. An incorrect claim that the crossing count is bounded by this negative part would assert $\tfrac34\le\tfrac18$, which is false.

The correction is the complement-strategy step in the proof. For a submartingale, both the holding strategy and its complement have nonnegative expected gains. This gives an upper bound on the holding strategy's expected gain by the expected total increment, rather than declaring that gain nonpositive. The terminal positive part and the initial-value term then provide the valid expected upcrossing bound.

Check Your Understanding

Use the finite-time theorem and its assumptions to answer the following.

For the two-step symmetric walk, list the paths that contribute to $U_2(0,1)$, and recompute its expectation.
Why must $H_{k-1}$ be measurable with respect to $\mathcal{F}_{k-1}$ in the expectation argument?
For the positively drifting walk, compute $\mathbb{E}[(0-X_2)^+]$. Why is it not, by itself, an upper bound on $\mathbb{E}[U_2(0,1)]$?
In the theorem, what changes in the weaker bound if $X_0$ is always at least $a$?
Explain why the probability bound for $\{U_n(a,b)\ge r\}$ requires $r>0$ and $b-a>0$.