Infinite Expectations in Random Walks: A Mathematical Exploration

Random walks are fascinating mathematical models used in various fields, from finance to computer science, and they are particularly interesting when it comes to determining the expected time to reach certain points. This article explores the concept of infinite expectations in random walks through a detailed examination of a specific problem and provides insights into the theoretical underpinnings of such phenomena.

Introduction to the Random Walk Problem

Consider a scenario where a fly starts at the origin (00) on an infinite lattice. It can move one unit in any of the four cardinal directions (N, E, S, W) with equal probability. Now, let's delve into the question of how long it would take, on average, to reach a specific point (ab).

Mathematically, we denote:

fab ∞, unless ab 00

In other words, unless the fly is at (00), the expected number of steps to reach (ab) is infinite, denoted as ∞. However, it is important to note that the fly will definitely eventually land on (ab), although the expected time to do so can be infinite.

Proving Infinite Expectations in 1-Dimensional Random Walks

To gain a deeper understanding, let's first consider the 1-dimensional case. Imagine a random walk on Z, the set of all integers, starting at 0. We ask how long it takes on average to reach 1.

Suppose the expected number of steps to get from 0 to 1 is T. By the symmetry of the problem, the expected time to go from 1 to 2 is also T. Therefore, the total expected time to go from 0 to 2 is 2T.

Now, consider what happens after one step from 1. With probability 1/2, you could be at 2, and with probability 1/2, you could be back at 0. If you were at 2, you took one step to get there. If you were back at 0, you took one step and needed an additional 2T steps to get to 2.

This gives us the equation:

T (1/2) * 1 (1/2) * (1 2T)

Simplifying this, we get:

T 1/2 1/2 T

T 1 T

Which leads to a contradiction indicating that T cannot be a finite value. This demonstrates that in a 1-dimensional simple random walk, the expected time to reach any fixed point infinity.

Finite Expectations for Special Cases

It's worth noting that in some special cases, the expected time to reach a certain point is finite. For example, if m0 and n0, the expected number of steps to hit either m or n is just mn. This result can be used as a stepping stone to understand more complex scenarios.

2-Dimensional Random Walks and Horizontal/Vertical Lines

Moving to the 2-dimensional case, we consider the problem of how long it will take to hit a specific vertical line, say xa. In this scenario, the vertical moves become irrelevant, and the horizontal moves form a 'lazy' random walk where you move right with probability 1/4, left with probability 1/4, and stay put with probability 1/2 (equivalent to moving up or down).

Using a similar argument as in the 1-dimensional case, it's clear that the expected time to reach xa is infinite, as reaching xa would still leave an infinite number of steps to reach any specific point on that line.

The same argument applies to horizontal lines other than y0, and between these two dimensions, we cover the entire plane lattice. This means that the expected time to reach any specific lattice point in two dimensions is also infinite.

Conclusion

Random walks, particularly in higher dimensions, can lead to fascinating and sometimes counterintuitive results, such as infinite expected times to reach certain points. This article has explored the theoretical foundations and provided a step-by-step explanation of how we arrive at these conclusions.

The concepts discussed here highlight the complexity and beauty of probabilistic models in mathematics and their applications in various fields. Understanding these principles can help in both theoretical analysis and practical problem-solving.