eduzhai > Physical Sciences > Materials Sciences >

A note on variable step random walk

  • sky
  • (0) Download
  • 20211030
  • Save American Journal of Materials Science 2015, 5(2): 53-56 DOI: 10.5923/j.materials.20150502.05 A Note on Random Walks with Varying Step Sizes Gopinath Subramanian School of Polymers and High Performance Materials, University of Southern Mississippi, Hattiesburg, USA Abstract An analytical approximation for the probability density function of a one-dimensional random walk with gradually varying step sizes is derived using the convolution theorem for Fourier transforms. The range of applicability of this expression is studied by numerical simulations for the particular case of strictly decreasing step sizes. Keywords Random walks, Polymers, Approximation 1. Introduction The random walk, a term coined by Pearson [1], finds utility in an incredible number of scientific and technological fields, ranging from polymer physics [2] and biology [3] to the “who-to-follow” algorithm used by the popular social networking website Twitter [4]. A one-dimensional random walk is a path traced by a walker that takes a succession of steps, with each step chosen with equal probability to be either to the left or to the right. The overwhelming majority of analyses assume, for simplicity, that the step length of a random walker remains constant throughout the duration of the random walk. However, this need not always be the case and studies of random walks with monotonically decreasing step size, referred to as Bernoulli convolutions, are available in the mathematics literature [5, 6, 7, 8, 9]. Random walks with monotonically increasing step size, referred to as greedy random walks, have also been studied [10]. In both these types of studies, the random walk is discretized into a sequence of steps and the step size is changed at every step. In the case of Bernoulli convolutions, the step size is a strictly decreasing function of step number, while in the case of greedy random walks, it is a strictly increasing function. In this note, I examine a slightly different type of random walk where the step size is held constant for a sufficiently large number of steps, , before it is changed. This problem lends itself to a simplified analysis, and yields a closed-form solution for the probability density function (PDF) of the end-to-end vector, and consequently, other quantities of interest such as the hydrodynamic radius. The analytical solution is compared with numerical simulations of random walks in order to assess the limits of its applicability. One potential application is in the field of * Corresponding author: (Gopinath Subramanian) Published online at Copyright © 2015 Scientific & Academic Publishing. All Rights Reserved gradient copolymers, where the polymer stiffness varies gradually along the backbone, such as the sinusoidal variation produced by Lefebvre et al. [11] Another application would be in diffusivity problems, where the diffusivity of a particle is a function of time, or if a particle were diffusing in a temperature gradient. 2. Formulation A one-dimensional random walk is first discretized into a sequence of blocks, where the block is made up of steps of size , and each individual step is either or . For simplicity, the step size of the first block is set to . Figure 1 shows, for the particular case of strictly decreasing step sizes, a plot of step size as a function of step number with two different block sizes, viz., (which is equivalent to changing step sizes at every step) and . Figure 1. A random walk is discretized into a sequence of blocks. Each block contains steps of equal length. The case where , shown with the solid red line, is equivalent to having the step length change at every step If we shift the origin so that it is at the position of the walker before it begins the block, and if the number of 54 Gopinath Subramanian: A Note on Random Walks with Varying Step Sizes steps of the block is sufficiently large, the PDF of the end-to-end distance of a one-dimensional random walker is given by a Gaussian with zero mean and variance as [12] (1) For a sequence of two blocks, the PDF of the end-to-end distance is given by the convolution of the Gaussians for each block as (2) It can be shown using the convolution theorem for Fourier transforms that the convolution of two normalized Gaussians, say and , is another normalized Gaussian. The resultant Gaussian also has the useful property that its mean and variance are respectively equal to the sum of the means and the sum of the variances of the individual Gaussians. In other words, (3) (4) This result can be extended to an arbitrary number of Gaussians. For the 1-D random walk under consideration, the PDF of the end-to-end distance after blocks is therefore a Gaussian with zero mean, and a variance equal to the sum of the individual variances, and is given by (5) For a continuously varying step length (such as might be encountered in diffusion problems), the replacement of the summation by an integral can be accomplished with relative ease, and will not be discussed here. If we set , and for all values of , equation 5 reduces to the standard Gaussian distribution for the end-to-end distance of a 1-D random walk given by 3. Comparison with Numerical Simulations of Strictly Decreasing Step Sizes For comparison with numerical simulations, the individual were restricted to be equal to a single value, , and PDFs were computed over random walks for a given set of parameters. The error was defined as the integral of the absolute difference between the analytical and numerical PDFs: (7) with (8) The prototypical 1-D random walk with strictly decreasing step sizes has an end-to-end distance given by: (9) where is a random variable that can take on values of or with equal probability. The PDF of is called an infinite Bernoulli convolution [6], which in the language of equation 5, is the PDF of the end-to-end distance of random walks with . The worst case scenario for using equation 5 is obtained for infinite Bernoulli convolutions in the limit as . Here, the random walk effectively terminates after the first step, and the PDF of approaches a function which is the mean of two delta functions centered at , given as: (10) where δ refers to the Dirac delta function. Denoting the pointwise error as (11) where and are as given in equations 5 and 10 respectively, the error can be computed as an integral over the real line as: (6) (12) This integral can be split into the sum of two limits: the first in the neighborhood of , and the second over the rest of the real line, which is written as: In the neighborhood of , does not affect the delta functions. Away from . Consequently, each of the limits evaluate to unity, yielding (13) , the delta functions do not affect (14) American Journal of Materials Science 2015, 5(2): 53-56 55 (a) (b) (c) (d) Figure 2. Comparison between numerical simulations (red points) and the approximation in equation 5 (green broken line) for infinite Bernoulli convolutions, for various values of . The normalized errors are indicated. Note that the ordinates are slightly different for each sub-figure. For , the approximation given by equation 5 is close to the results of the numerical simulations.which will be used to normalize any errors that are computed for comparing results of numerical simulations with equation 5 Figure 3. Normalized error as a function of the step length reduction factor for various values of block size . Low values of error are obtained for small and/or large Random walks with strictly decreasing step sizes were obtained by setting , as in the case of Bernoulli convolutions, and a natural end point for this type of random walk is when . Practically, this is achieved by setting a cutoff step size of , and terminating the random walk when the step size drops below this threshold. Decreasing the cutoff below this value by two orders of magnitude did not produce any changes in the errors. Figure 2 shows a plot of the actual distributions for infinite Bernoulli convolutions, along with the analytical approximations. Figure 2 (a) is the worst-case scenario with . For , the numerical distribution seems to have a self-similar structure, as shown in figure 2(b) and its inset. For and , shown in figure 2(c) and (e), the distributions have a simple form and was shown by Krapivsky and Redner [7] to be the result of a “fortuitous cancellation of errors.” For , the inverse of the golden ratio, the numerical simulations show the self-similar structure of the distribution, as previously reported [7], and referred to as the “golden walk.” While the approximation to the PDF given by equation 5 is 56 Gopinath Subramanian: A Note on Random Walks with Varying Step Sizes incapable of capturing the fine structure that the numerical [3] Howard C. Berg. “Random Walks in Biology.” Princeton simulations show, as increases, the structure disappears University Press, revised edition, September 1993. and the analytical approximation gets better because we start to approach the regime of gradually decreasing step sizes. For , the match between numerical simulations and [4] Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Zadeh. “WTF: The who to follow service at twitter.” In Proceedings of the 22Nd International the analytical approximation from equation 5 is reasonable, Conference on World Wide Web, WWW ’13, pages 505–514, and figure 2 should also give the reader a sense for whether a particular value of is acceptable for his/her purposes. Republic and Canton of Geneva, Switzerland, 2013. International World Wide Web Conferences Steering Committee. Figure 3 shows a plot of the normalized error, , [5] Richard Kershner and Aurel Wintner. “On symmetric as a function of for a few selected values of . For , there is a prominent kink at , and is the result of the Bernoulli convolutions.” American Journal of Mathematics, 57(3):541+, July 1935. numerical distribution crossing over from the self-similar [6] Paul Erdös. “On a family of symmetric Bernoulli structure seen in figure 2 (b) to the structure of figure 2 (d). convolutions.” American Journal of Mathematics, 61(4): As increases, the error progressively decreases, and the 974+, October 1939. analytical expression in equation 5 becomes applicable to a wider range of . [7] "P. L. Krapivsky and S. Redner. “Random walk with shrinking steps.” American Journal of Physics, 72(5): 591–598, May 2004. ACKNOWLEDGEMENTS Thanks to Ras Pandey and Bernd Schröder for useful discussions. Support for this work was provided by startup funds from the College of Science and Technology. [8] Tonguç Rador and Sencer Taneri. “Random walks with shrinking steps: First-passage characteristics.” Physical Review E, 73:036118+, March 2006. [9] C. A. Serino and S. Redner. “The Pearson walk with shrinking steps in two dimensions.” Journal of Statistical Mechanics: Theory and Experiment, 2010(01):P01006+, January 2010. REFERENCES [1] Karl Pearson. “The problem of the random walk.” Nature, 72:294+, 1905. [2] Werner Kuhn. “Über die gestalt fadenförmiger moleküle in lösungen.” Kolloidzeitschrift, 68:2, 1934. [10] E. Ben-Naim and S. Redner. “Winning quick and dirty: the greedy random walk.” Journal of Physics A: Mathematical and General, 37(47):11321+, November 2004. [11] Michelle D. Lefebvre, Monica Olvera de la Cruz, and Kenneth R. Shull. “Phase segregation in gradient copolymer melts.” Macromolecules, 37(3):1118–1123, 2004. [12] S. Chandrasekhar. “Stochastic problems in physics and astronomy.” Rev. Mod. Phys., 15:1–89, Jan 1943.

... pages left unread,continue reading

Document pages: 4 pages

Please select stars to rate!


0 comments Sign in to leave a comment.

    Data loading, please wait...