Exact mixing in an unknown Markov chain
type: Item
instance of: scholarly article
title: Exact mixing in an unknown Markov chain
zbMATH Open document ID: 0823.60057
author: Peter Winkler
author: László Lovász
published in: The Electronic Journal of Combinatorics
publication date: 1995-09-11T00:00:00Z
full work available at URL: https://eudml.org/doc/118710
full work available at URL: R15
review text: We give a simple stopping rule which will stop an unknown, irreducible \(n\)-state Markov chain at a state whose probability distribution is exactly the stationary distribution of the chain. The expected stopping time of the rule is bounded by a polynomial in the maximum mean hitting time of the chain. Our stopping rule can be made deterministic unless the chain itself has no random transitions.
Mathematics Subject Classification ID: 60J10
zbMATH DE Number: 793924
zbMATH Keywords: stopping rule
zbMATH Keywords: stationary distribution
zbMATH Keywords: stopping time
zbMATH Keywords: maximum mean hitting time
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 793924