A counterexample to the DeMarco‐Kahn upper tail conjecture

Given a fixed graph H, what is the (exponentially small) probability that the number X_H of copies of H in the binomial random graph G_n,p is at least twice its mean? Studied intensively since the mid 1990s, this so‐called infamous upper tail problem remains a challenging testbed for concentration inequalities. In 2011 DeMarco and Kahn formulated an intriguing conjecture about the exponential rate of decay of  for fixed ε > 0. We show that this upper tail conjecture is false, by exhibiting an infinite family of graphs violating the conjectured bound.     

Stationary tail probabilities in exponential server tandems with renewal arrivals

The problem considered is that of estimating the tail stationary probability for two exponential server queues in series fed by renewal arrivals. We compute the tail of the marginal queue length distribution at the second queue. The marginal at the first queue is known by the classical result for the GI/M/1 queue. The approach involves deriving necessary and sufficient conditions on the paths of the arrival and virtual service processes in order to get a large queue size at the second queue. We then use large deviations estimates of the probabilities of these paths, and solve a constrained convex optimization problem to find the most likely path leading to a large queue size. We find that the stationary queue length distribution at the second queue has an exponentially decaying tail, and obtain the exact rate of decay.Research supported in part by NSF grant NCR 88-57731 and the AT & T Foundation.     

Tail estimates for one-dimensional non-nearest-neighbor random walk in random environment

Suppose that the integers are assigned i.i.d. random variables {(β gx , . . . , β 1x , α x )} (each taking values in the unit interval and the sum of them being 1), which serve as an environment. This environment defines a random walk {X n } (called RWRE) which, when at x, moves one step of length 1 to the right with probability α x and one step of length k to the left with probability β kx for 1≤ k≤ g. For certain environment distributions, we determine the almost-sure asymptotic speed of the RWRE and show that the chance of the RWRE deviating below this speed has a polynomial rate of decay. This is the generalization of the results by Dembo, Peres and Zeitouni in 1996. In the proof we use a large deviation result for the product of random matrices and some tail estimates and moment estimates for the total population size in a multi-type branching process with random environment.     

Rough asymptotics for tandem non-homogeneous $$M/G/\infty$$ queues via Poissonized empirical processes

We obtain a large deviations principle and moderate deviations principle for the joint distribution of the queue length processes and departure process for tandem queues. The results are obtained by applying a result providing necessary and sufficient conditions on a class of functions for a large deviations principle and moderate deviations principle to hold for a Poissonized empirical process over the class of functions. As an application, we examine how large queue lengths and numbers of departures are built up. This revised version was published online in June 2006 with corrections to the Cover Date.     

Robust estimation in inverse problems via quantile coupling

In this article we consider a sequence of hierarchical space model of inverse problems.The underlying function is estimated from indirect observations over a variety of error distributions including those that are heavy-tailed and may not even possess variances or means.The main contribution of this paper is that we establish some oracle inequalities for the inverse problems by using quantile coupling technique that gives a tight bound for the quantile coupling between an arbitrary sample p-quantile and a normal variable,and an automatic selection principle for the nonrandom filters.This leads to the data-driven choice of weights.We also give an algorithm for its implementation.The quantile coupling inequality developed in this paper is of independent interest,because it includes the median coupling inequality in literature as a special case.     

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)     

Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales

The Alon–Roichman theorem states that for every ε> 0 there is a constant c(ε), such that the Cayley graph of a finite group G with respect to c(ε)log ∣G∣ elements of G, chosen independently and uniformly at random, has expected second largest eigenvalue less than ε. In particular, such a graph is an expander with high probability. Landau and Russell, and independently Loh and Schulman, improved the bounds of the theorem. Following Landau and Russell we give a new proof of the result, improving the bounds even further. When considered for a general group G, our bounds are in a sense best possible. We also give a generalization of the Alon–Roichman theorem to random coset graphs. Our proof uses a Hoeffding‐type result for operator valued random variables, which we believe can be of independent interest. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

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.     

The Janson inequalities for general up‐sets

Janson and Janson, ?uczak and Ruciński proved several inequalities for the lower tail of the distribution of the number of events that hold, when all the events are up‐sets (increasing events) of a special form—each event is the intersection of some subset of a single set of independent events (i.e., a principal up‐set). We show that these inequalities in fact hold for arbitrary up‐sets, by modifying existing proofs to use only positive correlation, avoiding the need to assume positive correlation conditioned on one of the events. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 391–395, 2015     

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

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

Moderate Deviations and Large Deviations for Kernel Density Estimators

Let f _n be the non-parametric kernel density estimator based on a kernel function K and a sequence of independent and identically distributed random variables taking values in ^d . It is proved that if the kernel function is an integrable function with bounded variation, and the common density function f of the random variables is continuous and f(x) 0 as |x| , then the moderate deviation principle and large deviation principle for hold.     

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.     

The missing log in large deviations for triangle counts

This paper solves the problem of sharp large deviation estimates for the upper tail of the number of triangles in an Erd?s‐Rényi random graph, by establishing a logarithmic factor in the exponent that was missing till now. It is possible that the method of proof may extend to general subgraph counts. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 437–451, 2012     

Asymptotic Analysis for Random Walks with Nonidentically Distributed Jumps Having Finite Variance

Let ξ₁,ξ₂,... be independent random variables with distributions F₁F₂,... in a triangular array scheme (F _i may depend on some parameter). Assume that Eξ _i = 0, Eξ _i ² < ∞, and put \(S_n = \sum {_{i = 1}^n \;} \xi _i ,\;\overline S _n = \max _{k \leqslant n} S_k\). Assuming further that some regularly varying functions majorize or minorize the “averaged” distribution \(F = \frac{1}{n}\sum {_{i = 1}^n F_i }\), we find upper and lower bounds for the probabilities P(S _n > x) and \(P(\bar S_n > x)\). We also study the asymptotics of these probabilities and of the probabilities that a trajectory {S _k } crosses the remote boundary {g(k)}; that is, the asymptotics of P(max_k≤n(S _k ? g(k)) > 0). The case n = ∞ is not excluded. We also estimate the distribution of the first crossing time.     

三维Wiener Sausage体积的中偏差

令{β(s),s≥0}表示R~3空间中的标准Brown运动,|W_r(t)|表示由{β(s),s≥0}产生的观察至时间t且以r为半径的Wiener sausage的体积.由中心极限定理可知,(|W_r(t)|-E|W_r(t)|)/(?)弱收敛至正态分布.本文研究这种情况下的中偏差.     

On the spectrum of Markov semigroups via sample path large deviations

The essential spectral radius of a sub-Markovian process is defined as the infimum of the spectral radiuses of all local perturbations of the process. When the family of rescaled processes satisfies sample path large deviation principle, the spectral radius and the essential spectral radius are expressed in terms of the rate function. The paper is motivated by applications to reflected diffusions and jump Markov processes describing stochastic networks for which the sample path large deviation principle has been established and the rate function has been identified while essential spectral radius has not been calculated.     

An approximation for the nonlinear filtering problem,with error bound †

For the standard continuous-time nonlinear filtering problem an approximation approach is derived. The approximate filter is given by the solution to an appropriate discrete-time approximating filtering problem that can be explicitly solved by a finite-dimensional procedure. Furthermore an explicit upper bound for the approximation error is derived. The approximating problem is obtained by first approximating the signal and then using measure transformation to express the original observation process in terms of the approximating signal     

Concentration inequalities for random fields via coupling

We present a new and simple approach to concentration inequalities in the context of dependent random processes and random fields. Our method is based on coupling and does not use information inequalities. In case one has a uniform control on the coupling, one obtains exponential concentration inequalities. If such a uniform control is no more possible, then one obtains polynomial or stretched-exponential concentration inequalities. Our abstract results apply to Gibbs random fields, both at high and low temperatures and in particular to the low-temperature Ising model which is a concrete example of non-uniformity of the coupling.      

Sharp error estimates for the numerical differentiation formulas on the classes of entire functions of exponential type

We establish sharp error estimates for some numerical di.erentiation formulas on the classes of entire functions of exponential type. The estimates strengthen some classical sharp inequalities of approximation theory.     

An Inequality for Large Deviation Probabilities of Sums of Bounded i.i.d. Random Variables

We provide precise bounds for tail probabilities, say {M _n x}, of sums M _n of bounded i.i.d. random variables. The bounds are expressed through tail probabilities of sums of i.i.d. Bernoulli random variables. In other words, we show that the tails are sub-Bernoullian. Sub-Bernoullian tails are dominated by Gaussian tails. Possible extensions of the methods are discussed.