Nonexistence of a class of variate generation schemes. (Q1413896)

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.