Approximating the stationary probability of a state in a Markov chain through Markov chain Monte Carlo techniques is, in general, inefficient. Standard random walk approaches require & xd5;(tau/pi(v))operations to...
详细信息
Approximating the stationary probability of a state in a Markov chain through Markov chain Monte Carlo techniques is, in general, inefficient. Standard random walk approaches require & xd5;(tau/pi(v))operations to approximate the probability pi(v) of a state v in a chain with mixing time tau, and even the best available techniques still have complexity & xd5;(tau 1.5/pi(v)0.5) and since these complexities depend inversely on pi(v), they can grow beyond any bound in the size of the chain or in its mixing time. In this paper we show that, for time-reversible Markov chains, there exists a simple randomized approximation algorithm that breaks this "small-pi(v) barrier".
Approximating the stationary probability of a state in a Markov chain through Markov chain Monte Carlo techniques is, in general, inefficient. Standard random walk approaches require (O) over tilde(tau/pi(v)) operatio...
详细信息
ISBN:
(纸本)9783959770620
Approximating the stationary probability of a state in a Markov chain through Markov chain Monte Carlo techniques is, in general, inefficient. Standard random walk approaches require (O) over tilde(tau/pi(v)) operations to approximate the probability pi(v) of a state v in a chain with mixing time T, and even the best available techniques still have complexity (O) over tilde (tau(1.5)/pi(v)(0.5));and since these complexities depend inversely on pi(v), they can grow beyond any bound in the size of the chain or in its mixing time. In this paper we show that, for time-reversible Markov chains, there exists a simple randomized approximation algorithm that breaks this "small-pi(v) barrier".
暂无评论