Volume 23, 2019
|Page(s)||739 - 769|
|Published online||20 December 2019|
Antiduality and Möbius monotonicity: generalized coupon collector problem☆
Mathematical Institute, University of Wrocław,
pl. Grunwaldzki 2/4,
* Corresponding author: email@example.com
Accepted: 5 March 2019
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.
Mathematics Subject Classification: 60J10 / 60G40 / 06A06
Key words: 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
© EDP Sciences, SMAI 2019
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.