Covering problems for Markov chains (Q749044): Difference between revisions

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.