Question

Suppose you are doing a random walk (see previous problem) on the blocks of a city street. At each "step" you choose to walk one block (at random) either forward, backward, left or right. In \(n\) steps, how far do you expect to be from your starting point? Write a program to help answer this question.

Short answer

After approximately \( n \) steps, you expect to be about \( \sqrt{n} \) blocks from your starting point.

Step-by-step solution

Understand the Problem

The problem asks us to determine the expected distance from the starting point after taking a specified number of random steps. Each step could be in one of four possible directions: forward, backward, left, or right.

Formulating the Random Walk

In a 2D random walk, each step can be represented by a vector. For instance, forward could be (0,1), backward (0,-1), left (-1,0), and right (1,0). Analyze the potential net movement after multiple steps which reduces to summing up these random vectors.

Calculate Expected Distance

The expected distance after n steps can be calculated by using the formula for expected distance of a random walk: \( E[D] = \sqrt{n} \). This formula comes from the variance in 2-dimensional random walks where variance is proportional to the number of steps.

Write the Program

To simulate the random walk, write a program that uses the basic structure of a loop iterating n times, randomly choosing from the four possible directions, updating the position, and finally calculating the distance from the origin. Use Python or similar to implement this.

Running the Simulation

Run the program for different values of n to verify the formula \( E[D] = \sqrt{n} \). The results of the simulation should confirm the theoretical expectation, showing random fluctuations but converging to the expected outcome with larger n.

Key concepts

2D Random Walk

A 2D random walk is a fascinating concept where you move in a two-dimensional grid randomly. Imagine starting at a point in the city, and for each step, you decide randomly whether to move:

• Forward
• Backward
• Left
• Right

This kind of movement can be visualized as random wandering around a grid. Each direction corresponds to a vector direction, such as forward being (0,1) and left being (-1, 0).
These random movements create what we call a random walk, which is a mathematical path that does not have a fixed direction. It is driven purely by the randomness of each step.
Random walks are important because they can model numerous systems in science and nature, such as predicting stock prices or even the movement of molecules.

Expected Distance Calculation

Calculating the expected distance in a 2D random walk involves understanding how far you might end up from the starting point after a number of random steps. The magic formula used for this is:\[ E[D] = \sqrt{n} \]where \(E[D]\) represents the expected distance and \(n\) is the number of steps.
This formula emerges from the principles of probability and randomness. It suggests a square root relationship between the number of steps and the expected distance from the start.
This estimation portrays that even after many steps, the expected distance isn't linearly proportional to the number of steps due to fluctuating path movements. Understanding this non-linear relationship is crucial for comprehending how randomness influences position over time.

Python Programming

To simulate a 2D random walk, Python is an excellent tool thanks to its straightforward syntax and powerful libraries.
To get started, you would write a simple program that executes as follows:

• Initialize a starting point at the origin, often represented as (0,0).
• For each of \(n\) steps, randomly choose a direction from the four available.
• Update the current position based on the chosen direction.
• After \(n\) steps, calculate the distance from the starting point.

In Python, you can use the `random.choice` method to select a direction and `math.sqrt` to calculate the distance.
Additionally, libraries such as NumPy or Matplotlib can be beneficial for handling complex calculations and visualizations of the paths and distances during multiple simulations.

Variance in Random Walks

Variance in random walks is a crucial concept that shows how much the individual outcomes of a random walk can differ. For a 2D random walk, the variance in positions after \(n\) steps is directly proportional to \(n\). This underlines the randomness and spread of possible positions as the number of steps increases.
Visualizing variance can help. Imagine repeatedly performing the 2D random walk for the same \(n\) steps. Despite starting from the same point, each simulation can end up at wildly different endpoints. This is due to the random choices at each step. Over many simulations, you may notice a wide scatter of endpoints, illustrating the variance.
Understanding variance in random walks is pivotal in fields like finance and ecology, where predictions and models must account for such dispersions from the average expected outcomes.