×
Pittel, Boris

Tight Markov chains and random compositions. (English) Zbl 1257.05009

Ann. Probab. 40, No. 4, 1535-1576 (2012).
The author is concerned with a conjecture of G. Louchard [Theor. Comput. Sci. 346, No. 2–3, 358–387 (2005; Zbl 1086.60007)] concerning a given ergodic \(N\)-state Markov chain and with the corresponding Carlitz composition ([L. Carlitz, Fibonacci Q. 14, 254–264 (1976; Zbl 0338.05005)]; [A. Knopfmacher and H. Prodinger, Eur. J. Comb. 19, No. 5, 579–589 (1998; Zbl 0902.05004)]).
Reviewer: Sophia L. Kalpazidou (Thessaloniki)

Cited in 1 Document

MSC:

05A15 Exact enumeration problems, generating functions
05A17 Combinatorial aspects of partitions of integers
11P99 Additive number theory; partitions
60C05 Combinatorial probability
60F05 Central limit and other weak theorems
60J05 Discrete-time Markov processes on general state spaces
60G70 Extreme value theory; extremal stochastic processes

Keywords:

Markov chains; random compositions

Citations:

Zbl 1086.60007; Zbl 0338.05005; Zbl 0902.05004
Cite Review PDF
Full Text: DOI arXiv Euclid

References:

[1] Aldous, D. J. (1982). Markov chains with almost exponential hitting times. Stochastic Process. Appl. 13 305-310. · Zbl 0491.60077 · doi:10.1016/0304-4149(82)90016-3
[2] Aldous, D. J. and Brown, M. (1992). Inequalities for rare events in time-reversible Markov chains. I. In Stochastic Inequalities ( Seattle , WA , 1991). Institute of Mathematical Statistics Lecture Notes-Monograph Series 22 1-16. IMS, Hayward, CA. · Zbl 0812.60054 · doi:10.1214/lnms/1215461937
[3] Aldous, D. J. and Brown, M. (1993). Inequalities for rare events in time-reversible Markov chains. II. Stochastic Process. Appl. 44 15-25. · Zbl 0812.60054 · doi:10.1016/0304-4149(93)90035-3
[4] Andrews, G. E. (1976). The Theory of Partitions. Encyclopedia of Mathematics and Its Applications 2 . Addison-Wesley, Reading, MA. · Zbl 0655.10001
[5] Bender, E. A. (1973). Central and local limit theorems applied to asymptotic enumeration. J. Combinatorial Theory Ser. A 15 91-111. · Zbl 0242.05006 · doi:10.1016/0097-3165(73)90038-1
[6] Bender, E. A. and Canfield, E. R. (2005). Locally restricted compositions. I. Restricted adjacent differences. Electron. J. Combin. 12 1-27 (electronic). · Zbl 1088.05007
[7] Breiman, L. (1968). Probability . Addison-Wesley, Reading, MA. · Zbl 0174.48801
[8] Carlitz, L. (1976). Restricted compositions. Fibonacci Quart. 14 254-264. · Zbl 0338.05005
[9] Derman, C. (1954). A solution to a set of fundamental equations in Markov chains. Proc. Amer. Math. Soc. 5 332-334. · Zbl 0058.34504 · doi:10.2307/2032250
[10] Durrett, R. (2005). Probability : Theory and Examples , 3rd ed. Brooks/Cole, Thomson Learning, Belmont, CA. · Zbl 1202.60002
[11] Hitczenko, P. and Louchard, G. (2001). Distinctness of compositions of an integer: A probabilistic analysis. Random Structures Algorithms 19 407-437. · Zbl 1014.05008 · doi:10.1002/rsa.10008
[12] Hitczenko, P. and Savage, C. D. (2004). On the multiplicity of parts in a random composition of a large integer. SIAM J. Discrete Math. 18 418-435 (electronic). · Zbl 1068.05003 · doi:10.1137/S0895480199363155
[13] Kac, M. (1947). On the notion of recurrence in discrete stochastic processes. Bull. Amer. Math. Soc. 53 1002-1010. · Zbl 0032.41802 · doi:10.1090/S0002-9904-1947-08927-8
[14] Keilson, J. (1979). Markov Chain Models-Rarity and Exponentiality. Applied Mathematical Sciences 28 . Springer, New York. · Zbl 0411.60068
[15] Klarner, D. A. (1965). Some results concerning polyominoes. Fibonacci Quart. 3 9-20. · Zbl 0128.24504
[16] Knopfmacher, A. and Prodinger, H. (1998). On Carlitz compositions. European J. Combin. 19 579-589. · Zbl 0902.05004 · doi:10.1006/eujc.1998.0216
[17] Knuth, D. E., Motwani, R. and Pittel, B. (1990). Stable husbands. Random Structures Algorithms 1 1-14. · Zbl 0719.05001 · doi:10.1002/rsa.3240010102
[18] Louchard, G. (2005). Private communication.
[19] Louchard, G. (1997). Probabilistic analysis of column-convex and directed diagonally-convex animals. Random Structures Algorithms 11 151-178. · Zbl 0881.05035 · doi:10.1002/(SICI)1098-2418(199709)11:2<151::AID-RSA4>3.0.CO;2-R
[20] Louchard, G. (1999). Probabilistic analysis of column-convex and directed diagonally-convex animals. II. Trajectories and shapes. Random Structures Algorithms 15 1-23. · Zbl 0933.05037 · doi:10.1002/(SICI)1098-2418(199908)15:1<1::AID-RSA1>3.0.CO;2-5
[21] Louchard, G. and Prodinger, H. (2002). Probabilistic analysis of Carlitz compositions. Discrete Math. Theor. Comput. Sci. 5 71-95 (electronic). · Zbl 0994.68081
[22] Privman, V. and Forgács, G. (1987). Exact solution of the partially directed compact lattice animal model. J. Phys. A 20 L543-L547. · doi:10.1088/0305-4470/20/8/011
[23] Privman, V. and Švrakić, N. M. (1988). Exact generating function for fully directed compact lattice animals. Phys. Rev. Lett. 60 1107-1109. · doi:10.1103/PhysRevLett.60.1107
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.