A recursive method for the F-policy G/M/1/K queueing system with an exponential startup time

This paper deals with the optimal control of a finite capacity G/M/1 queueing system combined the F-policy and an exponential startup time before start allowing customers in the system. The F-policy queueing problem investigates the most common issue of controlling arrival to a queueing system. We provide a recursive method, using the supplementary variable technique and treating the supplementary variable as the remaining interarrival time, to develop the steady-state probability distribution of the number of customers in the system. We illustrate a recursive method by presenting three simple examples for exponential, 3-stage Erlang, and deterministic interarrival time distributions, respectively. A cost model is developed to determine the optimal management F-policy at minimum cost. We use an efficient Maple computer program to determine the optimal operating F-policy and some system performance measures. Sensitivity analysis is also studied.     

The Transform Likelihood Ratio Method for Rare Event Simulation with Heavy Tails

We present a novel method, called the transform likelihood ratio (TLR) method, for estimation of rare event probabilities with heavy-tailed distributions. Via a simple transformation (change of variables) technique the TLR method reduces the original rare event probability estimation with heavy tail distributions to an equivalent one with light tail distributions. Once this transformation has been established we estimate the rare event probability via importance sampling, using the classical exponential change of measure or the standard likelihood ratio change of measure. In the latter case the importance sampling distribution is chosen from the same parametric family as the transformed distribution. We estimate the optimal parameter vector of the importance sampling distribution using the cross-entropy method. We prove the polynomial complexity of the TLR method for certain heavy-tailed models and demonstrate numerically its high efficiency for various heavy-tailed models previously thought to be intractable. We also show that the TLR method can be viewed as a universal tool in the sense that not only it provides a unified view for heavy-tailed simulation but also can be efficiently used in simulation with light-tailed distributions. We present extensive simulation results which support the efficiency of the TLR method.     

On φ-Families of Probability Distributions

We generalize the exponential family of probability distributions. In our approach, the exponential function is replaced by a φ-function, resulting in a φ-family of probability distributions. We show how φ-families are constructed. In a φ-family, the analogue of the cumulant-generating function is a normalizing function. We define the φ-divergence as the Bregman divergence associated to the normalizing function, providing a generalization of the Kullback–Leibler divergence. A formula for the φ-divergence where the φ-function is the Kaniadakis κ-exponential function is derived.     

Tree Complexity and a Doubly Exponential Gap between Structured and Random Sequences

This paper introduces a new complexity measure for binary sequences, the tree complexity. The tree complexity of a sequence grows asymptotically likeO(2^2h) (hthe height of the tree) for random sequences. Functions inF₂[[x]] can be identified with their coefficient sequence. Under this aspect we will show that the tree complexity isO(1) for all algebraic sequences inF^∞₂. This doubly exponential gap may serve as an indicator of “simply” structured sequences and furthermore it defines certain classes within the vast set of transcendental sequences.     

Bound on integrals: Elimination of the dual and reduction of the number of equality constraints

Let L_j (j = 1, …, n + 1) be real linear functions on the convex set $\text{F}$ of probability distributions. We consider the problem of maximization of L_n+1(F) under the constraint F ? $\text{F}$ and the equality constraints L₁(F) = z₁ (i = 1, …, n). Incorporating some of the equality constraints into the basic set $\text{F}$, the problem is equivalent to a problem with less equality constraints. We also show how the dual problems can be eliminated from the statement of the main theorems and we give a new illuminating proof of the existence of particular solutions.The linearity of the functions L_j(j = 1, …, n + 1) can be dropped in several results.     

On the strength of the finite intersection principle

We study the logical content of several maximality principles related to the finite intersection principle (FIP) in set theory. Classically, these are all equivalent to the axiom of choice, but in the context of reverse mathematics their strengths vary: some are equivalent to ACA₀ over RCA₀, while others are strictly weaker and incomparable with WKL₀. We show that there is a computable instance of FIP every solution of which has hyperimmune degree, and that every computable instance has a solution in every nonzero c.e. degree. In particular, FIP implies the omitting partial types principle (OPT) over RCA₀. We also show that, modulo Σ ₂ ⁰ induction, FIP lies strictly below the atomic model theorem (AMT).     

On the Monte carlo boolean decision tree complexity of read-once formulae

In the boolean decision tree model there is at least a linear gap between the Monte Carlo and the Las Vegas complexity of a function depending on the error probability. We prove for a large class of read-once formulae that this trivial speed-up is the best that a Monte Carlo algorithm can achieve. For every formula F belonging to that class we show that the Monte Carlo complexity of F with two-sided error p is (1 ? 2p)R(F), and with one-sided error p is (1 ? p)R(F), where R(F) denotes the Las Vegas complexity of F. The result follows from a general lower bound that we derive on the Monte Carlo complexity of these formulae. This bound is analogous to the lower bound due to Saks and Wigderson on their Las Vegas complexity.     

Breaking the rhythm on graphs

We study graph colorings avoiding periodic sequences with large number of blocks on paths. The main problem is to decide, for a given class of graphs F, if there are absolute constants t,k such that any graph from the class has a t-coloring with no k identical blocks in a row appearing on a path. The minimum t for which there is some k with this property is called the rhythm threshold of F, denoted by t(F). For instance, we show that the rhythm threshold of graphs of maximum degree at most d is between (d+1)/2 and d+1. We give several general conditions for finiteness of t(F), as well as some connections to existing chromatic parameters. The question whether the rhythm threshold is finite for planar graphs remains open.     

Set covering location models with stochastic critical distances

This paper formulates a new version of set covering models by introducing a customer-determined stochastic critical distance. In this model, all services are provided at the sites of facilities, and customers have to go to the facility sites to obtain the services. Due to the randomness of their critical distance, customers patronize a far or near facility with a probability. The objective is to find a minimum cost set of facilities so that every customer is covered by at least one facility with an average probability greater than a given level α. We consider an instance of the problem by embedding the exponential effect of distance into the model. An algorithm based on two searching paths is proposed for solutions to the instance. Experiments show that the algorithm performs well for problems with greater α, and the experimental results for smaller α are reported and analysed.     

A new technique for obtaining diophantine representations via elimination of bounded universal quantifiers

M. Davis proved in the early 1950s that every recursively enumerable set has an arithmetic representation with a unique bounded universal quantifier, known today as the Davis normal form. Davis, H. Putnam, and J. Robinson showed in 1961 how the Davis normal form can be transformed into a purely existential exponential Diophantine representation which uses not only addition and multiplication, but also exponentiation. The present author eliminated the exponentiation in 1970 and thus obtained the unsolvability of Hilbert's tenth problem. The paper presents a new method for transforming the Davis normal form into the exponential Diophantine representation. Bibliography: 12 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 220, 1995, pp. 83–92. Original article Translated by Yu. V. Matiyasevich. The research described in this work was made possible in part by Grant No. 94-01-01030 from the Russsian Foundation for Fundamental Research and Grant No. R43000 from the International Science Foundation.     

Exact algorithms for the Hamiltonian cycle problem in planar graphs

We construct an exact algorithm for the Hamiltonian cycle problem in planar graphs with worst case time complexity , where c is some fixed constant that does not depend on the instance. Furthermore, we show that under the exponential time hypothesis, the time complexity cannot be improved to .     

Inequalities for characteristic functions of multidimensional distributions

We obtain lower and upper bounds for the absolute values of characteristic functions of multivariate distributions F and also derive a lower bound on the norm of the zeroes of a characteristic function in terms of moments of the norm of the random vector with distribution F. Similar results are obtained for characteristic functions of probability measures on a separable Hilbert space.     

Towards finite-fold Diophantine representations

The celebrated theorem established by Martin Davis, Hilary Putnam, and Julia Robinson in 1961 states that every effectively enumerable set of natural numbers has an exponential Diophantine representation. This theorem was improved by the author in two ways:

Space complexity of random formulae in resolution

We study the space complexity of refuting unsatisfiable random k-CNFs in the Resolution proof system. We prove that for Δ ≥ 1 and any ϵ > 0, with high probability a random k-CNF over n variables and Δn clauses requires resolution clause space of Ω(n/Δ^1+ϵ). For constant Δ, this gives us linear, optimal, lower bounds on the clause space. One consequence of this lower bound is the first lower bound for size of treelike resolution refutations of random 3-CNFs with clause density Δ ≫ n. This bound is nearly tight. Specifically, we show that with high probability, a random 3-CNF with Δn clauses requires treelike refutation size of exp(Ω(n/Δ^1+ϵ)), for any ϵ > 0. Our space lower bound is the consequence of three main contributions: (1) We introduce a 2-player Matching Game on bipartite graphs G to prove that there are no perfect matchings in G. (2) We reduce lower bounds for the clause space of a formula F in Resolution to lower bounds for the complexity of the game played on the bipartite graph G(F) associated with F. (3) We prove that the complexity of the game is large whenever G is an expander graph. Finally, a simple probabilistic analysis shows that for a random formula F, with high probability G(F) is an expander. We also extend our result to the case of G-PHP, a generalization of the Pigeonhole principle based on bipartite graphs G. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 92–109, 2003     

Embedding optimal transports in statistical manifolds

We consider Monge-Kantorovich optimal transport problems on ? ^d , d ≥ 1, with a convex cost function given by the cumulant generating function of a probability measure. Examples include theWasserstein-2 transport whose cost function is the square of the Euclidean distance and corresponds to the cumulant generating function of the multivariate standard normal distribution. The optimal coupling is usually described via an extended notion of convex/concave functions and their gradient maps. These extended notions are nonintuitive and do not satisfy useful inequalities such as Jensen’s inequality. Under mild regularity conditions, we show that all such extended gradient maps can be recovered as the usual supergradients of a nonnegative concave function on the space of probability distributions. This embedding provides a universal geometry for all such optimal transports and an unexpected connection with information geometry of exponential families of distributions.     

On the transversal number and VC-dimension of families of positive homothets of a convex body

Let F be a family of positive homothets (or translates) of a given convex body K in Rⁿ. We investigate two approaches to measuring the complexity of F. First, we find an upper bound on the transversal number τ(F) of F in terms of n and the independence number ν(F). This question is motivated by a problem of Grünbaum [L. Danzer, B. Grünbaum, V. Klee, Helly’s theorem and its relatives, in: Proc. Sympos. Pure Math., vol. VII, Amer. Math. Soc., Providence, RI, 1963, pp. 101-180]. Our bound is exponential in n, an improvement from the previously known bound of Kim, Nakprasit, Pelsmajer and Skokan [S.-J. Kim, K. Nakprasit, M.J. Pelsmajer, J. Skokan, Transversal numbers of translates of a convex body, Discrete Math. 306 (18) (2006) 2166-2173], which was of order nⁿ. By a lower bound, we show that the right order of magnitude is exponential in n.Next, we consider another measure of complexity, the Vapnik-?ervonenkis dimension of F. We prove that vcdim(F)≤3 if n=2 and is infinite for some F if n≥3. This settles a conjecture of Grünbaum [B. Grünbaum, Venn diagrams and independent families of sets, Math. Mag. 48 (1975) 12-23]: Show that the maximum dual VC-dimension of a family of positive homothets of a given convex body K in Rⁿ is n+1. This conjecture was disproved by Naiman and Wynn [D.Q. Naiman, H.P. Wynn, Independent collections of translates of boxes and a conjecture due to Grünbaum, Discrete Comput. Geom. 9 (1) (1993) 101-105] who constructed a counterexample of dual VC-dimension . Our result implies that no upper bound exists.     

Free continuous actions on zero-dimensional spaces

We show that every countably infinite group admits a free, continuous action on the Cantor set having an invariant probability measure. We also show that every countably infinite group admits a free, continuous action on a non-homogeneous compact metric space and the action is minimal (that is to say, every orbit is dense). In answer to a question posed by Giordano, Putnam and Skau, we establish that there is a continuous, minimal action of a countably infinite group on the Cantor set such that no free continuous action of any group gives rise to the same equivalence relation.     

Economic application in a finite capacity multi-channel queue with second optional channel

We consider a finite capacity M/M/R queue with second optional channel. The interarrival times of arriving customers follow an exponential distribution. The service times of the first essential channel and the second optional channel are assumed to follow an exponential distribution. As soon as the first essential service of a customer is completed, a customer may leave the system with probability (1 − θ) or may opt for the second optional service with probability θ (0 ? θ ? 1). Using the matrix-geometric method, we obtain the steady-state probability distributions and various system performance measures. A cost model is established to determine the optimal solutions at the minimum cost. Finally, numerical results are provided to illustrate how the direct search method and the tabu search can be applied to obtain the optimal solutions. Sensitivity analysis is also investigated.     

Optimal Control of an M/G/1/K Queueing System with Combined <Emphasis Type="Italic">F</Emphasis> Policy and Startup Time

We investigate the optimal management problem of an M/G/1/K queueing system with combined F policy and an exponential startup time. The F policy queueing problem investigates the most common issue of controlling the arrival to a queueing system. We present a recursive method, using the supplementary variable technique and treating the supplementary variable as the remaining service time, to obtain the steady state probability distribution of the number of customers in the system. The method is illustrated analytically for exponential service time distribution. A cost model is established to determine the optimal management F policy at minimum cost. We use an efficient Maple computer program to calculate the optimal value of F and some system performance measures. Sensitivity analysis is also investigated.     

Cost analysis of the <Emphasis Type="Italic">R</Emphasis>-unloader queueing system

This paper deals with an unloader queueing model in which N identical trailers are unloaded by one or more unloaders. Theoretical solutions are obtained with the assumption of negative exponential distributions for trip times, unloading times, and finishing times. A cost model is developed to determine the optimal number of trailers. In order to evaluate the model robustness, simulation models are developed for three different distributions, exponential, second-order Erlang, and triangular. We demonstrate, through simulation results, that the unloader queueing model is sufficiently robust to the variations of probability distributions.