The Length of the Longest Increasing Subsequence of a Random Mallows Permutation
Tóm tắt
The Mallows measure on the symmetric group S
n
is the probability measure such that each permutation has probability proportional to q raised to the power of the number of inversions, where q is a positive parameter and the number of inversions of π is equal to the number of pairs iπ
j
. We prove a weak law of large numbers for the length of the longest increasing subsequence for Mallows distributed random permutations, in the limit that n→∞ and q→1 in such a way that n(1−q) has a limit in R.
Tài liệu tham khảo
Aldous, D.J.: Exchangeability and related topics. In: Hennequin, P.L. (ed.) École d’été de probabilités de Saint-Flour, XII–1983. Lecture Notes in Math., vol. 1117, pp. 1–198. Springer, Berlin (1985). http://www.stat.berkeley.edu/~aldous/Papers/me22.pdf
Aldous, D., Diaconis, P.: Hammersley’s interacting particle process and longest increasing subsequences. Probab. Theory Relat. Fields 103, 199–213 (1995)
Baik, J., Deift, P., Johansson, K.: On the distribution of the length of the longest increasing subsequence of random permutations. J. Am. Math. Soc. 12, 1119–1178 (1999)
Borodin, A., Diaconis, P., Fulman, J.: On adding a list of numbers (and other one-dependent determinantal processes). Bull. Am. Math. Soc. 47, 639–670 (2010)
Cator, E., Groeneboom, P.: Second class particles and cube root asymptotics for Hammersley’s process. Ann. Probab. 33, 879–905 (2005)
Deuschel, J.-D., Zeitouni, O.: Limiting curves for i.i.d. records. Ann. Probab. 23, 852–878 (1995)
Deuschel, J.-D., Zeitouni, O.: On increasing subsequences of i.i.d. samples. Comb. Probab. Comput. 8(3), 247–263 (1999)
Diaconis, P., Ram, A.: Analysis of systematic scan metropolis algorithms using Iwahori-Hecke algebra techniques. Mich. Math. J. 48, 157–190 (2000)
Gnedin, A., Olshanski, G.: A q-analogue of de Finetti’s Theorem. Electron. J. Comb. 16(1), R78 (2009). http://www.combinatorics.org/Volume_16/PDF/v16i1r78.pdf
Gnedin, A., Olshanski, G.: q-Exchangeability via quasi-invariance. Ann. Probab. 38(6), 2103–2135 (2010). http://projecteuclid.org/euclid.aop/1285334202
Hammersley, J.M.: A few seedlings of research. In: Proc. Sixth Berkeley Symp. Math. Statist. Probab., vol. 1, pp. 345–394. Univ. California Press, Berkeley (1972)
Hohlweg, C.: Minimal and maximal elements in Kazhdan–Lusztig two-sided cells of S n and Robinson–Schensted correspondence. Discrete Math. 304(1), 79–87 (2005)
Kerov, S.V.: Asymptotic Representation Theory of the Symmetric Group and its Application in Analysis. Translations of Mathematical Monographs, vol. 219. Amer. Math. Soc., Providence (2003)
Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. Amer. Math. Soc., Providence (2009)
Logan, B.F., Shepp, L.A.: A variational problem for random Young tableaux. Adv. Math. 26, 206–222 (1977)
Mallows, C.L.: Non-null ranking models. I. Biometrika 44, 114–130 (1957). http://www.jstor.org/stable/2333244
Robinson, D.W., Ruelle, D.: Mean entropy of states in classical statistical mechanics. Commun. Math. Phys. 5, 288–300 (1967)
Seppäläinen, T.: A microscopic model for the Burgers equation and longest increasing subsequences. Electron. J. Probab. 1, 1–51 (1994)
Starr, S.: Thermodynamic limit for the Mallows model on S n . J. Math. Phys. 50, 095208 (2009)
Thompson, C.J.: Mathematical Statistical Mechanics. Macmillan, New York (1972)
Tracy, C., Widom, H.: Level-spacing distributions and the Airy kernel. Commun. Math. Phys. 159, 151–174 (1994)
Vershik, A.M., Kerov, S.V.: Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableaux. Sov. Math. Dokl. 18, 527–531 (1977). Translation of Dokl. Acad. Nauk. SSSR 32, 1024–1027