Geodesic
The range of a simple random walk on \(\mathbb{Z}\): an elementary combinatorial approach
Bernhard A. Moser1
1Software Competence Center Hagenberg
The electronic journal of combinatorics, Tome 21 (2014) no. 4

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl
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 $\mathbf 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 $\mathbf{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.
DOI : 10.37236/4106
Classification : 05C81, 60G50
Mots-clés : random walk, discrepancy norm, lattice path enumeration

Bernhard A. Moser  1

1 Software Competence Center Hagenberg 
Bernhard A. Moser. The range of a simple random walk on \(\mathbb{Z}\): an elementary combinatorial approach. The electronic journal of combinatorics, Tome 21 (2014) no. 4. doi: 10.37236/4106
@article{10_37236_4106,
     author = {Bernhard A. Moser},
     title = {The range of a simple random walk on {\(\mathbb{Z}\):} an elementary combinatorial approach},
     journal = {The electronic journal of combinatorics},
     year = {2014},
     volume = {21},
     number = {4},
     doi = {10.37236/4106},
     zbl = {1298.05290},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4106/}
}
TY  - JOUR
AU  - Bernhard A. Moser
TI  - The range of a simple random walk on \(\mathbb{Z}\): an elementary combinatorial approach
JO  - The electronic journal of combinatorics
PY  - 2014
VL  - 21
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4106/
DO  - 10.37236/4106
ID  - 10_37236_4106
ER  - 
%0 Journal Article
%A Bernhard A. Moser
%T The range of a simple random walk on \(\mathbb{Z}\): an elementary combinatorial approach
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/4106/
%R 10.37236/4106
%F 10_37236_4106

Cité par Sources :