Search

Temporal shaping of time series is the activity of deriving a time series model with a prescribed marginal distribution and some sample path characteristics. Starting with an empirical sample path, one often computes from it an empirical histogram (a step-function density) and empirical autocorrelation function. The corresponding cumulative distribution function is piecewise linear, and so is the inverse distribution function. The so-called inversion method uses the latter to generate the corresponding distribution from a uniform random variable on [0,1), histograms being a special case. This paper shows how to manipulate the inverse histogram and an underlying marginally uniform process, so as to “shape” the model sample paths in an attempt to match the qualitative nature of the empirical sample paths, while maintaining a guaranteed match of the empirical marginal distribution. It proposes a new approach to temporal shaping of time series and identifies a number of operations on a piecewise-linear inverse histogram function, which leave the marginal distribution invariant. For cyclical processes with a prescribed marginal distribution and a prescribed cycle profile, one can also use these transformations to generate sample paths which “conform” to the profile. This approach also improves the ability to approximate the empirical autocorrelation function.

This paper considers a continuous-review, single-product, production-inventory system with a constant replenishment rate, compound Poisson demands, and lost sales. Two objective functions that represent metrics of operational costs are considered: (1) the sum of the expected discounted inventory holding costs and lost-sales penalties, both over an infinite time horizon, given an initial inventory level; and (2) the long-run time average of the same costs. The goal is to minimize these cost metrics with respect to the replenishment rate. It is, however, not possible to obtain closed-form expressions for the aforementioned cost functions directly in terms of positive replenishment rate (PRR). To overcome this difficulty, we construct a bijection from the PRR space to the space of positive roots of Lundberg's fundamental equation, to be referred to as the Lundberg positive root (LPR) space. This transformation allows us to derive closed-form expressions for the aforementioned cost metrics with respect to the LPR variable, in lieu of the PRR variable. We then proceed to solve the optimization problem in the LPR space and, finally, recover the optimal replenishment rate from the optimal LPR variable via the inverse bijection. For the special cases of constant or loss-proportional penalty and exponentially distributed demand sizes, we obtain simpler explicit formulas for the optimal replenishment rate.

MARM (Multivariate Autoregressive Modular) processes constitute a versatile class of multidimensional stochastic sequences which can exactly fit arbitrary multi-dimensional empirical histograms and approximately fit the leading empirical autocorrelations and cross-correlations. A companion paper (Part I) presented the general theory of MARM processes. This paper (Part II) proposes practical MARM modeling and forecasting methodologies of considerable generality, suitable for implementation on a computer. The purpose of Part II is twofold: (1) to specialize the general class of MARM processes to a practical subclass, called Empirically-Based MARM (EB-MARM) processes, suitable for modeling of empirical vector-valued time series, and devise the corresponding fitting and forecasting algorithms; and (2) to illustrate the efficacy of the EB-MARM fitting and forecasting algorithms. Specifically, we shall consider MARM processes with iid step-function innovation densities and distortions based on an empirical multi-dimensional histogram, as well as empirical autocorrelation and cross-correlation functions. Finally, we illustrate the efficacy of these methodologies with an example of a three-dimension time series vector, using a software environment, called MultiArmLab, which supports MARM modeling and forecasting.

This paper introduces a new class of real vector-valued stochastic processes, called MARM (Multivariate Autoregressive Modular) processes, which generalizes the class of (univariate) ARM (Autoregressive Modular) processes. Like ARM processes, the key advantage of MARM processes is their ability to fit a strong statistical signature consisting of first-order and second-order statistics. More precisely, MARM processes exactly fit an arbitrary multi-dimensional marginal distribution and approximately fit a set of leading autocorrelations and cross-correlations. This capability appears to render the MARM modeling methodology unique in its ability to fit a multivariate model to such a class of strong statistical signatures. The paper describes the construction of two flavors of MARM processes, MARM+ and MARM−, studies the statistics of MARM processes (transition structure and second order statistics), and devises MARM-based fitting and forecasting algorithms providing point estimators and confidence intervals. The efficacy of the MARM fitting and forecasting methodology will be illustrated on real-life data in a companion paper.

We consider a class of single-stage, single-product Make-to-Stock production-inventory system (MTS system) with backorders. The system employs a continuous-review base-stock policy which strives to maintain a prescribed base-stock level of inventory. In a previous paper of Zhao and Melamed (Methodology and Computing in Applied Probability 8:191–222, 2006), the Infinitesimal Perturbation Analysis (IPA) derivatives of inventory and backorders time averages with respect to the base-stock level and a parameter of the production-rate process were computed in Stochastic Fluid Model (SFM) setting, where the demand stream at the inventory facility and its replenishment stream from the production facility are modeled by stochastic rate processes. The advantage of the SFM abstraction is that the aforementioned IPA derivatives can be shown to be unbiased. However, its disadvantages are twofold: (1) on the modeling side, the highly abstracted SFM formulation does not maintain the identity of transactions (individual demands, orders and replenishments) and has no notion of lead times, and (2) on the applications side, the aforementioned IPA derivatives are brittle in that they contain instantaneous rates at certain hitting times which are rarely known, and consequently, need to be estimated. In this paper, we remedy both disadvantages by using a discrete setting, where transaction identity is maintained, and order fulfillment from inventory following demand arrivals and inventory restocking following replenishment arrivals are modeled as discrete jumps in the inventory level. We then compute the aforementioned IPA derivatives with respect to the base-stock level and a parameter of the lead-time process in the discrete setting under any initial system state. The formulas derived are shown to be unbiased and directly computable from sample path observables, and their computation is both simple and computationally robust.

This paper addresses Infinitesimal Perturbation Analysis (IPA) in the class of Make-to Stock (MTS) production-inventory systems with backorders under the continuous-review (R,r) policy, where R is the stock-up-to level and r is the reorder point. A system from this class is traditionally modeled as a discrete system with discrete demand arrivals at the inventory facility and discrete replenishment orders placed at the production facility. Here, however, we map an underlying discrete MTS system to a Stochastic Fluid Model (SFM) counterpart in which stochastic fluid-flow rate processes with piecewise constant sample paths replace the corresponding traditional discrete demand arrival and replenishment stochastic processes, under very mild regularity assumptions. The paper then analyzes the SFM counterpart and derives closed-form IPA derivative formulas of the time-averaged inventory level and time-averaged backorder level with respect to the policy parameters, R and r, and shows them to be unbiased. The obtained formulas are comprehensive in the sense that they are computed for any initial inventory state and any time horizon, and are simple and fast to compute. These properties hold the promise of utilizing IPA derivatives as an ingredient of offline design algorithms and online management and control algorithms of the class of systems under study.

This note applies the stochastic fluid model (SFM) paradigm to a class of single-stage, single-product make-to-stock (MTS) production-inventory systems with stochastic demand and random production capacity, where the finished-goods inventory is controlled by a continuous-time base-stock policy and unsatisfied demand is lost. This note derives formulas for infinitesimal perturbation analysis (IPA) derivatives of the sample-path time averages of the inventory level and lost sales with respect to the base-stock level and a parameter of the production rate process. These formulas are comprehensive in that they are exhibited for any initial inventory state, and include right and left derivatives (when they differ). The formulas are obtained via sample path analysis under very mild regularity assumptions, and are inherently nonparametric in the sense that no specific probability law need be postulated. It is further shown that all IPA derivatives under study are unbiased and fast to compute, thereby providing the theoretical basis for online adaptive control of MTS production-inventory systems.

Infinitesimal perturbation analysis (IPA) provides formulas for random gradients (derivatives) of performance measures with respect to parameters of interest, computed from sample paths of stochastic systems. In practice, IPA derivatives may be computed either from simulation runs or from empirical field data (when the formulas are nonparametric). Nonparametric IPA derivatives in fluid-flow queues have been recently derived for the loss volume and time average of buffer occupancy, with respect to buffer size, and arrival-rate or service-rate parameters. Additionally, these IPA derivatives have been shown to be unbiased in the sense that their expectation and differentiation operators commute, while their traditional discrete counterparts have long been known to be generally biased. Recent work has further shown how to map the computation of IPA derivatives from a fluid-flow queue to a compatible discrete counterpart without an appreciable loss of accuracy in performance measures. Thus, this work holds the promise of potential applications of IPA derivatives to gradient-based optimization of objective functions involving performance metrics parameterized by settable parameters in a queueing network context.This paper is an empirical study of IPA derivatives of individual queues within queueing systems which model telecommunications networks and some of their protocols. As a testbed, we used HNS (Hybrid Network Simulator) — a hybrid Java simulator of queueing networks with traffic streams subject to several telecommunications protocols. More specifically, the hybrid feature of HNS admits models with mixtures of discrete (packet) flows and continuous (fluid) flows, and collects detailed statistics and IPA derivatives for all flow types. The paper outlines the mapping of IPA derivatives from the fluid domain to the packet domain as implemented in HNS, and studies the accuracy of IPA derivatives in compatible fluid and packet queueing models, as well as the stabilization of their values in time. Our experimental results lend empirical support to the contention that IPA derivatives can be accurately computed from discrete versions by adopting a fluid-flow view. Furthermore, the long-run values of various IPA derivatives are empirically shown to stabilize quite fast. Finally, the results provide the basis and motivation for IPA applications to the optimization of telecommunications network design and to potential new open-loop protocols that take advantage of IPA information.

A call center is a facility for delivering telephone service, both incoming and outgoing. This paper addresses optimal staffing of call centers, modeled as M/G/n queues whose offered traffic consists of multiple customer streams, each with an individual priority, arrival rate, service distribution and grade of service (GoS) stated in terms of equilibrium tail waiting time probabilities or mean waiting times. The paper proposes a methodology for deriving the approximate minimal number of servers that suffices to guarantee the prescribed GoS of all customer streams. The methodology is based on an analytic approximation, called the Scaling-Erlang (SE) approximation, which maps the M/G/n queue to an approximating, suitably scaled M/G/1 queue, for which waiting time statistics are available via the Pollaczek-Khintchine formula in terms of Laplace transforms. The SE approximation is then generalized to M/G/n queues with multiple types of customers and non-preemptive priorities, yielding the Priority Scaling-Erlang (PSE) approximation. A simple goal-seeking search, utilizing SE/PSE approximations, is presented for the optimal staffing level, subject to GoS constraints. The efficacy of the methodology is demonstrated by comparing the number of servers estimated via the PSE approximation to their counterparts obtained by simulation. A number of case studies confirm that the SE/PSE approximations yield optimal staffing results in excellent agreement with simulation, but at a fraction of simulation time and space.

AutoRegressive Modular (ARM) processes are a new class of nonlinear stochastic processes, which can accurately model a large class of stochastic processes, by capturing the empirical distribution and autocorrelation function simultaneously. Given an empirical sample path, the ARM modeling procedure consists of two steps: a global search for locating the minima of a nonlinear objective function over a large parametric space, and a local optimization of optimal or near optimal models found in the first step. In particular, since the first task calls for the evaluation of the objective function at each vector of the search space, the global search is a time consuming procedure. To speed up the computations, parallelization of the global search can be effectively used by partitioning the search space among multiple processors, since the requisite communication overhead is negligible.This paper describes two space-partitioning methods, called Interleaving and Segmentation, respectively. The speedups resulting from these methods are compared for their performance in modeling real-life data.

ARM (Auto-Regressive Modular) processes constitute a broad class of nonlinear autoregressive schemes with modulo-1 reduction and additional transformations. Unlike their TES (Transform-Expand-Sample) precursors, which only admit iid innovation sequences, ARM processes admit dependent innovation sequences as well, so long as they are independent of the initial ARM variate. As such, the class of ARM processes constitutes a considerable generalization of the TES class, endowed with enhanced modeling flexibility. For example, a Markovian innovation sequence can model burstiness in traffic processes far better by making use of the Markovian state to capture the structure of bursts. This paper introduces ARM processes and derives their fundamental properties in terms of marginal distributions and autocorrelation functions. It defines several useful subclasses that illustrate the modeling flexibility of ARM classes. Finally, it outlines a modeling methodology of empirical time series that can simultaneously fit ...

In analyzing the output process generated by a steady-state simulation, we often seek to estimate the expected value of the output. The sample mean based on a finite sample of size n is usually the estimator of choice for the steady-state mean; and a measure of the sample mean's precision is the variance parameter, i.e., the limiting value of the sample size multiplied by the variance of the sample mean as n becomes large. This paper establishes asymptotic properties of the conventional batch-means (BM) estimator of the variance parameter as both the batch size and the number of batches become large. In particular, we show that the BM variance estimator is asymptotically unbiased and convergent in mean square. We also provide asymptotic expressions for the variance of the BM variance estimator. Exact and empirical examples illustrate our findings.

TES (transform-expand-sample) is a versatile class of stationary stochastic processes which can model arbitrary marginals, a wide variety of autocorrelation functions, and a broad range of sample path behaviors. TES parameters are of two kinds: the first kind is used for the exact fitting of the empirical distribution (histogram), while the second kind is used for approximating the empirical autocorrelation function. Parameters of the first kind are easy to determine algorithmically, but those of the second kind require a hard heuristic search on a large parametric function space. This paper describes an algorithmic procedure which can replace the heuristic search, thereby largely automating TES modeling. The algorithm is cast in nonlinear programming setting with the objective of minimizing a weighted sum of squared differences between the empirical autocorrelations and their candidate TES model counterparts. It combines a brute-forte search with steepest-descent nonlinear programming using Zoutendijk's feasible direction method. Finally, we illustrate the efficacy of our approach via three examples: two from the domain of VBR (variable bit rate) compressed video and one representing results from a laser intensity experiment. >

Regenerative simulation has become a familiar and established tool for simulation-based estimation. However, many applications (e.g., traffic in high-speed communications networks) call for autocorrelated stochastic models to which traditional regenerative theory is not directly applicable. Consequently, extensions of regenerative simulation to dependent time series is increasingly gaining in theoretical and practical interest, with Markov chains constituting an important case. Fortunately, a regenerative structure can be identified in Harris-recurrent Markov chains with minor modification, and this structure can be exploited for standard regenerative estimation. In this paper we focus on a versatile class of Harris-recurrent Markov chains, called TES (Transform-Expand-Sample). TES processes can generate a variety of sample paths with arbitrary marginal distributions, and autocorrelation functions with a variety of functional forms (monotone, oscillating and alternating). A practical advantage of TES processes is that they can simultaneously capture the first and second order statistics of empirical sample paths (raw field measurements). Specifically, the TES modeling methodology can simultaneously match the empirical marginal distribution (histogram), as well as approximate the empirical autocorrelation function. We explicitly identify regenerative structures in TES processes and proceed to address efficiency and accuracy issues of prospective simulations. To show the efficacy of our approach, we report on a TES/M/1 case study. In this study, we used the likelihood ratio method to calculate the mean waiting time performance as a function of the regenerative structure and the intrinsic TES parameter controlling burstiness (degree of autocorrelation) in the arrival process. The score function method was used to estimate the corresponding sensitivity (gradient) with respect to the service rate. Finally, we demonstrated the importance of the particular regenerative structure selected in regard to the estimation efficiency and accuracy induced by the regeneration cycle length.

TES (Transform-Expand-Sample) is a versatile class of stochastic sequences consisting of marginally uniform autoregressive schemes with modulo-1 reduction, followed by various transformations. TES modeling aims to fit a TES model to empirical records by simultaneously capturing both first-order and second-order properties of the empirical data In this paper we study the spectral properties of general TES processes and their component innovation sequences, thus generalizing the results reported in Jagerman and Melamed [9]. We derive formulas for the power spectral density function and the spectral distribution function which are suitable for efficient numerical computation, and exemplify them for TES processes with uniform and exponential marginals. The results contribute to the understanding of TES sequences as models of autocorrelated sequences, particularly in a Monte Carlo simulation context

Markov processes are an important ingredient in a variety of stochastic applications. Notable instances include queueing systems and traffic processes offered to them. This paper is concerned with Markovian traffic, i.e., traffic processes whose inter-arrival times (separating the time points of discrete arrivals) form a real-valued Markov chain. As such this paper aims to extend the classical results of renewal traffic, where interarrival times are assumed to be independent, identically distributed. Following traditional renewal theory, three functions are addressed: the probability of the number of arrivals in a given interval, the corresponding mean number, and the probability of the times of future arrivals. The paper derives integral equations for these functions in the transform domain. These are then specialized to a subclass, TES+, of a versatile class of random sequences, called TES (Transform-Expand-Sample), consisting of marginally uniform autoregressive schemes with modulo-1 reduction, followed by various transformations. TES models are designed to simultaneously capture both first-order and second-order statistics of empirical records, and consequently can produce high-fidelity models. Two theoretical solutions for TES+ traffic functions are derived: an operator-based solution and a matric solution, both in the transform domain. A special case, permitting the conversion of the integral equations to differential equations, is illustrated and solved. Finally, the results are applied to obtain instructive closed-form representations for two measures of traffic burstiness: peakedness and index of dispersion, elucidating the relationship between them.

The run statistics of a discrete-time, real-valued stochastic process are the statistics of process excursions above a given level. As such they are a special case of first passage times (hitting times) in discrete time. The study of run probabilities is motivated by applications such as compressed video, where a random and autocorrelated sequence of compressed frames arrives deterministically at a finite buffer, and the loss probability of consecutive frames (runs) constitutes a better measure of service quality than simple loss probabilities. This paper studies the run probabilities of a subclass of TES processes. A uniform TES process is a modulo-1 autoregressive stochastic process, uniform on [0,1); general TES processes are obtained by transforming a basic TES process to ones with general marginals. The paper develops an integral equation in the generating function of the run probabilities of TES processes. An exact matrix solution of theoretical interest is obtained, but the solution requires expens...

In this paper we establish a joint central limit theorem for customer and time averages by applying a martingale central limit theorem in a Markov framework. The limiting values of the two averages appear in the translation terms. This central limit theorem helps to construct confidence intervals for estimators and perform statistical tests. It thus helps determine which finite average is a more asymptotically efficient estimator of its limit. As a basis for testing for PASTA (Poisson arrivals see time averages), we determine the variance constant associated with the central limit theorem for the difference between the two averages when PASTA holds.

TES (Transform-Expand-Sample) is a versatile class of stochastic sequences which can capture arbitrary marginals and a wide variety of sample path behavior and autocorrelation functions. In TES, the initial variate is uniform on [0,1) and the next variate is obtained recursively by taking the fractional part (i.e., modulo-1 reduction) of a linear autoregressive scheme. We show how this class gives rise to uniform Markovian sequences in a general and natural way, by observing that marginal uniformity is closed under modulo-1 addition of an independent variate with arbitrary distribution. We derive the transition function of TES sequences and the autocovariance function of transformed TES sequences using Fourier and Laplace Transform methods. The autocovariance formulas are amenable to fast and accurate calculation and provide the theoretical basis for a computer-based methodology of heuristic TES modeling of empirical data. A companion paper contains various examples which show the efficacy of the TES appr...

This paper introduces a class of methods called TES (Transform-Expand-Sample) for generating autocorrelated variates with uniform marginals and Markovian structure. TES methods are readily implemented on a computer and have generation complexity comparable to that of the i.i.d. uniform sequence which they transform to an autocorrelated uniform sequence. For any prescribed correlation coefficient ρ, there is a TES method generating a uniform sequence with the 1-lag autocorrelation ρ, and the resultant autocorrelation is monotonic quadratic in two structural TES parameters. A simulation study reveals that TES methods give rise to autocorrelation functions with monotone decreasing as well as oscillating magnitude, bounded by monotone envelopes. The structural parameters were found to control the “amplitude” and “frequency” of the resultant autocorrelation function. A third parameter can be used to transform a TES sequence into more continuous-looking versions and to control the skewness of sample path cycles. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

We investigate when Arrivals See Time Averages (ASTA) in a stochastic model; i.e., when the stationary distribution of an embedded sequence, obtained by observing a continuous-time stochastic process just prior to the points (arrivals) of an associated point process, coincides with the stationary distribution of the observed process. We also characterize the relation between the two distributions when ASTA does not hold. We introduce a Lack of Bias Assumption (LBA) which stipulates that, at any time, the conditional intensity of the point process, given the present state of the observed process, be independent of the state of the observed process. We show that LBA, without the Poisson assumption, is necessary and sufficient for ASTA in a stationary process framework. Consequently, LBA covers known examples of non-Poisson ASTA, such as certain flows in open Jackson queueing networks, as well as the familiar Poisson case (PASTA). We also establish results to cover the case in which the process is observed just after the points, e.g., when departures see time averages. Finally, we obtain a new proof of the Arrival Theorem for product-form queueing networks.

Random numbers are used in simulation to sample realizations of random variables with prescribed distributions, as well as stochastic processes with prescribed probability laws. For instance, customer arrivals are often generated according to a Poisson processnamely, the interarrival times are iid exponential. (Equivalently, the number of arrivals obeys the appropriate Poisson distribution, but it is far more convenient to generate interarrival times in the simulation run.) Random numbers are generally produced via a random number generator (RNG) procedure, used to generate iid numbers that are uniformly distributed between 0 and 1. These numbers are often further transformed so as to conform to a prescribed distribution. For one thing, an RNG is a deterministic procedure whose generated number stream can always be recreated. An RNG is “random” in the sense that its random number sequence passes statistical tests for randomness, in this case the uniformity of the generated numbers and their mutual independence.

A study is made of the limiting behavior of averages from an embedded stochastic process obtained by sampling a discrete-time stochastic process at points of an associated discrete-time stochastic point process. It is determined when the limit of the averages from the embedded process coincides with the limit of the averages from the original process. In a certain stationary Markov framework, this happens if and only if the point process is a Bernoulli sequence with future points being independent of the state of the Markov process. >

PASTA (Poisson Arrivals See Time Averages) is a term coined by R. Wolff in his well known 1982 paper. In keeping with Wolff's terminology, we use the term anti-PASTA to refer to the following converse of PASTA. Given that arrivals do indeed see time averages, when must the arrival process necessarily be Poisson? We show that anti-PASTA is satisfied in a pure-jump Markov process, provided that the arrival process corresponds to a subset of the Markov process jumps.

TES (Transform-Expand-Sample) is a versatile class of stochastic sequences defined via an autoregressive scheme with modulo-1 reduction and additional transformations. The scope of TES encompasses a wide variety of sample path behaviors, which in turn give rise to autocorrelation functions with diverse functional forms - monotone, oscillatory, alternating, and others. TES sequences are readily generated on a computer, and their autocorrelation functions can be numerically computed from accurate analytical formulas at a modest computational cost.This paper presents the empirical TES modeling methodology which uses TES process theory to model empirical records. The novel feature of the TES methodology is that it expressly aims to simultaneously capture the empirical marginal distribution (histogram) and autocorrelation function. We draw attention to the non-parametric nature of TES modeling in that it always guarantees an exact match to the empirical marginal distribution. However, fitting the corresponding autocorrelation function calls for a heuristic search for a TES model over a large parametric space. Consequently, practical TES modeling of empirical records must currently rely on software assistance. A visual interactive software environment, called TEStool, has been designed and implemented to support TES modeling. The paper describes the empirical TES modeling methodology as implemented in TEStool and provides numerically-computable formulas for TES autocorrelations. Two examples illustrate the efficacy of the TES modeling approach. These examples serve to highlight the ability of TES models to capture first-order and second-order properties of empirical sample paths and to mimic their qualitative appearance.

This paper considers a regular Markov process with continuous parameter, countable state space, and stationary transition probabilities, and defines a class of traffic processes over it. The possibility that multiple traffic processes constitute mutually independent Poisson processes is investigated. A variety of independence conditions on a traffic process and the underlying Markov process are shown to lead to Poisson-related properties; these conditions include weak pointwise independence, and pointwise independence. Some examples of queueing-theoretic applications are given. For the class of traffic processes considered here in a queueing-theoretic context, Muntz's M M property, Gelenbe and Muntz's notion of completeness, and Kelly's notion of quasi-reversibility are shown to be essentially equivalent to pointwise independence of traffic and state. The relevance of the theory to queueing network decomposition is pointed out.

A Markov step process Z equipped with a possibly non-denumerable state space X can model a variety of queueing, communication and computer networks. The analysis of such networks can be facilitated if certain traffic flows consist of mutually independent Poisson processes with respective deterministic intensities λ i (t). Accordingly, we define the multivariate counting process N = (N 1, N 2, · ·· N c) induced by Z; a count in Ni occurs whenever Z jumps from x (χ into a (possibly empty) target set . We study N through the infinitesimal operator à of the augmented Markov process W = (Z, N), and the integral relationship connecting à with the transition operator T t of W. It is then shown that Ni depends on a non-negative function ri defined on χ; ri (x) may be interpreted as the expected rate of increase in Ni , given that Z is in state x. A multivariate N is Poisson (i.e., composed of mutually independent Poisson streams N i ) if and only if simultaneous jumps are impossible in a certain sense, and if the conditional expectation E[r i (Z(t) | 𝒩 i ] = E[r i (Z(t))] for i = 1, 2, ···, c and each t ≧ 0, where 𝒩 i is the σ-algebra σ{N(s), s ≦ t}. Necessary and sufficient conditions are also specified that, for each s ≦ t, the variates [N i (t)-N i (s)] are mutually independent Poisson distributed; this involves a weakened version of E[r i (Z(v)) | N(v) – N(u)] = E [r i (Z(v))] for i = 1, 2, ···, c and all 0 ≦ u ≦ v. It is shown that the above criteria are automatically met by the more stringent classical requirement that N(t) and Z(t) be independent for each t ≧ 0.

Consider a counting process {N(t)>0}. In the one-dimensional case it is shown that the set of distributions of N(t) for t>0. This result is a "marginal"version of the characterization of a point process by its stochastic intensity. It is shown that the correspondng results have to be modifed in the multi-dimensional case. These results are particularized to the case of point processes with Poisson marginals.

We consider a queueing network with types of customers. Poisson arrivals, type dependent routing and state dependent service. A number of stochastic aspects relating to sojourn times are investigated. Included are limiting state distributions imbedded at customer move times, mean sojourn times, and sojourn time distributions along overtake-free paths. It is shown that Reich's results extend to overtake-free paths yielding limiting sojourn time distributions which correspond to the sum of exponential independent stages of sojourn in individual nodes. The analysis is bused solely on considerations of population distributions through conditioning on customers' itineraries in the network.

The equilibrium behavior of Jackson queueing networks (Poisson arrivals, exponential servers and Bernoulli switches) has recently been investigated in some detail. In particular, it was found that in equilibrium, the traffic processes on the so-called exit arcs of a Jackson network with single server nodes constitute Poisson processes—a result extending Burke's theorem from single queues to networks of queues. A conjecture made by Burke and others contends that the traffic processes on non-exit arcs cannot be Poisson in equilibrium. This paper proves this conjecture to be true for a variety of Jackson networks with single server nodes. Subsequently, a number of characterizations of the equilibrium traffic streams on the arcs of open Jackson networks emerge, whereby Poisson-related stochastic properties of traffic streams are shown to be equivalent to a simple graph-theoretical property of the underlying arcs. These results then help to identify some inherent limitations on the feasibility of equilibrium decompositions of Jackson networks, and to point out conditions under which further decompositions are ‘approximately’ valid.

This paper proposes a methodology for computing numerical bounds on cumulative-time (i.e., the time spent in a specified set of states before entering another specified set of states) distributions over discrete state Markov processes. The methodology uses randomization procedures to compute results for appropriately defined transient Markov processes; the transient distribution computed is equivalent to the requisite cumulative-time distribution. A queueing application of the methodology to delay times in queueing networks is outlined and its efficacy is appraised by comparing the results with a sojourn time for a problem with a known distribution.

The three node Jackson queueing network is the simplest acyclic network in which in equilibrium the sojourn times of a customer at each of the nodes are dependent. We show that assuming the individual sojourn times are independent provides a good approximation to the total sojourn time. This is done by simulating the network and showing that the sojourn times generally pass a Kolmogorov-Smirnov test as having come from the approximating distribution. Since the sum of dependent random variables may have the same distribution as the sum of independent random variables with the same marginal distributions, it is conceivable that our approximation is exact. However, we numerically compute upper and lower bounds for the distribution of the total sojourn time; these bounds are so close that the approximating distribution lies outside of the bounds. Thus, the bounds are accurate enough to distinguish between the two distributions even though the Kolmogorov-Smirnov test generally cannot.

This paper relates the reversibility of certain discrete state Markovian queueing networks — the class of quasi-reversible networks — to the reversibility of the underlying switching process. Quasi-reversible networks are characterized by a product form equilibrium state distribution. When the state can be represented by customer totals at each node, the reversibility of the state process is equivalent to the reversibility of the switching process. More complicated quasi-reversible networks require additional conditions, to ensure the reversibility of the network state process.

In a previous paper Yamazaki et al. (Yamazaki, G., T. Kawashima, H. Sakasegawa. 1983. Reversibility of tandem blocking queueing systems. Kogakuin University, Tokyo, Japan.) prove that a certain tandem blocking queueing system and its reversed counterpart have the same capacity (throughput). The purpose of this note is to offer an alternative viewpoint based on a concept of duality. This leads to a more intuitive methodology and provides additional insight into the original and reversed systems.

A Markov step process Z equipped with a possible non-denumerable state space x can model a variety of queueing, communication and computer networks. The analysis of such networks can be facilitated if certain traffic flows consist of mutually independent Poisson processes. A multivariate N is Poisson (i.e., composed of mutually independent Poisson streams N sub i) if each r sub i (Z) is stationary, and r sub i(Z(t)) is independent of N(t) for each i and each t greater than or = 0. The latter is already much less restrictive than the independent of N(t) and Z(t), but it is able to find even weaker hypotheses which are both necessary and sufficient for N to be Poisson.

Let {Xt}t>0 be a Markov jump process and {Tn}n=0∞ a subset of the jump epochs of the process {Xt}t>0. The main results of this paper are computable formulae for the transient and invariant distributions of {XTn}n=0∞ and {XTn̄}n=0∞. We also characterize when the invariant distributions of {Xt}t>0 and {XTn}n=0∞ are the same and show that in this case {Tn}n=0∞ is a Poisson process. The results are applied to a variety of discrete-slate queueing networks to obtain their state distribution as seen by customers in arrival streams, departure streams, and traffic streams on the arcs. The main conclusion drawn is that for many traffic streams, the invariant distribution seen by customers in that stream coincides with the invariant distribution of {Xt}t>0 provided the customer in motion is excluded.

P. J. Burke and E. Reich independently showed the output of a M/M/1 queue in equilibrium to be a Poisson process. Consequently, analysis of tandem exponential servers with a Poisson input stream can be reduced to consideration of a series of M/M/1 queues. This work generalizes the above results to so-called Jackson networks, which consists of exponential servers with mutually independent Poisson exogenous inputs and random customer routings permitting customer feedback. The authors prove that traffic on all exit arcs is Poisson; moreover, the customer streams leaving any exit set are mutually independent.