mathematics//probability//stochastic process//random walk
A random walk is a stochastic process that adds a fresh independent step to its previous value at every instant, the running sum of white noise, and it is the model of any error that accumulates without being forgotten: the angle of an integrated gyroscope, the position of dead reckoning, a slowly wandering bias.
A random walk is a stochastic process that adds a fresh independent step to its previous value at every instant, the running sum of white noise, and it is the model of any error that accumulates without being forgotten: the angle of an integrated gyroscope, the position of dead reckoning, a slowly wandering bias.
xk+1=xk+wk,Var(xk)=k qx_{k+1}=x_k+w_k,\qquad \operatorname{Var}(x_k)=k\,qxk+1=xk+wk,Var(xk)=kq
With independent steps wkw_kwk of variance qqq, the variances add, so after kkk steps the variance is kqkqkq and the standard deviation kq\sqrt{kq}kq. The spread of possible positions opens like the square root of time: four times the time for twice the spread. No single walk shows it; a hundred walks started together fan out, and the fan has that shape. In continuous time the same object is the Wiener process, or Brownian motion.
Integrating a noisy signal turns its white noise into a random walk, and its bias into a straight line.
A drone integrating a gyroscope whose white noise is specified as an angle random walk of 0.5∘/h0.5^\circ/\sqrt{\mathrm h}0.5∘/h<path d="M95,702
c-2.7,0,-7.17,-2.7,-13.5,-8c-5.8,-5.3,-9.5,-10,-9.5,-14
c0,-2,0.3,-3.3,1,-4c1.3,-2.7,23.83,-20.7,67.5,-54
c44.2,-33.3,65.8,-50.3,66.5,-51c1.3,-1.3,3,-2,5,-2c4.7,0,8.7,3.3,12,10
s173,378,173,378c0.7,0,35.3,-71,104,-213c68.7,-142,137.5,-285,206.5,-429
c69,-144,104.5,-217.7,106.5,-221
l0 -0
c5.3,-9.3,12,-14,20,-14
H400000v40H845.2724
s-225.272,467,-225.272,467s-235,486,-235,486c-2.7,4.7,-9,7,-19,7
c-6,0,-10,-1,-12,-3s-194,-422,-194,-422s-65,47,-65,47z
M834 80h400000v40h-400000z"/> drifts by about 0.50.50.5° (one standard deviation) after an hour and 0.060.060.06° after a minute; an uncorrected bias of 0.10.10.1°/s adds 666° in that same minute. Over that minute the bias costs a hundred times more than the walk, which is why it is calibrated or estimated as a state (dead reckoning).
It has no steady state. Its mean stays put but its variance grows without bound, so it is not stationary: an autoregressive model xk=ϕ xk−1+wkx_k=\phi,x_{k-1}+w_kxk=ϕxk−1+wk with ϕ=1\phi=1ϕ=1 has its eigenvalue exactly on the unit circle (a unit root), and a series that drifts like this is differenced before it is modelled, the I of ARIMA.
Filters use it on purpose. A Kalman filter that models a slowly changing quantity as a random walk (a bias, a constant velocity perturbed by random accelerations) is saying that the quantity can drift anywhere, at a rate set by qqq, and its uncertainty grows accordingly between measurements (process noise).
A random walk on a graph, hopping between nodes with fixed probabilities, shares the name and is a different object, a Markov chain over a finite set of states.