The range of a simple random walk on \(\mathbb{Z}\): an elementary combinatorial approach (Q463050): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / 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. | |||
Property / 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C81 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 60G50 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6360685 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
random walk | |||
Property / zbMATH Keywords: random walk / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
discrepancy norm | |||
Property / zbMATH Keywords: discrepancy norm / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
lattice path enumeration | |||
Property / zbMATH Keywords: lattice path enumeration / rank | |||
Normal rank |
Revision as of 14:17, 30 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The range of a simple random walk on \(\mathbb{Z}\): an elementary combinatorial approach |
scientific article |
Statements
The range of a simple random walk on \(\mathbb{Z}\): an elementary combinatorial approach (English)
0 references
23 October 2014
0 references
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.
0 references
random walk
0 references
discrepancy norm
0 references
lattice path enumeration
0 references