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.     

Limit laws of entrance times for homeomorphisms of the circle

Given a homeomorphismf of the circle with irrational rotation number and a descending chain of renormalization intervalsj _n off, we consider for each interval the point process obtained by marking the times for the orbit of a point in the circle to enterJ _n. Assuming the point is randomly chosen by the unique invariant probability measure off, we obtain necessary and sufficient conditions which guarantee convergence in law of the corresponding point process and we describe all the limiting processes. These conditions are given in terms of the convergent subsequences of the orbit of the rotation number off under the Gauss transformation and under a certain realization of its natural extension. We also consider the case when the point is randomly chosen according to Lebesgue measure,f being a diffeomorphism which isC ¹-conjugate to a rotation, and we show that the same necessary and sufficient conditions guarantee convergence in this case.     

Construction of non-linear semi-groups using product formulas

Under certain circumstances, the Trotter-Lie formulaW _t=lim(U _t/nV_t/n) ⁿ is used to construct a non-linear semi-groupW _t on closed subsets ofL ^P, 1≦p<∞. In particular we consider the situation whereU _t=e ^tA is a positivity preservingC ₀ (linear) semi-group andV _t is generated by a (non-linear) functionF with certain monotonicity properties. In general,A andF are “singular” onL ^p and no requirement is made that one of them be “relatively bounded” with respect to the other. The generator of the resulting semi-groupW _t turns out to be an extension ofA +F restricted to a suitable domain. Research supported by a Danforth Graduate Fellowship and a Weizmann Postdoctoral Fellowship.     

Hilbert’s irreducibility theorem for prime degree and general polynomials

Letf (X, t)εℚ[X, t] be an irreducible polynomial. Hilbert’s irreducibility theorem asserts that there are infinitely manyt ₀εℤ such thatf (X, t ₀) is still irreducible. We say thatf (X, t) isgeneral if the Galois group off (X, t) over ℚ(t) is the symmetric group in its natural action. We show that if the degree off with respect toX is a prime ≠ 5 or iff is general of degree ≠ 5, thenf (X, t ₀) is irreducible for all but finitely manyt ₀εℤ unless the curve given byf (X, t)=0 has infinitely many points (x ₀,t ₀) withx ₀εℚ,t ₀εℤ. The proof makes use of Siegel’s theorem about integral points on algebraic curves, and classical results about finite groups, going back to Burnside, Schur, Wielandt, and others. Supported by the DFG.     

On the Uniform Convergence of the Empirical Density of an Ergodic Diffusion

We investigate the uniform convergence of the density of the empirical measure of an ergodic diffusion. It is known that under certain conditions on the drift and diffusion coefficients of the diffusion, the empirical density f _t converges in probability to the invariant density f, uniformly on the entire real line. We show that under the same conditions, uniform convergence of f _t to f on compact intervals takes place almost surely. Moreover, we prove that under much milder conditions (the usual linear growth condition on the drift and diffusion coefficients and a finite second moment of the invariant measure suffice), we have the uniform convergence of f _t to f on compacta in probability. This revised version was published online in June 2006 with corrections to the Cover Date.     

Continuity in functional differential equations with infinite delay

In this paper, we investigate the continuous dependence of solutions of the functional differential equation with infinite delayx(t)=f(t,x _t ) on initial functions. Endowing the phase space ag-norm as well as a supremum norm, we show that if the equation satisfies a mild fading memory dondition, then the continuity off in respect to the topology induced by the supremum norm can yield the continuity of solutions of the equation in respect to the topology induced by theg-norm which is stronger than the ahead one.This research was supported in part by an NSF grant with number NSF-DMS-8521408.On leave from South China Normal University, Guangzhou, PRC. This research was supported in part by the National Science Foundation of PRC.     

Measure-valued Markov branching processes conditioned on non-extinction

We consider a particular class of measure-valued Markov branching processes that are constructed as “superprocesses” over some underlying Markov process. Such a processX dies out almost surely, so we introduce various conditioning schemes which keepX alive at large times. Under suitable hypotheses, which include the convergence of the semigroup for the underlying process to some limiting probability measureν, we show that the conditional distribution oft ⁻¹ X _t converges to that ofZν ast → ∞, whereZ is some strictly positive, real random variable. Research supported in part by NSF grant DMS 8701212. Research supported in part by an NSERC operating grant.     

Deformations of Functions Without Real Critical Points

Abstract

Given a real analytic function f(x, y) with one critical point P ₀, we study deformations f _t of fsuch that, for any t ≠ 0, the analytic function f _t has no critical points in a neighborhood of P ₀. We give explicitly a deformation without real critical points for any function which has only one real branch with characteristic exponents (4, 2q, r).     

A Nim-like Game and Dynamic Recurrence Relations

The nim-like game 〈n, f; X, Y〉 is defined by an integer n ≥ 2 a constraint function f, and two players and X and Y. Players X and Y alternate taking coins from a pile of n coins, with X taking the first turn. The winner is the one who takes the last coin. On the kth turn, a player may remove t_k coins, where 1 ≤ t₁ ≤ n ? 1 and 1 ≤ t_k ≤ max{1, f(t_k?1) for k > 1. Let the set S_f = {1} ∪ {n| there is a winning strategy for Y in the nim-like game 〈n, f; X, Y〉}. In this paper, an algorithm is provided to construct the set S_f = {a₁, a₂,…} in an increasing sequence when the function f(x) is monotonic. We show that if the function f(x) is linear, then there exist integers n₀ and m such that a_n+1 = a_n + a_n?m for n > n₀ and we give upper and lower bounds for m (dependent on f. A duality is established between the asymptotic order of the sequence of elements in S_f and the degree of the function f(x). A necessary and sufficient condition for the sequence {a₀, a₁, a₂,…} of elements in S_f to satisfy a regular recurrence relation is described as well.     

A Note on the Convergence of Integral Functionals of Diffusion Processes. An Application to Strong Convergence

For a diffusion type process dX_t = dW_i + a(t, X)dt and a sequence (f_n) of nonnegative functions necessary and sufficient conditions to the f_n are established which guarantee the a.s. convergence of f_n(X_t)dt to zero. This result is applied to derive simple necessary and sufficient conditions for the strong convergence of distributions of diffusion processes formulated in terms of the corresponding drift functions.     

Strong asymptotics in Lagrange interpolation with equidistant nodes

In this paper we prove three conjectures of Revers on Lagrange interpolation for f_λ(t)=|t|^λ,λ>0, at equidistant nodes. In particular, we describe the rate of divergence of the Lagrange interpolants L_N( f_λ,t) for 0<|t|<1, and discuss their convergence at t=0. We also establish an asymptotic relation for max_|t|1| |t|^λ−L_N( f_λ,t)|. The proofs are based on strong asymptotics for |t|^λ−L_N( f_λ,t), 0|t|<1.     

Optimal iterative processes for root-finding

Letf ₀(x) be a function of one variable with a simple zero atr ₀. An iteration scheme is said to be locally convergent if, for some initial approximationsx ₁, ...,x _s nearr ₀ and all functionsf which are sufficiently close (in a certain sense) tof ₀, the scheme generates a sequence {x _k} which lies nearr ₀ and converges to a zeror off. The order of convergence of the scheme is the infimum of the order of convergence of {x _k} for all such functionsf. We study iteration schemes which are locally convergent and use only evaluations off,f, ...,f ^[d] atx ₁, ...,x _k–1 to determinex _k, and we show that no such scheme has order greater thand+2. This bound is the best possible, for it is attained by certain schemes based on polynomial interpolation.This work was supported (in part) by the Office of Naval Research under contract numbers N0014-69-C-0023 and N0014-71-C-0112.     

Explosive solutions of elliptic equations with absorption and nonlinear gradient term

Letf be a non-decreasing C¹-function such that andF(t)/f ² a(t)→ 0 ast → ∞, whereF(t)=∫ ₀ ^t f(s) ds anda ∈ (0, 2]. We prove the existence of positive large solutions to the equationΔu +q(x)|Δu| ^a =p(x)f(u) in a smooth bounded domain Ω ⊂R^N, provided thatp, q are non-negative continuous functions so that any zero ofp is surrounded by a surface strictly included in Ω on whichp is positive. Under additional hypotheses onp we deduce the existence of solutions if Ω is unbounded.     

Positive solutions of a nonlinear initial-value problem on half-line

The nonlinear initial-value problemu″(t)+f(t,u(t))=0,u(t ₀)+bu′(t ₀)=c,t ₀≥0,b≤0,c≥0, is considered for positive solutions on [t ₀, ∞). Existence of positive solutions is proved without the hypothesis thatf(t, ω)≥0 (or ≤0), using the lattice fixed point theorem. A monotonicity condition inf(t, ω) is used to prove the uniqueness of the solution of the initial-value problem. Whenf(t, ω)≥0 (or ≤0), uniqueness is also obtained under a sublinearity condition onf(t, ω).     

Homogenization of some parabolic operators with several time scales

The main focus in this paper is on homogenization of the parabolic problem ∂ _t uɛ − ∇ · (a(x/ɛ,t/ɛ,t/ɛ ^r )∇u ^ɛ ) = f. Under certain assumptions on a, there exists a G-limit b, which we characterize by means of multiscale techniques for r > 0, r ≠ 1. Also, an interpretation of asymptotic expansions in the context of two-scale convergence is made.     

Nonparametric Approach for Non-Gaussian Vector Stationary Processes

Suppose that {z(t)} is a non-Gaussian vector stationary process with spectral density matrixf(λ). In this paper we consider the testing problemH: ∫^π_−π K{f(λ)} dλ=cagainstA: ∫^π_−π K{f(λ)} dλ≠c, whereK{·} is an appropriate function andcis a given constant. For this problem we propose a testT_nbased on ∫^π_−π K{f(λ)} dλ=c, wheref(λ) is a nonparametric spectral estimator off(λ), and we define an efficacy ofT_nunder a sequence of nonparametric contiguous alternatives. The efficacy usually depnds on the fourth-order cumulant spectraf₄^Zofz(t). If it does not depend onf₄^Z, we say thatT_nis non-Gaussian robust. We will give sufficient conditions forT_nto be non-Gaussian robust. Since our test setting is very wide we can apply the result to many problems in time series. We discuss interrelation analysis of the components of {z(t)} and eigenvalue analysis off(λ). The essential point of our approach is that we do not assume the parametric form off(λ). Also some numerical studies are given and they confirm the theoretical results.     

The Topkis-Veinott algorithm for solving nonlinear programs with lower and upper bounded variables

In this paper we consider a nonlinear programming problem of the form to minimize f(x) subject to a x b, where f is a differentiable function on E_n and a and b are fixed vectors in E_n. We develop a variation of the feasible direction algorithm of Topkis and Veinott for solving the above problem and provide explicit expressions of the optimal directions for a family of direction-finding problems using different normalization constraints. We show that the algorithm converges to a Kuhn-Tucker point. The reported computational results indicate efficiency of the algorithm. It also indicates the strong effect of the form of the normalization constraint on convergence properties.     

The law of the Euler scheme for stochastic differential equations

Summary We study the approximation problem ofE f(X _T ) byE f(X _T ⁿ ), where (X _t ) is the solution of a stochastic differential equation, (X _T ⁿ ) is defined by the Euler discretization scheme with stepT/n, andf is a given function. For smoothf's, Talay and Tubaro have shown that the errorE f(X _T ) –f(X _T ⁿ ) can be expanded in powers of 1/n, which permits to construct Romberg extrapolation precedures to accelerate the convergence rate. Here, we prove that the expansion exists also whenf is only supposed measurable and bounded, under an additional nondegeneracy condition of Hörmander type for the infinitesimal generator of (X _t ): to obtain this result, we use the stochastic variations calculus. In the second part of this work, we will consider the density of the law ofX _T ⁿ and compare it to the density of the law ofX _T .     

Three characterizations of non-binary correlation-immune and resilient functions

A functionf(X ₁,X ₂, ...,X _n ) is said to betth-order correlation-immune if the random variableZ=f(X ₁,X ₂,...,X _n ) is independent of every set oft random variables chosen from the independent equiprobable random variablesX ₁,X ₂,...,X _n . Additionally, if all possible outputs are equally likely, thenf is called at-resilient function. In this paper, we provide three different characterizations oft th-order correlation immune functions and resilient functions where the random variable is overGF (q). The first is in terms of the structure of a certain associated matrix. The second characterization involves Fourier transforms. The third characterization establishes the equivalence of resilient functions and large sets of orthogonal arrays.     

Interior transition layers of solutions to the perturbed elliptic Sine-Gordon equation on an interval

We consider the perturbed elliptic Sine-Gordon equation on an interval-u″t+γsinu(t)=μf(u(t)),t ∈I := (-T, T),u(t) > 0,t ∈I,u(±T)=0 where λ, μ>0 are parameters andT>0 is a constant. By applying variational methods subject to the constraint depending on λ, we obtain eigenpairs (μ,u)=(μ(λ),u _λ) which solve this eigenvalue problem for a given λ>0. Then we study the asymptotic behavior ofu _λ and μ(λ) as λ→∞. Especially, we study the location of interior transition layers ofu _λ as λ→∞. This research has been supported by the Japan Society for the Promotion of Science.