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.
Keywords: Markov chains, strong stationary duality, antiduality, absorption times, fastest strong stationary times, Möbius monotonicity, generalized coupon collector problem, Double Dixie cup problem, separation cutoff, partial ordering, perfect simulation
Lorek, Paweł 1
@article{PS_2019__23__739_0,
author = {Lorek, Pawe{\l}},
title = {Antiduality and {M\"obius} monotonicity: generalized coupon collector problem},
journal = {ESAIM: Probability and Statistics},
pages = {739--769},
year = {2019},
publisher = {EDP Sciences},
volume = {23},
doi = {10.1051/ps/2019004},
mrnumber = {4044608},
zbl = {1506.60075},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ps/2019004/}
}
TY - JOUR AU - Lorek, Paweł TI - Antiduality and Möbius monotonicity: generalized coupon collector problem JO - ESAIM: Probability and Statistics PY - 2019 SP - 739 EP - 769 VL - 23 PB - EDP Sciences UR - https://www.numdam.org/articles/10.1051/ps/2019004/ DO - 10.1051/ps/2019004 LA - en ID - PS_2019__23__739_0 ER -
Lorek, Paweł. Antiduality and Möbius monotonicity: generalized coupon collector problem. ESAIM: Probability and Statistics, Tome 23 (2019), pp. 739-769. doi: 10.1051/ps/2019004
[1] and , Shuffling cards and stopping times. Am. Math. Mon. 93 (1986) 333–348. | Zbl | MR | DOI
[2] and , Strong uniform times and finite random walks. Adv. Appl. Math. 97 (1987) 69–97. | Zbl | MR | DOI
[3] , and , Characterization of cutoff for reversible Markov chains. Ann. Probab. 45 (2017) 1448–1487. | Zbl | MR | DOI
[4] and , The cutoff phenomenon for ergodic Markov processes. Electron. J. Probab. 13 (2008) 26–78. | Zbl | MR
[5] and , Computing cutoff times of birth and death chains. Electron. J. Probab. 20 (2015) 1–47. | Zbl | MR
[6] and , 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 , , , , and . Springer, Switzerland (2016) 529–536. | MR
[7] , Separation and coupling cutoffs for tuples of independent Markov processes. Lat. Am. J. Probab. Math. Stat. 7 (2010) 65–77. | Zbl | MR
[8] and , Strong stationary times via a new form of duality. Ann. Probab. 18 (1990) 1483–1522. | Zbl | MR | DOI
[9] and , On times to quasi-stationarity for birth and death processes. J. Theor. Probab. 22 (2009) 558–586. | Zbl | MR | DOI
[10] and , What do we know about the Metropolis algorithm? J. Comput. Syst. Sci. 57 (1998) 20–36. | Zbl | MR | DOI
[11] and , Separation cut-offs for birth and death chains. Ann. Appl. Probab. 16 (2006) 2098–2122. | Zbl | MR | DOI
[12] and , Generating a random permutation with random transpositions. Z. Wahrscheinlichkeitstheor. verw. Geb. 57 (1981) 159–179. | Zbl | MR | DOI
[13] , and , Total variation cutoff in birth-and-death chains. Probab. Theory Relat. Fields 146 (2010) 61–85. | Zbl | MR | DOI
[14] and , The coupon collector’s problem revisited: generalizing the double dixie cup problem of Newman and Shepp. ESAIM: PS 20 (2016) 367–399. | Zbl | Numdam | MR | DOI
[15] and , On a classical problem of probability theory. Publ. Math. Inst. Hung. Acad. Sci. Ser. A 6 (1961) 215–220. | Zbl | MR
[16] , An Introduction to Probability Theory and Its Applications, 2nd edn., Vol. 2. John Wiley & Sons, NJ (1971). | Zbl | MR
[17] , An exact formula for the move-to-front rule for self-organizing lists. J. Theor. Probab. 9 (1996) 113–160. | Zbl | MR | DOI
[18] , On hitting times and fastest strong stationary times for skip-free and more general chains. J. Theor. Probab. 22 (2009) 587–600. | Zbl | MR | DOI
[19] , 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. | Zbl | MR | DOI
[20] and , Strong stationary duality for diffusion processes. J. Theor. Probab. 29 (2016) 1298–1338. | Zbl | MR | DOI
[21] , and , Total variation and separation cutoffs are not equivalent and neither one implies the other. Electron. J. Probab. 21 (2016) 1–36. | Zbl | MR | DOI
[22] , Extreme value distributions for random coupon collector and birthday problems. Extremes 4 (2001) 129–145. | Zbl | MR | DOI
[23] and , Coincidence properties of birth and death processes. Pac. J. Math. 9 (1959) 1109–1140. | Zbl | MR | DOI
[24] , Log-concavity and log-convexity in passage time densities of diffusion and birth-death processes. J. Appl. Probab. 8 (1971) 391–398. | Zbl | MR | DOI
[25] , The cutoff profile for the simple-exclusion process on the circle. Ann. Probab. 44 (2016) 3399–3430. | Zbl | MR | DOI
[26] , and , Markov Chains and Mixing Times, 2nd edn. American Mathematical Society, Rhode Island (2017). | Zbl | MR | DOI
[27] , Generalized Gambler’s ruin problem: explicit formulas via Siegmund duality. Methodol. Comput. Appl. Probab. 19 (2017) 603–613. | Zbl | MR | DOI
[28] , Siegmund duality for Markov chains on partially ordered state spaces. Probab. Eng. Inf. Sci. 32 (2018) 495–521. | MR | Zbl | DOI
[29] and , Monotonicity requirements for efficient exact sampling with Markov chains. Markov Process. Relat. Fields 23 (2017) 485–514. | Zbl | MR
[30] and , Strong stationary duality for Möbius monotone Markov chains. Queueing Syst. 71 (2012) 79–95. | Zbl | MR | DOI
[31] and , Cutoff for the Ising model on the lattice. Invent. Math. 191 (2013) 719–755. | Zbl | MR | DOI
[32] , and , Separation cutoff for upward skip-free chains. J. Appl. Probab. 1 (2016) 299–306. | Zbl | MR | DOI
[33] , On absorption times and Dirichlet eigenvalues. ESAIM: PS 14 (2010) 117–150. | Zbl | MR | Numdam | DOI
[34] , The generalised coupon collector problem. J. Appl. Probab. 45 (2008) 621–629. | Zbl | MR | DOI
[35] , The double dixie cup problem. Am. Math. Mon. 67 (1960) 58–61. | Zbl | MR | DOI
[36] and , On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes. Discrete Appl. Math. 110 (2001) 251–272. | Zbl | MR | DOI
[37] , On the foundations of combinatorial theory I. Theory of Möbius functions. Probab. Theory and Relat. Fields 368 (1964) 340–368. | Zbl | MR
[38] , The equivalence of absorbing and reflecting barrier problems for stochastically monotone Markov processes. Ann. Probab. 4 (1976) 914–924. | Zbl | MR | DOI
Cité par Sources :
