A simple formula for mean multiplexing delay for independent regenerative sources

Simple expressions are given for the mean delay, mean waiting time, and mean busy period length in a multiplexer. Data streams with active periods having a general distribution are permitted, and the data rate during the active periods can be random. Data can also arrive in batches. The key restrictions of the model are that the sources are independent, idle periods are exponentially distributed, and a source generates at least enough data during an active period to keep the server busy throughout the period. The exact formulas allow evaluation of the error in approximations such as a heavy traffic diffusion approximation.Both continuous and discrete time models are considered. The discrete-time model includes that studied by Viterbi and subsequently generalized by Neuts. The Pollaczek-Khinchine formula for the mean amount of work in anM/GI/1 queue is retrieved as a limiting case.Preliminary version presented at IEEE INFOCOM, San Francisco, April 1993.     

Image space analysis of generalized fractional programs

The solution of a particular nonconvex program is usually very dependent on the structure of the problem. In this paper we identify classes of nonconvex problems involving either sums or products of ratios of linear terms which may be treated by analysis in a transformed space. In each class, the image space is defined by a mapping which associates a new variable with each original ratio of linear terms. In the image space, optimization is easy in certain directions, and the overall solution may be realized by sequentially optimizing in these directions.In addition to these ratio problems, we also show how to use image space analysis to treat the subclass of problems whose objective is to optimize a product of linear terms. For each class of nonconvex problems, we present an algorithm that locates global solutions by computing both upper and lower bounds on the solution and then solving a sequence of linear programming sub-problems. We also demonstrate the algorithms described in this paper by solving several example problems.     

Political aspects of environmental policy

To the economist, many environmental problems are really allocation problems which can be solved by means of market prices that should approximate the shadow prices of environmental restrictions. Why is it so difficult to implement the corresponding institutional arrangements politically?     

The distribution of the likelihood ratio for mixtures of densities from the one-parameter exponential family

We here consider testing the hypothesis ofhomogeneity against the alternative of a two-component mixture of densities. The paper focuses on the asymptotic null distribution of 2 log _n , where _n is the likelihood ratio statistic. The main result, obtained by simulation, is that its limiting distribution appears pivotal (in the sense of constant percentiles over the unknown parameter), but model specific (differs if the model is changed from Poisson to normal, say), and is not at all well approximated by the conventional ₍₂₎ ² -distribution obtained by counting parameters. In Section 3, the binomial with sample size parameter 2 is considered. Via a simple geometric characterization the case for which the likelihood ratio is 1 can easily be identified and the corresponding probability is found. Closed form expressions for the likelihood ratio _n are possible and the asymptotic distribution of 2 log _n is shown to be the mixture giving equal weights to the one point distribution with all its mass equal to zero and the ²-distribution with 1 degree of freedom. A similar result is reached in Section 4 for the Poisson with a small parameter value (0.1), although the geometric characterization is different. In Section 5 we consider the Poisson case in full generality. There is still a positive asymptotic probability that the likelihood ratio is 1. The upper precentiles of the null distribution of 2 log _n are found by simulation for various populations and shown to be nearly independent of the population parameter, and approximately equal to the (1–2)100 percentiles of ₍₁₎ ² . In Sections 6 and 7, we close with a study of two continuous densities, theexponential and thenormal with known variance. In these models the asymptotic distribution of 2 log _n is pivotal. Selected (1–) 100 percentiles are presented and shown to differ between the two models.     

Zero-sum stochastic games with unbounded costs: Discounted and average cost cases

Zero-sum stochastic games with countable state space and with finitely many moves available to each player in a given state are treated. As a function of the current state and the moves chosen, player I incurs a nonnegative cost and player II receives this as a reward. For both the discounted and average cost cases, assumptions are given for the game to have a finite value and for the existence of an optimal randomized stationary strategy pair. In the average cost case, the assumptions generalize those given in Sennott (1993) for the case of a Markov decision chain. Theorems of Hoffman and Karp (1966) and Nowak (1992) are obtained as corollaries. Sufficient conditions are given for the assumptions to hold. A flow control example illustrates the results.     

Optimal control of infinite-dimensional uncertain systems

In this paper, we consider a minimax problem of optimal control for a class of strongly nonlinear uncertain evolution equations on a Banach space. We prove the existence of optimal controls. A nontrivial example of a class of systems governed by a nonlinear partial differential equation with uncertain spatial parameters is presented for illustration.This work was supported in part by the National Science and Engineering Research Council of Canada under Grant No. A7109 and The Engineering Faculty Development Fund, University of Ottawa.The authors would like to thank the anonymous reviewers for their valuable comments and suggestions.     

Single-server queues with spatially distributed arrivals

Consider a queueing system where customers arrive at a circle according to a homogeneous Poisson process. After choosing their positions on the circle, according to a uniform distribution, they wait for a single server who travels on the circle. The server's movement is modelled by a Brownian motion with drift. Whenever the server encounters a customer, he stops and serves this customer. The service times are independent, but arbitrarily distributed. The model generalizes the continuous cyclic polling system (the diffusion coefficient of the Brownian motion is zero in this case) and can be interpreted as a continuous version of a Markov polling system. Using Tweedie's lemma for positive recurrence of Markov chains with general state space, we show that the system is stable if and only if the traffic intensity is less than one. Moreover, we derive a stochastic decomposition result which leads to equilibrium equations for the stationary configuration of customers on the circle. Steady-state performance characteristics are determined, in particular the expected number of customers in the system as seen by a travelling server and at an arbitrary point in time.     

Rational choice based on vague preferences

This paper studies vague preferences. In contrast to the concept of fuzzy preferences, the more general notion of vague preferences does not entail the assumption that the different degrees of preference are completely ordered. It is shown that the more general concept of a vague preference order arises very naturally in the context of aggregating a set of (exact) weak orders. Furthermore, necessary and sufficient conditions for the rationalizability of an exact choice function by means of a vague preference order are given. It turns out that in the general case these conditions are weaker than in the case where the degrees of preference are completely ordered. Consequently, there exist choice functions which are rationalizable by a general vague preference order but which are not rationalizable by a fuzzy preference order, or more generally by any vague preference order which induces a complete ranking of the degrees of preference. Examples of such choice functions are provided.This is a revised version of a discussion paper which was written at the University of Karlsruhe. I am grateful to Georg Bol and an anonymous referee for valuable comments. The research has been made possible by a fellowship of the DFG (Deutsche Forschungsgemeinschaft) which is also gratefully acknowledged.     

Rate conservation laws: A survey

We survey the rate conservation law, RCL for short, arising in queues and related stochastic models. RCL was recognized as one of the fundamental principles to get relationships between time and embedded averages such as the extended Little's formulaH=G, but we show that it has other applications. For example, RCL is one of the important techniques for deriving equilibrium equations for stochastic processes. It is shown that the various techniques, including Mecke's formula for a stationary random measure, can be formulated as RCL. For this purpose, we start with a new definition of the rate with respect to a random measure, and generalize RCL by using it. We further introduce the notion of quasi-expectation, which is a certain extension of the ordinary expectation, and derive RCL applicable to the sample average results. It means that the sample average formulas such asH=G can be obtained as the stationary RCL in the quasi-expectation framework. We also survey several extensions of RCL and discuss examples. Throughout the paper, we would like to emphasize how results can be easily obtained by using a simple principle, RCL.     

Non-Cayley Vertex-Transitive Graphs of Order Twice the Product of Two Odd Primes

For a positive integer n, does there exist a vertex-transitive graph Γ on n vertices which is not a Cayley graph, or, equivalently, a graph Γ on n vertices such that Aut Γ is transitive on vertices but none of its subgroups are regular on vertices? Previous work (by Alspach and Parsons, Frucht, Graver and Watkins, Marusic and Scapellato, and McKay and the second author) has produced answers to this question if n is prime, or divisible by the square of some prime, or if n is the product of two distinct primes. In this paper we consider the simplest unresolved case for even integers, namely for integers of the form n = 2pq, where 2 < q < p, and p and q are primes. We give a new construction of an infinite family of vertex-transitive graphs on 2pq vertices which are not Cayley graphs in the case where p ≡ 1 (mod q). Further, if p ? 1 (mod q), p ≡ q ≡ 3(mod 4), and if every vertex-transitive graph of order pq is a Cayley graph, then it is shown that, either 2pq = 66, or every vertex-transitive graph of order 2pq admitting a transitive imprimitive group of automorphisms is a Cayley graph.