×

Harmonic analysis of finite lamplighter random walks. (English) Zbl 1203.43009

Summary: Recently, several papers have been devoted to the analysis of lamplighter random walks, in particular, in the case where the underlying graph is the infinite path \( \mathbb{Z} \). In the present paper, we develop a spectral analysis for lamplighter random walks on finite graphs. In the general case, we use the \(C _{2}\)-symmetry to reduce the spectral computations to a series of eigenvalue problems on the underlying graph. If the graph has a transitive isometry group \(G\), we also describe the spectral analysis in terms of the representation theory of the wreath product \(C_{2} \wr G\). We apply our theory to the lamplighter random walks on the complete graph and on the discrete circle. These examples have already been studied by Häggström and Jonasson by probabilistic methods.

MSC:

43A85 Harmonic analysis on homogeneous spaces
05C05 Trees
20C15 Ordinary representations and characters
20E22 Extensions, wreath products, and other compositions of groups
60G50 Sums of independent random variables; random walks
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] L. Bartholdi and W. Woess, Spectral computations on lamplighter groups and Diestel–Leader graphs. J. Fourier Anal. Appl. 11 (2005), No. 2, 175–202. · Zbl 1082.05058 · doi:10.1007/s00041-005-3079-0
[2] N. Biggs, Algebraic graph theory. Cambridge Univ. Press, Cambridge (1993). · Zbl 0805.68094
[3] S. Boyd, P. Diaconis, P. Parrillo, and L. Xiao, Symmetry analysis of reversible Markov chains. Internet Math. 2 (2005), No. 1, 31–71. · Zbl 1087.60057 · doi:10.1080/15427951.2005.10129100
[4] T. Ceccherini-Silberstein, F. Scarabotti, and F. Tolli, Trees, wreath products, and finite Gelfand pairs. Adv. Math. 206 (2006), 503–537. · Zbl 1106.43006 · doi:10.1016/j.aim.2005.10.002
[5] _____, Finite Gelfand pairs and their applications to probability and statistics. J. Math. Sci. (New York) 141 (2007), No. 2, 1182–1229. · Zbl 1173.43001 · doi:10.1007/s10958-007-0041-5
[6] _____, Harmonic analysis on finite groups: Representation theory, Gelfand pairs, and diffusion processes. Book in preparation.
[7] P. Diaconis, Group representations in probability and statistics. Inst. Math. Statist. Lect. Notes Monogr. Ser. 11, Inst. Math. Statist., Hayward, CA (1988). · Zbl 0695.60012
[8] W. Dicks and T. Schick, The spectral measure of certain elements of the complex group ring of a wreath product. Geom. Dedic. 93 (2002), 121–137. · Zbl 1021.47014 · doi:10.1023/A:1020381532489
[9] W. Feller, An introduction to probability theory and its applications. Vol. I. John Wiley and Sons, New York–London–Sydney (1971). · Zbl 0219.60003
[10] L. Geissinger and D. Kinch, Representations of the hyperoctahedral group. J. Algebra 53 (1978), 1–20. · Zbl 0379.20007 · doi:10.1016/0021-8693(78)90200-4
[11] R. I. Grigorchuk, and A. Zuk, The lamplighter group as a group generated by a 2-state automaton and its spectrum. Geom. Dedic. 87 (2001), 209–244. · Zbl 0990.60049 · doi:10.1023/A:1012061801279
[12] O. Häggström and J. Jonasson, Rates of convergence for lamplighter processes. Stochastic Process. Appl. 67 (1997), No. 2, 227–249. · Zbl 0889.60074 · doi:10.1016/S0304-4149(97)00007-0
[13] L. He, X. Liu, and G. Strang, Trees with Cantor eigenvalue distribution. Stud. Appl. Math. 110 (2003), No. 2, 123–138. · Zbl 1141.05325 · doi:10.1111/1467-9590.00233
[14] B. Huppert, Character theory of finite groups. De Gruyter Expos. Math. 25, Walter de Gruyter (1998). · Zbl 0932.20007
[15] G. D. James and A. Kerber, The representation theory of the symmetric group. Encycl. Math. Appl. 16, Addison-Wesley, Reading, MA (1981). · Zbl 0491.20010
[16] A. Kerber, Applied finite group actions. Algorithms and Combinatorics 19, Springer-Verlag, Berlin (1999). · Zbl 0951.05001
[17] S. Lang, Algebra. Grad. Texts Math. 211, Springer-Verlag, New York (2002).
[18] J. H. van Lint and R. M. Wilson, A course in combinatorics. Cambridge Univ. Press, Cambridge (2001). · Zbl 0980.05001
[19] Y. Peres and D. Revelle, Mixing times for random walks on finite lamplighter groups. Electron. J. Probab. 9 (2004), No. 26, 825–845. · Zbl 1064.60095
[20] M. Puschel and J. M. F. Moura, The algebraic approach to the discrete cosine and sine transforms and their fast algorithms. SIAM J. Comput. 32 (2003), No. 5, 1280–1316. · Zbl 1046.42003 · doi:10.1137/S009753970139272X
[21] B. E. Sagan, The symmetric group. Wadsworth & Brooks, Pacific Grove, CA (1991). · Zbl 0823.05061
[22] F. Scarabotti, The discrete sine transform and the spectrum of the finite q-ary tree. SIAM J. Discrete Math. 19 (2006), No. 4, 1004–1010. · Zbl 1103.05053 · doi:10.1137/S0895480104445344
[23] F. Scarabotti and F. Tolli, Spectral analysis of finite Markov chains with spherical simmetries. Adv. Appl. Math. 38 (2007), No. 4, 445–481. · Zbl 1128.60006 · doi:10.1016/j.aam.2006.01.007
[24] _____, Radon transforms and lamplighter random walks. Preprint. · Zbl 1227.05229
[25] C. H. Schoolfield, A signed generalization of the Bernoulli–Laplace diffusion model. J. Theor. Probab. 15 (2002), No. 1, 97–127. · Zbl 0989.60100 · doi:10.1023/A:1013841306577
[26] J. P. Serre, Linear representations of finite groups. Grad. Texts Math. 42, Springer-Verlag, New York–Heidelberg (1977). · Zbl 0355.20006
[27] B. Simon, Representations of finite and compact groups. Amer. Math. Soc. (1996). · Zbl 0840.22001
[28] S. Sternberg, Group theory and physics. Cambridge Univ. Press, Cambridge (1994). · Zbl 0816.53002
[29] G. Strang, The discrete cosine transform. SIAM Rev. 41 (1999), No. 1, 135–147. · Zbl 0939.42021 · doi:10.1137/S0036144598336745
[30] W. Woess, A note on the norms of transition operators on lamplighter graphs and groups. Int. J. Algebra Comput. 15 (2005), Nos. 5–6, 1261–1272. · Zbl 1084.05034 · doi:10.1142/S0218196705002591
[31] _____, Lamplighters, Diestel–Leader graphs, random walks, and harmonic functions. Combin. Probab. Comput. 14 (2005), No. 3, 415–433. · Zbl 1066.05075 · doi:10.1017/S0963548304006443
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.