Exit Probability and First Passage Time of a Lazy Pearson Walker: Scaling Behaviour

Show more

Received 1 June 2016; accepted 24 July 2016; published 27 July 2016

1. Introduction

The random walk is a problem, studied widely in mathematics, statistics and physics to analyze various natural phenomena. As an example, in statistical physics, process of polymerization [1] [2] , diffusion [3] of microparticles etc. are some classic phenomena, which have drawn much attention of the researcher in last few decades. The basic mechanism of such phenomena is explained by random walk [4] in various forms. Different kinds of random walks are studied on the lattice in different dimensions by computer simulation. A few of them may be mentioned here. The absorbing phase transition in a conserved lattice gas with random neighbour particle hopping is studied [5] . Quenched averages for self avoiding walks on random lattices [6] , asymptotic shape of the region visited by an Eulerian walker [7] , linear and branched avalanches are studied in self avoiding random walks [8] . Effect of quenching is studied in quantum random walk [9] . The drift and the trapping in biased diffusion on disordered lattices are also studied [10] .

Recently, some more interesting results on random walk are reported. The average number of distinct sites is visited by a random walker on the random graph [11] . Statistics of first passage time of the Browian motion conditioned by maximum value of the area [12] is studied recently. It may be mentioned here that the first passage time in complex scale invariant media was studied very recently [13] . The theory of mean first passage time for jump processes is developed [14] and verified by applying in Levy flights and fractional Brownian motion. The statistics of the gap and time interval between the highest positions of a Markovian one dimensional random walker [15] , the universal statistics of longest lasting records random walks and Levy flights are also studied [16] recently.

In real life, the random walk problem has been generalized in continuum. The exact solution of a Brownian inchworm model and self-propulsion was also studied [17] . Theory of continuum random walks and application in chemotaxis was developed [18] . Random walks in continuum were also studied for diffusion and reaction in catalyst [19] .

The Pearson walk [20] is a variant of random walk which shows many interesting results. This is defined as the walker that may choose any direction randomly, instead of taking specified direction in lattices. This Pearson random walk was studied [21] [22] with shrinking step size. Very recently, the Pearson walk [20] is studied with uniformly distributed random size of flight [23] . The statistics of a tired Pearson walker was also studied recently [24] to analyze the exit probability and first passage time [25] .

In the literature of mathematics [26] [27] , the lazy random walk is defined as the walker having 50% chance to move from any site and studied extensively on the lattice. The lazy random walk is not merely a pedagogical concept. It is already used to study the superpixel segmentation [28] . What will happen if a Pearson walker becomes lazy where it’s moves are probabilistic? In this article, the motion of a lazy Pearson walker is studied by computer simulation and the numerical results are reported. In the next section (Section 2), the model of lazy Pearson walker is described and the numerical results are given. The paper ends with a summary in Section 3.

2. Model and Results

The lazy random walk [26] [27] is usually described on the lattice where the walker has 50% chance to move from any given site. In this paper, the lazy Pearson random walk is described with various values of probability (p) of jump from the present position, instead of as defined on the lattice. In two dimension, a lazy Pearson walker starts its journey from the origin and jumps (unit distance) with probability p in any direction () chosen randomly (unformly distributed) between 0 and. In two dimensions, the rule of the jump of the lazy Pearson walker may be expressed by following Markovian evolution:

The exit probability () of a lazy walker is defined as the probability of exit (first time) of a walker from a circular/spherical (in 2D/3D respectively) zone specified by its radius, in a given time of observation. This probability is calculated here over number of different random samples.

Figure 1(a) shows such a plot of exit probability () as a function of radius () of exit zone for different values of probability (p) of jump of a lazy Pearson walker in two dimensions. For a given value of p, the exit probability () decreases as the radius () of exit zone increases, in a given time of observation (here). As the probability of jump (p) decreases, the exit probability () falls in a faster rate as increases. A careful inspection shows that for a fixed value of p, the is almost constant upto a certain value of and then decreases monotonically. Further, it may be noted that for a given value of, the exit probability decreases as p decreases. These observation promted to assume a scaling like, where, are some numbers and F is a function. The curves represented by the different symbols (different values of p) in Figure 1(a) falls in a single curve (shown in Figure 1(b)) if one choose, and. It may be mentioned here that the statistics is based on number of different random samples in two dimen- sions.

Figure 1. The exit probability () versus exit radius () (a) and its scaling (b). Different symbol correspond to different values of jump probability (p) in two dimensions. p = 0.2 (+), p = 0.4 (・), p = 0.6 (#) and p = 0.8 ($). Here, and.

The time required by a lazy walker to exit first from the specified zone, is called first passage time (). The probability distribution of the first passage time is studied for various values of probability (p) of jump of a lazy walker. Figure 2(a) shows the probability distribution of first passage time for different values of p. It is an unimodal function. Here, it may be noted that as p increases, the mode of the distribution shifts towards the lower values of and the distribution gets sharper and sharper. Here also, one may think of a scaling be- haviour of as:. Using and the data for various values of p collapse supporting the proposed scaling behavior. This is shown in Figure 2(b). It may be mentioned here that this scaling behaviour is independent of the choice of.

Lazy Pearson walk in three dimensions is also studied. Here, the dynamical equations (or the algorithm of movement) may be expressed as:

Here, is chosen randomly (uniformly distributed) between 0 and. is chosen randomly (uniformly distributed) between 0 and. In this case, the exit probability () is studied as a function of the radius () of the spherical zone for different values of probability (p) of jump of a lazy walker. In three dimensions, the time of observation is and the statistics is based on number of different random samples. This is shown in Figure 3(a). The behavious are quite similar to that observed in two dimensions (shown in Figure 1(a)). Here also, one may think of a scaling behaviour like:. By choosing and a fair data collapse is obtained which supports the assumed scaling behaviour. This is shown in Figure 3(b).

The probability distribution of first passage time () of a lazy Pearson walker is also studied in three dimensions for different values of probability (p) of jump and shown in Figure 4(a). The variations are quite similar to that observed in two dimensional lazy walker. A scaling like, , is proposed here. Choosing and, this scaling behaviour of the probability distribution of first passage time was established numerically by the method of data collapse. This is shown in Figure 4(b). Here also, it is observed that this scaling behaviour is independent of the choice of.

3. Summary

In this paper, the motion of a lazy Pearson walker is studied with different probability (p) of jump in two and three dimensions, by computer simulation. The exit probability and the probability distribution of first passage time are studied. The probability of exit () from a zone of radius, is studied as a function of with

Figure 2. The distribution (a) of first passage time (t_{1}) and its scaling (b). Different symbol correspond to different values of jump probability (p) in two dimensions. p = 0.3 (+), p = 0.5 (・), p = 0.7 (#) and p = 0.9 ($). Here, , and.

Figure 3. The exit probability () versus exit radius () (a) and its scaling (b). Different symbol correspond to different values of jump probability (p) in three dimensions. p = 0.2 (+), p = 0.4 (・), p = 0.6 (#) and p = 0.8 ($). Here, and.

Figure 4. The distribution (a) of first passage time () and its scaling (b). Different symbol correspond to different values of jump probability (p) in three dimensions. p = 0.2 (+), p = 0.4 (・), p = 0.6 (#) and p = 0.8 ($). Here, , and.

different values of jump probability p. Here, p can take any value between 0 and 1, unlike the case of conventional lazy walker. For a given value of p, the exit probability was found to fall as grows. The exit probability is found to scale as, which is obtained by method of data collapse.

The first passage time () i.e., the time required for first exit from a zone is studied. The probability distribution of first passage time was studied for different values of jump probability (p). The probability distribution of first passage time, is a nonmonotonic unimodal function. The mode serves the role of the scale of time of exit from the zone of radius. This time scale decreases as the probability p (of jump) increase, which is quite natural. The probability distribution of first passage time was found to scale as. Where, F and G are two scaling functions and, , and are some exponents. In both the dimensions, it is found that, , , and. Interestingly, it is observed that this scaling behaviour (and the exponents also) is independent of the choice of.

Acknowledgements

The library facility provided by Calcutta University is gratefully acknowledged.

References

[1] Bhattacherjee, S.M., Giacometti, A. and Maritan, A. (1995) Flory Theory for Polymers. Journal of Physics: Condensed Matter, 25, 503101
See also Barat, K. and Chakrabarti, B.K. (1995) Physics Reports, 258, 377.

[2] Hsu, H.-P. and Grassberger, P. (2011) A Review of MC Simulation of Polymers with PERM. Journal of Statistical Physics, 144, 597.

http://dx.doi.org/10.1007/s10955-011-0268-x

[3] Bhattacharjee, J.K. (1996) Critical Diffusivity in Restricted Geometry: Decoupled Mode Approximation. Physical Review Letters, 77, 1524.

http://dx.doi.org/10.1103/PhysRevLett.77.1524

[4] Tejedor, V. (2012) Random Walks and First Passage Properties: Trajectrory Analysis and Search Optimization. Ph.D thesis, Universite Pierre and Marie Curie, France and Technische Universitat, Munchen.

[5] Lubeck, S. and Hucht, F. (2001) Absorbing Phase Transition in a Conserved Lattice Gas with Random Neighbour Particle Hopping. Journal of Physics A: Mathematical and Theoretical, 34, L577.

http://dx.doi.org/10.1088/0305-4470/34/42/103

[6] Sumedha and Dhar, D. (2006) Journal of Statistical Physics, 115, 55.

[7] Kapri, R. and Dhar, D. (2009) Asymptotic Shape of the Region Visited by an Eulerian Walker. Physical Review E, 80, 1051118.

http://dx.doi.org/10.1103/PhysRevE.80.051118

[8] Manna, S.S. and Stella, A.L. (2002) Self-Organized Random Walks and Stochastic Sandpile: From Linear to Branched Avalanches. Physica A: Statistical Mechanics and Its Applications, 316, 135-143.

http://dx.doi.org/10.1016/S0378-4371(02)01497-8

[9] Goswami, S. and Sen, P. (2012) Quantum Random Walk: Effect of Quenching. Physical Review A, 86, 022314.

http://dx.doi.org/10.1103/PhysRevA.86.022314

[10] Dhar, D. and Stauffer, D. (1998) Drift and Trapping in Biased Diffusion on Disordered Lattices. International Journal of Modern Physics C, 9, 349.

http://dx.doi.org/10.1142/S0129183198000273

[11] De Bacco, C., Majumdar, S.N. and Sollich, P. (2015) Journal of Physics A: Mathematical and Theoretical, 48, 205004.

http://dx.doi.org/10.1088/1751-8113/48/20/205004

[12] Kearney, M.J. and Majumdar, S.N. (2014) The Average Number of Distinct Sites Visited by A Random Walker on Random Graphs. Journal of Statistical Physics, 47, 465001.

[13] Condamin, S., Benichou, O., Tejedor, V., Voituriez, R. and Klafter, J. (2007) First-Passage Times in Complex Scale-Invariant Media. Nature, 450, 77-80.

http://dx.doi.org/10.1038/nature06201

[14] Tejedor, V., Benichou, O., Metzler, R. and Voituriez, R. (2011) Residual Mean First-Passage Time for Jump Processes: Theory and Applications to Lévy Flights and Fractional Brownian Motion. Journal of Physics A: Mathematical and Theoretical, 44, 255003.

http://dx.doi.org/10.1088/1751-8113/44/25/255003

[15] Majumdar, S.N., Mounaix, P. and Schehr, G. (2014) On the Gap and Time Interval between the First Two Maxima of Long Random Walks. Journal of Statistical Mechanics, 2014, P09013.

[16] Godreche, C., Majumdar, S.N. and Schehr, G. (2014) Universal Statistics of Longest Lasting Records of Random Walks and Lévy Flights. Journal of Physics A: Mathematical and Theoretical, 47, Article ID: 255001.

http://dx.doi.org/10.1088/1751-8113/47/25/255001

[17] Baule, A., Vijay Kumar, K. and Ramaswamy, S. (2008) Exact Solution of a Brownian Inchworm Model for Self-Propulsion. Journal of Statistical Mechanics, Article ID: P11008.

http://dx.doi.org/10.1088/1742-5468/2008/11/p11008

[18] Schnitzer, M.J. (1993) Theory of Continuum Random Walks and Application to Chemotaxis. Physical Review E, 48, 2553-2568.

http://dx.doi.org/10.1103/PhysRevE.48.2553

[19] Drewry, H.P.G. and Seaton, N.A. (1995) Continuum Random Walk Simulations of Diffusion and Reaction in Catalyst Particles. AIChE Journal, 41, 880-893.

http://dx.doi.org/10.1002/aic.690410415

[20] Pearson, K. (1905) The Problem of the Random Walk. Nature, 72 294.

http://dx.doi.org/10.1038/072294b0

[21] Krapivsky, P.L. and Redner, S. (2004) Random Walk with Shrinking Steps. American Journal of Physics, 72, 591-598.

http://dx.doi.org/10.1119/1.1632487

[22] Sherino, C.A. and Redner, S. (2010) The Pearson Walk with Shrinking Steps in Two Dimensions. Journal of Statistical Mechanics, Article ID: P01006.

http://dx.doi.org/10.1088/1742-5468/2010/01/P01006

[23] Acharyya, A.B. (2015) arXiv:1506.0269v2[cond-mat, stat-mech]

[24] Acharyya, M. (2015) Model and Statistical Analysis of a Tired Random Walk in Continuum. Journal of Modern Physics, 6, 2021-2034.

http://dx.doi.org/10.4236/jmp.2015.614208

[25] Redner, S. (2001) A Guide to First-Passage Processes. Cambridge University Press, Cambridge.

[26] Leonard, C.A. (2014) Survey of the Schrodinger Problem and Some of Its Connection with Optimal Transport. Discrete and Continuous Dynamical Systems—Series A, 34, 1533-1574.

http://dx.doi.org/10.3934/dcds.2014.34.1533
Leonard, C. (2013) Lazy Random Walks and Optimal Transport on Graphs. arXiv:1308.0226 [Math.MG]

[27] Kelner, J. (2009) MIT Lecture Notes on Topics in Theoretical Computer Science: An Algorithmist’s Toolkit. (MIT Course Number-18.409)

http://ocw.mit.edu

[28] Shen, J., Du, Y., Wang, W. and Li, X. (2014) Lazy Random Walks for Superpixel Segmentation. IEEE Transactions on Image Processing, 23, 1451-1462.

http://dx.doi.org/10.1109/TIP.2014.2302892