Is the expectation of the supremum of a random walk with negative drift finite?

Solution 1:

By replacing $\xi_k$'s by $\xi_k \vee (-m)$ for some appropriately chosen $m > 0$ if necessary, we may assume WLOG that $\xi_k$'s are bounded below by $-m$ and we do so.

Let $M_n = \max_{0\leq k\leq n}S_k$. Also, define $W_0 = 0$ and $W_{n+1}=(W_n + \xi_{n+1})^+$, where $x^+ := x \vee 0$ is the positive part of the real number $x$.

Lemma. $M_n $ and $ W_n$ have the same distribution for all $n \geq 0$.

From the lemma and the monotone convergence theorem, we get

$$ \mathbf{E}[M] = \lim_{n\to\infty} \mathbf{E}[M_n] = \lim_{n\to\infty} \mathbf{E}[W_n]. $$

In light of this, we show that $\mathbf{E}[W_n]$ is bounded. Assume otherwise that $\mathbf{E}[W_n] \to \infty$. Then

\begin{align*} \mathbf{E}\left[ (W_{n+1}^2 - W_n^2) \mathbf{1}_{\{W_n \geq m\}} \right] &= \mathbf{E}\left[ (2\xi_{n+1} W_n + \xi_{n+1}^2) \mathbf{1}_{\{W_n \geq m\}} \right] \\ &= 2 \mathbf{E}[\xi_1] \mathbf{E}\left[ W_n \mathbf{1}_{\{W_n \geq m\}} \right] + \mathbf{E}[\xi_1^2] \mathbf{P}(W_n \geq m) \\ &\to -\infty \quad \text{as } n \to \infty. \end{align*}

On the other hand, using the fact that $W_{n+1} \leq W_n + \xi_{n+1}^+$ always holds, we get

\begin{align*} \mathbf{E}\left[ (W_{n+1}^2 - W_n^2) \mathbf{1}_{\{W_n < m\}} \right] &\leq \mathbf{E}\left[ ((W_n + \xi^+_{n+1})^2 - W_n^2) \mathbf{1}_{\{W_n < m\}} \right]\\ &= \mathbf{E}\left[ (2\xi_{n+1}^+ W_n + (\xi^+_{n+1})^2) \mathbf{1}_{\{W_n < m\}} \right] \\ &\leq 2m \mathbf{E}[\xi_1^+] + \mathbf{E}[(\xi_1^+)^2] \\ &< \infty. \end{align*}

These altogether show that $\mathbf{E}\left[ W_{n+1}^2 - W_n^2 \right]$ is eventually negative. However, this contradicts

$$ \mathbf{E}\left[ W_{n+1}^2 - W_n^2 \right] = \mathbf{E}\left[ M_{n+1}^2 - M_n^2 \right] \geq 0 \quad\text{for all } n. $$

From this, we conclude that $\mathbf{E}[W_n]$ is bounded as required.

Proof of Lemma. Define

$$ F_n(x) = (\xi_n + x)^+ . $$

Also, let $S_{p,n} = \sum_{i=1}^{n} \xi_{i+p}$ and $M_{p,n} = \max_{0 \leq k \leq n} S_{p,k}$. Then

$$ M_{n} = \max\Bigl\{ 0, \max_{1\leq k \leq n} S_k \Bigr\} = \Bigl(\max_{1\leq k \leq n} S_k \Bigr)^+ = \Bigl(\xi_1 + \max_{1\leq k \leq n} S_{1,k-1} \Bigr)^+ = F_1(M_{1,n-1}). $$

So, repeatedly applying this relation shows that $M_n = (F_1 \circ F_2 \circ \cdots \circ F_n)(0)$. However, from the recurrence relation, we know that $ W_n = (F_n \circ F_{n-1} \circ \cdots \circ F_1)(0) $. Since $(\xi_1, \xi_2, \ldots, \xi_n) $ has the same distribution as $ (\xi_n, \xi_{n-1}, \ldots, \xi_1)$, we are done. $\square$

Disclaimer. This proof is motivated by the queuing theory:

• The lemma above seems to have been known at least since Lindley.

• It is known that $\mathbf{E}[M^k] < \infty$ if and only if $\mathbf{E}[(\xi_1^+)^{k+1}] < \infty$; see J. Kiefer and J. Wolfowitz. In fact, the above proof is an adaptation of the proof from their paper.

Solution 2:

Introduction

The study of the supremum process of an iid random walk began with the study for the simple random walk. However, the study of the same for a negative-drift random walk began with of the introduction of the Cramer-Lundberg model. I'll pick up the details from the book of Embrechts, Kluppelberg and Mikosch titled "Modelling extreme events for Insurance and Finance".

The Cramer-Lundberg, or renewal model, is a basic risk insurance model, that works on a very simple idea : a customer , at iid exponentially distant time points , withdraws iid amounts of money from a bank/insurance company/moneylender. The insurance company has an initial capital, and a constant source of income. The question is, what is the probability that the insurance company will face ruin i.e. that it will not have money left to fulfill some claim of the customer at a certain finite point of time?

Once the parameters of the exponential, the mean of the claim amounts and the income are adjusted , a "net profit" condition for the company is assumed. It is quite easy to show, combining the claim amounts, claim times and the constant income, that the probability of ruin for this model is the probability that a negative-drift(as a result of the "net profit" assumption) random walk never crosses a certain threshold.

This briefly explains the relevance of the problem as a subproblem in the subject of "renewal theory" and the topic of financial mathematics.

Spitzer's formula/identity

A paper of Spitzer in 1956 titled "a combinatorial lemma and its applications to probability theory" actually gives a complete description of the distribution of the running maximum, for any random walk (which is a discrete time stochastic process with iid increments). I will make sure that I can cover the theorem in its entirety. However, the applicability of the lemma is poor because the quantities involved aren't explicit.

So, let $Y_1,...,Y_n$ be iid random variables, and let $S_0 = 0$, $S_n = Y_1+...+Y_n$. Let $M_n = \max_{t \leq n}\{S_t\}$ and $M_{\infty} = \max_{n \geq 0} S_n$. Let $F(x) = P(Y_1 \leq x)$, and let $F^{n}(x) = P[S_n \leq x]$ be the n-fold convolution of $F$.

Using Wiener-Hopf theory, the following integral exists on a certain complex domain $D$ : $$ f_+(t) = 1 - \exp\left[-\sum_{n=1}^\infty \frac 1n \int_{0}^\infty e^{itu} F^{n}(u)du\right] $$

It can be proven(this is actually not very difficult) that $f_+(t)$ is a completely monotone function i.e. that $(-1)^k\frac{d^k}{dx^k}f_+(t)$ is positive for all $k \geq 0$. For such functions, Bernstein's theorem asserts the existence of a measure whose Laplace transform is the given function. In this case, the measure is found to have a "proper" CDF as well i.e. there exists an $F_+ : \mathbb R \to \mathbb R$ such that $F_+$ is concentrated on $(0,\infty)$, is right-continuous and increasing (but doesn't satisfy the criteria $\lim_{x \to \infty} F_+(x) =1$ necessarily) such that $$ f_+(is) = \int_{0}^\infty e^{-st}dF_+(t)\quad \forall s>0 $$ (the integral is a Riemann-Stieltjes integral) $F_+$ is called the right Wiener-Hopf factor of $F$. But now, we can finally state :

Theorem[Spitzer] : Let $B = \sum_{n=1}^\infty \frac{P[S_n>0]}{n}$. Then, $M^*$ is finite a.s. if and only if $B$ is finite. (Otherwise, $M^*=\infty$ a.s.) Furthermore, if $B$ is finite, then $\lim_{x \to \infty} F_+(x) = (1-e^{-B})$, and an explicit description of the quantity $P(M^* \leq u)$ is given by $$ P[M^* \leq u] = e^{-B} \sum_{n=0}^\infty F_+^{n}(u) $$ where $F_+^n$ is the n-fold convolution of $F_+$ with itself, as a generalized distribution function.

Therefore, the study of the crossing probability comes down to the study of the right Wiener Hopf factor. However, it is quite clear that this formula is difficult to work with. So while any study begins with this formula, it eventually boils down to finding sufficient conditions under which the distribution of $M^*$ can be found.

The simplest case

The first explicit case was discovered by Cramer and Lundberg themselves when they were investigating the model. The Smith Renewal Theorem was used for this purpose. I will be modifying the statement slightly to capture the essence and stick to the narrative of the question. The basic idea is that if $F$ decays exponentially, then the ruin probability decays exponentially. This has been taken from the paper of Embrechts and Veraverbeke titled "Estimates for the probability of ruin with special emphasis on the possibility of large claims".

Theorem [The Cramer-Lundberg estimate] Consider the function $f(s) = \int_{-\infty}^{\infty} e^{-st} dF(t) = E[e^{-sX}]$. Suppose that $f(s)<\infty$ for some $s<0$ and $E[X]<0$. Then, there exist constants $C_1,C_2>0$ such that $P[M^* \geq u] \leq C_1e^{-C_2u}$ for $u\geq 0$. In particular, $E[M^*] < \infty$.

Now suppose that $F$ has a density $f$. The assertion of the Cramer-Lundberg estimate is that if there is a $s'>0$ such that $\int_0^t e^{s't}f(t)dt < \infty$, then $E[M^*]<\infty$. This therefore covers all the obvious cases : negative mean bounded random variables, negative mean normal random variables, etc.

A stronger result

It is quite clear, however, that the result above doesn't consider a class of distributions with a heavier tail. That is the focus of this section.

Definition : A function $G : [0,\infty) \to \mathbb R$ increasing , right-continuous and satisfying $G(0)=0$, $\lim_{x \to \infty} G(x) \leq 1$ is called a sub-exponential distribution function if $$ \lim_{x \to \infty} \frac{1-G^2(u)}{1-G(u)} = 2 $$ (where, as usual, $G^2(u) = \int_{0}^u G(u-y)dG(y)$)

The point is, for sub-exponential random variables, the following "principle" holds true :

The tail of the distribution of the sum of sub-exponential random variables, behaves like the maximum of these random variables.

To give you a quick idea of why this occurs, we have the following lemma picked up from the EKM book. A function $L$ is called slowly varying at infinity if for all $C>1$, $\frac{L(Cx)}{L(x)} \to 1$ as $x \to \infty$.

Suppose that $X_1,X_2$ are independent random variables such that for some $\alpha\geq 0$, we have $P[X_i>X] = x^{-\alpha}L_i(x)$ where $L_i$ are slowly varying at infinity. Then,$$ \frac{P[X_1+X_2 > x]}{P[X_1 > x] + P[X_2 > x]} \to 1\quad ; \quad x \to \infty $$

Brief proof : For one side, we use the fact that $$ P[X_1+X_2 > x] \supset P[X_1>x] \cup P[X_2>x] $$ For the other side, we use the fact that for $0<\delta<\frac 12$, we have $$ P[X_1+X_2 > x] \subset P[X_1 >\delta X]\cup P[X_2 > \delta X] \cup P[X_1 > \delta X , X_2 > \delta X] $$

This, along with independence and the regularly varying assumption, give the result as $\delta \downarrow 0$.

By induction, if $X_1,...,X_n$ are iid random variables with a tail like $x^{-\alpha}L(x)$, then $P[S_n>x] \approx n x^{-\alpha} L(x)$. Furthermore, it is quite easily seen from independence that $P[\max(X_1,...,X_n) > u] \approx n x^{-\alpha} L(x)$ as well! Therefore, the sum of a sequence of such random variables has a tail like the maximum of those random variables. This is a remarkable observation that will be reflected upon later.

Now, we come to the theorem of interest for sub-exponential distributions, specified by EKM. For this, suppose that $X$ is a random variable with $E[X]<0$. Let $X^+ = X 1_{X>0}$. Define the integrated tail distribution of $X^+$, $$ F_I(x) =\frac 1{E[X^+]}\int_{0}^x P[X^+> y] dy $$ Note that $F_I$ is a well-defined CDF.

Theorem[Cramer-Lundberg for large claims] : Suppose that $F_I$ is sub-exponential. Then, for some constant $C$ , we have $P[M^* \geq u] \leq C (1-F_I(u))$ for all $u > 0$.

Breaking down this formula, what is the connection with this and what we said and did slightly earlier? First, note that $1-F_I(u)$ is just $\frac{\int_x^\infty P[X^+ > y] dy}{E[X^+]}$ from the layer-cake formula for $E[X^+]$. Therefore, $1-F_I(u)$ is the normalized probability that the positive part exceeds a certain large number.

The idea behind this formula, is that the maximum of the sum exceeds a large number , "almost"(i.e. up to a constant) if and only if one of the values of the iid instances exceeds that large number itself. In some sense, think of it this way : for the random walk to go to a far off place, it is quite likely that a single abnormally large jump takes it there, rather than a compendium of small jumps.

Now, while we can think of a large number of sub-exponential functions, we actually proved in a lemma above that for a random variable $X$ with $P[X>u] = x^{-\alpha} L(x)$ for $L$ slowly varying, is a sub-exponential random variable.

Now, we can detach from the papers and prove our own result.

Suppose that $X$ is a random variable satisfying $E[(X^+)^{2+\delta}]>0$ for some $\delta>0$,and $P[X>x] = x^{-\alpha} L(x)$ for some slowly varying $L$ (Note : I expect the hypothesis to simplify, but I'd prefer to be just correct at this point). Then, for the random walk with iid increments given by $X$, we have $E[M^*]< \infty$.

Proof : Note that by the lemma we proved earlier, $X$ is sub-exponential. If $E[(X^+)^{2+\delta}]< \infty$,then by Markov's inequality, $$ P[X^+ > y] = P[(X^+)^{2+\delta} > y^{2+\delta}]\leq \frac{E[(X^+)^{2+\delta}]}{y^{2+\delta}} $$ and therefore, $$ \int_{x}^\infty P[X^+ > y] dy \leq E[(X^+)^{2+\delta}] \int_{x}^\infty \frac 1{y^{2+\delta}}dy \leq \frac{E[(X^+)^{2+\delta}]}{1+\delta} \frac{1}{x^{1+\delta}} $$

Therefore, there is a constant $C'$ such that $P[M^* \geq u] \leq C'\frac 1{u^{1+\delta}}$ for all $u>0$. It follows that $$E[M^*] = \int_0^\infty P(M^* \geq u) du \leq 1+ C' \int_1^\infty \frac 1{u^{1+\delta}} du \leq 1 + \frac{C'}{\delta}$$

as required.