What is Random walk: Definition and 96 Discussions

In mathematics, a random walk is a mathematical object, known as a stochastic or random process, that describes a path that consists of a succession of random steps on some mathematical space such as the integers.
An elementary example of a random walk is the random walk on the integer number line,


{\displaystyle \mathbb {Z} }
, which starts at 0 and at each step moves +1 or −1 with equal probability. Other examples include the path traced by a molecule as it travels in a liquid or a gas (see Brownian motion), the search path of a foraging animal, the price of a fluctuating stock and the financial status of a gambler: all can be approximated by random walk models, even though they may not be truly random in reality.
As illustrated by those examples, random walks have applications to engineering and many scientific fields including ecology, psychology, computer science, physics, chemistry, biology, economics, and sociology. Random walks explain the observed behaviors of many processes in these fields, and thus serve as a fundamental model for the recorded stochastic activity. As a more mathematical application, the value of π can be approximated by the use of a random walk in an agent-based modeling environment. The term random walk was first introduced by Karl Pearson in 1905.Various types of random walks are of interest, which can differ in several ways. The term itself most often refers to a special category of Markov chains, but many time-dependent processes are referred to as random walks, with a modifier indicating their specific properties. Random walks (Markov or not) can also take place on a variety of spaces: commonly studied ones include graphs, others on the integers or the real line, in the plane or higher-dimensional vector spaces, on curved surfaces or higher-dimensional Riemannian manifolds, and also on groups finite, finitely generated or Lie. The time parameter can also be manipulated. In the simplest context the walk is in discrete time, that is a sequence of random variables (Xt) = (X1, X2, ...) indexed by the natural numbers. However, it is also possible to define random walks which take their steps at random times, and in that case, the position Xt has to be defined for all times t ∈ [0,+∞). Specific cases or limits of random walks include the Lévy flight and diffusion models such as Brownian motion.
Random walks are a fundamental topic in discussions of Markov processes. Their mathematical study has been extensive. Several properties, including dispersal distributions, first-passage or hitting times, encounter rates, recurrence or transience, have been introduced to quantify their behavior.

View More On Wikipedia.org
  1. J

    I Can anyone explain me this quantum entanglement experiment

    Experiment I have encountered this experiment that generates quantum entanglement but I cannot understand its mechanism. Is the conservation of energy and momentum involved? Is interference part of this experiment? What are the phenomena that contribute together to generate entanglement in this...
  2. K

    I Exploring Continuous Approximation of 1D Random Walk Steps (Reif, pg 14)

    Reif,pg 14. ##n_1## is the number of steps to the right in a 1D random walk. ##N## are the total number of steps "When ##N## is large, the binomial probability distribution ##W\left(n_{1}\right)## ##W\left(n_{1}\right)=\frac{N !}{n_{1} !\left(N-n_{1}\right) !} p^{n_{1}} q^{N-n_{1}}## tends to...
  3. G

    Fortran Solving Magnetic Field Using Floating Random Walk

    Hi everyone, I am working on the Fortran code to solve a magnetic field by using "Floating Random Walk" method. I use a square domain for this case and show in the attachment. The external magnetic strength comes from left to right boundary. Both top and bottom are assuming as insulation...
  4. J

    I How to choose a random walk to best model diffusion?

    To choose random walk on a graph, it seems natural to to assume that the walker jumps using each possible edge with the same probability (1/degree) - such GRW (generic random walk) maximizes entropy locally (for each step). Discretizing continuous space and taking infinitesimal limit we get...
  5. dRic2

    Calculating the Probability of Two Men Meeting Again with a Double Random Walk

    I set up the problem in the following way: considering the relative motion, at each step there is a probability that - they take a step in the opposite direction going away from each other, so the distance increases and the associated probability is 1/4 - they take a step in the opposite...
  6. H

    Unit of Velocity from a Random Walk measured by an accelerometer

    Hi, I am working on a kalman filter where my measurement equation involves "-g + v" , where g is in m/s^2 and v is velocity random walk given in m/s/sqrt(hr). Feels like a stupid question, but how can I transform the unit of velocity random walk so I can do the calculation correctly?
  7. C

    Courses Graduate level Mathematics courses of interest for Biological Physics

    I am an incoming graduate student in Theoretical Physics at Universiteit Utrecht, and I struggle to make a choice for one of my mathematical electives. I hope someone can help me out. My main interests lie in the fields of Statistical Physics, phase transitions and collective and critical...
  8. arcTomato

    Solution to Random Walk Problem | n_i

    I don't have any idea to prove this 😢 ##n_i##is number of trial, right?
  9. arcTomato

    Please teach me how to prove this random walk problem....

    I think I can prove equal length version problem, But I am confusing in this case,,, Please help me!
  10. iVenky

    I White noise & 1/f noise after a system h(t)

    Hi, I am trying to solve this math equation on finding the variance of a noise after passing through a system whose impulse response is h(t) X is the input noise of the system and Y is the output noise after system h(t) if let's say variance of noise Y is σy2=∫∫Rxx(u,v)h(u)h(v)dudv where...
  11. Kitty123

    Map a one dimensional random walk to a two-state paramagnet

    1. The question asks us to map a one dimensional random walk to a two state paramagnet and then write an expression for the number of journeys of N steps which end up at r=Rdelta. Then we are asked to find an expression for the probability that N steps will end up at r. 2...
  12. G

    A How can I simulate 2D correlated data with continuous-valued variables?

    Not sure this is the right area to post this. Let's say I have particles on a lattice, and they all have some property (ie, color) that is correlated at some known correlation length. I want to simulate this! In 1D I could do something like have color be a random walk in the given dimension...
  13. G

    Random walk - why is the STD equal sqrt(n)

    typical random walk : one step forward or backward with equal probability and independence of each step , what is the expectation and Variance . so i define indicator variable xi ={1 or -1 with equal probabilty . E(xi) = 0 Var(xi) = 1 now define Sn as the sum of i=1,...,n each step is...
  14. B

    I Probability of a random walk reaching the point X; maximal c

    https://ibb.co/guBuPd As the title indicates, I want to calculate the Probability of a stock price reaching a determined point, by considering the system as a random walk model, and after that, to compute the so called "maximal curves". I found the whole explanation in this article...
  15. J

    Random Walk of KMnO4 in Water: Why Do We Observe Non-Probabilistic Behavior?

    I had a question regarding the random walk problem in statistical mechanics. If I drop, say, one molecule of KMnO4 in a beaker of water, what we generally observe (spread of KMnO4 to the ends of the beaker) is different from what we should get from probabilistic assumptions. I must be going...
  16. S

    What Is the Probability Distribution Function After Four Steps in a Random Walk?

    Homework Statement Suppose a particle moves along the x-axis beginning at 0. It moves one integer step to the left or right with equal probability. What is the pdf of its position after four steps? 2. Homework Equations Binomial distribution ##P(k) = {{n}\choose{k}} p^k (1-p)^{n-k}## The...
  17. grquanti

    I Jump probability of a random walker

    Hello everybody. I have a Markowian homogeneous random walk. Given the transition matrix of the chain, I know that ##P[ X(t) = i | X(t-1) = j ] ≡ P_{j→i}=T_{ij}## where ##T## is the transition matrix and ##X(t)## is the position of the walker...
  18. P

    Show Random Walk Respects Identity

    Hi, I have the following homework question: Let Xt be the continuous-time simple random walk on a circle as in Example 2, Section 7.2. Show that there exists a c,β > 0, independent of N such that for all initial probability distributions ν and all t > 0 ∥νe^tA−π∥_TV ≤ ce^(−βt/N2) Here's what...
  19. F

    Expected number of steps random walk

    Homework Statement Let w(1) = event of a random walk with right drift (p > q, p+q = 1) starting at 1 returns to 0 Let p(w(1)) = probability of w(1) Let S=min{t>=0:wt(1)=0} be the minimum number of steps t a walk starting from 1 hits 0. What is E[S|w(1)]? Homework Equations I know E[S|w(0)] = 0...
  20. J

    I Average number of times a random walk passes a point

    Hi, I'm trying to work out how many time a particle going on a random walk starting at the origin would pass a particular point or points for a given total number of steps. I've simulated the problem and get approximately the same answer every time, however I'm struggling to know where to even...
  21. Themis

    Exploring Random Walk in 1-D: Solving Compilation Issues

    Hi I created a program to run a random walk in 1d with only input the number of steps and the number of walks. I used a random number generator to produce only two outcomes (step forward and step back) and in the main function I want to calculate the average of x (over a number of walks) and...
  22. S

    Can someone retrace this easy random walk calculation?

    Okay, it's not easy for me but probably for you ;) Hello first of all! I have two questions: 1. Why is there a minus before the expression in the red circle? 2. How did the x((n-1)-1) in the last line come to be?More precise: I understand the first parts. It's the random walk and x signifies...
  23. S

    Understanding the Role of Degrees of Freedom in 1-Dimensional Random Walks

    Hello! I'm struggling with a probably easy physics question concerning random walks. Here I have the slide regarding this: Delta is the distance that a particle moves. Can someone explain where the n-1 initially comes from? Does it have to do wtih the concept of the degrees of freedom? Than...
  24. Buzz Bloom

    Random Walk Question re Inflation

    I have been puzzled about the possible interaction mechanisms among the various particles during inflation that would have performed the mixing of mass-energy (ME) required for the uniformity of the CBR. Here is my understanding about what must happen to acheve the necessary mixing of ME during...
  25. jk22

    Difference in random walk description

    We studied random walk starting from a probability conservation : p(x,t)=p(x+dx,t+dt)+p(x-dx,t+dt) Which means the particle can go left or right by dx in time dt. The solution of the differential equation starting from a delta is a gaussian, which means the particle could go apparently at...
  26. H

    Will a random walk hit every point infinitely often?

    Well, not quite a random walk. The steps aren't necessarily ±1, but they have mean 0 and will take values >ε with positive probability. It seems intuitive that such a process will be unbounded and will cross this bound infinitely many times (in 1D). Does anyone know of a result that says this?
  27. M

    Random Walk in Arbitrary Dimension

    Homework Statement Find the probability distribution for a random walk on a d-dimensional lattice.[/B]Homework Equations [/B]The Attempt at a Solution I'm trying to find the probability distribution for a random walk on a lattice with lattice constant a in arbitrary dimension d. The rules...
  28. Rapier

    Transforming Random Walk Steps into Directional Movement

    Homework Statement The problem is relatively simple. I am modelling mass diffusion, and that's going well, but she has offered extra credit if we can write the problem without using any if-statements. In a clutch my plan is fall back on a Case Statement and pull barracks-lawyer and insist...
  29. K

    Why "rate random walk" exists on gyroscpe ?

    hi I read an article about stochastic error modeling, and I didn't understand this extract about error sources : how can the "rate random walk" be present, while the gyroscope directly angular rate ? the article's title is : "Stochastic Modeling of MEMS Inertial Sensors " by Petko Petkov and...
  30. C

    How Does a Drunk's Random Walk Between Lamp Posts Model a Binomial Distribution?

    Homework Statement A drunk lurches from one lamp post to the next on his way home. At each lamp post he pauses and is equally likely move towards or away from home. Suppose the posts are separated by a distance ##a## and find the mean and standard deviation of his displacement ##d## from the...
  31. B

    Fokker Planck Solution Biased Random Walk

    This is part b) of an assignment question. In part a) we were asked to derive the Fokker Planck relation for the biased random walk. The answer is: dP/dt = -vdP/dx + D d2P/dx2 Where the first term is the drift term due to the biased motion and the second term is the diffusion term. Then...
  32. A

    Random Walk in confined region and loop configurations

    Suppose I take a random walk on a 2 dimensional square lattice, but this lattice plane has a finite size, e.g. Dx*Dy. I can not cross the boundary, my step length is the lattice cell size, I either go straight or make turns with right angle. Is there any work on this type of random walk? If...
  33. J

    Maximal Entropy Random Walk - quantum corrections to stochastic models

    Imagine there is a complex system and we are interested in its basic statistical properties, like the stationary probability distribution. For example for a single electron wandering in defected lattice of semiconductor. Physics offers two basic ways of answering such question: - from one side...
  34. L

    Feynman Lectures: The Random Walk Explained

    There is a chapter in Feynman Lectures on Physics called The Random Walk(41-4). I understand everything till the paragraph right after equation 41.18. I have no idea what he is trying to say. There is an equation 41.19, which is diff. eq. for object that is forced and is in a environment that...
  35. M

    Is a Binomial Distribution the Correct Approach for a Random Walk Problem?

    Random walk or binomial?? Statement: A drunk person wonders aimlessly along a path by going forward 1 step and backward 1 step with equal probabilities of ½. After 10 steps, a) what is the probability that he has moved 2 steps forward? b) What is the probability that he will make it to his...
  36. M

    Probability of Random Walk and Reaching a Destination with Equal Probabilities

    Statement: A drunk person wonders aimlessly along a path by going forward 1 step and backward 1 step with equal probabilities of ½. After 10 steps, a) what is the probability that he has moved 2 steps forward? b) What is the probability that he will make it to his front door within 20 steps...
  37. S

    Random Walk on a Circle: How Does the Last Unique Position Visited Distribute?

    Homework Statement Consider a random walk on a circle of N points, labeled {0,1,...,N-1}. Let the initial state be X = 0 and define T to be the first time all points have been visited at least once. Show that the distribution of X[T] (i.e. last unique position visited) is uniform over...
  38. P

    Time before visit number one, random walk

    Hi there! I'm working on a random walk-problem my professor gave me. Given a MC with the following properties: P0,0 = 1 - p P0,1 = p Pi,i-1 = 1 - pi Pi,i+1 = pi i \in[1,∞) Xn: state at step number n The chain is irreducible and ergodic and 0 < p ≤ 1 introducing N: N = {min n...
  39. S

    Are Random Walks with Different Step Sizes Identical in Brownian Motion Limit?

    Consider a random walk (in any dimension) with N steps and a step size of 1. Take a real number \alpha > 0 and consider another random walk which takes \alpha^2 N steps but wil step size \frac{1}{\alpha}. I immediately noticed that the mean deviation after the full walk in both cases is the...
  40. W

    Limiting Distribution of Scaled Random Walk

    Hi all, in text the formula for scaled random walk is: W^(n) (t) = (1/√n) M_nt in the example it says that: set t=0.25, n=100 and consider the set of possible values of W^(100) (0.25) = 1/10 M_25. This random variable is generated by 25 coin tosses, and since the unscaled random walk...
  41. R

    Asymmetric Random Walk on the Set of Integers

    Homework Statement Give the value of u_0.Homework Equations Let p>q>0 with p+q = 1 and a = q/p < 1. Let X_n denote the random walk with transitions X_{n+1} = CASE 1: X_n + 1 with probability p and CASE 2: X_n - 1 with probability q. For i ≥ 0, we set u_i = P(X_n = 0 for some n ≥ 0|X_0 = i)...
  42. C

    Understanding the Random Walk: Exploring the Average Distance After N Steps

    I read about the random walk the other day. The simplest 2D form, where you start at zero and move up or down one unit at random, both are as likely. To get an the average distance from zero after N steps, the following argument was used: The distance after one step is 1. If after some steps...
  43. F

    Statistical Mechanics - Random Walk

    I'm reading through Reif's "Statistical Mechanics" to prepare for the upcoming semester. Basically, a drunk guy takes N total steps, n1 to the right and n2 to the left. The probability that the current step will be to the right is "p," while the probability that the current step will be to the...
  44. H

    Can someone help me find the moment generating function of a random walk?

    Hi, can someone who is familiar with the analysis of random walks (statistical mechanics, condensed matter physics etc.) help me on solving a particular problem? We define the following random walk, the random variable w(t) is evolved as w(t+1)=w(t), with probability of...
  45. S

    Maximum final component of a simple symmetric multidimensional random walk?

    I am developing a simple probabilistic model of my own mistakes in (1) solving math problems and (2) implementing algorithms on a computer. I have reduced the problem to one which seems simple enough, but which I have been unable to solve, due to my mathematical inexperience. I figured I would...
  46. P

    MHB Modified Random Walk: Expected Duration and Recurrence Equation Analysis

    (1)Consider the expected duration of the modified random walk. Show that conditioning on the first step produces a recurrence equation of the following form. Ea = ˜pEa+1 + ˜qEa−1 + ˜c. (2)Clearly identify the values of ˜p, ˜q and ˜c in terms of p, q and r...
  47. M

    Estimating Drift & Variance for Random Walk With Drift: Help Needed

    Hello there, I am wondering if somebody could help in an issue far from my expertise. I have some data which is reasonable to conjecture could be modeled with a random walk with drift. I am struggling though to understand how to estimate from the empriic data the most likely drift and...
  48. P

    How to simulate a random walk on a sphere

    Dear All, I am simulating a random walk on a sphere with unit radius. I want to move from current location p_t to the new location p_{t+1} along the big circle, whose arc has an angle omega relative to p_t's latitude. I tried using the law of cosine. But at the poles, the law of cosine...
  49. J

    Why 8 probabilities in 3D random walk?

    Why are there 8 possible moves in 3D random walk? With R being the distance from the origin, how is its relationship with the number of steps and dimensionality? Thx!
  50. S

    What is the Probability of Reaching Node D Before Node E Starting from Node G?

    http://img844.imageshack.us/img844/8333/1111jx.png Homework Statement With which probability, starting in g, node d gets hit before node e?Homework Equations The Attempt at a Solution I think the probability of hitting each node starting in g is the following: p(g) = 1 p(c) = 1/2 p(a) =...