Random walk exit identities

82 Views Asked by At

I'm stuck with a seemingly easy relation which I have not been able to find in the standard probability literature. This is surprising since the result exists for much more general processes (for Levy processes in terms of scale functions).


The formulation:

For a simple random walk, i.e. a process $$S_n=x+\sum_{i=1}^n X_i$$ where $x>0$ is constant and $X_i$ are independent and identically distributed with $$\mathbb{P}(X_1=1)=p=1-\mathbb{P}(X_1=-1)$$ For $b>x$, I would like to know the quantities $$\mathbb{E}_x(e^{-\delta\tau_b}1_{\tau_b<\tau_0}),\quad \mbox{and} \quad \mathbb{E}_x(e^{-\delta\tau_0}1_{\tau_0<\tau_b})$$ where $\mathbb{E}_x$ is the conditional expectation given that $S_0=x$, $\delta\ge 0$ is a constant and $$\tau_m=\inf\{n\ge 0: S_n=m\}.$$


My attempt:

The process $$M_n=e^{-\delta S_n-n[\log(1-p+pe^{-2\delta})+\delta]}$$ is bounded a martingale for small enough $\delta\ge0$, so by optional stopping

$$e^{-\delta x}=e^{-\delta b}\mathbb{E}_x(e^{-\eta\tau_b}1_{\tau_b<\tau_0})+\mathbb{E}_x(e^{-\eta\tau_0}1_{\tau_0<\tau_b})$$ for $\eta:=\log(1-p+pe^{-2\delta})+\delta$.

The above equation has two unknowns. For $\delta\to 0$ we also have the obvious second relation $\mathbb{P}(\tau_0<\tau_b)=1-\mathbb{P}(\tau_b<\tau_0)$, from which a solution can be obtained. In general for $\delta>0$ an analogous second relation is not obvious.

The equation derived by the martingale argument also shows that it suffices to compute one of the quantities of interest to obtain the other one though it.

1

There are 1 best solutions below

1
On BEST ANSWER

For $\delta \ge 0$, $p \in (0 ; 1)$, and $b \ge 1$ fixed, let $e_n = \Bbb E(\exp(-\delta \tau_b) 1_{\tau_b < \tau0} \mid S_0 = n)$ for $0 \le n \le b$.

We have $e_0 = 0, e_b = 1$, and if $0<n<b$ then $e_n = \exp(-\delta)(pe_{n+1}+(1-p)e_{n-1})$.

$a_n$ is then a recurrent linear sequence. We have $b-1$ unknowns and $b-1$ equations so there should be a unique solution.
The characteristic polynomial of the recurrence is $\exp(-\delta)pX^2 - X + \exp(-\delta)(1-p)$.
Its discriminant $\Delta$ is $1 - 4p(1-p)\exp(-2\delta)$.
Since $0<p<1$ we have $0 < p(1-p) < \frac 14$ ; and since $\delta \ge 0$, we have $\exp(-2\delta) \ge 1$.
Those bounds show that $\Delta > 0$, so the characteristic polynomial has two distinct real roots

Let $u,v = \exp(\delta)(1 \pm \sqrt \Delta) / (2p)$ be the two roots (note that they are independent of $b$).
Then $e_n$ has to be of the form $Au^n + Bv^n$ for some real constants $A,B$.
Using $e_0 = 0$ and $e_b = 1$ to solve for $A$ and $B$, we eventually obtain

$e_n = (u^n-v^n)/(u^b-v^b)$

Let $e'_n = \Bbb E(\exp(-\delta \tau_0) 1_{\tau_0 < \tau_b} \mid S_0 = n)$. This sequence satisfies the same linear reccurence as $(e_n)$ except that the constraints at $0$ and $b$ have become $e'_0 = 1$ and $e'_b = 0$. For symmetry reasons, you can also obtain $e'_n$ from $e_n$ by replacing $n$ with $b-n$, and $p$ with $1-p$. Doing so reverses the characteristic polynomial, so we also have to replace $u$ and $v$ with $u^{-1}$ and $v^{-1}$. We get :

$e'_n = (u^{n-b}-v^{n-b})/(u^{-b}-v^{-b}) = (u^bv^n-u^nv^b)/(u^b-v^b)$

When $\delta \to 0$, the characteristic polynomial becomes $pX^2-X+(1-p) )$, which has $1$ as a root.
Replacing $v$ with $1$, we get $e_n = (u^n-1)/(u^b-1)$ and $e'_n=(u^b-u^n)/(u^b-1)$. Those two sum to $1$ as you predicted.