3 - Generating functions II: recurrence, sites visited, and the role of dimensionality

Summary

We've now had an introduction to the random walk. There has also been an introduction to the generating function and its utilization in the analysis of the process. Here we investigate some aspects of the random walk, both because they are interesting in their own right and because they further demonstrate the usefulness of the generating function as a theoretical technique in discussing this problem. In particular, we will apply the generating function method to study the problem of “recurrence” in the random walk. That is, we will address the question of whether the walker will ever return to its starting point, and, if so, with what probability.We will find that the spatial dimensions in which the walk takes place play a crucial role in determining this probability. Using an almost identical approach, the number of distinct points visited by the walker will also be determined.

We present the two studies below as a display of the power of the generating function technique in the study of the random walk process. For the skeptic, other examples will be provided in subsequent chapters.

Recurrence

We begin this chapter with a discussion of the question of recurrence of an unrestricted random walk. We will utilize the generating function, and an important statistical identity, to see how the dimensionality of the random walker's environment controls the probability of its revisiting the site from which it has set out. This study complements our earlier discussion and provides evidence for the power of the generating function approach.

A new generating function

A useful – but apparently little known – quantity enables one to obtain some key results with remarkably little effort.