The expected value of some functions of the convex hull of a random set of points sampled inR d

This paper presents formulas and asymptotic expansions for the expected number of vertices and the expected volume of the convex hull of a sample ofn points taken from the uniform distribution on ad-dimensional ball. It is shown that the expected number of vertices is asymptotically proportional ton ^{(d−1)/(d+1)}, which generalizes Rényi and Sulanke’s asymptotic raten ^(1/3) ford=2 and agrees with Raynaud’s asymptotic raten ^{(d−1)/(d+1)} for the expected number of facets, as it should be, by Bárány’s result that the expected number ofs-dimensional faces has order of magnitude independent ofs. Our formulas agree with the ones Efron obtained ford=2 and 3 under more general distributions. An application is given to the estimation of the probability content of an unknown convex subset ofR ^d .     

Grassmannian Fixed Point Ratios

We provide estimates for the fixed point ratios in the permutation representations of a finite classical group over a field of order q on k-subspaces of its natural n-dimensional module. For sufficiently large n, each element must either have a negligible ratio or act linearly with a large eigenspace. We obtain an asymptotic estimate in the latter case, which in most cases is q ^–dk where d is the codimension of the large eigenspace. The results here are tailored for our forthcoming proof of a conjecture of Guralnick and Thompson on composition factors of monodromy groups.     

Dynamic Routing and Admission Control in High-Volume Service Systems: Asymptotic Analysis via Multi-Scale Fluid Limits

Motivated by applications in telephone call centers, we consider a service system model with m customer classes and r server pools. The model is one with doubly stochastic arrivals, which means that the m-vector λ of instantaneous arrival rates is allowed to vary both temporally and stochastically. Two levels of dynamic control are considered: customers may be either blocked or accepted at the time of their arrival, and then accepted customers of each class must be routed, either immediately upon acceptance or after some period of waiting, to a server pool that is qualified to handle that class. Customers who are made to wait before commencement of their service are liable to defect. The objective is to minimize the expected sum of blocking costs, waiting costs and defection costs over a fixed and finite planning horizon. We consider an asymptotic parameter regime in which (i) the arrival rates, service rates and defection rates are uniformly accelerated by a large factor κ, then (ii) arrival rates are increased by an additional factor g(κ), and the number of servers in each pool is increased by g(κ) as well. This produces a separation of time scales, justifying a pointwise stationary stochastic fluid approximation for our original system model. In the stochastic fluid approximation, optimal admission control and routing decisions are determined by a simple linear program that uses the current arrival rate vector λ as data. We explain how to implement the fluid model's optimal control policy in our original service system context, and prove that the proposed implementation is asymptotically optimal in the first-order sense. AMS subject classification: 60K30, 90B15, 90B36     

A continuous method for computing bounds in integer quadratic optimization problems

In the graph partitioning problem, as in other NP-hard problems, the problem of proving the existence of a cut of given size is easy and can be accomplished by exhibiting a solution with the correct value. On the other hand proving the non-existence of a cut better than a given value is very difficult. We consider the problem of maximizing a quadratic function x ^T Q x where Q is an n × n real symmetric matrix with x an n-dimensional vector constrained to be an element of {–1, 1} ⁿ . We had proposed a technique for obtaining upper bounds on solutions to the problem using a continuous approach in [4]. In this paper, we extend this method by using techniques of differential geometry.     

Amalgamation in finite dimensional cylindric algebras

For every finite n > 1, the embedding property fails in the class of all n-dimensional cylindric type algebras which satisfy the following. Their boolean reducts are boolean algebras and two of the cylindrifications are normal, additive and commute. This result also holds for all subclasses containing the representable n-dimensional cylindric algebras. This considerably strengthens a result of S. Comer on CA _n and provides a strong counterexample for interpolation in finite variable fragments of first order logic. We provide a new modern proof, using an argument inspired by modal logic. February 22, 1999.     

Asymptotic Analysis of Two Coupled Queues with Vastly Different Arrival Rates and Finite Customer Capacities

We consider two coupled queues, with each having a finite capacity of customers. When both queues are nonempty they evolve independently, but when one becomes empty the service rate in the other changes. Such a model corresponds to a generalized processor sharing (GPS) discipline. We study the joint distribution p(m, n) of finding (m, n) customers in the (first, second) queue, in the steady state. We study the problem in an asymptotic limit of “heavy traffic,” where also the arrival rate to the second queue is assumed to be small relative to that of the first. The capacity of the first queue is scaled to be large, while that of the second queue is held constant. We consider several different scalings, and in each case obtain limiting differential and/or difference equation for p(m, n), and these we explicitly solve. We show that our asymptotic approximations are quite accurate numerically. This work supplements previous investigations into this GPS model, which assumed infinite capacities/buffers. The present model corresponds to a random walk in a lattice rectangle, where p(m, n) satisfies a different boundary condition on each edge.     

On the Discrepancy for Boxes and Polytopes

 We consider so-called Tusnády’s problem in dimension d: Given an n-point set P in R ^d , color the points of P red or blue in such a way that for any d-dimensional interval B, the number of red points in differs from the number of blue points in by at most Δ, where should be as small as possible. We slightly improve previous results of Beck, Bohus, and Srinivasan by showing that , with a simple proof. The same asymptotic bound is shown for an analogous problem where B is allowed to be any translated and scaled copy of a fixed convex polytope A in R ^d . Here the constant of proportionality depends on A and we give an explicit estimate. The same asymptotic bounds also follow for the Lebesgue-measure discrepancy, which improves and simplifies results of Beck and of Károlyi.     

Monotonicity of the cd-index for polytopes

We prove that the cd-index of a convex polytope satisfies a strong monotonicity property with respect to the cd-indices of any face and its link. As a consequence, we prove for d-dimensional polytopes a conjecture of Stanley that the cd-index is minimized on the d-dimensional simplex. Moreover, we prove the upper bound theorem for the cd-index, namely that the cd-index of any d-dimensional polytope with n vertices is at most that of C(n,d), the d-dimensional cyclic polytope with n vertices. Received September 29, 1998; in final form February 8, 1999     

Conservative algebras of 2-dimensional algebras,II

In 1990 Kantor defined the conservative algebra W(n) of all algebras (i.e. bilinear maps) on the n-dimensional vector space. If n>1, then the algebra W(n) does not belong to any well-known class of algebras (such as associative, Lie, Jordan, or Leibniz algebras). We describe automorphisms, one-sided ideals, and idempotents of W(2). Also similar problems are solved for the algebra W₂ of all commutative algebras on the 2-dimensional vector space and for the algebra S₂ of all commutative algebras with trace zero multiplication on the 2-dimensional vector space.     

Skewing (n+1) tensor indices where the index range is n

It is known that any totally skew quantity with (n?+?1) indices, each of which ranges over n values, vanishes identically. The aim of this short note is to show that this is equivalent to the simple fact that any (n?+?1) vectors in an n-dimensional vector space are linearly dependent.     

Asymptotic analysis of the M/G/1 queue with a time‐dependent arrival rate

We consider the M/G/1 queue with an arrival rate λ that depends weakly upon time, as λ = λ(εt) where ε is a small parameter. In the asymptotic limit ε → 0, we construct approximations to the probability p _n(t)that η customers are present at time t. We show that the asymptotics are different for several ranges of the (slow) time scale Τ= εt. We employ singular perturbation techniques and relate the various time scales by asymptotic matching. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the Discrepancy for Boxes and Polytopes

 We consider so-called Tusnády’s problem in dimension d: Given an n-point set P in R ^d , color the points of P red or blue in such a way that for any d-dimensional interval B, the number of red points in differs from the number of blue points in by at most Δ, where should be as small as possible. We slightly improve previous results of Beck, Bohus, and Srinivasan by showing that , with a simple proof. The same asymptotic bound is shown for an analogous problem where B is allowed to be any translated and scaled copy of a fixed convex polytope A in R ^d . Here the constant of proportionality depends on A and we give an explicit estimate. The same asymptotic bounds also follow for the Lebesgue-measure discrepancy, which improves and simplifies results of Beck and of Károlyi. Received 17 November 1997; in revised form 30 July 1998     

Higher-dimensional voronoi diagrams in linear expected time

A general method is presented for determining the mathematical expectation of the combinatorial complexity and other properties of the Voronoi diagram ofn independent and identically distributed points. The method is applied to derive exact asymptotic bounds on the expected number of vertices of the Voronoi diagram of points chosen from the uniform distribution on the interior of ad-dimensional ball; it is shown that in this case, the complexity of the diagram is ∵(n) for fixedd. An algorithm for constructing the Voronoid diagram is presented and analyzed. The algorithm is shown to require only ∵(n) time on average for random points from ad-ball assuming a real-RAM model of computation with a constant-time floor function. This algorithm is asymptotically faster than any previously known and optimal in the average-case sense. Based upon work supported by the National Science Foundation under Grant No. CCR-8658139 while the author was a student at Carnegie-Mellon University.     

Approximation Numbers of Identity Operators between Symmetric Sequence Spaces

We prove asymptotic formulas for the behavior of approximation quantities of identity operators between symmetric sequence spaces. These formulas extend recent results of Defant, Masty o, and Michels for identities l_pⁿF_n with an n-dimensional symmetric normed space F_n with p-concavity conditions on F_n and 1p2. We consider the general case of identities E_nF_n with weak assumptions on the asymptotic behavior of the fundamental sequences of the n-dimensional symmetric spaces E_n and F_n. We give applications to Lorentz and Orlicz sequence spaces, again considerably generalizing results of Pietsch, Defant, Masty o, and Michels.     

Constrained Semi-Markov decision processes with average rewards

This paper deals with constrained average reward Semi-Markov Decision Processes (SMDPs) with finite state and action sets. We consider two average reward criteria. The first criterion is time-average rewards, which equal the lower limits of the expected average rewards per unit time, as the horizon tends to infinity. The second criterion is ratio-average rewards, which equal the lower limits of the ratios of the expected total rewards during the firstn steps to the expected total duration of thesen steps asn . For both criteria, we prove the existence of optimal mixed stationary policies for constrained problems when the constraints are of the same nature as the objective functions. For unichain problems, we show the existence of randomized stationary policies which are optimal for both criteria. However, optimal mixed stationary policies may be different for each of these critria even for unichain problems. We provide linear programming algorithms for the computation of optimal policies.     

A recursive construction for universal cycles of 2-subspaces

We prove that universal cycles of 2-dimensional subspaces of vector spaces over any finite field F exist, i.e., if V is a finite-dimensional vector space over F, there is a cycle of vectors v₁,v₂,…,v_n such that each 2-dimensional subspace of V occurs exactly once as the span of consecutive vectors.     

Conformal vector fields on Kaehler manifolds

It is known that a conformal vector field on a compact Kaehler manifold is a Killing vector field. In this paper, we are interested in finding conditions under which a conformal vector field on a non-compact Kaehler manifold is Killing. First we prove that a harmonic analytic conformal vector field on a 2n-dimensional Kaehler manifold (n ≠ 2) of constant nonzero scalar curvature is Killing. It is also shown that on a 2n-dimensional Kaehler Einstein manifold (n > 1) an analytic conformal vector field is either Killing or else the Kaehler manifold is Ricci flat. In particular, it follows that on non-flat Kaehler Einstein manifolds of dimension greater than two, analytic conformal vector fields are Killing.     

Asymptotic conditional distribution of exceedance counts: fragility index with different margins

We consider a random vector X, whose components are neither necessarily independent nor identically distributed. The fragility index (FI), if it exists, is defined as the limit of the expected number of exceedances among the components of X above a high threshold, given that there is at least one exceedance. It measures the asymptotic stability of the system of components. The system is called stable if the FI is one and fragile otherwise. In this paper, we show that the asymptotic conditional distribution of exceedance counts exists, if the copula of X is in the domain of attraction of a multivariate extreme value distribution, and if the marginal distribution functions satisfy an appropriate tail condition. This enables the computation of the FI corresponding to X and of the extended FI as well as of the asymptotic distribution of the exceedance cluster length also in that case, where the components of X are not identically distributed.     

Fractures and vector valued maps

We study a class of non smooth vector valued maps, defined on n-dimensional domains, which allow for fractures of any integer dimension lower than n. We extend some well known features about (n-1)-dimensional jumps of SBV functions and 0-dimensional singularities, or cavitations, of the distributional determinant of Sobolev functions. Variational problems involving the size of the fractures of any dimension are then studied.Received: 10 September 2003, Accepted: 5 April 2004, Published online: 16 July 2004Mathematics Subject Classification (2000): 49Q15, 28A75, 49J52     

Analysis of the infinite server queues with semi-Markovian multivariate discounted inputs

We consider a general k-dimensional discounted infinite server queueing process (alternatively, an incurred but not reported claim process) where the multivariate inputs (claims) are given by a k-dimensional finite-state Markov chain and the arrivals follow a renewal process. After deriving a multidimensional integral equation for the moment-generating function jointly to the state of the input at time t given the initial state of the input at time 0, asymptotic results for the first and second (matrix) moments of the process are provided. In particular, when the interarrival or service times are exponentially distributed, transient expressions for the first two moments are obtained. Also, the moment-generating function for the process with deterministic interarrival times is considered to provide more explicit expressions. Finally, we demonstrate the potential of the present model by showing how it allows us to study semi-Markovian modulated infinite server queues where the customers (claims) arrival and service (reporting delay) times depend on the state of the process immediately before and at the switching times.