Stochastic Processes
Random Walks
Mathematical Models
Probability Theory
Markov Chains

Random walk around a central location in a limited area?

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

A random walk is a mathematical formalization of a path that consists of a succession of random steps. This concept finds extensive application in various fields such as physics, economics, biology, and computer science. This article will explore the concept of a random "walk" around a central location within a confined or limited area.

Overview of Random Walks

A random walk is a sequence of random steps on some mathematical space. The simplest random walk is a one-dimensional walk where at each step, the walker can go either forward or backward with equal probability. In a two-dimensional space, each step can lead the walker to either of the four cardinal directions: north, south, east, or west.

Mathematical Representation

The random walk can be mathematically represented as follows:

For a one-dimensional random walk:

X_n=X_n1+Z_nX\_{n} = X\_{n-1} + Z\_{n}

Where: • XnX_{n} is the position at step nn. • ZnZ_{n} is a random variable that can take $+1$ or $ -1 $ with probability 12\frac{1}{2}.

For a two-dimensional walk, it can be represented as:

(X_n,Y_n)=(X_n1+Z_nx,Y_n1+Z_ny)(X\_{n}, Y\_{n}) = (X\_{n-1} + Z\_{n}^{x}, Y\_{n-1} + Z\_{n}^{y})

Where: • $Z_\{n\}^\{x\}$ and $Z_\{n\}^\{y\}$ are independent random variables that represent the step in the X and Y direction, respectively.

Random Walk within a Confined Area

When considering a random walk in a confined area centered around a specific location, the complexity increases. The most common constraints involve ensuring that the walk stays within the boundary, which can be circular, square, or any arbitrary shape.

Circular Boundary

For circular boundaries: • Ensure that the distance from the central point does not exceed the radius of the circle. • Use polar coordinates to simplify calculations, especially when dealing with angles.

Square Boundary

In a square or rectangular boundary: • Reflect the particle back into the area if it tries to step outside. • If the walker reaches a boundary edge, one can either: • Reflect the walk. • Wrap around to the opposite edge.

Numerical Example

Consider a square area centered at the origin with boundaries at 10-10 and 1010 on both X and Y axes. Assume a two-dimensional random walk starting from the origin.

• If the next step is outside [10,10][-10, 10] for either X or Y, the step is adjusted or reversed to stay within the limits.

Key Iterations Over 10 Steps:

StepX PositionY PositionAction
1-11Accepted
200Accepted
3-110Reflected
4-91Accepted
5-82Accepted
6103Reflected
783Accepted
894Accepted
9105Reflected
1096Accepted

Applications and Utility

Random walks around a central location are used to model numerous phenomena: • Ecological Studies: Tracking animal movement in a confined habitat. • Physics: Modeling diffusion processes constrained within materials. • Computer Science: Generating realistic pathfinding in video games or simulations.

Monte Carlo Simulations

Random walks are pivotal in Monte Carlo simulations for estimating integrals and solving systems with a large number of degrees of freedom, such as in statistical mechanics.

Conclusion

Random walks around a central location in a limited area not only present interesting mathematical challenges but also have a rich array of applications across multiple fields. By adjusting for constraints such as boundaries, the utility of random walks can be extended to model real-world phenomena more accurately and inform decision-making processes in diverse domains.


Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

All Rights Reserved.