Covering problems for Markov chains
type: Item
instance of: scholarly article
title: Covering problems for Markov chains
zbMATH Open document ID: 0712.60076
author: D. Kharzeev
published in: The Annals of Probability
publication date: 1988-01-01T00:00:00Z
review text: The problem considered in this article is similar to the coupon collector's problem as considered by \textit{W. Feller} [An introduction to probability theory and its applications, Vol. I, third ed. (1968; Zbl 0155.231)]. Consider an N-state Markov chain. How long until the Markov chain has covered its state space, i.e., how long until all states are visited? How many states have not been visited after N(log N\(+C)\) steps? \textit{D. J. Aldous} [Z. Wahrscheinlichkeitstheor. Verw. Geb. 62, 375-394 (1983; Zbl 0503.60046)] first considered this type of problem, and in a previous paper, the author [Ann. Probab. 16, No.1, 189-199 (1988; Zbl 0638.60014)] gave bounds applicable to mean covering times for finite Markov chains. In this article an extension to bounds on the moment- generating function is given.
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 60G17
zbMATH DE Number: 4172096
zbMATH Keywords: coupon collector's problem
zbMATH Keywords: moment-generating function
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aop/1176991686
OpenAlex ID: W2068008593
DOI: 10.1214/AOP/1176991686
Recommended article: Covering runs in binary Markov sequences
Recommended article: Markov loops, coverings and fields
Recommended article: Cover times for sequences of reversible Markov chains on random graphs
Recommended article: Q3991023
Recommended article: Reachability problems for Markov chains
Recommended article: Finite Markov Chains and Algorithmic Applications
Recommended article: Technical comment. A problem on Markov chains
Recommended article: The Littlewood-Offord problem for Markov chains
Recommended article: Lower bounds for covering times for reversible Markov chains and random walks on graphs
Recommended article: Some bounds for Markov chains
description: scientific article; zbMATH DE number 4172096