The range of a simple random walk on Z: An elementary combinatorial approach

Autoren Bernhard Moser
Editoren
Titel The range of a simple random walk on Z: An elementary combinatorial approach
Typ Artikel
Journal The Electronic Journal of Combinatorics
Nummer 4
Band 22
ISSN 1077-8926
Monat December
Jahr 2014
Seiten #P.10
SCCH ID# 1473
Abstract

Two different elementary approaches for deriving an explicit formula for the distribution of the range of a simple random walk on Z of length n are presented. Both of them rely on Hermann Weyl's discrepancy norm, which equals the maximal partial sum of the elements of a sequence. By this the original combinatorial problem on Z can be turned into a known path-enumeration problem on a bounded lattice. The solution is provided by means of the adjacency matrix Q d of the walk on a bounded lattice (0,1,…,d) . The second approach is algebraic in nature, and starts with the adjacency matrix Q d . The powers of the adjacency matrix are expanded in terms of products of non-commutative left and right shift matrices. The representation of such products by means of the discrepancy norm reveals the solution directly.