Nonexistence of a class of variate generation schemes.

DOI10.1016/S0167-6377(02)00217-1MaRDI QIDQ1413896zbMATH OpenOpenAlexWikidataFDO

Authors Shane G. Henderson, Peter W. Glynn

Publication date 17 November 2003

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0167-6377(02)00217-1, https://hdl.handle.net/1813/9193

zbMATH Keywords

discrete-event systemgeneral state space Markov chainsrandom variable generationregenerative processessplitting techniquesteady state simulationtransitional kernel

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) Numerical analysis or methods applied to Markov chains (65C40) Numerical optimization and variational techniques (65K10) Discrete event control/observation systems (93C65)

Review text

The authors are motivated by a problem arising in the regenerative analysis of discrete-event system simulation and ask the question whether a certain class of random variate generation schemes exists or no. More precisely, while for many systems (as Markov chains, e.g.) regeneration times are easily determined by observing the sample paths, this is not the case in general. The identification of the regeneration times is based on modeling a discrete-event system as a general state space Markov chain (GSSMC), which can be obtained by observing the discrete-event system at event times. One can then use a ``splitting technique to identify the regeneration. All of the known methods require explicit knowledge of the \(m\)-step transition kernel of the GSSMC for some \(m\geq1\). So, the question raised in the paper is whether these regeneration times can be computed without explicit knowledge of the \(m\)-step transition kernel. Section~2 explains in greater detail how this problem arises within the regenerative simulation setting. Section~3 places the problem in a slightly more abstract setting and provides two nonexistence proofs under different assumptions about one's level of knowledge about the transition kernel. Finally, Section~4 describes the implication of these results for the regenerative method of steady state simulation.

Recommendations

• Regenerative steady-state simulation of discrete-event systems
• Some topics in regenerative steady-state simulation
• Accelerated regeneration for Markov chain simulations
• Notes: Conditions for the Applicability of the Regenerative Method
• A martingale approach to regenerative simulation

Cites work

• A Bernoulli factory
• A New Approach to the Limit Theory of Recurrent Markov Chains
• A splitting technique for Harris recurrent Markov chains
• scientific article; zbMATH DE number 4013703 (Why is no real title available?)
• scientific article; zbMATH DE number 4060392 (Why is no real title available?)
• scientific article; zbMATH DE number 108577 (Why is no real title available?)
• Likelihood ratio gradient estimation for stochastic recursions
• Limit theory for performance modeling of future event set algorithms
• Markov chains and stochastic stability
• On simulation output analysis for generalized semi-markov processes
• One-Dependent Regenerative Processes and Queues in Continuous Time
• Regeneration in tandem queues with multiserver stations
• Regenerative steady-state simulation of discrete-event systems
• Simulation of queueing processes based on weak regeneration
• Some topics in regenerative steady-state simulation
• Stationarity detection in the initial transient problem
• Weak regenerative structure of an open Jackson queueing network

Cited in

(3)

• Fast simulation of new coins from old
• From the Bernoulli factory to a dice enterprise via perfect sampling of Markov chains
• Simulating events of unknown probabilities via reverse time martingales

This page was built for publication: Nonexistence of a class of variate generation schemes.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1413896)