Gap-free compositions and gap-free samples of geometric random variables

Alon, 2000 Andrews, 1976 Bai, 1998, Normal approximations of the number of records in geometrically distributed random variables, Random Struct. Alg., 13, 319, 10.1002/(SICI)1098-2418(199810/12)13:3/4<319::AID-RSA7>3.0.CO;2-Y Devroye, 1992, A limit theory for random skip lists, Ann. Appl. Probab., 2, 597, 10.1214/aoap/1177005651 Flajolet, 1985, Probabilistic counting algorithms for data base applications, J. Comput. System Sci., 31, 182, 10.1016/0022-0000(85)90041-8 Goh, 1992, Gap-free set partitions, Random Struct. Algorithms, 3, 9, 10.1002/rsa.3240030103 P.J. Grabner, A. Knopfmacher, Analysis of some new partition statistics, Ramanujan J., to appear. Hitczenko, 2004, Distinctness of compositions of an integer: a probabilistic analysis, Random Struct. Alg., 19, 407, 10.1002/rsa.10008 Hitczenko, 2005, On the multiplicity of parts in a random composition of a large integer, SIAM J. Discrete Math., 18, 418, 10.1137/S0895480199363155 Jacquet, 1998, Analytical de–Poissonization and its applications, Theoret. Comput. Sci., 201, 1, 10.1016/S0304-3975(97)00167-9 S. Janson, W. Szpankowski, Analysis of the asymmetric leader election algorithm, Electr. J. Combin. 4(1): research paper 17 (1997) 16pp. P. Kirschenhofer, H. Prodinger, in: E. Hlawka, R.F. Tichy (Eds.), On the Analysis of Probabilistic Counting, Lecture Notes in Mathematics, vol. 1452, 1990, pp. 117–120. Knopfmacher, 2001, Combinatorics of geometrically distributed random variables: value and position of the rth left-to-right maximum, Discrete Math., 226, 255, 10.1016/S0012-365X(00)00133-3 D. Knuth, The Art of Computer Programming, vol. 3: Sorting and Searching, Addison-Wesley, Reading, MA, 1973. Papadakis, 1992, Average search and update costs in skip lists, BIT, 32, 316, 10.1007/BF01994884 Prodinger, 1996, Combinatorics of geometrically distributed random variables, Discrete Math., 153, 253, 10.1016/0012-365X(95)00141-I H. Prodinger, Combinatorics of geometrically distributed random variables: lengths of ascending runs, LATIN2000, Lecture Notes in Computer Science, vol. 1776, 2000, pp. 473–482. Prodinger, 2001, Combinatorics of geometrically distributed random variables, Ann. Combin., 5, 141, 10.1007/s00026-001-8010-z Pugh, 1990, Skip lists: a probabilistic alternative to balanced trees, Comm. ACM, 33, 668, 10.1145/78973.78977 Szpankowski, 2001