Random Walks and Related Topics

代数的トポロジーを勉強していても, random walk という言葉を目にすることは, ほとんどない。 私が random walk について最初に知ったのは, hyperplane arrangement との関係において, である。

Bidigare と Hanlon と Rockmore の [BHR99] や K.S. Brown の [Bro00] で, hyperplane arrangement 上の random walk が調べられている。

• hyperplane arrangement 上の random walk

より一般的なものは, 格子などの graph 上の random walk だろう。

• graph 上の random walk

その高次元化として, simplicial complex 上の random walk も考えられている。 Parzanchevski と Rosenthal の [PR] など。

他には, 次のような構造上の random walk が考えられている。

• 群の上の random walk [DS81]
• finite quantum group 上の random walk [FG06]

また, graph 上の random walk の quantum 版として quantum walk というものもある。

• quantum walk

Survey として [Amb], [Aha+], [Kem], [Kenb], [Kena], [Kon08] などがあることから分かるように, 盛んに調べられているようである。

Konno と Sato の [KS] では, zeta function との関係が述べられている。

References

[Aha+]

Dorit Aharonov, Andris Ambainis, Julia Kempe, and Umesh Vazirani. Quantum Walks On Graphs. arXiv: quant-ph/0012090.

[Amb]

Andris Ambainis. Quantum walks and their algorithmic applications. arXiv: quant-ph/0403120.

[BHR99]

Pat Bidigare, Phil Hanlon, and Dan Rockmore. “A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements”. In: Duke Math. J. 99.1 (1999), pp. 135–174. url: http://dx.doi.org/10.1215/S0012-7094-99-09906-4.

[Bro00]

Kenneth S. Brown. “Semigroups, rings, and Markov chains”. In: J. Theoret. Probab. 13.3 (2000), pp. 871–938. arXiv: math/0006145. url: http://dx.doi.org/10.1023/A:1007822931408.

[DS81]

Persi Diaconis and Mehrdad Shahshahani. “Generating a random permutation with random transpositions”. In: Z. Wahrsch. Verw. Gebiete 57.2 (1981), pp. 159–179. url: https://doi.org/10.1007/BF00535487.

[FG06]

Uwe Franz and Rolf Gohm. “Random walks on finite quantum groups”. In: Quantum independent increment processes. II. Vol. 1866. Lecture Notes in Math. Springer, Berlin, 2006, pp. 1–32. url: https://doi.org/10.1007/11376637_1.

[Kem]

Julia Kempe. Quantum random walks - an introductory overview. arXiv: quant-ph/0303081.

[Kena]

Viv Kendon. Decoherence in quantum walks - a review. arXiv: quant- ph/0606016.

[Kenb]

Viv Kendon. Quantum walks on general graphs. arXiv: quant-ph/ 0306140.

[Kon08]

Norio Konno. “Quantum walks”. In: Quantum potential theory. Vol. 1954. Lecture Notes in Math. Springer, Berlin, 2008, pp. 309–452. url: https://doi.org/10.1007/978-3-540-69365-9_7.

[KS]

Norio Konno and Iwao Sato. On the relation between quantum walks and zeta functions. arXiv: 1103.0079.

[PR]

Ori Parzanchevski and Ron Rosenthal. Simplicial complexes: spectrum, homology and random walks. arXiv: 1211.6775.