# Finite time and asymptotic behaviour of the maximal excursion of a random walk

## Abstract

We evaluate the limit distribution of the maximal excursion of a random walk in any dimension for homogeneous environments and for self-similar supports under the assumption of spherical symmetry. This distribution is obtained in closed form and is an approximation of the exact distribution comparable to that obtained by real space renormalization methods. Then we focus on the early time behaviour of this quantity. The instantaneous diffusion exponent $`\nu _n`$ exhibits a systematic overshooting of the long time exponent. Exact results are obtained in one dimension up to third order in $`n^{1/2}`$. In two dimensions, on a regular lattice and on the Sierpiński gasket we find numerically that the analytic scaling $`\nu _n\nu +An^\nu `$ holds.   
Keywords: random walk, maximal excursion, finite size scaling, enumeration technique, Sierpiński gasket

The random walk (RW) on a lattice has long been studied due to its widespread applications in mathematics, physics, chemistry and other research areas. It turns out that despite the huge amount of accomplished work, it still remains a thriving research topic. Lots of results can be obtained in the continuum limit (Brownian motion) but results for RW on a lattice often yield drastically different behaviour - as it is the case for the winding angle distribution  \- or, at least, unusual finite time convergence properties. In the present work we investigate a central quantity for RW, the maximal excursion from the origin at time $`n`$, $`M_n=\mathrm{max}(x_m,0mn)`$. This random variable is of great interest in many practical purposes such as the control of pollution spread, propagation ranges of epidemics, tracer displacement in fluids, the radius of gyration of polymer chains , or of lattice animals  or other extreme statistics. A great deal of work was devoted to the first passage time (FPT) statistics which is a closely related quantity. Nevertheless methods used to find the exact FPT distribution in one dimensional inhomogeneous environments  do not help to get a closed form of the exact distribution of $`M_n`$. Except for the one dimensional case, only the leading order asymptotic expressions (as $`n\mathrm{}`$) are available. It was proved long ago by Erdős and Kac , that in this limit the distribution of $`M_n`$ coincides with that of the Brownian motion. This result appears as some kind of a central limit theorem. However, it does not deal with centered, reduced variables. Moreover it offers no practical access (for physically motivated purposes) to the convergence speed towards the limit law. The only global estimates available for $`M_n`$ are the laws of iterated logarithm of Khinchine and Chung  for the one dimensional random walk, claiming that although all the distributions have the same limit form, the intrinsic uncertainty on $`M_n`$ increases with $`n`$. Hence, it is not clear what the finite time behaviour of the maximal excursion $`M_n`$ is. It is our aim to clarify this point.

In this article, we first derive the leading order expression for the distribution of $`M_n`$ in a generalized form. This expression is shown to apply also on self-similar structures. Then we proceed to the next leading order expansion for short time. In this regime, the first moment of $`M_n`$ scales as $`M_nn^{\nu _n}`$ where $`\nu _n`$ is the effective instantaneous diffusion exponent, and tends to $`\nu _n\nu `$ as $`n\mathrm{}`$ ($`\nu =1/2`$ on regular lattices, $`\nu =\mathrm{ln}2/\mathrm{ln}(d+3)`$ on the $`d`$-dimensional Sierpiński gasket). We show numerical evidence that the effective instantaneous diffusion exponent $`\nu _n`$ approaches the limiting value $`\nu `$ according to $`\nu _n\nu n^\nu `$. This result is valid for both regular and self-similar lattices. We finally discuss this point in the context of other problems of statistical physics.

First let us briefly recall the formulae for the maximal excursion of a $`d`$-dimensional Brownian motion $`𝐫_t`$, that is $`M_t=\mathrm{max}(𝐫_u_2,ut)`$, where $`𝐫_2=\sqrt{_ir_i^2}`$ is the Euclidean distance. The limit distribution is denoted by $`𝐏_d(a,t)=\mathrm{Pr}\{M_t<a\}`$. The calculation goes through the solution of the diffusion equation in $`d`$ dimensions with spherical symmetry and absorbing boundaries on the hypersphere of radius $`a`$. Let $`U(𝐫,t)`$ be the probability density function for the position vector $`𝐫`$ of the walker relative to the origin at time $`t`$, without ever crossing the hypersphere boundary at distance $`a`$. Then $`U(𝐫,t)`$ satisfies the diffusion equation

$$_tU(𝐫,t)=\frac{1}{2d}_𝐫^2U(𝐫,t)$$
(1)   
where $`_𝐫^2`$ is the $`d`$-dimensional Laplace operator. The diffusion constant is set as $`1/(2d)`$ so that the solution corresponds to a simple random walk on $`𝐙^d`$ with a time $`\tau `$ between steps and a lattice spacing $`\sqrt{\tau }`$ in the limit $`\tau 0`$. The boundary condition is that $`U(𝐫,t)=0`$ for $`𝐫_2=a`$, and the initial condition is

$$U(𝐫,0)=\delta (𝐫)=\frac{\delta _+(|𝐫|)}{A_d|𝐫|^{d1}},$$

where $`A_d`$ is the surface area of the unit hypersphere in $`d`$ dimensions and $`\delta _+`$ is the (one-sided) delta function. The probability of remaining inside the hypersphere up to time $`t`$, $`𝐏_d(a,t)`$, is the volume integral of $`U(𝐫,t)`$ over the hypersphere. Due to spherical symmetry, $`U(𝐫,t)`$ is a function of $`r=𝐫_2`$ only, which we now denote by $`U(r,t)`$, so that, from (1)

$$_tU(r,t)=\frac{1}{2dr^{d1}}_rr^{d1}_rU(r,t),$$
(2)   
with $`U(r,0)=\frac{\delta _+(r)}{A_dr^{d1}},U(a,t)=0`$ and

$$𝐏_d(a,t)=_0^aA_dr^{d1}U(r,t)𝑑r$$

The solution of (2) is given in the form of an infinite eigenfunction expansion. This calculation can be done for self-similar lattices in the framework of the O’Shaughnessy-Procaccia approximation . It consists in assuming a spherical symmetry of a fractal object, and in introducing an effective diffusion coefficient $`D=D_0r^{2+1/\nu }`$ computed from the solution of the stationary diffusion problem on self-similar lattices without angular dependence. Thanks to this approximation, an analytic approach can be pursued. The final distribution, denoted $`𝐏_{d,\nu }`$ for general $`\nu `$ is obtained in the Laplace domain in closed form

$$𝐏_{d,\nu }(a,s)=\frac{1}{s}\left[1\frac{2^{1d\nu }}{\mathrm{\Gamma }(d\nu )}\frac{(4\nu ^2D_0^1a^{\frac{1}{\nu }}s)^{\frac{d\nu 1}{2}}}{I_{d\nu 1}\left(\sqrt{4\nu ^2D_0^1a^{\frac{1}{\nu }}s}\right)}\right]$$
(3)   
Here $`I_n(x)`$ is the modified Bessel function of order $`n`$. From this formula all moments are plainly computed

$$M_t^k_{d,\nu }=\left\{\frac{2\nu k}{\mathrm{\Gamma }(k\nu +1)}\frac{2^{1d\nu }}{\mathrm{\Gamma }(d\nu )(4D_0^1\nu ^2)^{k\nu }}\underset{0}{\overset{\mathrm{}}{}}\frac{u^{(2k+d)\nu 2}}{I_{d\nu 1}(u)}𝑑u\right\}t^{k\nu }$$
(4)   
Putting $`D_0=1/2d`$ and $`\nu =1/2`$ in (3), we easily recover the known distributions on regular lattices in one , two  and three  dimensions. A similar method was used in  to solve the first passage time problem in the presence of a steady potential flow. It is worthwhile mentioning that the limit $`d\mathrm{}`$ for $`\nu =1/2`$ in (3) yields $`𝐏_{\mathrm{}}(a,s)=\frac{1}{s}\left(1\mathrm{exp}(a^2s)\right)`$ to leading order. Hence, as intuitively expected, the maximal excursion of a random walker is exactly known in infinite dimension and peaks at $`a=\sqrt{t}`$.

On self-similar lattices ($`\nu 1/2`$), Equation (3) is only an estimate of the exact limit law. We have compared distribution (3) with the distribution obtained by real space renormalization group (RSRG) techniques for the 2D Sierpiński gasket . Both laws turn out to approximate the exact distribution to the same order (see Figure 1 and the discussion in ).

We have also evaluated the moments. To first order, they behave as $`M^kn^{k\nu }`$, so we define the normalized moments $`M^k=M_n^k/n^{k\nu }`$ which tend to a constant asymptotically. The first two normalized moments obtained from (4), $`M=1.20`$ and $`M^2=1.59`$, should be compared with the moments obtained from the RSRG method ($`M=1.19`$, $`M^2=1.57`$) and with the numerical estimates ($`M=1.28`$, $`M^2=1.84`$). Both theoretical formulae underestimate the actual values . This can be understood as follows. Strictly speaking, no limit distribution can be defined for $`M_n`$ but, for consecutive time series $`n,5n,5^2n,\mathrm{}`$, $`P_n(a/n^\nu )`$ is left invariant, because if a random walker takes $`T`$ steps to leave a triangle of size $`R`$, it needs a time $`5T`$ to leave a triangle twice bigger. Thus $`P_n(a)`$ fulfills the scaling relation $`P_n(a)=P_{5n}(2a)`$. However, between these times and for fixed $`a/n^\nu `$, the rescaled distribution $`P_n(a/n^\nu )`$ has a log-periodic variation. This log-periodic behavior has been known for some time for lattice random walks . Both function (3) and the RSRG result give the probability to stay in the triangle of size $`R=2^i`$, that is one minus the probability to reach sites at distance $`R+1`$ from the origin. As observed in Figure (1) this corresponds to an extremum in the oscillation of $`P_n(a/n^\nu )`$ (leftmost dashed line of Fig. 1) rather than to an average.

Now we turn our attention to the convergence speed towards the asymptotic law (3). For convenience we study the case of the discrete time random walk on the lattice, where analytical results can be obtained in one dimension and an exact numerical approach is possible in higher dimensions. We focus on the instantaneous diffusion exponent $`\nu _n`$ which furnishes an information about the convergence speed of the moments. The numerical estimation of $`\nu `$ using a Monte-Carlo sampling can lead to false conclusions as in  (see ). Here we use exact enumeration methods and therefore we avoid such problems.

The exact solution of the problem in one dimension is obtained by solving the master equation with absorbing boundaries at points $`\pm a`$ with the use of a Fourier development (obtained in  with a minor misprint), but the moments cannot be calculated in a straightforward manner from this expression beyond first order. We derived another form of the distribution by a recursive use of the reflection theorem. The probability density of the maximal excursion at step $`n`$ reads

$$P_n(M_n=a)=2\underset{k=0}{\overset{\mathrm{}}{}}(1)^k\left[p_n\left((2k+1)a\right)+p_n\left((2k+1)(a+1)\right)+2\underset{i=1}{\overset{2k}{}}p_n\left((2k+1)a+i\right)\right]$$
(5)   
where $`p_n(x)`$ is the probability density function for the discrete random walk to be at position $`x`$ (which is null for $`|x|>n`$). Formula (5) allows a convergent expansion of the first moments in powers of $`n^{1/2}`$, which exist, since $`P_n(M_n=a)`$ is an analytic function of $`n^{1/2}`$. At order $`n^{1/2}`$, divergent series are encountered which can be summed by classical methods , yielding

$$M_n=\sqrt{\frac{\pi n}{2}}\frac{1}{2}+\frac{1}{12}\sqrt{\frac{2\pi }{n}}+𝒪\left(\frac{1}{n}\right)$$
(6)   
$$M_n^2=2Gn\sqrt{\frac{\pi n}{2}}+\frac{G+1}{3}+𝒪\left(\frac{1}{\sqrt{n}}\right)$$
(7)   
where $`G=0.9166\mathrm{}`$ is the Catalan constant. In the calculation of the second cumulant the terms of order $`\sqrt{n}`$ and $`1/\sqrt{n}`$ cancel, as expected. The distribution $`P_t(M_t=a)`$ for continuous time random walks (CTRW) follows plainly from (5) since $`P_t(M_t=a)=_nP_n(M_n=a)\mathrm{\Pi }_t(n)`$, where $`\mathrm{\Pi }_t(n)`$ is the probability for the CTRW to perform $`n`$ steps in time $`t`$. Numerically, a series expansion similar to (7) is found for an exponential distribution of waiting times. The exponential distribution is particular because it is the only one for which a master equation formulation and a CTRW on the same lattice are isomorphic . A striking feature of the random variable $`M`$ compared to other extremal quantities at finite times is that the leading order expansion of $`M_n^k`$ scales as $`n^{k/2}+\mathrm{cte}.n^{(k1)/2}`$ and not as $`n^{k/2}+\mathrm{cte}.n^{k/21}`$, hence finite size effects persist for a large number of steps.

In two dimensions, no exact result is available for finite times and the analyticity of the probability density $`P_n(M_n=r)`$ is not obvious. Hence we investigate this case numerically. It is possible to perform an exact enumeration of the walks by studying the joint probability density of the position and maximal excursion $`P_n(x,y,M)`$ on the square lattice $`^2`$. We can compute $`P_n(x,y,M)`$ in the region $`0xM,0yx`$ only, due to symmetries. We use the family of metrics $`d_p(𝐱)=\left(_i(|x_i|^p)\right)^{1/p}`$ to compute the maximal excursion from the origin of the lattice. In Figure 2 we plot the instantaneous exponent $`\nu _n`$ with three classical choices of metric: $`d_1`$, $`d_2`$ (Euclidean distance) and $`d_{\mathrm{}}`$ (max distance). The metric $`d_1`$ and $`d_{\mathrm{}}`$ both induce a strong overshooting of $`\nu _n`$ with the limit value $`1/2`$. The curves have the same shape as that of the one dimensional case, also potted for reference in Figure 2. The first two moments have many features in common with their 1D equivalents. For example, using the metric $`d_{\mathrm{}}`$ we find that the series expansion $`M_n^k=_{p=0}^{\mathrm{}}m_{kp}^k(\sqrt{n})^{kp}`$ holds for both first and second moments up to third order, with $`m_0^1=0.50,m_1^1=0.322`$ and $`m_1^2=1.083,m_0^2=0.95,m_1^2=0.33`$. The leading order terms are exactly evaluated from the asymptotic results and read $`m_1^1=1.0830,m_2^2=1.3048`$. In the Euclidean metric $`d_2`$, we find a drastic change in the shape of the curve $`\nu _n`$ (Figure 2).

The instantaneous exponent approaches $`\frac{1}{2}`$ from below and remains below $`\frac{1}{2}`$ at time $`n=400`$. This phenomenon is a lattice effect. We show this fact by computing $`\nu _n`$ in an off-lattice random walk model (Figure 3).

Since it is not possible to use exact enumeration techniques in this case, we resort to a Monte-Carlo simulation. We inspect $`2.10^8`$ random walks with fixed distance increments and a uniform distribution of the angles (Pearson walks ). In this situation, $`\nu _n`$ in metric $`d_2`$ is very close to that obtained in metric $`d_1`$ and $`d_{\mathrm{}}`$, and it decreases towards $`\frac{1}{2}`$. Both lattice and off-lattice models should give equivalent results once the discretization effects are smoothed out. Therefore $`\nu _n`$ should ultimately approach $`\frac{1}{2}`$ from above in the on-lattice model. We have investigated the change of $`\nu _n`$ when varying continuously the metric $`d_p`$ with $`1p\mathrm{}`$ on the lattice (Figure 2). For large enough values of $`p`$ ($`p>50`$), we do observe that the curve crosses the value $`\frac{1}{2}`$. In the metric $`d_2`$, however, the time needed for $`\nu _n`$ to cross $`\frac{1}{2}`$ should be enormous.

This result shows that the definition of the metric strongly influences the convergence properties of the maximal excursion on regular lattices. The two natural metrics for the square lattice, $`d_1`$ and $`d_{\mathrm{}}`$, lead to a behaviour similar to that observed in the continuum model.

On the Sierpiński gasket we enumerate the walks starting from the top of the biggest triangle up to a fixed time. The metric chosen here is the chemical distance from the origin. For each maximal excursion $`r`$ we compute the probability of remaining below $`r`$ after $`n`$ steps, $`P_n^S(r)`$. Unlike the transfer matrix method, this method works only at fixed time, but allows us to discard the long transient regime and to compare the exact limit distribution to its spherically symmetric approximation. We have computed the instantaneous exponent $`\nu _n`$ up to step $`n=10^4`$ on a gasket of size 256 (cf. Figure 4).

Like the moments, $`\nu _n`$ displays a log-periodic oscillation persisting in the long time regime with an amplitude less than $`810^3`$. $`\nu _n`$ tends to the asymptotic value $`\nu =\frac{\mathrm{ln}2}{\mathrm{ln}5}`$ for long time. It seems that on a very general class of lattices the finite time behaviour of $`\nu _n`$ and therefore of $`M_n^k`$ is an analytic function of $`n^\nu `$. This fact lacks a clear physical understanding. The real space renormalization results do show that $`n^\nu `$ is the well defined time scale for this problem but the exact evaluation of finite size effects is not accessible from this method. To assess this hypothesis we have smoothed out the log-periodic oscillations of $`\nu _n`$. For a log-periodic function $`f(x)=f(Tx)`$, one can define $`z=\mathrm{ln}(x)`$ and $`\stackrel{~}{f}(z)=f(x)`$ so that the running logarithmic average reads

$$\overline{f}\left(\frac{Tx}{2}\right)=\frac{1}{_z^{z+\mathrm{ln}T}𝑑u}_z^{z+\mathrm{ln}T}\stackrel{~}{f}(u)𝑑u=\frac{1}{_x^{Tx}\frac{dv}{v}}_x^{Tx}f(v)\frac{dv}{v}$$

Using a discrete form of this average we write

$$\overline{\nu }_{\frac{5n}{2}}=\frac{1}{_{i=n}^{5n}\frac{1}{i}}\underset{i=n}{\overset{5n}{}}\frac{\nu _i}{i}$$

We tried to fit $`\overline{\nu }_n`$ using

$$\overline{\nu }_n=\nu +An^\nu +Bn^{2\nu }+o(n^{2\nu })$$
(8)   
and we found a very good regression for $`A=0.082\pm 0.002`$ and $`B=0.18\pm 0.1`$. However, the best fit with only one power law is $`\nu +\mathrm{cte}.n^\alpha `$ with $`\alpha =0.49`$, so that strictly speaking a nonanalytic short time dependence cannot be ruled out. The underlying assumption in the computation of $`\overline{\nu }_n`$ is that the regular log-oscillatory pattern of $`\nu _n`$ is additive. This assumption does not hold because the averaged exponent $`\overline{\nu }_n`$ still shows some oscillation. The local exponent $`\alpha `$ fluctuates between 0.40 and 0.52, which does not allow to confirm unambiguously the hypothesis of the analytic behavior of $`\overline{\nu }_n`$ as a function of $`n^\nu `$.

We would like to point out that in the context of lattice animals, the quantity $`M_n^k`$, or equivalently the “caliper diameter” (average spanning diameter of lattice animals once projected on a fixed axis) displays a sub-leading order behaviour which scales as $`n^{(k1)\nu }`$ , aside from the well-known non analytic subleading term, and can be interpreted as a ’surface contribution’. In the case of the maximal excursion of a random walk, we have proved in one dimension and evidenced through enumerations in higher dimensions that the early time instantaneous exponent $`\nu _n`$ is systematically above its limit value $`\nu `$ with a leading order development $`\nu _n\nu +An^\nu `$ where $`A`$ depends on the precise choice of the metric. This result is consistent with the fact that the corrective scaling to the moments due to finite size effects includes only terms of the form $`(n^\nu )^p,p`$, which was proved in one dimension and which can also be interpreted as a surface contribution.

In conclusion, besides its intrinsic interest, the maximal excursion of a random walk shares difficulties which are often encountered in physical problems dealing with finite size series. In certain cases, power law exponents inferred from the finite size series expansions should be considered with caution, as might be the case for directed percolation series.