Simple formula for the probability that a random walk with non equal steps does not hit zero?

78 Views Asked by At

I've been interested with gambler-ruin-type problems with steps of unequal size. In doing so, I stumbled upon a very curious observation that I cannot manage to prove. For TL;DR, see the conjecture below.


Here's the setting: Let $d\in\{1,2,3,\ldots\}$, and define i.i.d. random variables $X_i$ with distribution $$\mathbb P\{X_i=1\}=p\qquad\qquad\mathbb P\{X_i=-d\}=1-p.$$ I'm interested in the random walk $$S_n=S_0+X_1+\cdots+X_n.$$


So long as $p>\frac{d}{d+1}$, we have that $\mathbb E(X_i)>0$, and thus the random walk drifts off to $+\infty$ with probability 1. I'm interested in the probability that the random walk starting at some $k\geq 1$ never touches zero before it diverges:

$$P(k)=\mathbb P\{\forall n:~S_n>0~|~S_0=k\}.$$

By standard first-step analysis (i.e., $P(k)=pP(k+1)+(1-p)P(k-d)$) we can in principle recursively solve for $P(k)$ in terms of $P(1)$, i.e., there is some constant $c_k$ such that $$P(k)=c_kP(1),\qquad k\geq1.\tag{$\ast$}$$

As far as I can tell, there is no simple formula for $c_k$ for arbitrary $k$ when $d\geq2$. However, for finite $k$ not too large, $c_k$ can be calculated using a computer. That said, this leaves out the value of $P(1)$, which is of course required to calculate $(\ast)$.


At first, I was resigned to just approximate $P(1)$ numerically by solving the problem $$P^N(k)=\mathbb P\{S_n\text{ hits $N$ before $0$}~|~S_0=k\}$$ using a computer; in doing so, we can use the boundary condition $P^N(N)=1$ to solve for $P^N(1)$. If $N$ is very large then $P^N(1)\approx P(1)$. As I did this, I was struck by how often I would get seemingly extremely simple results for what $P(1)$ supposedly is, such as $0.2000000000$, $0.3333333333$, or $0.6666666667$ (I was instead expecting stuff like $0.5437927472$ or whatever). After playing around with the values of $p$ and $d$, I eventually came up with the following "conjecture," which shows remarkable agreement with the numerics I just mentioned no matter what I put for $p$ and $d$:

Conjecture. For every $d\in\{1,2,3,\ldots\}$ and $\frac{d}{d+1}<p<1$, $$P(1)=\mathbb P\{\forall n:~S_n>0~|~S_0=1\}=1+d-\frac dp=1-d\frac{1-p}{p}.$$

The simplicity of this formula leads me to believe that the must be a simple argument to compute $P(1)$, but I haven't been able to figure it out.

1

There are 1 best solutions below

1
On BEST ANSWER

Let $f(z) = \sum_{k=1}^{\infty} P(k)z^k$ be the generating function of $P(k)$. Then the first-step analysis

$$ P(k) = pP(k+1) + (1-p)P(k-d) $$

translates to the functional identity

$$ f(z) = \frac{p}{z}f(z) - p P(1) + (1-p) z^d f(z), $$

which yields

$$ f(z) = - \frac{p}{1 - \frac{p}{z} - (1-p)z^d} P(1). $$

On the other hand, it is clear that $P(k) \to 1$ as $k \to \infty$. Hence,

\begin{align*} 1 = \lim_{k\to\infty} P(k) = \lim_{z \to 1^-} \frac{\sum_{k=0}^{\infty} P(k) z^k}{\sum_{k=0}^{\infty} z^k} = \lim_{z \to 1^-} (1 - z)f(z) = \frac{p}{p - (1-p)d} P(1). \end{align*}

Rearranging this identity for $P(1)$ gives

$$ P(1) = 1 - \frac{(1-p)d}{p} $$

as conjectured by OP.