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.

  • 3
    $\begingroup$ 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 ? $\endgroup$ – mike Jul 27 at 7:49
  • 2
    $\begingroup$ 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. $\endgroup$ – Dor Jul 27 at 9:15
  • 3
    $\begingroup$ what is the distribution of steps? $\endgroup$ – Fedor Petrov Jul 31 at 20:17
  • 3
    $\begingroup$ 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) $\endgroup$ – 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<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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.