Probability of a Random Walk crossing a straight line

Question

Let $(S_n)_{n=1}^{\infty}$ be a standard random walk with $S_n = \sum_{i=1}^n X_i$ and $\mathbb{P}(X_i = \pm 1) = \frac{1}{2}$. Let $\alpha \in \mathbb{R}$ be some constant. I would like to know the value of

$$\mathcal{P}(\alpha) := \mathbb{P}\left(\exists \ n \in \mathbb{N}: S_n > \alpha n\right)$$

In other words, I am interested in the probability that a random walk $(S_n)_{n=1}^{\infty}$ crosses the straight line through the origin with slope $\alpha$.

Since the standard random walk is recurrent, it follows that $\mathcal{P}(\alpha) = 1$ for $\alpha \leq 0$, while obviously $\mathcal{P}(\alpha) = 0$ for $\alpha \geq 1$. Hence the non-trivial part and the part I am interested in is the region $\alpha \in (0,1)$. For this region we know that $\mathbb{P}(S_1 > \alpha) = \frac{1}{2}$, hence $\mathcal{P}(\alpha) \geq \frac{1}{2}$, but finding an exact value seems difficult.

Note: One way to explicitly calculate $\mathcal{P}(0)$ is by

$$\mathcal{P}(0) = \sum_{n=1}^{\infty} \frac{C_n}{2^{2n-1}} = 1$$

where $C_n$ is the $n$-th Catalan number, as was pointed out on e.g. http://oeis.org/A000108 by Geoffrey Critzer. For general $\alpha$ however such a summation does not seem to give a nice expression, since the coefficients are uglier and the exponents of $2$ depend on $\alpha$ (for $\alpha = 0$ one gets exponents $2n - 1$, but for irrational $\alpha$ this exponent becomes something ugly). But finding a closed form for these coefficients for general $\alpha$ might also help solve this problem.

Edit: As it may be too much to ask for a nice formula for $\mathcal{P}(\alpha)$, I would also be very happy if someone could provide (good) bounds on or approximations of the value of $\mathcal{P}(\alpha)$. For example: Does $\mathcal{P}(\alpha)$ decrease linearly in $\alpha$? Any insight is very much appreciated!

Answer 1

I wrote a Maple program in 2003 which computes $P(\alpha)$ (both the "upper" and "lower" values) for a given rational number $\alpha$, much in line with the method described by Johan. I think I was able to compute it for all $\alpha=a/b$ for integers $1\le a\lt b\le 300$ in a couple of hours, so the program could probably compute fairly good approximations to $P(1-2/\log_2(p))$ when $p$ is not too large. (Edit: When $p$ is large, $1/2$ will be a very good approximation. For example, if $p\gt1000$ then $0.499\lt P(1-2/\log_2(p))\lt1/2$.)

I didn't publish any of this, but much of it is contained in the article "The Maximum Average Gain in a Sequence of Bernoulli Games" by Wolfgang Stadje (American Mathematical Monthly, December 2008).

EDIT: Since I don't have access to Maple anymore, I translated the program to Matlab:

function p=p(s,t);
d=gcd(s+t,2*t);
s=(s+t)/d;
t=2*t/d;
pol=zeros(1,t+1);
pol([1 s+1 t+1])=[1 -2 1];
r=roots(pol);
[rsort,i]=sort(abs(r));
p=1-prod(abs(1-r(i(1:t-s))));

The program computes $P(s/t)$ for integers $0\lt s\lt t$, by computing $1$ minus the product of $1-r$ for those zeroes $r$ of $z^{2t/d}-2z^{(t-s)/d}+1$ that have absolute value less than $1$ (there are $(t-s)/d$ of them), where $d=\gcd(s+t,2t)$.

By the way, in my notes I found the lower bound $P(\alpha)\ge A$, where $\alpha=1-\frac{2\log A}{\log(2A-1)}$, with equality for $\alpha=(k-2)/k$. I think Johan was involved in obtaining this bound.

EDIT (May 14): So, here is a fairly detailed proof of the formula used in the program above.

Lemma 1. For integers $0\lt 2b\lt a$, the polynomial $g(z)=z^a-2z^b+1$ has no multiple zeros and exactly $b$ zeroes inside the unit circle.

Proof. If $g(z)=g'(z)=0$ then $z\ne 0$ and $$0=g'(z)=az^{a-1}-2bz^{b-1}=z^{b-1}(az^{a-b}-2b),$$ so $az^{a-b}-2b=0$. Hence, $0=g(z)-g'(z)*z/a=1-2(1-b/a)z^b$ so that $|z|^b=\frac1{2(1-b/a)}=\frac a{2(a-b)}$. Also, $az^{a-b}-2b=0$ so $|z|^{a-b}=2b/a$. This implies that $$\left(\frac a{2(a-b)}\right)^{a-b}=\left(\frac{2b}a\right)^b.$$ This can be rewritten as $2(1-b/a)^{1-b/a}(b/a)^{b/a}=1$. But it is easily checked that $2(1-y)^{1-y}y^y\gt1$ for $0\lt y\lt1/2$, a contradiction.

The second part can be proved by a straight forward application of Rouché's theorem.

Lemma 2. Suppose that $\sum_{i=1}^kA_ir_i^{-j}=1$ for $1\le j\le k$. Then $\sum_{i=1}^kA_i=1-\prod_{i=1}^k(1-r_i)$.

Proof. The equations can be seen as a system of linear equations in $A_1,\dots,A_k$, and the result can be obtained by using Cramer's rule and Vandermonde determinants. I skip the details. (Actually, I think I had a simpler proof of this lemma, but I could neither find it in my notes, nor figure it out right now.)

Now, let $L=\max_{n\gt0}{S_n/n}$, so that $P(\alpha)=P(L\gt\alpha)$. Also, let $Y_i=(X_i+1)/2$ and $T_n=\sum_{i=1}^nY_i$ (so that $T_n$ is a random walk with steps $0$ and $1$ instead of $\pm 1$). (The main reason for this is that my original result was for $T_n$, but I also think that the formulae get a little simpler in this case.)

Let me restate the result I am going to prove:

Theorem. For integers $0\lt s\lt t$, $P(s/t)=1-\prod_{i=1}^{t-s}(1-r_i)$, where $r_1,\dots,r_{t-s}$ are the zeroes of $z^{2t}-2z^{(t-s)}+1$ that have absolute value less than $1$.

Proof. Let $M=\max_{n\gt0}{T_n/n}$ and $Q(\alpha)=P(M\gt\alpha)$. I will prove the corresponding result for $Q(s/t)$, and then translate it to $P$, using the fact that $T_n=(S_n+n)/2$ which implies that $P(\alpha)=Q((\alpha+1)/2)$.

Suppose then that $1/2\lt s/t\lt1$ and consider $Q(s/t)$. Just as Johan did, we define another random walk $U_n=\sum_{i=1}^nZ_i$ with steps $Z_i=s$ or $Z_i=s-t$ so that $Q(s/t)$ equals the probability that $U_n$ will ever reach $-1$, define $f(j)$ as the probablity that $U_n$ will reach $-1$ when it is currently at $j$, and find that $f(j)=f(j+s)/2+f(j+s-t)/2$ for $j\ge0$. The characteristic equation of this recursion is $g(z)=z^t-2z^{t-s}+1=0$. By Lemma 1 and since $f(j)$ tends to $0$ as $j$ tends to infinity, we must have $f(j)=\sum_{i=1}^{t-s}A_ir_i^j$, where $r_1,\dots,r_{t-s}$ are the (necessarily simple) zeroes of $g(z)$ inside the unit circle. Since $f(j)=0$ for $s-t\le j\le -1$, Lemma 2 implies that $Q(s/t)=f(0)=\sum_{i=1}^{t-s}A_i=1-\prod_{i=1}^{t-s}(1-r_i)$.

Now, if $0\lt s/t\lt1$ then $P(s/t)=Q((s+t)/(2t))$, which, by what we have just proved, equals $1-\prod_{i=1}^{t-s}(1-r_i)$, where $r_1,\dots,r_{t-s}$ are the zeroes of $z^{2t}-2z^{t-s}+1$ inside the unit circle. This concludes the proof.

Answer 2

I believe that leonbloy's comment/hint is relevant, and whenever $\alpha$ is rational, $P(\alpha)$ is algebraic. For instance, $P(1/3)$ is simply the probability that a random walk on $\mathbb{Z}$ starting at the origin and taking steps of $+2$ or $-1$ with equal probability will ever reach $-1$. If $f(n)$ is the probability of ever reaching a negative point given that the walk is currently at $n$, then $f(n)$ satisfies $$f(n) = \frac{f(n+2)+f(n-1)}2.$$ The standard ansatz $f(n) = x^n$ gives three solutions for $x$: $x=1$ or $x=(-1\pm \sqrt{5})/2$. It is easily seen that the only solution of the form $f(n) = Ax_1^n + Bx_2^n + Cx_3^n$ that satisfies the boundary conditions (at $-1$ and infinity) is $f(n) = (-1/2+\sqrt{5}/2)^{n+1}$, from which it follows that $$P(1/3) = \frac{\sqrt{5}-1}2.$$ Similarly, $P(1/2)$ is equal to the unique root of $x = (x^4+1)/2$ in $(0,1)$, and in general, $P(k/(k+2))$ is the unique relevant root of $x = (x^{k+2}+1)/2$.

If $\alpha$ is rational but not of this form, the boundary conditions become a little more complicated. For instance, consider $\alpha=1/5$. This can be modeled by a random walk on $\mathbb{Z}$ where a particle takes steps of $+3$ or $-2$. The corresponding ansatz gives $x^2 = (x^5+1)/2$, which has two roots of absolute value smaller than 1, one positive and one negative. Since the walk can now jump to the left, it can reach a first negative value both at $-1$ and at $-2$. Apart from $f(n)\to 0$ at infinity, we get the two boundary conditions $f(-1)=1$ and $f(-2)=1$. We can now find $f$ explicitly (at least numerically) as $f(n) = Ax_1^n+Bx_2^n$ where $x_1$ and $x_2$ are the roots in $(-1,1)$ and $A$ and $B$ are determined by the boundary conditions.

As has already been pointed out, $P(\alpha)$ makes a jump at every rational number. With the approach outlined above, one can in principle compute both the "lower" and "upper" values of $P(\alpha)$ (the upper value being the probability that $S_n$ reaches, but does not cross, the line of slope $\alpha$) whenever $\alpha$ is rational. This is feasible only when $\alpha$ is a relatively simple fraction, but it should still be possible to obtain a good plot of $P(\alpha)$ as a function of $\alpha$.

I recall that after this problem was discussed at the open problem session of FPSAC 2003, Pontus von Brömssen made some such plots. I haven't been in touch with him in the last few years, but apparently he has an (inactive) MO-account. I will notify him of this question.

ADDED: One might worry about whether in general, a solution obtained as indicated above is the correct one. For instance, in the example with $\alpha = 1/5$, the equation $x^2 = (x^5+1)/2$ has, apart from the three real roots, also two non-real roots, and even after finding a solution $f$ involving only the two real roots other than 1, it might not be totally obvious that there is no other real function of the form $g(n) = A_1x_1^n+\cdots+A_5x_5^n$ that satisfies the boundary conditions (this would be possible if the two non-real roots had absolute value smaller than 1).

There is a simple application of Brownian motion that shows that anything that satisfies the recursion $g(n+2) = (g(n) + g(n+5))/2$ as well as the boundary conditions, must be the correct solution. I picked this up recently from Jeff Steif (in a slightly different context), who told me he heard it from Yuval Peres twenty years ago. Here is how it goes:

Suppose that someone gives us a function $g$ that satisfies $g(-1) = g(-2) = 1$, $g(n+2) = (g(n) + g(n+5))/2$ for $n\geq 0$, and $g(n)\to 0$ as $n\to\infty$. Since such a function must have the form $A_1x_1^n+\cdots+A_5x_5^n$, it is easy to see that all the values have to be in the interval $[0,1]$ (there could not be a smallest value of $g$).

Now start a Brownian motion on the real line from the point $g(0)$, and run it until it hits either $g(-2)$ or $g(3)$. If it hit $g(3)$, continue until it hits $g(1)$ or $g(6)$, etc. In finite time, the particle will reach either $1=g(-1) = g(-2)$ or 0 (in case it went through $g(n)$ for some sequence of $n$'s tending to infinity).

It follows from basic properties of the Brownian motion that the probability that it reaches 1 before reaching zero is $g(0)$. Since the process correctly emulates the discrete random walk of steps $+3$ and $-2$, it follows that the probability that the emulated walk on the integers reaches $-1$ or $-2$ before going to infinity is also $g(0)$.

Therefore the boundary conditions uniquely specify the solution (and the argument obviously generalizes to any rational $\alpha$).

Answer 3

Here's a gem I heard from Olle Häggström in 2003. It doesn't completely answer the question, but it's a surprisingly simple (imo) way to obtain an upper bound on $P(\alpha)$.

Suppose the walk does cross a line of slope $\alpha$. Then at some point it is above that line for the last time. Conditioning on that last time, we can permute the steps before that point any way we like, so it follows that the conditional probability that the first step of the walk was a $+1$ is at least $(1+\alpha)/2 $. But that probability is just $$\frac{1/2}{P(\alpha)},$$ and it follows that $$P(\alpha) \leq \frac{1/2}{(1+\alpha)/2} = \frac{1}{1+\alpha}.$$

ADDED: It is possible to obtain quite sharp estimates of $P(\alpha)$ by combining this type of argument with some combinatorics of the first $n$ steps of the walk. On the other hand, the reason the estimate is not sharp is that the walk sometimes overshoots (actually always if $\alpha$ is irrational) so that the last point on or above the line of slope $\alpha$ is strictly above. This indicates that the exact value of $P(\alpha)$ will depend in a complicated way on the extent to which $\alpha$ can be approximated by rational numbers, and a simple formula may be too much to ask for. I'm sure that interesting things can be said about $P(\alpha)$, but it might require specifying what we want to know.

Answer 4

(Just a hint. Should be a comment more than an answer, but don't have enough rep)

It seems interesting the slightly more general problem in which the initial distance to the line is greater than zero - or that the line has the equation $a n + b$ Considering $a$ fixed and $b$ variable, one can get (if I'm not mistaken) a the following equation on $P(b)$ (probability that the process crosses the line) as:

$P(b)= \begin{cases} \frac{1}{2}\left[ P(b+a-1)+P(b+a+1) \right], & \mbox{if } b \geq 0; \\ 1, & \mbox{if } b < 0. \end{cases} $

We want a solution (apart from the trivial $P(b)=1$) that goes to zero as $b \to \infty$ , and we are specially interested in $P(0^+)$ Does not seem easy, seems very sensitive to the parameter $a$. I believe that if $a$ is rational, $a=m/n$, the function has discontinuities at points $k/n$.

Answer 5

An upper estimate is given in Appendix A of "The Probabilistic Method" by Alon/Spencer. This gives $P(S_n > a) < e^{-a^2/2n}$ for $a > 0$ (Theorem A.1.1). There are lots of bounds like this one, if you are interested in simple upper bounds.