Large deviations for empirical measures of Markov chains

In this paper we obtain large-deviation upper and lower bounds for the empirical measure of a Markov chain with general state space, as well as for the associated multivariate empirical measure and empirical process. In each of these instances we improve in various ways the results in the literature.     

The Brownian loop soup

We define a natural conformally invariant measure on unrooted Brownian loops in the plane and study some of its properties. We relate this measure to a measure on loops rooted at a boundary point of a domain and show how this relation gives a way to chronologically add Brownian loops to simple curves in the plane.Cornell University; Research supported in part by the National Science FoundationUniversité Paris-Sud and IUFMathematics Subject Classification (2000):60J65, 81T40     

Essential spectral radius for Markov semigroups (I): discrete time case

Using two new measures of non-compactness (P) and _w (P) for a positive kernel P on a Polish space E, we obtain a new formula of Nussbaum-Gelfand type for the essential spectral radius r _ess (P) on b. Using that formula we show that different known sufficient conditions for geometric ergodicity such as Doeblins condition, drift condition by means of Lyapunov function, geometric recurrence etc lead to variational formulas of the essential spectral radius. All those can be easily transported on the weighted space b _u . Some related results on L ² () are also obtained, especially in the symmetric case. Moreover we prove that for a strongly Feller and topologically transitive Markov kernel, the large deviation principle of Donsker-Varadhan for occupation measures of the associated Markov process holds if and only if the essential spectral radius is zero; this result allows us to show that the sufficient condition of Donsker-Varadhan for the large deviation principle is in fact necessary. The knowledge of r _ess (P) allows us to estimate eigenvalues of P in L ² in the symmetric case, and to estimate the geometric convergence rate by means of that in the metric of Wasserstein. Applications to different concrete models are provided for illustrating those general results. Mathematics Subject Classification (2000):60J05, 60F10, 47A10, 47D07     

Controllability and extremality in nonconvex differential inclusions

LetF:[0, T]×R ⁿ 2 ^{R n} be a set-valued map with compact values; let :R ⁿ R ^m be a locally Lipschitzian map,z(t) a given trajectory, andR the reachable set atT of the differential inclusion . We prove sufficient conditions for (z(T))intR and establish necessary conditions in maximum principle form for (z(T))(R). As a consequence of these results, we show that every boundary trajectory is simultaneously a Pontryagin extremal, Lagrangian extremal, and relaxed Lagrangian extremal.The author is grateful to an anonymous referee for his valuable remarks and comments which have helped to improve the paper.The paper was written while the author was visiting the laboratory of Prof. S. Suzuki, Department of Mechanical Engineering, Sophia University, Tokyo, Japan.     

Large deviations estimates for self-intersection local times for simple random walk in {\mathbb{Z}}^3

We obtain large deviations estimates for the self-intersection local times for a simple random walk in dimension 3. Also, we show that the main contribution to making the self-intersection large, in a time period of length n, comes from sites visited less than some power of log(n). This is opposite to the situation in dimensions larger or equal to 5. Finally, we present an application of our estimates to moderate deviations for random walk in random sceneries.      

(φ,ξ,η,λ)‐Structures of Parabolic Type

We consider (,,,)structures of parabolic type on hypersurfaces of dual spaces and study the rank of the affinor . We consider almost contact metric structures of parabolic type of the first kind on hypersurfaces of 4dimensional dual metric space. We study the properties of these structures and give examples of normal, integrable, and Sasakian parabolic structures.     

The Newton modified barrier method for QP problems

The Modified Barrier Functions (MBF) have elements of both Classical Lagrangians (CL) and Classical Barrier Functions (CBF). The MBF methods find an unconstrained minimizer of some smooth barrier function in primal space and then update the Lagrange multipliers, while the barrier parameter either remains fixed or can be updated at each step. The numerical realization of the MBF method leads to the Newton MBF method, where the primal minimizer is found by using Newton's method. This minimizer is then used to update the Lagrange multipliers. In this paper, we examine the Newton MBF method for the Quadratic Programming (QP) problem. It will be shown that under standard second-order optimality conditions, there is a ball around the primal solution and a cut cone in the dual space such that for a set of Lagrange multipliers in this cut cone, the method converges quadratically to the primal minimizer from any point in the aforementioned ball, and continues, to do so after each Lagrange multiplier update. The Lagrange multipliers remain within the cut cone and converge linearly to their optimal values. Any point in this ball will be called a hot start. Starting at such a hot start, at mostO(In In ^-1) Newton steps are sufficient to perform the primal minimization which is necessary for the Lagrange multiplier update. Here, >0 is the desired accuracy. Because of the linear convergence of the Lagrange multipliers, this means that onlyO(In ^-1)O(In In ^-1) Newton steps are required to reach an -approximation to the solution from any hot start. In order to reach the hot start, one has to perform Newton steps, wherem characterizes the size of the problem andC>0 is the condition number of the QP problem. This condition number will be characterized explicitly in terms of key parameters of the QP problem, which in turn depend on the input data and the size of the problem.Partially supported by NASA Grant NAG3-1397 and National Science Foundation Grant DMS-9403218.     

A large deviation principle for (r,p)-capacities on the Wiener space

Summary We formulate and prove a large deviation principle for the (r, p)-capacity on an abstract Wiener space. As an application, we obtain a sharpening of Strassen's law of the iterated logarithm in terms of the capacity.     

Estimates for distances between first exit times via parabolic equations in unbounded cylinders

First exit times and their dependence on variations of parameters are studied for diffusion processes with non-stationary coefficients. Estimates of L_p-distances and some other distances between two exit times are obtained. These estimates are based on some new prior estimates for solutions of parabolic Kolmogorovs equations with infinite horizon without Cauchy conditions.Mathematics Subject Classifications (2000): 60G17, 60G40, 60J50, 60J60, 60J65     

On the eigenvalues and eigenvectors of an overlapping Markov chain

Starting with a sequence of i.i.d. [uniform] random variables with m possible values, we consider the overlapping Markov chain formed by sliding a window of size k through the i.i.d. sequence. We study the limiting covariance matrix B_k of this Markov chain and give algorithms for constructing the eigenvectors of B_k. We also discuss the applicability of the results in strengthening Pearsons ² test as well as the relation to approximate entropy and the usefulness in the area of testing the hypothesis of uniformity of random number generators.Mathematics Subject Classification (2000):Primary: 60J10; Secondary: 11K45     

Uniqueness for isotropic diffusions with a linear drift

This paper proves that-valued solutions to the SDE are unique in distribution, when D^d is convex and open, D, c>0, is positive and locally Lipschitz on D and zero on D, and {xD:g(x)r} is convex for r sufficiently small. The proof (for =0) is based on the transformation X_te^ctX_t, which removes the drift, and a random time change. Although the set-up is rather specialized the result gives uniqueness for some SDEs that cannot be treated by any of the conventional techniques.Mathematics Subject Classification (2000):60J60, 60H10     

Large deviations for local time fractional Brownian motion and applications

Let be a fractional Brownian motion of Hurst index H∈(0,1) with values in R, and let be the local time process at zero of a strictly stable Lévy process of index 1<α?2 independent of WH. The α-stable local time fractional Brownian motion is defined by ZH(t)=WH(Lt). The process ZH is self-similar with self-similarity index and is related to the scaling limit of a continuous time random walk with heavy-tailed waiting times between jumps [P. Becker-Kern, M.M. Meerschaert, H.P. Scheffler, Limit theorems for coupled continuous time random walks, Ann. Probab. 32 (2004) 730-756; M.M. Meerschaert, H.P. Scheffler, Limit theorems for continuous time random walks with infinite mean waiting times, J. Appl. Probab. 41 (2004) 623-638]. However, ZH does not have stationary increments and is non-Gaussian. In this paper we establish large deviation results for the process ZH. As applications we derive upper bounds for the uniform modulus of continuity and the laws of the iterated logarithm for ZH.     

Coding lemmata in L

Under the assumption that there exists an elementary embedding(henceforth abbreviated as and in particular under we prove a Coding Lemma for and find certain versions of it which are equivalent to strong regularity of cardinals below . We also prove that a stronger version of the Coding Lemma holds for a stationary set of ordinals below .Mathematics Subject Classification (2000):03E55     

Topological existence and stability for stackelberg problems

The aim of this paper is to study, in a topological framework, existence and stability for the solutions to a parametrized Stackelberg problem. To this end, approximate solutions are used, more precisely, -solutions and strict -solutions. The results given are of minimal character and the standard types of constraints are considered, that is, constant constraints, constraints defined by a finite number of inequalities, and more generally constraints defined by an arbitrary multifunction.     

Analytic combinatory calculi and the elimination of transitivity

We introduce, in a general setting, an analytic version of standard equational calculi of combinatory logic. Analyticity lies on the one side in the fact that these calculi are characterized by the presence of combinatory introduction rules in place of combinatory axioms, and on the other side in that the transitivity rule proves to be eliminable. Apart from consistency, which follows immediately, we discuss other almost direct consequences of analyticity and the main transitivity elimination theorem; in particular the Church–Rosser and the leftmostreduction theorems for the associated notions of reduction. The last two sections deal with analytic combinatory calculi with the extensionality rule added. Here, as far as the elimination of transitivity is concerned, we have only partial results, which unfortunately do not cover, at present, full CL + Ext. Yet, they are sufficient to prove the decidability of weaker combinatory calculi with extensionality, including e.g. BCK + Ext.Mathematics Subject Classification (2000):03B40, 03F03, 03F07     

A Special Basis of the Space of Meromorphic Sections on Riemann Surfaces

A special choice of basis for meromorphic sections of line bundles, in which all poles lie at the punctures, allows the decomposition of field operators (which are sections of bundles) into modes analogous to the standard decomposition on the sphere. Many of the calculational techniques used on the sphere can be reproduced for higher genus surfaces in this basis.Using this technique, in this paper, we compute a basis of K (the space of meromorphic sections on a Riemann surface, holomorphic away from two fixed points). This basis consists of the sections which have the expected zero or pole order at the two points.AMS Subject Classification (1991): 14H55     

A Note on π-Engel Conditions

In this paper we show that the weakly -Engel conditions are closely related to the existance of normal -complements; while the -Engel conditions are closely related to the -nilpotent groups.AMS Subject Classification (2000): 20D20     

Generalizations of Perfect, Semiperfect, and Semiregular Rings

For a ring R and a right R-module M, a submodule N of M is said to be -small in M if, whenever N + X = M with M/X singular, we have X = M. If there exists an epimorphism p: P M such that P is projective and Ker(p) is -small in P, then we say that P is a projective -cover of M. A ring R is called -perfect (resp., -semiperfect, -semiregular) if every R-module (resp., simple R-module, cyclically presented R-module) has a projective -cover. The class of all -perfect (resp., -semiperfect, -semiregular) rings contains properly the class of all right perfect (resp., semiperfect, semiregular) rings. This paper is devoted to various properties and characterizations of -perfect, -semiperfect, and -semiregular rings. We define (R) by (R)/Soc(R_R) = Jac(R/Soc(R_R)) and show, among others, the following results:

On the Completeness and Decidability of the Horn‐Like Fragment of the First‐Order Linear Temporal Logic

We prove the completeness and decidability of the Hornlike sequents, specifically, the socalled D₂sequents (of the firstorder linear temporal logic) considered in the author's paper [Lith. Math. J., 41(3), 266–281 (2001)]. In this paper, with the help of the infinitary calculus G_L, grounded by the author in his earlier papers, for D₂sequents we construct a D₂Sat calculus of the socalled saturated type consisting of decidable deductive procedures replacing the omegarule for the always operator. In the present paper, in order to prove the completeness and decidability of the calculus D₂Sat, we construct the socalled invariant decidable calculus D₂IN. We prove the equivalence of the calculi D₂IN, D₂Sat, and G _L ^** for the socalled saturated D₂sequents. From this equivalence, by reducing an arbitrary D₂sequent to a saturated D₂sequent, and also from the completeness of the G _L ^** calculus and decidability of the invariant calculus D₂IN, we deduce the completeness and decidability of the calculus D₂Sat in the class of D₂sequents.