This article introduces the LBATCH and ABATCH rules for applying the batch means method to analyze output of Monte Carlo and, in particular, discrete-event simulation experiments. Sufficient conditions are given for these rules to produce strongly consistent estimators of the variance of the sample mean and asymptotically valid confidence intervals for the mean. The article studies the performance of these rules and two others suggested in the literature, comparing confidence interval coverage rates and mean half-lengths. The article also gives detailed algorithms for implementing the rules in O(t) time with O(log2 t) space. FORTRAN, C, and SIMSCRIPT II.5 implementations of the procedures are available by anonymous file transfer protocol.

Abstract Consider a flow network whose nodes do not restrict flow transmission and arcs have random, discrete, and independent capacities. Let s and t be a pair of selected nodes, let δ denote the value of a maximum s—t flow, and let Γ denote a set of s–t cuts. Also, let ℱ denote a set of independent joint capacity distributions with common state space. For fixed l < u, this paper develops methods for approximating the probability that l ≤ Δ < u and the probability that a cut in Γ is minimum given that l ≤ δ < u for each distribution in ℱ. Since these evaluations are NP‐hard problems, it shows how information obtained during an iterative procedure for computing the probability that l ≤ δ < u can be used for designing an efficient Monte Carlo sampling plan that performs sampling at few capacity distributions and uses sampling data to estimate the probabilities of interest at each distribution in ℱ. The set of sampling distributions is chosen by solving an uncapacitated facility location problem. The paper also describes techniques for computing confidence intervals and includes an algorithm for implementing the sampling experiment. An example illustrates the efficiency of the proposed method. This method is applicable to the computation of performance measures for networks whose elements have discrete random weights (lengths, gains, etc.) for a set of joint weight distributions with common state space. © 1993 by John Wiley & Sons, Inc.

article Free Access Share on Generating a sample from a k-cell table with changing probabilities in O(log2k time Authors: George S. Fishman Univ. of North Carolina Univ. of North CarolinaView Profile , L. Stephen Yarberry View Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 19Issue 2June 1993 pp 257–261https://doi.org/10.1145/152613.152621Published:01 June 1993Publication History 3citation213DownloadsMetricsTotal Citations3Total Downloads213Last 12 Months6Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Abstract Consider a flow network G = (𝒱,ℰ) with node set 𝒱 and arc set ℰ = {1, …, e}. Assume that the nodes do not restrict flow transmission and the arcs have random, discrete and independent capacities B1, …, Be, and let B = {B1, …, Be}. Also, let s and t be a pair of nodes in 𝒱, let Λ(B) denote the value of a maximum s–t flow, and let Γ denote a set of s–t cuts. This work describes a highly efficient Monte Carlo sampling plan for estimating the probability that l < Λ(B) ⩽ u, the probability that a cut in Γ is critical and l < Λ(B) ⩽ u, and the probability that a cut in Γ is critical, given that l < Λ(B) ⩽ u. The proposed method takes advantage of an easily computed upper bound on the probability that l < Λ(B) ⩽ u, which is a function of both l and u to gain its computational advantage. The article also describes techniques for computing confidence intervals that are valid for any sample size. Algorithms for implementing the proposed sampling experiment are included, and an example illustrates the efficiency of the proposed method.

Abstract Consider an undirected network G with node set V and arc set E = {1, …, n} where arcs fail randomly and independently. Let T be a subset of V and let Mk denote the number of ways that all the nodes of T are connected (T‐connectivity) with exactly k operating arcs and n ‐ k failed arcs. This paper describes a sampling plan for estimating {Mk} and linear functions of these parameters, including the T‐connectedness reliability function g(p) for common failure probability 1 ‐ p. Point and simultaneous interval estimates are derived for {Mk/( }, where the interval estimates meet a fixed width criterion in O(n log n) time as the size of the network n grows. Whereas all previously proposed Monte Carlo sampling plans enable one to estimate g(p) for a fixed p, the proposed method allows one to estimate the entire function {g(p), p ∈ P}, where either P = P* = {qi: O ≦ qi ≦ 1, 1 ≦ i = ≦ v} or P = P** = {[a, b]: 0 ≦ a ≦ b ≦ 1}. Here P* denotes a finite set of points in [0, 1] and P** an interval in [0, 1]. Simultaneous interval estimates are derived that meet a fixed width criterion in O(n) time for P = P* and in O(n2) time for P = P** as n → ∞. A priori bounds are also derived for g (p) and it is shown how these can be used to give guidance on the performance of the sampling plan. An example based on a network with 44 nodes and 85 arcs illustrates the proposed method.

A procedure ts discussed for interval estimation of the mean O of a correlated binary (0, 1) sequence The proposed method can be applied to sunulation data that are not intrinsically bmary m nature The method assumes that the sequence ts strictly stauonary and that a particular stnng of m bmary digits is a recurrent event m the sequence, where m _> 1 is unknown Of the 2 m choices for the possible recurrent events, the strmgs of all zeros and of all ones are exammed For each m = l, 2,. the sequence is demarcated by entrance to the recurrent event.The subsequences between the demarcation points thus form mdependent epochs by assumption Classical techniques then yield variance estimates for the number of ones and zeros m the epoch as well as an estimate of the covanance of the ones and zeros.A quadratic equation m O is solved to obtain an mterval estimate.Each string of all ones or all zeros examined yields a 1 -ct confidence mterval The intervals are intersected to obtain shorter mtervals with confidence greater than 1 -2c~ Since each m = 1, 2, yields an mterval, a conservative rule is developed to determme the m whose mterval is fmally used.This rule is based upon the empirical run lengths in the binary sequence.The procedure is then apphed to interval estunation of the waitmg time dlstnbution m a simulation of the M/M/I queue with activity level 0.9.For O = 0.l and 0.5 the proposed method worked well For O = 0.9 results showed some degradauon.An error analysis led to a set of recommendations for keepmg performance m practice close to the desired theoretical levels An appendLx describes algorithms for computing the crmcal quantmes upon which the proposed method rehes