Large deviations for Langevin spin glass dynamics

Summary We study the asymptotic behaviour of asymmetrical spin glass dynamics in a Sherrington-Kirkpatrick model as proposed by Sompolinsky-Zippelius. We prove that the annealed law of the empirical measure on path space of these dynamics satisfy a large deviation principle in the high temperature regime. We study the rate function of this large deviation principle and prove that it achieves its minimum value at a unique probability measureQ which is not markovian. We deduce that the quenched law of the empirical measure converges to _Q . Extending then the preceeding results to replicated dynamics, we investigate the quenched behavior of a single spin. We get quenched convergence toQ in the case of a symmetric initial law and even potential for the free spin.     

Two-Queue Polling Models with a Patient Server

We consider two-queue polling models with the special feature that a timer mechanism is employed at Q ₁: whenever the server polls Q ₁ and finds it empty, it activates a timer and remains dormant, waiting for the first arrival. If such an arrival occurs before the timer expires, a busy period starts in accordance with Q ₁'s service discipline. However, if the timer is shorter than the interarrival time to Q ₁, the server does not wait any more and switches back to Q ₂. We consider three configurations: (i) Q ₁ is controlled by the 1-limited protocol while Q ₂ is served exhaustively, (ii) Q ₁ employs the exhaustive regime while Q ₂ follows the 1-limited procedure, and (iii) both queues are served exhaustively. In all cases, we assume Poisson arrivals and allow general service and switchover time distributions. Our main results include the queue length distributions at polling instants, the waiting time distributions and the distribution of the total workload in the system.     

Large deviations for a simple closed queueing model

We consider a simple queueing model with one service station. The arrival and service processes have intensitiesa(N–Q _t) andNf(N ^–1 Q _t), where Q_t is the queue length,N is a large integer,a>0 andf(x) is a positive continuous function. We establish the large deviation principle for the sequence of the normalized queue length processq _N ^t =N ^–1Q_t,N1 for both light (a<f(0)) and heavy (af(0)) traffic and use this result for an investigation of ergodic properties ofq _N ^t ,N 1.     

On the diameter and radius of randon subgraphs of the cube

The n-dimensional cube Qⁿ is the graph whose vertices are the subsets of {1,…n}, with two vertices adjacent if and only if their symmetric difference is a singleton. Clearly Qⁿ has diameter and radious n. Write M = n2^n-1 = e(Qⁿ) for the size of Qⁿ. Let Q = (Q_t)_o^M be a random Qⁿ-process. Thus Q^t is a spanning subgraph of Qⁿ of size t, and Q_t is obtained from Q_t–1 by the random addition of an edge of Qⁿ not in Q_t–1, Let t^(k) = τ(Q;δ?k) be the hitting time of the property of having minimal degree at least k. We show that the diameter d_t = diam (Q_t) of Q_t in almost every Q? behaves as follows: d_t starts infinite and is first finite at time t⁽¹⁾, it equals n + 1 for t⁽¹⁾ ? t⁽²⁾ and d_t, = n for t ? t⁽²⁾. We also show that the radius of Q_t, is first finite for t = t⁽¹⁾, when it assumes the value n. These results are deduced from detailed theorems concerning the diameter and radius of the almost surely unique largest component of Q_t, for t = Ω(M). © 1994 John Wiley & Sons, Inc.     

The Virtual Poincaré Polynomials of Homogeneous Spaces

We factor the virtual Poincaré polynomial of every homogeneous space G/H, where G is a complex connected linear algebraic group and H is an algebraic subgroup, as t^2u (t²–1)^r Q_G/H(t²) for a polynomial Q_G/H with nonnegative integer coefficients. Moreover, we show that Q_G/H(t²) divides the virtual Poincaré polynomial of every regular embedding of G/H, if H is connected.     

Diffusion Approximation in Overloaded Switching Queueing Models

The asymptotic behavior of a queueing process in overloaded state-dependent queueing models (systems and networks) of a switching structure is investigated. A new approach to study fluid and diffusion approximation type theorems (without reflection) in transient and quasi-stationary regimes is suggested. The approach is based on functional limit theorems of averaging principle and diffusion approximation types for so-called Switching processes. Some classes of state-dependent Markov and non-Markov overloaded queueing systems and networks with different types of calls, batch arrival and service, unreliable servers, networks (M _SM,Q /M _SM,Q /1/) ^r switched by a semi-Markov environment and state-dependent polling systems are considered.     

Some path properties of generalized Lévy sheet

Let X(t) be an N parameter generalized Lévy sheet taking values in ℝ^d with a lower index α, ℜ = {(s, t] = ∏ _i=1 ^N (s _i, t _i], s _i < t _i}, E(x, Q) = {t ∈ Q: X(t) = x}, Q ∈ ℜ be the level set of X at x and X(Q) = {x: ∃t ∈ Q such that X(t) = x} be the image of X on Q. In this paper, the problems of the existence and increment size of the local times for X(t) are studied. In addition, the Hausdorff dimension of E(x, Q) and the upper bound of a uniform dimension for X(Q) are also established.     

A Large Deviation Principle for Stochastic Integrals

Assuming that {(X _n ,Y _n )} satisfies the large deviation principle with good rate function I ^♯ , conditions are given under which the sequence of triples {(X _n ,Y _n ,X _n ⋅Y _n )} satisfies the large deviation principle. An ε-approximation to the stochastic integral is proven to be almost compact. As is well known from the contraction principle, we can derive the large deviation principle when applying continuous functions to sequences that satisfy the large deviation principle; the method showed here skips the contraction principle, uses almost compactness and can be used to derive a generalization of the work of Dembo and Zeitouni on exponential approximations. An application of the main result to stochastic differential equations is given, namely, a Freidlin-Wentzell theorem is obtained for a sequence of solutions of SDE’s.     

The modulator of the local time

Let x(t), 0 ≦ t ≦ 1, be a real measurable function having a local time α(x, t) which is a continuous function of t for almost all x. It is also assumed that, for some m ≧ 2 and some real interval B, α^m(x, 1) is integrable over B. The modulator is a function M_m(t, B), t > 0, denned in terms of α. It is shown that the modulator serves as a measure of the smoothness of the L_m(B)-valued function α(., t) with respect to t. Then it is shown that the modulator plays a central role in precisely describing certain irregularity properties of x(t). The results are applied to the case where x(t) is the sample function of a real stochastic process. In this way new results are obtained for large classes of Gaussian and Markov processes.     

Oscillations of Higher Order Neutral Differential Equations with Variable Coefficients

We obtain sufficient conditions for the oscillation of all solutions of the higher order neutral differential equation dⁿ/d^m[y(t) + P(t) y(t - μ)] + Q(t) y(t ?σ) = 0, t ≧ t₀ where n ≧ 1, P ? C[t₀, ∞), R ], Q ? C[t₀, ∞), R ] and τ, μ ? R ⁺. Our results extend and improve several known results in the literature.     

Nonlinear filtering and large deviations:a pde-control theoretic approach

We consider the asymptotic nonlinear filtering problem dx=f(x)dt + ?^1/2 dw,dy=h(x) dt + ? dv and obtain lim_?→0 ? log q ²(x,t) = -W(x,t) for unnormalized conditional densities q ²(x,t) using PDE methods. HereW(x,t) is the value function for a deterministic optimal control problem arising in Mortensen's deterministic estimation, and is the unique viscosity solution of a Hamilton-Jacobi-Bellman equation. ijab has also studied this filtering problem, and we extend his large deviation result for certain unnormalized conditional measures. The resulting variational problem corresponds to the above control problem     

Large Deviations for Quicksort

LetQ_nbe the random number of comparisons made by quicksort in sortingndistinct keys when we assume that alln! possible orderings are equally likely. Known results concerning moments forQ_ndo not show how rare it is forQ_nto make large deviations from its mean. Here we give a good approximation to the probability of such a large deviation and find that this probability is quite small. As well as the basic quicksort, we consider the variant in which the partitioning key is chosen as the median of (2t+1) keys.     

Large Deviation Principle for Additive Functionals of Brownian Motion Corresponding to Kato Measures

Let (B _t ,P ^W _x ) be the Brownian motion. Let be a Radon measure in the Kato class and A _t the additive functional associated with . We prove that A _t /t obeys the large deviation principle.     

Hypercontractivity, Nash inequalities and subordination for classes of nonlinear semigroups

A suitable notion of hypercontractivity for a nonlinear semigroup {T _t } is shown to imply Nash-type inequalities for its generator H, provided a subhomogeneity property holds for the energy functional (u,Hu). We use this fact to prove that, for semigroups generated by operators of p-Laplacian-type, hypercontractivity implies ultracontractivity. Then we introduce the notion of subordinated nonlinear semigroups when the corresponding Bernstein function is f(x)=x ^α , and write an explicit formula for the associated generator. It is shown that hypercontractivity still holds for the subordinated semigroup and, hence, that Nash-type inequalities hold as well for the subordinated generator.     

Polling and greedy servers on a line

A single server moves with speed on a line interval (or a circle) of length (circumference)L. Customers, requiring service of constant durationb, arrive on the interval (or circle) at random at mean rate customers per unit length per unit time. A customer's mean wait for service depends partly on the rules governing the server's motion. We compare two different servers: thepolling server and thegreedy server. Without knowing the locations of waiting customers, a polling server scans endlessly back and forth across the interval (or clockwise around the circle), stopping only where it encounters a waiting customer. Knowing where customers are waiting, a greedy server always travels toward the current nearest one. Except for certain extreme values of ,L, b, and, the polling and greedy servers are roughly equally effective. Indeed, the simpler polling server is often the better. Theoretical results show, in most cases, that the polling server has a high probability of moving toward the nearest customer, i.e. moving as a greedy server would. The greedy server is difficult to analyze, but was simulated on a computer.     

Su alcune proprietà di geometria euclidea ed hermitiana in uno spazio vettoriale quaternionale

Riassunto Identificati, in modo opportuno, gli spazi vettoriali Qⁿ ed R⁴ⁿ, si esaminano varie proprietà che intercorrono tra la metrica hermitiana di Qⁿ e la metrica euclidea di R⁴ⁿ. Si definisce poi, per ogni sottospazio E_t di E _4n (t =1, 2, 3, 4) una nozione di deviazione caratteristica assoluta che estende l'analoga nozione nota nel caso di cⁿ. Si riescono così a caratterizzare i sottospazi E_t pseudocaratteristici (cioè contenuti in un E₄ che si identifica ad una retta di Qⁿ), ed i sottospazi E_t a prodotto hermitiano reale. Lavoro eseguito nell'ambito dell'attività dei Gruppi di Ricerca del Comitato per la Matematica del C. N. R. per l'anno accademico 1964–65.     

Queueing systems fed by many exponential on-off sources: an infinite-intersection approach

In queueing theory, an important class of events can be written as ‘infinite intersections’. For instance, in a queue with constant service rate c, busy periods starting at 0 and exceeding L > 0 are determined by the intersection of the events , i.e., queue Q _t is empty at 0 and for all t∊ [0, L] the amount of traffic A _t arriving in [0,t) exceeds the server capacity. Also the event of exceeding some predefined threshold in a tandem queue, or a priority queue, can be written in terms of this kind of infinite intersections. This paper studies the probability of such infinite intersections in queueing systems fed by a large number n of i.i.d. traffic sources (the so-called ‘many-sources regime’). If the sources are of the exponential on-off type, and the queueing resources are scaled proportional to n, the probabilities under consideration decay exponentially; we explicitly characterize the corresponding decay rate. The techniques used stem from large deviations theory (particularly sample-path large deviations). M. Mandjes is also with Korteweg-de Vries Institute, University of Amsterdam, Amsterdam, the Netherlands, and EURANDOM, Eindhoven, the Netherlands. Work done while P. Mannersalo was on leave at CWI. MSC 2000: 60F10 (Large deviations), 60K25 (Queueing theory)     

Probabilities of high excursions of Gaussian fields

Let {ξ(t), t ∈ T} be a differentiable (in the mean-square sense) Gaussian random field with E ξ(t) ≡ 0, D ξ(t) ≡ 1, and continuous trajectories defined on the m-dimensional interval T ì \mathbbR^m T \subset {\mathbb{R}^m} . The paper is devoted to the problem of large excursions of the random field ξ. In particular, the asymptotic properties of the probability P = P{−v(t) < ξ(t) < u(t), t ∈ T}, when, for all t ∈ T, u(t), v(t) ⩾ χ, χ → ∞, are investigated. The work is a continuation of Rudzkis research started in [R. Rudzkis, Probabilities of large excursions of empirical processes and fields, Sov. Math., Dokl., 45(1):226–228, 1992]. It is shown that if the random field ξ satisfies certain smoothness and regularity conditions, then P = e^−Q  + Qo(1), where Q is a certain constructive functional depending on u, v, T, and the matrix function R(t) = cov(ξ′(t), ξ′(t)).     

Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem

In this paper, we consider problem (P) of minimizing a quadratic function q(x)=x ^t Qx+c ^t x of binary variables. Our main idea is to use the recent Mixed Integer Quadratic Programming (MIQP) solvers. But, for this, we have to first convexify the objective function q(x). A classical trick is to raise up the diagonal entries of Q by a vector u until (Q+diag(u)) is positive semidefinite. Then, using the fact that x _i ²=x _i, we can obtain an equivalent convex objective function, which can then be handled by an MIQP solver. Hence, computing a suitable vector u constitutes a preprocessing phase in this exact solution method. We devise two different preprocessing methods. The first one is straightforward and consists in computing the smallest eigenvalue of Q. In the second method, vector u is obtained once a classical SDP relaxation of (P) is solved. We carry out computational tests using the generator of (Pardalos and Rodgers, 1990) and we compare our two solution methods to several other exact solution methods. Furthermore, we report computational results for the max-cut problem.     

Hochschild Cohomology Ring of the Mod-2 Group Ring of the Generalized Quaternion Group

We will determine the ring structure of the Hochschild cohomology HH?( ₂ Q _t ) of the mod-2 group ring  ₂ Q _t for arbitrary generalized quaternion groups Q _t of order 4t by calculating the ordinary cup product in H?(Q _t , _ψ  ₂ Q _t ).