A Probabilistic Approach to Carne’s Bound

Carne’s bound is a sharp inequality controlling the transition probabilities for a discrete reversible Markov chain (Section 1). Its ordinary proof uses spectral techniques which look as efficient as miraculous. Here we present a new proof, comparing a “drift” for ways “out” and “back”, to get the gaussian part of the bound (Section 2), and using a conditioning technique to get the flight factor (Section 4). Moreover we show how our proof is more “supple” than Carne’s one and may generalize (Section 3.2).      

A multiclass network with non-linear, non-convex, non-monotonic stability conditions

We consider a stochastic queueing network with fixed routes and class priorities. The vector of class sizes forms a homogeneous Markov process of countable state space Z⁶ ₊. The network is said “stable” (resp.“unstable”) if this Markov process is ergodic (resp. transient). The parameters are the traffic intensities of the different classes. An unusual condition of stability is obtained thanks to a new argument based on the characterization of the “essential states”. The exact stability conditions are then detected thanks to an associated fluid network: we identify a zone of the parameter space in which diverging, fluid paths appear. In order to show that this is a zone of instability (and that the network is stable outside this zone), we resort to the criteria of ergodicity and transience proved by Malyshev and Menshikov for reflected random walks in Z⁶ ₊ (Malyshev and Menshikov, 1981). Their approach allows us to neglect some “pathological” fluid paths that perturb the dynamics of the fluid model. The stability conditions thus determined have especially unusual characteristics: they have a quadratic part, the stability domain is not convex, and increasing all the service rates may provoke instability (Theorem 1.1 and section 7). This revised version was published online in June 2006 with corrections to the Cover Date.     

Multi-Server Queueing Systems with Multiple Priority Classes

We present the first near-exact analysis of an M/PH/k queue with m > 2 preemptive-resume priority classes. Our analysis introduces a new technique, which we refer to as Recursive Dimensionality Reduction (RDR). The key idea in RDR is that the m-dimensionally infinite Markov chain, representing the m class state space, is recursively reduced to a 1-dimensionally infinite Markov chain, that is easily and quickly solved. RDR involves no truncation and results in only small inaccuracy when compared with simulation, for a wide range of loads and variability in the job size distribution. Our analytic methods are then used to derive insights on how multi-server systems with prioritization compare with their single server counterparts with respect to response time. Multi-server systems are also compared with single server systems with respect to the effect of different prioritization schemes—“smart” prioritization (giving priority to the smaller jobs) versus “stupid” prioritization (giving priority to the larger jobs). We also study the effect of approximating m class performance by collapsing the m classes into just two classes. Supported by NSF Career Grant CCR-0133077, NSF Theory CCR-0311383, NSF ITR CCR-0313148, and IBM Corporation via Pittsburgh Digital Greenhouse Grant 2003. AMS subject classification: 60K25, 68M20, 90B22, 90B36     

Supply chain organization and e-commerce: a model to analyze store-picking, warehouse-picking and drop-shipping

Across many industries, e-commerce generates substantial modifications in supply chain structures. The aim of this article is to assess different forms of existing organizations when a store-based sales network coexists with a web site order network. Three main organizational models can be detected: “store-picking”, “dedicated warehouse-picking” and “drop-shipping”. We use a “newsboy” order policy model to compare the advantages of these different models and to note the impact of some parameters on inventory and flow management policies throughout the supply chain. Several effects are presented, particularly those linked to the size of the Internet market in relation to traditional market size and market demand hazards.      

A complexity measure for families of binary sequences

In earlier papers finite pseudorandom binary sequences were studied, quantitative measures of pseudorandomness of them were introduced and studied, and large families of “good” pseudorandom sequences were constructed. In certain applications (cryptography) it is not enough to know that a family of “good” pseudorandom binary sequences is large, it is a more important property if it has a “rich”, “complex” structure. Correspondingly, the notion of “f-complexity” of a family of binary sequences is introduced. It is shown that the family of “good” pseudorandom binary sequences constructed earlier is also of high f-complexity. Finally, the cardinality of the smallest family achieving a prescibed f-complexity and multiplicity is estimated. This revised version was published online in August 2006 with corrections to the Cover Date.     

Exact asymptotics for the stationary distribution of a Markov chain: a production model

We derive rough and exact asymptotic expressions for the stationary distribution π of a Markov chain arising in a queueing/production context. The approach we develop can also handle “cascades,” which are situations where the fluid limit of the large deviation path from the origin to the increasingly rare event is nonlinear. Our approach considers a process that starts at the rare event. In our production example, we can have two sequences of states that asymptotically lie on the same line, yet π has different asymptotics on the two sequences.     

A Simple Novel Approach to Valuing Risky Zero Coupon Bond in a Markov Regime Switching Economy

We have addressed the problem of pricing risky zero coupon bond in the framework of Longstaff and Schwartz structural type model by pricing it as a Down-and-Out European Barrier Call option on the company’s asset-debt ratio assuming Markov regime switching economy. The growth rate and the volatility of the stochastic asset debt ratio is driven by a continuous time Markov chain which signifies state of the economy. Regime Switching renders market incomplete and selection of a Equivalent martingale measure (EMM) becomes a subtle issue. We price the zero coupon risky bond utilizing the powerful technique of Risk Minimizing hedging of the underlying Barrier option under the so called “Risk Minimal” martingale measure via computing the bond default probability.     

Reduction of hugoniot-maslov chains for trajectories of solitary vortices of the “shallow water” equations to the hill equation

According to Maslov’s idea, many two-dimensional, quasilinear hyperbolic systems of partial differential equations admit only three types of singularities that are in general position and have the property of “structure self-similarity and stability.” Those are: shock waves, “narrow” solitons, and “square-root” point singularities (solitary vortices). Their propagation is described by an infinite chain of ordinary differential equations (ODE) that generalize the well-known Hugoniot conditions for shock waves. After some reasonable closure of the chain for the case of solitary vortices in the “shallow water” equations, we obtain a nonlinear system of sixteen ODE, which is exactly equivalent to the (linear) Hill equation with a periodic potential. This means that, in some approximations, the trajectory of a solitary vortex can be described by the Hill equation. This result can be used to predict the trajectory of the vortex center if we know its observable part. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 112, No. 1, pp. 47–66.     

Generating binary trees with uniform probability

A binary tree is characterized as a sequence of graftings. This sequence is used to construct a Markov chain useful for generating trees with uniform probability. A code for the Markov chain gives a characteristic binary string for the trees. The main result is the calculation of the transition probabilities of the Markov chain. Some applications are pointed out.     

Heavy traffic analysis of M/G/1 type queueing systems with Markov-modulated arrivals

M/G/1 type queueing systems whose arrival rate is a function of an independent continuous time Markov chain are considered. We suggest a simple analytical approach which allows rigorous mathematical analysis of the stationary characteristics under heavy traffic. Their asymptotic behaviour is described in terms of characteristics of the modulating process (defined as a solution of a set of linear algebraic equations). The analysis is based on certain “semi-explicit” formulas for the performance characteristics. This research was supported by INTAS under grant No. 96-0828.     

On trees covering chains or stars

In this paper, in the context of the “dessins d’enfants” theory, we give a combinatorial criterion for a plane tree to cover a tree from the classes of “chains” or “stars.” We also discuss some applications of this result that are related to the arithmetical theory of torsion on curves. Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 6, pp. 207–215, 2007.     

The Geometry of Standard Deontic Logic

Whereas geometrical oppositions (logical squares and hexagons) have been so far investigated in many fields of modal logic (both abstract and applied), the oppositional geometrical side of “deontic logic” (the logic of “obligatory”, “forbidden”, “permitted”, . . .) has rather been neglected. Besides the classical “deontic square” (the deontic counterpart of Aristotle’s “logical square”), some interesting attempts have nevertheless been made to deepen the geometrical investigation of the deontic oppositions: Kalinowski (La logique des normes, PUF, Paris, 1972) has proposed a “deontic hexagon” as being the geometrical representation of standard deontic logic, whereas Joerden (jointly with Hruschka, in Archiv für Rechtsund Sozialphilosophie 73:1, 1987), McNamara (Mind 105:419, 1996) and Wessels (Die gute Samariterin. Zur Struktur der Supererogation, Walter de Gruyter, Berlin, 2002) have proposed some new “deontic polygons” for dealing with conservative extensions of standard deontic logic internalising the concept of “supererogation”. Since 2004 a new formal science of the geometrical oppositions inside logic has appeared, that is “n-opposition theory”, or “NOT”, which relies on the notion of “logical bi-simplex of dimension m” (m = n − 1). This theory has received a complete mathematical foundation in 2008, and since then several extensions. In this paper, by using it, we show that in standard deontic logic there are in fact many more oppositional deontic figures than Kalinowski’s unique “hexagon of norms” (more ones, and more complex ones, geometrically speaking: “deontic squares”, “deontic hexagons”, “deontic cubes”, . . ., “deontic tetraicosahedra”, . . .): the real geometry of the oppositions between deontic modalities is composed by the aforementioned structures (squares, hexagons, cubes, . . ., tetraicosahedra and hyper-tetraicosahedra), whose complete mathematical closure happens in fact to be a “deontic 5-dimensional hyper-tetraicosahedron” (an oppositional very regular solid).      

“Miniaturized” Linearizations for Quadratic 0/1 Problems

In order to solve a quadratic 0/1 problem, some techniques, consisting in deriving a linear integer formulation, are used. Those techniques, called “linearization”, usually involve a huge number of additional variables. As a consequence, the exact resolution of the linear model is, in general, very difficult. Our aim, in this paper, is to propose “economical” linear models. Starting from an existing linearization (typically the so-called “classical linearization”), we find a new linearization with fewer variables. The resulting model is called “Miniaturized” linearization. Based on this approach, we propose a new linearization scheme for which numerical tests have been performed.     

Extremal Lyapunov exponents: an invariance principle and applications

We propose a new approach to analyzing dynamical systems that combine hyperbolic and non-hyperbolic (“center”) behavior, e.g. partially hyperbolic diffeomorphisms. A number of applications illustrate its power.     

Average sample-path optimality for continuous-time Markov decision processes in Polish spaces

In this paper we study the average sample-path cost(ASPC) problem for continuous-time Markov decision processes in Polish spaces.To the best of our knowledge,this paper is a first attempt to study the ASPC criterion on continuous-time MDPs with Polish state and action spaces.The corresponding transition rates are allowed to be unbounded,and the cost rates may have neither upper nor lower bounds.Under some mild hypotheses,we prove the existence of ε(ε≥ 0)-ASPC optimal stationary policies based on two differe...     

Markov Incremental Constructions

A classic result asserts that many geometric structures can be constructed optimally by successively inserting their constituent parts in random order. These randomized incremental constructions (RICs) still work with imperfect randomness: the dynamic operations need only be “locally” random. Much attention has been given recently to inputs generated by Markov sources. These are particularly interesting to study in the framework of RICs, because Markov chains provide highly nonlocal randomness, which incapacitates virtually all known RIC technology. We generalize Mulmuley’s theory of Θ-series and prove that Markov incremental constructions with bounded spectral gap are optimal within polylog factors for trapezoidal maps, segment intersections, and convex hulls in any fixed dimension. The main contribution of this work is threefold: (i) extending the theory of abstract configuration spaces to the Markov setting; (ii) proving Clarkson–Shor-type bounds for this new model; (iii) applying the results to classical geometric problems. We hope that this work will pioneer a new approach to randomized analysis in computational geometry. This work was supported in part by NSF grants CCR-0306283, CCF-0634958.     

An approach to matrix problems

A new general approach to the so-called “matrix problems” is given. With this approach, the “derivative” of a matrix problem is again a matrix problem of the same type.     

Estimation of the Defect Status on Visual Field Longitudinal Data

In this paper, we show the use of Multivariate Time Series models, Markov Random Fields and Bayesian methodologies to solve an applied ophthalmological problem related to the study of glaucoma. Glaucoma is a very serious and widely extended eye disease characterized by a gradual decrease in the intensity of the patient’s sight. It is not, however, homogeneous over all the visual field, and starts at one or several sites and gradually spreads to nearby sites. Measurement of the patient’s “seeing threshold” at different points in the visual field is an important diagnostic tool for glaucoma and other diseases. It results in a map with 52 numerical values, each of which represents the level of intensity perceived by the patient at that site, and ranges from 0 (complete blindness) to 35 (exceptional vision). Additionally a “defect status” variable can be attached at each site in the visual field. This variable would indicate whether the site is normal or defective. Using Bayesian methodologies, the “defect status” process can be regarded as a parameter of the probability distribution of the thresholds and can be estimated as the maximum of its posterior distribution. The stochastic model assumed for the observed “threshold”, given the “defect status”, is a first order autoregressive integrated model (VARI(1,1)) in time, with first order homogeneous spatial correlation. The defect status is modeled by using a Spatiotemporal Autologistic Model with non-homogeneous spatial dependence. This dependence assumes that the propagation of the lesions follows the directions taken by the nerve fibers. MCMC methods are used to jointly estimate the defect status, and parameters and hyperparameters of the model.     

KAM Stability for a three-body problem of the Solar system

A new (iso-energetic) KAM method is tested on a specific three-body problem “extracted” from the Solar system (Sun-Jupiter + asteroid 12 Victoria). Analytical results in agreement with the observed data are established. This paper is a concise presentation of [2]. Supported by the MIUR projects: “Dynamical Systems: Classical, Quantum, Stochastic” and “Variational Methods and Nonlinear Differential Equations” Received: February 3, 2004