×

Random walks on finite nilpotent groups driven by long-jump measures. (English) Zbl 1486.60006

Summary: We consider a variant of simple random walk on a finite group. At each step, we choose an element, \(s\), from a set of generators (“directions”) uniformly, and an integer, \(j\), from a power law distribution (“speed”) associated with the chosen direction, and move from the current position, \(g\), to \(g{s^j}\). We show that if the finite group is nilpotent, the time it takes this walk to reach its uniform equilibrium is of the same order of magnitude as the diameter of a suitable pseudo-metric on the group, which is attached to the generators and speeds. Additionally, we give sharp bounds on the \({\ell^2}\)-distance between the distribution of the position of the walker and the stationary distribution, and compute the relevant diameter for some examples.

MSC:

60B15 Probability measures on groups or semigroups, Fourier transforms, factorization
60G50 Sums of independent random variables; random walks
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Zhen-Qing Chen, Takashi Kumagai, Laurent Saloff-Coste, Jian Wang, and Tianyi Zheng, Long range random walks and associated geometries on groups of polynomial growth, arXiv preprint 1807.00354 (2018). · Zbl 1507.60056
[2] Thierry Coulhon and Alexander Grigor’yan, On-diagonal lower bounds for heat kernels and Markov chains, Duke Math. J. 89 (1997), no. 1, 133-199. · Zbl 0920.58064
[3] Persi Diaconis and Laurent Saloff-Coste, Moderate growth and random walk on finite groups, Geom. Funct. Anal. 4 (1994), no. 1, 1-36. · Zbl 0795.60005
[4] Persi Diaconis and Laurent Saloff-Coste, Nash inequalities for finite Markov chains, J. Theoret. Probab. 9 (1996), no. 2, 459-510. · Zbl 0870.60064
[5] William Feller, An introduction to probability theory and its applications. Vol. II, Second edition, John Wiley & Sons, Inc., New York-London-Sydney, 1971. · Zbl 0219.60003
[6] Yves Guivarc’h, Croissance polynomiale et périodes des fonctions harmoniques, Bull. Soc. Math. France 101 (1973), 333-379. · Zbl 0294.43003
[7] Ravi Kannan, László Lovász, and Miklós Simonovits, Random walks and an \[{O^{\ast }}({n^5})\]volume algorithm for convex bodies, Random Structures Algorithms 11 (1997), no. 1, 1-50. · Zbl 0895.60075
[8] Donald E. Knuth, The art of computer programming. Vol. 2, Addison-Wesley, Reading, MA, 1998, Seminumerical algorithms, Third edition. · Zbl 0895.65001
[9] Ch. Pittet and L. Saloff-Coste, On the stability of the behavior of random walks on groups, J. Geom. Anal. 10 (2000), no. 4, 713-737. · Zbl 0985.60043
[10] Laurent Saloff-Coste, Lectures on finite Markov chains, Lecture Notes in Math., vol. 1665, pp. 301-413, Springer, Berlin, 1997. · Zbl 0885.60061
[11] Laurent Saloff-Coste, Random walks on finite groups, Probability on discrete structures, Encyclopaedia Math. Sci., vol. 110, Springer, Berlin, 2004, pp. 263-346. · Zbl 1049.60006
[12] Laurent Saloff-Coste and Tianyi Zheng, Random walks on nilpotent groups driven by measures supported on powers of generators, Groups Geom. Dyn. 9 (2015), no. 4, 1047-1129. · Zbl 1364.20018
[13] Laurent Saloff-Coste and Tianyi Zheng, Random walks under slowly varying moment conditions on groups of polynomial volume growth, Ann. Fac. Sci. Toulouse Math. (6) 24 (2015), no. 4, 837-855. · Zbl 1333.60090
[14] Laurent Saloff-Coste and Tianyi Zheng, Random walks and isoperimetric profiles under moment conditions, Ann. Probab. 44 (2016), no. 6, 4133-4183. · Zbl 1378.60019
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.