Spectral analysis of finite Markov chains with spherical symmetries. (English) Zbl 1128.60006
The authors develop a Fourier analysis associated with the action of a finite group \(G\) on a finite set \(X\), whose restriction to each orbit on \(X\) gives rise to a Gelfand pair. In this setting, they analyze \(G\)-invariant operators on the space \(L(X)\) of complex-valued functions on \(X\). A general method is given to reduce the computation of the spectrum of such an operator to the computation of the spectra of matrices of smaller dimension, which are obtained by restricting the operator to each isotypic component of the decomposition of \(L(X)\) into \(G\)-irreducible representations.
This analysis is used to determine the spectra of some random walks on graphs (the \(q\)-ary tree, truncated cube, and a deformation of the Ehrenfest model). For a combination of the Ehrenfest model and the Bernoulli-Laplace model, called the second order Ehrenfest diffusion model, the authors give upper and lower estimates for the rate of convergence of the random walk to the stationary distribution.
This analysis is used to determine the spectra of some random walks on graphs (the \(q\)-ary tree, truncated cube, and a deformation of the Ehrenfest model). For a combination of the Ehrenfest model and the Bernoulli-Laplace model, called the second order Ehrenfest diffusion model, the authors give upper and lower estimates for the rate of convergence of the random walk to the stationary distribution.
Reviewer: Anatoly N. Kochubei (Kyïv)
MSC:
| 60B15 | Probability measures on groups or semigroups, Fourier transforms, factorization |
| 05E25 | Group actions on posets, etc. (MSC2000) |
| 20C99 | Representation theory of groups |
| 43A85 | Harmonic analysis on homogeneous spaces |
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
Keywords:
Markov chain; Ehrenfest diffusion model; Bernoulli-Laplace model; Gelfand pair; irreducible representationReferences:
| [1] | Aldous, D.; Fill, J. M., Reversible Markov chains and random walks on graphs (2003), forthcoming book |
| [2] | Bailey, R. A.; Praeger, Ch. E.; Rowley, C. A.; Speed, T. P., Generalized wreath product of permutation groups, Proc. London Math. Soc. (3) (1), 47, 69-82 (1983) · Zbl 0496.20018 |
| [3] | Boyd, S.; Diaconis, P.; Parrilo, P.; Xiao, L., Symmetry analysis of reversible Markov chains, Internet Math., 2, 1, 31-71 (2005) · Zbl 1087.60057 |
| [4] | T. Ceccherini-Silberstein, F. Scarabotti, F. Tolli, Finite Gelfand pairs and their applications to probability and statistics, J. Math. Sci. (New York), in press; T. Ceccherini-Silberstein, F. Scarabotti, F. Tolli, Finite Gelfand pairs and their applications to probability and statistics, J. Math. Sci. (New York), in press · Zbl 1173.43001 |
| [5] | Ceccherini-Silberstein, T.; Scarabotti, F.; Tolli, F., Trees, wreath products and finite Gelfand pairs, Adv. Math., 206, 503-537 (2006) · Zbl 1106.43006 |
| [6] | Chung, F. R.K.; Graham, R. L., Stratified random walks on the \(n\)-cube, Random Structures Algorithms, 11, 3, 199-222 (1997) · Zbl 0886.60068 |
| [7] | Diaconis, P., Group Representations in Probability and Statistics, IMS Lecture Notes Monogr. Ser., vol. 11 (1988), Inst. Math. Statist.: Inst. Math. Statist. Hayward, CA · Zbl 0695.60012 |
| [8] | Diaconis, P., The cut-off phenomenon in finite Markov chains, Proc. Natl. Acad. Sci. USA, 93, 1659-1664 (1996) · Zbl 0849.60070 |
| [9] | Diaconis, P.; Rockmore, D., Efficient computation of isotypic projections for the symmetric group, (Groups and Computation. Groups and Computation, New Brunswick, NJ, 1991. Groups and Computation. Groups and Computation, New Brunswick, NJ, 1991, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11 (1993), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 87-104 · Zbl 0826.20019 |
| [10] | Diaconis, P.; Shahshahani, M., Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Geb., 57, 159-179 (1981) · Zbl 0485.60006 |
| [11] | Diaconis, P.; Shahshahani, M., Time to reach stationarity in the Bernoulli-Laplace diffusion model, SIAM J. Math. Anal., 18, 208-218 (1987) · Zbl 0617.60009 |
| [12] | Dunkl, C. F., A Krawtchouk polynomial addition theorem and wreath products of symmetric groups, Indiana Univ. Math. J., 25, 335-358 (1976) · Zbl 0326.33008 |
| [13] | Dunkl, C. F., An addition theorem for Hahn polynomials: The spherical functions, SIAM J. Math. Anal., 9, 627-637 (1978) · Zbl 0386.33008 |
| [14] | Dunkl, C. F., Spherical functions on compact groups and applications to special functions, Symposia Mathematica, 22, 145-161 (1979) · Zbl 0403.43008 |
| [15] | Dunkl, C. F., Orthogonal functions on some permutation groups, (Proc. Sympos. Pure Math., vol. 34 (1979), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 129-147 · Zbl 0404.20005 |
| [16] | Figà-Talamanca, A., An application of Gelfand pairs to a problem of diffusion in compact ultrametric spaces, (Topics in Probability and Lie Groups: Boundary Theory. Topics in Probability and Lie Groups: Boundary Theory, CRM Proc. Lecture Notes, vol. 28 (2001), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 51-67 · Zbl 0985.60004 |
| [17] | Garcia, N.; Palacios, J. L., On mixing times for stratified walks on the \(d\)-cube, Random Structures Algorithms, 20, 4, 540-552 (2002) · Zbl 1014.60069 |
| [18] | Hildebrand, F. B., Finite-Difference Equations and Simulations (1968), Prentice Hall: Prentice Hall International, Englewood Cliffs, NJ · Zbl 0157.22702 |
| [19] | Letac, G., Les fonctions sphériques d’un couple de Gelfand symétrique et les chaînes de Markov, Adv. in Appl. Probab., 14, 2, 272-294 (1982) · Zbl 0482.60011 |
| [20] | Kac, M., Random walk and the theory of Brownian motion, Amer. Math. Monthly, 54, 369-391 (1947) · Zbl 0031.22604 |
| [21] | Karlin, S.; Taylor, H. M., A Second Course in Stochastic Processes (1975), Academic Press · Zbl 0315.60016 |
| [22] | Kemeny, J. G.; Snell, J. L., Finite Markov Chains (1960), Van Nostrand: Van Nostrand Princeton, NJ · Zbl 0112.09802 |
| [23] | Morris, B.; Sinclair, A., Random walks on truncated cubes and sampling 0-1 knapsack solutions, SIAM J. Comput., 34, 1, 195-226 (2004), (electronic) · Zbl 1101.68044 |
| [24] | Nikiforov, A. F.; Suslov, S. K.; Uvarov, V. B., Classical Orthogonal Polynomials of a Discrete Variable, Springer Ser. Comput. Phys. (1991), Springer-Verlag: Springer-Verlag Berlin · Zbl 0743.33001 |
| [25] | Puschel, M.; Moura, J. M.F., The algebraic approach to the discrete cosine and sine transforms and their fast algorithms, SIAM J. Comput., 32, 5, 1280-1316 (2003) · Zbl 1046.42003 |
| [26] | Sagan, B. E., The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Functions, Grad. Texts in Math., vol. 203 (2001), Springer-Verlag: Springer-Verlag New York · Zbl 0964.05070 |
| [27] | Scarabotti, F., Fourier analysis of a class of finite radon transforms, SIAM J. Discrete Math., 16, 4, 545-554 (2003) · Zbl 1041.44002 |
| [28] | Scarabotti, F., The discrete sine transform and the spectrum of the finite \(q\)-ary tree, SIAM J. Discrete Math., 19, 4, 1004-1010 (2005), (electronic) · Zbl 1103.05053 |
| [29] | Stanley, R. P., Differential posets, J. Amer. Math. Soc., 1, 4, 919-961 (1988) · Zbl 0658.05006 |
| [30] | Stanton, D., Orthogonal polynomials and Chevalley groups, (Special Functions: Group Theoretical Aspects and Applications. Special Functions: Group Theoretical Aspects and Applications, Math. Appl. (1984), Reidel: Reidel Dordrecht), 87-128 · Zbl 0578.20041 |
| [31] | Stanton, D., Harmonics on posets, J. Combin. Theory Ser. A, 40, 1, 136-149 (1985) · Zbl 0573.06001 |
| [32] | Strang, G., The discrete cosine transform, SIAM Rev., 41, 1, 135-147 (1999) · Zbl 0939.42021 |
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.
