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

MaRDI QIDQ463050zbMATH OpenFDO

Authors Bernhard A. Moser

Publication date 23 October 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p10

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

discrepancy normlattice path enumerationrandom walk

Mathematics Subject Classification ID

Random walks on graphs (05C81) Sums of independent random variables; random walks (60G50)

Review text

Summary: Two different elementary approaches for deriving an explicit formula for the distribution of the range of a simple random walk on \(\mathbb{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 \(\mathbb{Z}\) can be turned into a known path-enumeration problem on a bounded lattice. The solution is provided by means of the adjacency matrix \(\mathbb Q_d\) of the walk on a bounded lattice \((0,1,\ldots,d)\). The second approach is algebraic in nature, and starts with the adjacency matrix \(\mathbb 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.

Recommendations

• The range of a simple random walk on ℤ
• Moments of an amplitude process in a random walk and approximations : computations and applications
• On the distribution of the range of an asymmetric random walk
• The transient behaviour of the simple random walk in the plane
• The fundamental matrix for a certain random walk

Cites work

• Enumeration of simple random walks and tridiagonal matrices
• Geometric characterization of Weyl's discrepancy norm in terms of its \(n\)-dimensional unit balls
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 2157777 (Why is no real title available?)
• scientific article; zbMATH DE number 3194856 (Why is no real title available?)
• scientific article; zbMATH DE number 3068096 (Why is no real title available?)
• Lattice path enumeration and Toeplitz matrices
• On Stability of Distance Measures for Event Sequences Induced by Level-Crossing Sampling
• On the range of random walk
• The Asymptotic Distribution of the Range of Sums of Independent Random Variables
• The range of a simple random walk on ℤ

Cited in

(1)

• scientific article; zbMATH DE number 878361 (Why is no real title available?)

This page was built for publication: The range of a simple random walk on \(\mathbb{Z}\): an elementary combinatorial approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q463050)