Perfect Sampling of Markov Chains with Piecewise Homogeneous Events

Details Perfect Sampling of Markov Chains with Piecewise Homogeneous Events Perfect Sampling of Markov Chains with Piecewise Homogeneous Events

2010-12-14

arxiv.org/abs/1012.2910v2

Computer Science

Discrete Mathematics

Scientific paper

Perfect sampling is a technique that uses coupling arguments to provide a sample from the stationary distribution of a Markov chain in a finite time without ever computing the distribution. This technique is very efficient if all the events in the system have monotonicity property. However, in the general (non-monotone) case, this technique needs to consider the whole state space, which limits its application only to chains with a state space of small cardinality. We propose here a new approach for the general case that only needs to consider two trajectories. Instead of the original chain, we use two bounding processes (envelopes) and we show that, whenever they couple, one obtains a sample under the stationary distribution of the original chain. We show that this new approach is particularly effective when the state space can be partitioned into pieces where envelopes can be easily computed. We further show that most Markovian queueing networks have this property and we propose efficient algorithms for some of them.

Affiliated with

Also associated with

No associations

Rating

Perfect Sampling of Markov Chains with Piecewise Homogeneous Events does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Perfect Sampling of Markov Chains with Piecewise Homogeneous Events, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Perfect Sampling of Markov Chains with Piecewise Homogeneous Events will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-178274