# Identity involving the probability that a random walk stays below a curve

I'm looking for a direct proof of the following identity:

Let $$W_n$$ be a simple random walk with $$W_0=0$$. For all $$x>0$$ we have $$\lim _{N\to \infty} \sqrt{N} \cdot \mathbb P \Big( \forall n \le N , \ W_n \le x\sqrt{N} -x\sqrt{N-n} \Big) =\frac{e^{-\frac{x^2}{2}}}{\int _x^\infty e^{-\frac{y^2}{2}}dy}.$$ I have an indirect proof that follows from a specific model that I've been working on related to DLA.

It's not hard to show that the probability in the left hand side decays like $$C/\sqrt{N}$$ (because one can show that it behaves like the probability that a random walk stays negative for $$N$$ steps). This is the reason for the factor $$\sqrt{N}$$ inside the limit.

• The curve is smooth at 0 (scaled to converge to Brownian motion), do you know if the probability is the same as for crossing the tangent line at 0 ? – mike Jul 27 at 7:49
• It is not the same. The ratio between these probabilities doesn't tend to 1. However, the limit of this ratio does tend to 1 as x tends to infinity. One can compute the probability of staying below a line using the exponential martigale. I tried to do the same in here but it didn't work. – Dor Jul 27 at 9:15
• what is the distribution of steps? – Fedor Petrov Jul 31 at 20:17
• Plus or minus one with probability half. It should be the same formula when we replace the discrete time random walk with a continuous time random walk, and also the same if we replace the deterministic curve with a Poisson process with rate 0.5*(N-n)^(-1/2) at time n (this might be the way to go because formulas for the exponential martingale become simpler when we make everything continuous time) – Dor Aug 1 at 14:49

Example 2 of arXiv:0704.2826 considers the analogous problem for the continuous-time random walk, in the more general case that the curve has the form $$g(t)=a+b\sqrt{T-t}$$ with $$a+b\sqrt T\geq 0$$. The random walk starting at the origin stays below that curve for all $$t with probability $$P(T,a,b)=1-\frac{\int_{-\infty}^{-a/\sqrt T} e^{-y^2/2}dy}{\int_{-\infty}^{b} e^{-y^2/2}dy}.$$ This holds for any $$T$$, not only in the large-$$T$$ limit.
The case in the OP corresponds to $$a=x\sqrt T$$, $$b=-x$$, and this probability vanishes, the reason being that in this case $$g(0)=0$$, the boundary intersects the origin at $$t=0$$ and the continuous-time random walk is never strictly below the boundary.
To make contact with the discrete-time random walk formula of the OP, I take $$a=x\sqrt T + \epsilon$$, so $$g(0)=\epsilon$$, and then to first order in the infinitesimal step size $$\epsilon$$ one has $$P(T,x\sqrt T+\epsilon,-x)=\frac{\varepsilon}{\sqrt T}\frac{e^{-x^2/2}}{\int_{x}^{\infty} e^{-y^2/2}dy}+{\cal O}(\epsilon^2).$$ This reduces to the expression in the OP upon identification of $$N=DT/\epsilon^2$$, with $$D\equiv 1$$ the diffusion constant of the random walk. This correspondence between discrete-time and continuous-time random walks only holds in the $$T\rightarrow\infty$$ limit.