Antiduality and Möbius monotonicity: generalized coupon collector problem

Lorek, Paweł

ESAIM: Probability and Statistics, Tome 23 (2019), pp. 739-769.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

For a given absorbing Markov chain X^* on a finite state space, a chain X is a sharp antidual of X^* if the fastest strong stationary time (FSST) of X is equal, in distribution, to the absorption time of X^*. In this paper, we show a systematic way of finding such an antidual based on some partial ordering of the state space. We use a theory of strong stationary duality developed recently for Möbius monotone Markov chains. We give several sharp antidual chains for Markov chain corresponding to a generalized coupon collector problem. As a consequence – utilizing known results on the limiting distribution of the absorption time – we indicate separation cutoffs (with their window sizes) in several chains. We also present a chain which (under some conditions) has a prescribed stationary distribution and its FSST is distributed as a prescribed mixture of sums of geometric random variables.

[1] D. Aldous and P. Diaconis, Shuffling cards and stopping times. Am. Math. Mon. 93 (1986) 333–348. | DOI | MR | Zbl

[2] D. Aldous and P. Diaconis, Strong uniform times and finite random walks. Adv. Appl. Math. 97 (1987) 69–97. | DOI | MR | Zbl

[3] R. Basu, J. Hermon and Y. Peres, Characterization of cutoff for reversible Markov chains. Ann. Probab. 45 (2017) 1448–1487. | DOI | MR | Zbl

[4] G.-Y. Chen and L. Saloff-Coste, The cutoff phenomenon for ergodic Markov processes. Electron. J. Probab. 13 (2008) 26–78. | MR | Zbl

[5] G.-Y. Chen and L. Saloff-Coste, Computing cutoff times of birth and death chains. Electron. J. Probab. 20 (2015) 1–47. | MR | Zbl

[6] M.C.H. Choi and P. Patie, A sufficient condition for continuous-time finite skip-free Markov chains to have real eigenvalues, in Mathematical and Computational Approaches in Advancing Modern Science and Engineering, edited by J. Bélair, I. Frigaard, H. Kunze, R. Makarov, R. Melnik and R. Spiteri. Springer, Switzerland (2016) 529–536. | MR

[7] S.B. Connor, Separation and coupling cutoffs for tuples of independent Markov processes. Lat. Am. J. Probab. Math. Stat. 7 (2010) 65–77. | MR | Zbl

[8] P. Diaconis and J.A. Fill, Strong stationary times via a new form of duality. Ann. Probab. 18 (1990) 1483–1522. | DOI | MR | Zbl

[9] P. Diaconis and L. Miclo, On times to quasi-stationarity for birth and death processes. J. Theor. Probab. 22 (2009) 558–586. | DOI | MR | Zbl

[10] P. Diaconis and L. Saloff-Coste, What do we know about the Metropolis algorithm? J. Comput. Syst. Sci. 57 (1998) 20–36. | DOI | MR | Zbl

[11] P. Diaconis and L. Saloff-Coste, Separation cut-offs for birth and death chains. Ann. Appl. Probab. 16 (2006) 2098–2122. | DOI | MR | Zbl

[12] P. Diaconis and M. Shahshahani, Generating a random permutation with random transpositions. Z. Wahrscheinlichkeitstheor. verw. Geb. 57 (1981) 159–179. | DOI | MR | Zbl

[13] J. Ding, E. Lubetzky and Y. Peres, Total variation cutoff in birth-and-death chains. Probab. Theory Relat. Fields 146 (2010) 61–85. | DOI | MR | Zbl

[14] A.V. Doumas and V.G. Papanicolaou, The coupon collector’s problem revisited: generalizing the double dixie cup problem of Newman and Shepp. ESAIM: PS 20 (2016) 367–399. | DOI | Numdam | MR | Zbl

[15] P.L. Erdłs and A. Rényi, On a classical problem of probability theory. Publ. Math. Inst. Hung. Acad. Sci. Ser. A 6 (1961) 215–220. | MR | Zbl

[16] W. Feller, An Introduction to Probability Theory and Its Applications, 2nd edn., Vol. 2. John Wiley & Sons, NJ (1971). | MR | Zbl

[17] J.A. Fill, An exact formula for the move-to-front rule for self-organizing lists. J. Theor. Probab. 9 (1996) 113–160. | DOI | MR | Zbl

[18] J.A. Fill, On hitting times and fastest strong stationary times for skip-free and more general chains. J. Theor. Probab. 22 (2009) 587–600. | DOI | MR | Zbl

[19] J.A. Fill, The passage time distribution for a birth-and-death chain: strong stationary duality gives a first stochastic proof. J. Theor. Probab. 22 (2009) 543–557. | DOI | MR | Zbl

[20] J.A. Fill and V. Lyzinski, Strong stationary duality for diffusion processes. J. Theor. Probab. 29 (2016) 1298–1338. | DOI | MR | Zbl

[21] J. Hermon, H. Lacoin and Y. Peres, Total variation and separation cutoffs are not equivalent and neither one implies the other. Electron. J. Probab. 21 (2016) 1–36. | DOI | MR | Zbl

[22] L. Holst, Extreme value distributions for random coupon collector and birthday problems. Extremes 4 (2001) 129–145. | DOI | MR | Zbl

[23] S. Karlin and J. Mcgregor, Coincidence properties of birth and death processes. Pac. J. Math. 9 (1959) 1109–1140. | DOI | MR | Zbl

[24] J. Keilson, Log-concavity and log-convexity in passage time densities of diffusion and birth-death processes. J. Appl. Probab. 8 (1971) 391–398. | DOI | MR | Zbl

[25] H. Lacoin, The cutoff profile for the simple-exclusion process on the circle. Ann. Probab. 44 (2016) 3399–3430. | DOI | MR | Zbl

[26] D. Levin, Y. Peres and E. Wilmer, Markov Chains and Mixing Times, 2nd edn. American Mathematical Society, Rhode Island (2017). | DOI | MR | Zbl

[27] P. Lorek, Generalized Gambler’s ruin problem: explicit formulas via Siegmund duality. Methodol. Comput. Appl. Probab. 19 (2017) 603–613. | DOI | MR | Zbl

[28] P. Lorek, Siegmund duality for Markov chains on partially ordered state spaces. Probab. Eng. Inf. Sci. 32 (2018) 495–521. | DOI | MR | Zbl

[29] P. Lorek and P. Markowski, Monotonicity requirements for efficient exact sampling with Markov chains. Markov Process. Relat. Fields 23 (2017) 485–514. | MR | Zbl

[30] P. Lorek and R. Szekli, Strong stationary duality for Möbius monotone Markov chains. Queueing Syst. 71 (2012) 79–95. | DOI | MR | Zbl

[31] E. Lubetzky and A. Sly, Cutoff for the Ising model on the lattice. Invent. Math. 191 (2013) 719–755. | DOI | MR | Zbl

[32] Y.-H. Mao, C. Zhang and Y.-H. Zhang, Separation cutoff for upward skip-free chains. J. Appl. Probab. 1 (2016) 299–306. | DOI | MR | Zbl

[33] L. Miclo, On absorption times and Dirichlet eigenvalues. ESAIM: PS 14 (2010) 117–150. | DOI | Numdam | MR | Zbl

[34] P. Neal, The generalised coupon collector problem. J. Appl. Probab. 45 (2008) 621–629. | DOI | MR | Zbl

[35] D.J. Newman, The double dixie cup problem. Am. Math. Mon. 67 (1960) 58–61. | DOI | MR | Zbl

[36] I. Pak and V.H. Vu, On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes. Discrete Appl. Math. 110 (2001) 251–272. | DOI | MR | Zbl

[37] G.-C. Rota, On the foundations of combinatorial theory I. Theory of Möbius functions. Probab. Theory and Relat. Fields 368 (1964) 340–368. | MR | Zbl

[38] D. Siegmund, The equivalence of absorbing and reflecting barrier problems for stochastically monotone Markov processes. Ann. Probab. 4 (1976) 914–924. | DOI | MR | Zbl