Day 1: Random Walk

Day 1: Random Walk#

In mathematics, a random walk, sometimes known as a drunkard’s walk, is a stochastic process that describes a path that consists of a succession of random steps on some mathematical space. Random walks have applications to engineering and many scientific fields including ecology, psychology, computer science, physics, chemistry, biology, economics, and sociology.

  • 100 Paths from a Simple Random Walk

Definition#

Let {Z_i,i≥1} be a sequence of real-valued independent an identically distributed (i.i.d.) random variables defined on a probability space (Ω,F,P). Then, the stochastic process {X_n,n≥0}, defined as X_0=0, and

Xn=∑i=1nZi,∀n≥1,

is called random walk, or more precisely one-dimensional random walked based on {Z_i,i≥1}. An elementary example of a random walk is the random walk on the integer number line, which starts at 0 and at each step moves +1 or −1 with equal probability.

  • Simple Random Walk

  • Simple Random Walk with linear interpolation between steps

🔔 Random Facts 🔔#

  • The term random walk was introduced by English biostatistician and mathematician Karl Pearson in a letter to the journal Nature in 1905. In this letter, Pearson described a problem that involved a person taking a series of steps in random directions and inquired about the resulting distance from the starting point after a large number of steps:

  • A Random Walk in one or two dimensions is recurrent, meaning that a walker starting at a point will, with probability 1, eventually return to that point. However, in three or more dimensions, the Random Walk becomes transient, where there is a non-zero probability that the walker will never return to the starting point. This fascinating result is known as Pólya’s Recurrence Theorem.

  • The trajectory of a Random Walk in two or three dimensions forms a fractal-like structure. For example, in two dimensions, the fractal dimension of the Random Walk’s path is 2, meaning it densely fills the plane.

  • In epidemiology, Random Walks can model the spread of infectious diseases by simulating how individuals move and interact in a population. This helps in predicting infection patterns and formulating strategies to mitigate outbreaks.

  • Brownian motion can be seen as the limit of a Random Walk when the step size and time intervals between steps become infinitely small. This connection is formalised in the result known as Donsker’s invariance principle or the Functional Central Limit Theorem.

P.s. If you are curious about probability distributions visit the Advent Calendar 2023 ✨

Contents