Large deviations for optimal filtering with fractional Brownian motion

We establish large deviation estimates for the optimal filter where the observation process is corrupted by a fractional Brownian motion. The observation process is transformed to an equivalent model which is driven by a standard Brownian motion. The large deviations in turn are established by proving qualitative properties of perturbations of the equivalent observation process.     

关于大偏差概率的一个界

研究得到了关于随机和S(t)=∑N(t)i=1Xi,t≥0大偏差的幂的一个界,其中(N(t))t≥0是一族非负整值随机变量,(Xn)n∈N是独立同分布的随机变量,其共同的分布函数是F与(N(t))t≥0独立.本结论是在假设分布函数F的右尾属于ERV族的情况下得到的.     

Colliding stacks: A large deviations analysis

We analyze the performance of a prototypical scheme for shared storage allocation: two initially empty stacks evolving in a contiguous block of memory of size m. We treat the case in which the stacks are more likely to shrink than grow, but with the probabilities of insertion and deletion allowed to depend arbitrarily on stack height as a fraction of m. New results are obtained on the m → ∞ asymptotics of the stack collision time, and of the final stack heights. The results of Wentzell and Freidlin on the large deviations of Markov chains are used, and the relation of their formalism to the Hamiltonian formulation of classical mechanics is emphasized. Certain results on higher-order asymptotics follow from WKB expansions.     

A unified approach to the large deviations for small perturbations of random evolution equations

LetX ^ɛ = {X ^ɛ (t ; 0 ⩽t ⩽ 1 } (ɛ > 0) be the processes governed by the following stochastic differential equations:

Self-normalized large deviations for stationary sequences

In this note, we prove the large deviation principle for self-normalized partial sums of a stationary weakly dependent random sequence. This revised version was published online in June 2006 with corrections to the Cover Date.     

An application of berezin integration to large deviations

We apply a method invented by Luttinger to obtain an asymptotic expansion in powers of 1/T forE[e ^–TF()]. is theproportion of local time andE is the expectation for a time-homogeneous Markov process withN states. The result extends the large-deviation result of Donsker and Varadhan by providing a complete expansion as opposed to only the leading term.     

Sample path large deviations and intree networks

Using the contraction principle, in this paper we derive a set of closure properties for sample path large deviations. These properties include sum, reduction, composition and reflection mapping. Using these properties, we show that the exponential decay rates of the steady state queue length distributions in an intree network with routing can be derived by a set of recursive equations. The solution of this set of equations is related to the recently developed theory of effective bandwidth for high speed digital networks, especially ATM networks. We also prove a conditional limit theorem that illustrates how a queue builds up in an intree network.     

Martingales and large deviations for binary search trees

We establish an almost sure large deviations theorem for the depth of the external nodes of binary search trees (BSTs). To achieve this, a parametric family of martingales is introduced. This family also allows us to get asymptotic results on the number of external nodes at deepest level. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 112–127, 2001     

Nonlinear filtering of semi-Dirichlet processes

Herein, we consider the nonlinear filtering problem for general right continuous Markov processes, which are assumed to be associated with semi-Dirichlet forms. First, we derive the filtering equations in the semi-Dirichlet form setting. Then, we study the uniqueness of solutions of the filtering equations via the Wiener chaos expansions. Our results on the Wiener chaos expansions for nonlinear filters with possibly unbounded observation functions are novel and have their own interests. Furthermore, we investigate the absolute continuity of the filtering processes with respect to the reference measures and derive the density equations for the filtering processes.     

次线性期望下独立随机变量列的大偏差和中偏差

本文研究在次线性期望下的独立随机变量列的大偏差和中偏差原理. 利用次可加方法, 我们得 到次线性期望下的大偏差原理. 与次线性期望下的中心极限定理相应的中偏差原理也被建立.     

Extended large deviations

LetX ₁,X ₂,..., be a sequence ofi.i.d. random variables with a moment generating function finite in a neighborhood of 0. Further, for each integern1, letS _n denote the sum of the firstn terms in this sequence. We study the extended large deviation of such sums, meaning,P{S _n >n _n }, where _n is any sequence converging to infinity. We also derive functional extended large deviation theorems and then apply them to obtain functional versions of the Erdös-Rényi strong law of large numbers.Research partially supported by an NSF Grant.     

On replica symmetry of large deviations in random graphs

The following question is due to Chatterjee and Varadhan (2011). Fix and take , the Erd?s‐Rényi random graph with edge density p, conditioned to have at least as many triangles as the typical . Is G close in cut‐distance to a typical ? Via a beautiful new framework for large deviation principles in , Chatterjee and Varadhan gave bounds on the replica symmetric phase, the region of where the answer is positive. They further showed that for any small enough p there are at least two phase transitions as r varies. We settle this question by identifying the replica symmetric phase for triangles and more generally for any fixed d‐regular graph. By analyzing the variational problem arising from the framework of Chatterjee and Varadhan we show that the replica symmetry phase consists of all such that lies on the convex minorant of where is the rate function of a binomial with parameter p. In particular, the answer for triangles involves rather than the natural guess of where symmetry was previously known. Analogous results are obtained for linear hypergraphs as well as the setting where the largest eigenvalue of is conditioned to exceed the typical value of the largest eigenvalue of . Building on the work of Chatterjee and Diaconis (2012) we obtain additional results on a class of exponential random graphs including a new range of parameters where symmetry breaking occurs. En route we give a short alternative proof of a graph homomorphism inequality due to Kahn (2001) and Galvin and Tetali (2004). © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 109–146, 2015     

Large deviations and moderate deviations for kernel density estimators of directional data

Let fn be the non-parametric kernel density estimator of directional data based on a kernel function K and a sequence of independent and identically distributed random variables taking values in d-dimensional unit sphere Sd-1. It is proved that if the kernel function is a function with bounded variation and the density function f of the random variables is continuous, then large deviation principle and moderate deviation principle for {sup x∈sd-1 ｜fn（x） - E（fn（x））｜, n ≥ 1} hold.     

关于重尾随机和大偏差的一个注记

设｛Xκ，κ≥1｝为一列独立同分布的非随机变量，且具有共同的分布函数F。记Sn为序列｛Xκ，κ≥1｝的前n项部分和。在F属于ERV分布族的假定下，文中证明了关于随机和SN(t)的随机中心化的精细大偏差结果。这里N（t）为一个与｛Xκ，κ≥1｝独立的非负整数值的随机过程。     

Heavy traffic approximations of large deviations of feedforward queueing networks

We consider a multi-class feedforward queueing network with first come first serve queueing discipline and deterministic services and routing. The large deviation asymptotics of tail probabilities of the distribution of the workload vector can be characterized by convex path space minimization problems with non-linear constraints. So far there exists no numerical algorithm which could solve such minimization problems in a general way. When the queueing network is heavily loaded it can be approximated by a reflected Brownian motion. The large deviation asymptotics of tail probabilities of the distribution of this heavy traffic limit can again be characterized by convex path space minimization problems with non-linear constraints. However, due to their less complicated structure there exist algorithms to solve such minimization problems. In this paper we show that, as the network tends to a heavy traffic limit, the solution of the large deviation minimization problems of the network approaches the solution of the corresponding minimization problems of a reflected Brownian motion. Stated otherwise, we show that large deviation and heavy traffic asymptotics can be interchanged. We prove this result in the case when the network is initially empty. Without proof we state the corresponding result in the stationary case. We present an illuminating example with two queues. This revised version was published online in June 2006 with corrections to the Cover Date.     

Precise large deviations for a customer-based individual risk model

In this paper,we propose a customer-based individual risk model,in which potential claims by customers are described as i.i.d.heavy-tailed random variables,but different insurance policy holders are allowed to have different probabilities to make actual claims.Some precise large deviation results for the prospective-loss process are derived under certain mild assumptions,with emphasis on the case of heavy-tailed distribution function class ERV(extended regular variation).Lundberg type limiting results on the finite time ruin probabilities are also investigated.     

LARGE DEVIATIONS AND MODERATE DEVIATIONS FOR m-NEGATIVELY ASSOCIATED RANDOM VARIABLES

M-negatively associated random variables,which generalizes the classical one of negatively associated random variables and includes m-dependent sequences as its par- ticular case,are introduced and studied.Large deviation principles and moderate devi- ation upper bounds for stationary m-negatively associated random variables are proved. Kolmogorov-type and Marcinkiewicz-type strong laws of large numbers as well as the three series theorem for m-negatively associated random variables are also given.     

Densities of idempotent measures and large deviations

Considering measure theory in which the semifield of positive real numbers is replaced by an idempotent semiring leads to the notion of idempotent measure introduced by Maslov. Then, idempotent measures or integrals with density correspond to supremums of functions for the partial order relation induced by the idempotent structure. In this paper, we give conditions under which an idempotent measure has a density and show by many examples that they are often satisfied. These conditions depend on the lattice structure of the semiring and on the Boolean algebra in which the measure is defined. As an application, we obtain a necessary and sufficient condition for a family of probabilities to satisfy the large deviation principle.

     

Probabilistic bounds (via large deviations) for the solutions of stochastic programming problems

Several exponential bounds are derived by means of the theory of large deviations for the convergence of approximate solutions of stochastic optimization problems. The basic results show that the solutions obtained by replacing the original distribution by an empirical distribution provides an effective tool for solving stochastic programming problems.Supported in part by a grant from the US-Israel Science Foundation.     

Large deviations ordering of point processes in some queueing networks

Given a stochastic ordering between point processes, say that a p.p. N is smooth if it is less than the Poisson process with the same average intensity for this ordering. In this article we investigate whether initially smooth processes retain their smoothness as they cross a network of FIFO ·/D/1 queues along fixed routes. For the so-called strong variability ordering we show that point processes remain smooth as they proceed through a tandem of quasi-saturated (i.e., loaded to 1) M+·/D/1 queues. We then introduce the Large Deviations ordering, which involves comparison of the rate functions associated with Large Deviations Principles satisfied by the point processes. For this ordering, we show that smoothness is retained when the processes cross a feed-forward network of unsaturated ·/D/1 queues. We also examine the LD characteristics of a deterministic p.p. at the output of an M+·/D/1 queue. This revised version was published online in June 2006 with corrections to the Cover Date.