Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Các thuộc tính của chuỗi Markov khuyến khích trên các phần mở rộng tuyến tính
Tóm tắt
Thư viện Tsetlin là một mô hình rất được nghiên cứu về cách mà cách sắp xếp sách trên kệ thư viện phát triển theo thời gian. Một trong những thuộc tính thú vị nhất của chuỗi Markov này là phổ của nó có thể được tính toán chính xác và rằng các giá trị riêng theo tuyến tính trong các xác suất chuyển tiếp. Kết quả này đã được tổng quát theo nhiều cách khác nhau bởi nhiều người. Trong nghiên cứu này, chúng tôi điều tra một trong các sự tổng quát do chuỗi Markov khuyến khích mở rộng trên các phần mở rộng tuyến tính của một poset P do Ayyer et al. giới thiệu (J Algebr Comb 39(4):853–881, 2014). Họ đã chỉ ra rằng nếu poset P là một rừng có gốc, ma trận chuyển tiếp của chuỗi Markov này có các giá trị riêng theo tuyến tính trong các xác suất chuyển tiếp và mô tả số lượng của chúng. Chúng tôi chứng minh rằng thuộc tính tương tự cũng đúng với một lớp lớn hơn của các poset mà chúng tôi cũng suy ra các kết quả hội tụ đến trạng thái ổn định.
Từ khóa
Tài liệu tham khảo
Ayyer, A., Klee, S., Schilling, A.: Combinatorial Markov chains on linear extensions. J. Algebr. Comb. 39(4), 853–881 (2014)
Ayyer, A., Klee, S., Schilling, A.: Markov chains for promotion operators. In: Can, M.B., Li, Z., Steinberg, B., Wang, Q. (eds.) Algebraic Monoids, Group Embeddings, and Algebraic Combinatorics, pp. 285–304. Springer (2014)
Ayyer, A., Schilling, A., Steinberg, B., Thiéry, N.M.: Directed nonabelian sandpile models on trees. Commun. Math. Phys. 335(3), 1065–1098 (2015)
Ayyer, A., Schilling, A., Steinberg, B., Thiéry, N.M.: Markov chains, \(\cal{R}\)-trivial monoids and representation theory. Int. J. Algebr. Comput. 25(01n02), 169–231 (2015)
Bidigare, P., Hanlon, P., Rockmore, D.: A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements. Duke Math. J. 99(1), 135–174 (1999)
Björner, A.: Random walks, arrangements, cell complexes, greedoids, and self-organizing libraries. In: Grötschel, M., Katona, G. (eds.) Building Bridges, pp. 165–203. Springer (2008)
Björner, A.: Note: Random-to-front shuffles on trees. Electron. Commun. Probab. 14, 36–41 (2009)
Brown, K.S.: Semigroups, rings, and Markov chains. J. Theor. Probab. 13(3), 871–938 (2000)
Brown, K.S.: Semigroup and ring theoretical methods in probability. In: Representations of Finite Dimensional Algebras and Related Topics in Lie Theory and Geometry. Fields Institute Communications, vol. 40, pp. 3–26 (2004)
Brown, K.S., Diaconis, P.: Random walks and hyperplane arrangements. Ann. Probab. 26, 1813–1854 (1998)
Donnelly, P.: The heaps process, libraries, and size-biased permutations. J. Appl. Probab. 28, 321–335 (1991)
Fill, J.A.: An exact formula for the move-to-front rule for self-organizing lists. J. Theor. Probab. 9(1), 113–160 (1996)
Haiman, M.D.: Dual equivalence with applications, including a conjecture of Proctor. Discrete Math. 99(1), 79–113 (1992)
Hendricks, W.J.: The stationary distribution of an interesting Markov chain. J. Appl. Probab. 9, 231–233 (1972)
Hendricks, W.J.: An extension of a theorem concerning an interesting Markov chain. J. Appl. Probab. 10, 886–890 (1973)
Kapoor, S., Reingold, E.M.: Stochastic rearrangement rules for self-organizing data structures. Algorithmica 6(1–6), 278–291 (1991)
Malvenuto, C., Reutenauer, C.: Evacuation of labelled graphs. Discrete Math. 132(1), 137–143 (1994)
Phatarfod, R.M.: On the matrix occurring in a linear search problem. J. Appl. Probab. 28, 336–346 (1991)
Schützenberger, M.-P.: Promotion des morphismes d’ensembles ordonnés. Discrete Math. 2(1), 73–94 (1972)
Stanley, R.P.: Enumerative combinatorics. Vol. 1. In: Cambridge Studies in Advanced Mathematics vol. 49. Cambridge University Press, Cambridge (1997)
Tsetlin, M.L.: Finite automata and models of simple forms of behaviour. Russ. Math. Surv. 18(4), 1–27 (1963)