Probability of a Random Walk crossing a straight line

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!

-
 What is $k$ in the equation for $\mathcal{P}(0)$? – Konstantinos Panagiotou May 9 2011 at 13:54 Thanks Konstantinos for pointing that out. The $k$ was supposed to be an $n$, so I changed it now. – TMM May 9 2011 at 14:26 Not an answer, just an observation. If you instead write $S_n=\epsilon+\sum_{i=1}^n X_i$ then for irrational $\alpha$ I expect that $\mathcal{P}_{\epsilon}(\alpha)$ will be everywhere discontinuous as a function of $\epsilon$. This gives me some doubt that there will be a nice, closed-form answer, since in any recurrence-relation type approach to the problem you will end up having to consider terms like $\mathcal{P}_{\epsilon}(\alpha)$ You might find something of use in the literature on combinatorics on words, but I don't know this literature very well at all so I'm not sure. – Louigi Addario-Berry May 9 2011 at 15:54

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.

-
 For example, I can approximate $P(1-2/\log_2(5))$ fairly quickly by $0.823974215430924=P(127/916) 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$). -  Nice! And running some calculations with series similar to$P(0)$above confirms that$P(1/3 + \epsilon) \approx 0.618034\ldots$and$P(1/2 + \epsilon) \approx 0.543689\ldots$which matches your results. And your general solution strategy seems doable, although solving the equations for$f(n)$become more difficult when the denominator in rational$\alpha$increases. But calculating$P(\alpha_{+})$and$P(\alpha_{-})$for some good rational approximations$\alpha_{-} \leq \alpha \leq \alpha_{+}$should be possible, and should give reasonably tight bounds on$P(\alpha)$for any real$\alpha$. – TMM May 10 2011 at 9:28 The amount by which$P$can vary in an interval not containing any rationals with denominator greater than some$N$will be exponentially decaying in$N$. So, if you want to calculate$\mathcal{P}(\alpha)$by approximating with$\mathcal{P}(\alpha^-)$then you only need to choose$\alpha^-$with denominator of the order of the logarithm of the required error bound, and the degree of the polynomial you have to solve is also of the order of the logarithm of the error. – George Lowther May 10 2011 at 20:34 @George: Yes, but the exact denominators we use may of course depend on good approximations for$\alpha$, e.g. you don't approximate$\pi$from above with denominator$8$but with denominator$7$. And there are some pitfalls to watch out for, e.g. approximating$P(1/2)$with$P(1/2 - \eps)$will never give a good approximation, but as long as the interval$[\alpha_{-},\alpha_{+}]$does not contain any rationals with small denominator the approximations should be fine. And with irrational$\alpha$we can always guarantee this. – TMM May 11 2011 at 9:42 Ah, mathoverflow does not have \newcommand{\eps}{\epsilon} in its preamble ;( – TMM May 11 2011 at 9:45 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. -  Actually, for$\alpha < 1$the random walk will always cross the line if the first step is a$+1$, which happens with probability$\frac{1}{2}$. So the probability of staying below the line is trivially at most$\frac{1}{2}$, giving$\mathcal{P}(\alpha) \leq \frac{1}{2}$for any$\alpha < 1$. This is a sharper upper bound than$\mathcal{P}(\alpha) \leq \frac{1}{1 + \alpha}$for any$\alpha < 1$. So although the derivation is nice, the upper bound is not so useful. – TMM May 3 2011 at 11:17 Sorry, I think I was visualizing the walk the wrong way and thought of the "slope" as something else than what is defined as$\alpha$. I'll edit my post. – Johan Wästlund May 3 2011 at 12:22 No, wait, I thought of$P(\alpha)$as the probability that the walk does cross, but it's the probability of not crossing. But I don't have time to edit right now. – Johan Wästlund May 3 2011 at 12:31 I apologize for the confusion caused by the title (probability of crossing) and question (probability of not crossing). I have updated the definition of$P(\alpha)$so that now it does mean the probability of crossing. – TMM May 3 2011 at 17:18 Thanks, no need to apologize! – Johan Wästlund May 3 2011 at 18:35 show 2 more comments (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)= \left\{ \begin{array}{ll} \frac{1}{2}\left[ P(b+a-1)+P(b+a+1) \right] & \mbox{if } b \geq 0 \\ 1 & \mbox{if } b < 0 \end{array} \right. $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 funcion has discontinuites at points$k/n$. - 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. -  Sorry - I didn't read the 'exists' part of your question carefully, so this isn't quite what you're looking for. It is a bound for a particular$n\$, though. – John Jun 10 2011 at 18:02