Random walks on the BMW monoid: an algebraic approach. (English) Zbl 1427.60015
Summary: We consider Metropolis-based systematic scan algorithms for generating Birman-Murakami-Wenzl (BMW) monoid basis elements of the BMW algebra. As the BMW monoid consists of tangle diagrams, these scanning strategies can be rephrased as random walks on links and tangles. We also consider the Brauer algebra and use Metropolis-based scans to generate Brauer diagrams, giving rise to random walks on perfect matchings. Taking an algebraic perspective, we translate these walks into left multiplication operators in the BMW algebra and so give an algebraic interpretation of the Metropolis algorithm in this setting.
MSC:
| 60B99 | Probability theory on algebraic and topological structures |
| 05C81 | Random walks on graphs |
| 20P05 | Probabilistic methods in group theory |
Keywords:
metropolis algorithm; systematic scans; random walks; representation theory; semisimple algebrasReferences:
| [1] | Aldous, D., Fill, J.A.: Reversible markov chains and random walks on graphs. Unfinished monograph, recompiled 2014 (2002).http://www.stat.berkeley.edu/ aldous/RWG/book.html |
| [2] | Benkart, G., Ram, A., Shader, C.L.: Tensor product representations for orthosymplectic Lie superalgebras. J. Pure Appl. Algebra 130(1), 1-48 (1998) · Zbl 0932.17008 · doi:10.1016/S0022-4049(97)00084-4 |
| [3] | Bergeron, F., Favreau, L.: Fourier transform over semi-simple algebras and harmonic analysis for probabilistic algorithms. Discrete Math., 139(1-3):19-32. Formal power series and algebraic combinatorics (Montreal, PQ, 1992) (1995) · Zbl 0838.60005 |
| [4] | Brémaud, P.; Marsden, JE (ed.); Sirovich, L. (ed.); Golubitsky, M. (ed.); Jäger, W. (ed.), Markov chains, volume 31 of texts in applied mathematics (1999), New York · Zbl 0949.60009 · doi:10.1007/978-1-4757-3124-8 |
| [5] | Cai, Y.; Hou, Z. (ed.); Filar, JA (ed.); Chen, A. (ed.), How rates of convergence for Gibbs fields depend on the interaction and the kind of scanning used (2002), Dordrecht |
| [6] | Ceccherini-Silberstein, T., Scarabotti, F., Tolli, F.: Harmonic Analysis on Finite Groups, Volume 108 of Cambridge Studies in Advanced Mathematics. Representation Theory, Gelfand Pairs and Markov Chains. Cambridge University Press, Cambridge (2008) · Zbl 1149.43001 |
| [7] | Clausen, M.: Fast generalized Fourier transforms. Theoret. Comput. Sci. 67(1), 55-63 (1989) · Zbl 0677.65143 · doi:10.1016/0304-3975(89)90021-2 |
| [8] | Clausen, M., Baum, U.: Fast Fourier Transforms. Bibliographisches Institut, Mannheim (1993) · Zbl 0802.65141 |
| [9] | Diaconis, P.: Group representations in probability and statistics. Institute of Mathematical Statistics Lecture Notes-Monograph Series, 11. Institute of Mathematical Statistics., Hayward, CA (1988) · Zbl 0695.60012 |
| [10] | Diaconis, P., Ram, A.: Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques. Michigan Math. J. 48, 157-190 (2000) · Zbl 0998.60069 · doi:10.1307/mmj/1030132713 |
| [11] | Diaconis, P., Saloff-Coste, L.: Random walks on finite groups: a survey of analytic techniques. In: Heyer, H. (ed.) Probability Measures on Groups and Related Structures. XI (Oberwolfach, 1994), pp. 44-75. World Sci. Publ, River Edge (1995) · Zbl 0918.60059 |
| [12] | Fishman, G.: Coordinate selection rules for Gibbs sampling. Ann. Appl. Probab. 6(2), 444-465 (1996) · Zbl 0855.60060 · doi:10.1214/aoap/1034968139 |
| [13] | Goodman, F., Hauschild, H.: Affine Birman-Wenzl-Murakami algebras and tangles in the solid torus. Fundam. Math. 190, 77-137 (2006) · Zbl 1100.57008 · doi:10.4064/fm190-0-4 |
| [14] | Hammersley, J.M., Handscomb, D.C.: Monte Carlo Methods. Methuen & Co., Ltd., Barnes & Noble, Inc., London, New York (1965) · Zbl 0121.35503 |
| [15] | Karlin, S.: A First Course in Stochastic Processes. Academic Press, New York (1966) · Zbl 0177.21102 |
| [16] | Liu, J.: Monte Carlo Strategies in Scientific Computing. Springer Series in Statistics. Springer, New York (2008) · Zbl 1132.65003 |
| [17] | Maslen, D., Rockmore, D.: Separation of variables and the computation of Fourier transforms on finite groups. I. J. Amer. Math. Soc. 10(1), 169-214 (1997) · Zbl 0860.20016 · doi:10.1090/S0894-0347-97-00219-1 |
| [18] | Maslen, D., Rockmore, D.N., Wolff, S.: The efficient computation of fourier transforms on semisimple algebras. J. Fourier Anal. Appl. 24, 1377-1400 (2017) · Zbl 1530.65189 · doi:10.1007/s00041-017-9555-5 |
| [19] | Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21(1087), 1087-1092 (1953) · Zbl 1431.65006 · doi:10.1063/1.1699114 |
| [20] | Morton, H., Wasserman, A.: A basis for the Birman-Wenzl algebra. Revised 2000. Unpublished Manuscript (1989) |
| [21] | Nazarov, M.: Young’s orthogonal form for Brauer’s centralizer algebra. J. Algebra 182(3), 664-693 (1996) · Zbl 0868.20012 · doi:10.1006/jabr.1996.0195 |
| [22] | Saloff-Coste, L.: Random walks on finite groups. In: Kesten, H. (ed.) Probability on Discrete Structures, Volume 110 of Encyclopaedia Math. Sci., pp. 263-346. Springer, Berlin (2004) · Zbl 1049.60006 |
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.
