Covering Problems for Markov Chains
Matthews, Peter
Ann. Probab., Tome 16 (1988) no. 4, p. 1215-1228 / Harvested from Project Euclid
Upper and lower bounds are given on the moment generating function of the time taken by a Markov chain to visit at least $n$ of $N$ selected subsets of its state space. An example considered is the class of random walks on the symmetric group that are constant on conjugacy classes. Application of the bounds yields, for example, the asymptotic distribution of the time taken to see all $N!$ arrangements of $N$ cards as $N\rightarrow\infty$ for certain shuffling schemes.
Publié le : 1988-07-14
Classification:  Symmetric group,  random shuffle,  random allocation,  60G17,  60J10,  60B15
@article{1176991686,
     author = {Matthews, Peter},
     title = {Covering Problems for Markov Chains},
     journal = {Ann. Probab.},
     volume = {16},
     number = {4},
     year = {1988},
     pages = { 1215-1228},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1176991686}
}
Matthews, Peter. Covering Problems for Markov Chains. Ann. Probab., Tome 16 (1988) no. 4, pp.  1215-1228. http://gdmltest.u-ga.fr/item/1176991686/