Comparisons between observable and unobservable M/M/1 queues with respect to optimal customer behavior

We consider an M/M/1 queueing system in which the queue length may or may not be observable by a customer upon entering the system. The “observable” and “unobservable” models are compared with respect to system properties and performance measures under two different types of optimal customer behavior, which we refer to as “selfishly optimal” and “socially optimal”. We consider average customer throughput rates and show that, under both types of optimal customer behavior, the equality of effective queue-joining rates between the observable and unobservable systems results in differences with respect to other performance measures such as mean busy periods and waiting times. We also show that the equality of selfishly optimal queue-joining rates between the two types of system precludes the equality of socially optimal joining rates, and vice versa.     

Decomposable critical tensors

Let λ = (λ₁, … , λ_t) be a partition of m and its conjugate partition. Denote also by λ the irreducible C-character of S_m associated with λ. Let V be a finite dimensional vector space over C.The reach of an element of the symmetry class of tensors V_λ (symmetry class of tensors associated with λ) is defined. The concept of critical element is introduced, as an element whose reach has dimension equal to . It is observed that, in ∧^mV, the notions of critical element and decomposable element coincide. Known results for decomposable elements of ∧^mV are extended to critical elements of V_λ. In particular, for a basis of ⊗^mV induced by a basis of V, generalized Plücker polynomials are constructed in a way that the set of their common roots contains the set of the families of components of decomposable critical elements of V_λ.     

Applications of bulk queues to group testing models with incomplete identification

A population of items is said to be “group-testable”, (i) if the items can be classified as “good” and “bad”, and (ii) if it is possible to carry out a simultaneous test on a batch of items with two possible outcomes: “Success” (indicating that all items in the batch are good) or “failure” (indicating a contaminated batch). In this paper, we assume that the items to be tested arrive at the group-testing centre according to a Poisson process and are served (i.e., group-tested) in batches by one server. The service time distribution is general but it depends on the batch size being tested. These assumptions give rise to the bulk queueing model M/G^(m,M)/1, where m and M(>m) are the decision variables where each batch size can be between m and M. We develop the generating function for the steady-state probabilities of the embedded Markov chain. We then consider a more realistic finite state version of the problem where the testing centre has a finite capacity and present an expected profit objective function. We compute the optimal values of the decision variables (m, M) that maximize the expected profit. For a special case of the problem, we determine the optimal decision explicitly in terms of the Lambert function.     

Noncommutative convexity arises from linear matrix inequalities

This paper concerns polynomials in g noncommutative variables x=(x₁,…,xg), inverses of such polynomials, and more generally noncommutative “rational expressions” with real coefficients which are formally symmetric and “analytic near 0.” The focus is on rational expressions r=r(x) which are “matrix convex” near 0; i.e., those rational expressions r for which there is an ?>0 such that if X=(X₁,…,Xg) is a g-tuple of n×n symmetric matrices satisfying

     

Doubly nilpotent numbers in the 2D plane

Dual numbers, split-quaternions, split-octonions, and other number systems with nilpotent spaces have received sporadic yet persistent interest, beginning from their roots in the 19th century, to more recent attention in connection with supersymmetry in physics. In this paper, a number system in the 2D plane is investigated, where the squares of its basis elements p and q each map into the coordinate origin. Modeled similarly to an original concept by C. Musès, this new system will be termed “PQ space” and presented as a generalization of nilpotence and zero. Compared to the complex numbers, its multiplicative group and underlying vector space are equipped with as little as needed modifications to achieve the desired properties. The locus of real powers of basis elements p^α and q^α resembles a four-leaved clover, where the coordinate origin at (0, 0) will not only represent the additive identity element, but also a map of “directed zeroes” from the multiplicative group. Algebraic and geometric properties of PQ space are discussed, and its naturalness advertised by comparison with other systems. The relation to Musès’ “p and q numbers” is shown and its differences defended. Next to possible applications and extensions, a new butterfly-shaped fractal is generated from a recursion algorithm of Mandelbrot type.     

Partial vexillarity and bigrassmannian permutations

We define two closely related notions of degree for permutation patterns of type 2143. These give rise to classes of “m-vexillary elements” in the symmetric group. Using partitions, the Ehresmann–Bruhat partial order, and sets constructed from permutation inversions, we characterize the m-vexillary elements. We relate the maximal bigrassmannian permutations in the (Ehresmann–Bruhat) order ideal generated by any given m-vexillary element w to the maximal rectangles contained in the shape of w.     

Generating asymptotically optimal broadcasting schedules to minimize average waiting time

The performance of a Video-on-Demand broadcasting scheme is commonly evaluated by the maximum waiting time encountered by the customer before viewing can start. This paper addresses the issue of minimizing the average waiting time. Recently, we proposed Harmonic Block Windows scheduling to specifically minimize the average waiting time for given bandwidth. Here, we present an efficient heuristic algorithm that generates asymptotically optimal Harmonic Block Windows schedules. Using simulation, we demonstrate that, as we increase the “block size”, the normalized average waiting time of these schedules approaches the theoretical minimum achievable by any “fixed start points” schedule.     

Mixing times with applications to perturbed Markov chains

A measure of the “mixing time” or “time to stationarity” in a finite irreducible discrete time Markov chain is considered. The statistic , where {π_j} is the stationary distribution and m_ij is the mean first passage time from state i to state j of the Markov chain, is shown to be independent of the initial state i (so that η_i = η for all i), is minimal in the case of a periodic chain, yet can be arbitrarily large in a variety of situations. An application considering the effects perturbations of the transition probabilities have on the stationary distributions of Markov chains leads to a new bound, involving η, for the 1-norm of the difference between the stationary probability vectors of the original and the perturbed chain. When η is large the stationary distribution of the Markov chain is very sensitive to perturbations of the transition probabilities.     

A cycle lemma for permutation inversions

In this paper we study some properties of the inversion statistic. Some enumerative results concerning the permutations of the multiset {x₁^m₁,x₂^m₂} with respect to the inversion parameter are established and it is shown that these depend on gcd(m₁,m₂). Using a “cycle lemma”, a combinatorial proof of the results is given. Moreover, some applications to the Gaussian binomial coefficient are illustrated.     

Joint distribution of run statistics in partially exchangeable processes

Let {X_i}_i≥1 be an infinite sequence of recurrent partially exchangeable random variables with two possible outcomes as either “1” (success) or “0” (failure). In this paper we obtain the joint distribution of success and failure run statistics in {X_i}_i≥1. The results can be used to obtain the joint distribution of runs in ordinary Markov chains, exchangeable and independent sequences.     

Quantum field theoretic properties of a model of Nelson: Domain and eigenvector stability for perturbed linear operators

The Yukawa-like interaction of a nonrelativistic “nucleon” field with a relativistic “meson” field is studied. E. Nelson defined a self-adjoint Hamiltonian for this model, using an approximate dressing transformation to transform the standard high-momentum cutoff Hamiltonian H_κ into an operator H₀ + A_κ + E_κ, where E_κ is the divergent nucleon self-interaction part which is removed and A_κ is controled κ-uniformly as a sesquilinear form perturbation of H₀; so H_ren is defined to transform to H₀ + A_∞. In the present work it is proved that the model has some of the main properties that are familiar in the axiomatic approach to quantum fields. Vacuum expectation values are proved to exist and satisfy the axioms of Wightman, except for Lorentz covariance. In the case of a small coupling constant, “physical nucleon” one-particle states are constructed and the “one-body problem” of Haag is solved. These field theoretic properties are translated into domain and spectral stability properties for the perturbed operator H₀ + A_∞. Stability theory for perturbations by sesquilinear forms is presented in an Appendix, with a number of new techniques.     

Sooner and later waiting time problems in a two-state Markov chain

LetX ₁,X ₂,... be a time-homogeneous {0, 1}-valued Markov chain. LetF ₀ be the event thatl runs of 0 of lengthr occur and letF ₁ be the event thatm runs of 1 of lengthk occur in the sequenceX ₁,X ₂, ... We obtained the recurrence relations of the probability generating functions of the distributions of the waiting time for the sooner and later occurring events betweenF ₀ andF ₁ by the non-overlapping way of counting and overlapping way of counting. We also obtained the recurrence relations of the probability generating functions of the distributions of the sooner and later waiting time by the non-overlapping way of counting of 0-runs of lengthr or more and 1-runs of lengthk or more.     

Curves having one place at infinity and linear systems on rational surfaces

Denoting by L_d(m₀,m₁,…,m_r) the linear system of plane curves of degree d passing through r+1 generic points p₀,p₁,…,p_r of the projective plane with multiplicity m_i (or larger) at each p_i, we prove the Harbourne-Hirschowitz Conjecture for linear systems L_d(m₀,m₁,…,m_r) determined by a wide family of systems of multiplicities and arbitrary degree d. Moreover, we provide an algorithm for computing a bound for the regularity of an arbitrary system , and we give its exact value when is in the above family. To do that, we prove an H¹-vanishing theorem for line bundles on surfaces associated with some pencils “at infinity”.     

Periodic solutions of the Lyness max equation

We investigate the periodic nature of solutions of a “max-type” difference equation sometimes referred to as the “Lyness max” equation. The equation we consider is x_n+1=max{x_n,A}/x_n−1, n=0,1,…, where A is a positive real parameter and the initial conditions are arbitrary positive numbers. We also present related results for a similar equation sometimes referred to as the “period 7 max” equation.     

On saturated distinguished chains over a local field II

This is a continuation of the paper (J Number Theory 79 (1999) 217) on saturated distinguished chains (SDCs) over a local field K. Here, we give a “canonical” choice of the next element α₁ in a SDC for α=π₁+π₁π considered in (Ota, 1999) for wildly totally ramified Galois extensions, and this leads us to consider a tower of fields, K⊂K₁⊂K₂⊂…, where K₁=K(α₁) and K_n/K is wildly totally ramified. The union of these fields is particularly interesting, for its conductor over K is very small, close to 1. Moreover, in some cases K is uniquely determined up to isomorphism over K for any such extensions of the same type. We also consider SDCs for an element α=π₁+π₁π₂+?+π₁π₂?π_n for totally ramified Galois extensions of type (m,m,...,m), where m is a power of the characteristic of the residual field of K.     

Contributions to max-min convex geometry. I: Segments

We give some contributions to the theory of “max-min convex geometry”, that is, convex geometry in the semimodule over the max-min semiring R_max,min=R∪{-∞,+∞}. We introduce “elementary segments” that generalize from n=2 the horizontal, vertical or oblique segments contained in the main bisector of . We show that every segment in is a concatenation of a finite number of elementary subsegments (at most 2n-1, respectively at most 2n-2, in the case of comparable, respectively, incomparable, endpoints x,y). In this first part we study “max-min segments”, and in the subsequent second part (submitted) we study “max-min semispaces” and some of their relations to “max-min convex sets”.     

Formulæ for the number of partitions of n into at most m parts (using the quasi-polynomial ansatz)

The purpose of this short article is to announce, and briefly describe, a Maple package, PARTITIONS, that (inter alia) completely automatically   discovers, and then proves, explicit expressions (as sums of quasi-polynomials) for _pm(n)$p_m(n)$ for any desired m. We do this to demonstrate the power of “rigorous guessing” as facilitated by the quasi-polynomial ansatz.