Antiduality and Möbius monotonicity: Generalized Coupon Collector Problem

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 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 so...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-03
Main Author: Lorek, Paweł
Format: Article
Language:English
Subjects:
Absorption
Markov analysis
Markov chains
Random variables
Windows (intervals)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 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\"obius 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 a limiting distribution of the absorption time - we indicate a separation cutoff (with its window size) in several chains. We also present a chain which (under some conditions) has a prescribed stationary distribution and its fastest strong stationary time is distributed as a prescribed mixture of sums of geometric random variables.
ISSN:2331-8422