Search

In this paper, we consider partial sums of martingale differences weighted by random variables drawn uniformly on the sphere, and globally independent of the martingale differences. Combining Lindeberg's method and a series of arguments due to Bobkov, Chistyakov and G{\"o}tze, we show that the Kolmogorov distance between the distribution of these weighted sums and the limiting Gaussian is "super-fast" of order (log n)^2 /n, under conditions allowing us to control the higher-order conditional moments of the martingale differences. We give an application of this result to the least squares estimator of the slope in the linear model with Gaussian design.

We prove the Almost Sure Invariance Principle (ASIP) with close to optimal error rates for nonuniformly hyperbolic maps. We do not assume exponential contraction along stable leaves, therefore our result covers in particular slowly mixing invertible dynamical systems as Bunimovich flowers, billiards with flat points as in Chernov and Zhang (2005) and Wojtkowski' (1990) system of two falling balls. For these examples, the ASIP is a new result, not covered by prior works for various reasons, notably because in absence of exponential contraction along stable leaves, it is challenging to employ the so-called Sinai's trick (Sinai 1972, Bowen 1975) of reducing a nonuniformly hyperbolic system to a nonuniformly expanding one. Our strategy follows our previous papers on the ASIP for nonuniformly expanding maps, where we build a semiconjugacy to a specific renewal Markov shift and adapt the argument of Berkes, Liu and Wu (2014). The main difference is that now the Markov shift is two-sided, the observables depend on the full trajectory, both the future and the past.

In this paper, we give precise rates of convergence in the strong invariance principle for stationary sequences of bounded real-valued random variables satisfying weak dependence conditions. One of the main ingredients is a new Fuk-Nagaev type inequality for a class of weakly dependent sequences. We describe also several classes of processes to which our results apply.

We give rates of convergence in the almost sure invariance principle for sums of dependent random variables with semi exponential tails, whose coupling coefficients decrease at a subexponential rate. We show that the rates in the strong invariance principle are in powers of log n. We apply our results to iid products of random matrices.

In this paper, we consider a generalization of the elephant random walk model. Compared to the usual elephant random walk, an interesting feature of this model is that the step sizes form a sequence of positive independent and identically distributed random variables instead of a fixed constant. For this model, we establish the law of the iterated logarithm, the central limit theorem, and we obtain rates of convergence in the central limit theorem with respect to the Kologmorov, Zolotarev and Wasserstein distances. We emphasize that, even in case of the usual elephant random walk, our results concerning the rates of convergence in the central limit theorem are new.

We prove a strong invariance principle for the Kantorovich distance between the empiricaldistribution and the marginal distribution of stationary $\alpha$-mixing sequences.

We study stochastic properties of the norm cocycle associated with iid products of positive matrices. We obtain the almost sure invariance principle (ASIP) with rate o(n 1/p) under the optimal condition of a moment or order p > 2 and the Berry-Esseen theorem with rate O(1/ $\sqrt$ n) under the optimal condition of a moment of order 3. The results are also valid for the matrix norm. For the matrix coefficients, we also have the ASIP but we obtain only partial results for the Berry-Esseen theorem. The proofs make use of coupling coefficients that surprisingly decay exponentially fast to 0 while there is only a polynomial decay in the case of invertible matrices. All the results are actually valid in the context of iid products of matrices leaving invariant a suitable cone.

In this paper, we give estimates of the quadratic transportation cost in the conditional central limit theorem for a large class of dependent sequences. Applications to irreducible Markov chains, dynamical systems generated by intermittent maps and $\tau$-mixing sequences are given.

Let $A_n= \varepsilon_n \cdots \varepsilon_1$, where $(\varepsilon_n)_{n \geq 1}$ is a sequence of independent random matrices taking values in $ GL_d(\mathbb R)$, $d \geq 2$, with common distribution $\mu$. In this paper, under standard assumptions on $\mu$ (strong irreducibility and proximality), we prove Berry-Esseen type theorems for $\log ( \Vert A_n \Vert)$ when $\mu$ has a polynomial moment. More precisely, we get the rate $((\log n) / n)^{q/2-1}$ when $\mu$ has a moment of order $q \in ]2,3]$ and the rate $1/ \sqrt{n} $ when $\mu$ has a moment of order $4$, which significantly improves earlier results in this setting.

We obtain large and moderate deviation estimates, as well as concentration inequalities, for a class of nonuniformly expanding maps with stretched exponential decay of correlations. In the large deviation regime, we also exhibit examples showing that the obtained upper bounds are essentially optimal.

The first aim of this paper is to wonder to what extent we can generalize the central limit theorem of Gordin [5] under the so-called L 1-projective criteria to ergodic stationary random fields when completely commuting filtrations are considered. Surprisingly it appears that this result cannot be extended to its full generality and that an additional condition is needed.

We give rates of convergence in the Central Limit Theorem for the coefficients and the spectral radius of the left random walk on GLd(R), assuming the existence of an exponential or polynomial moment.

In this paper we investigate the local limit theorem for additive functionals of nonstationary Markov chains that converge in distribution. We consider both the lattice and the non-lattice cases. The results are also new in the stationary setting and lead to local limit theorems linked to convergence to stable distributions. The conditions are imposed to individual summands and are expressed in terms of lower psi-mixing coefficients., Comment: 24 pages

Social science studies dealing with control in networks typically resort to heuristics or describing the static control distribution. Optimal policies, however, require interventions that optimize control over a socioeconomic network subject to real-world constraints. We integrate optimisation tools from deep-learning with network science into a framework that is able to optimize such interventions in real-world networks. We demonstrate the framework in the context of corporate control, where it allows to characterize the vulnerability of strategically important corporate networks to sensitive takeovers, an important contemporaneous policy challenge. The framework produces insights that are relevant for governing real-world socioeconomic networks, and opens up new research avenues for improving our understanding and control of such complex systems.

In this paper, we give rates of convergence, for minimal distances and for the uniform distance, between the law of partial sums of martingale differences and thelimiting Gaussian distribution. More precisely, denoting by $P_{X}$ the law of a random variable $X$ and by $G_{a}$ the normal distribution ${\mathcal N} (0,a)$, we are interested by giving quantitative estimates for the convergence of $P_{S_n/\sqrt{V_n}}$ to $G_1$, where $S_n$ is the partial sum associated with either martingale differences sequences or more general dependent sequences, and $V_n= {\rm Var}(S_n)$. Applications to linear statistics, non stationary $\rho$-mixing sequences and sequential dynamical systems are given.

In this paper we investigate the local limit theorem for additive functionals of a nonstationary Markov chain with finite or infinite second moment. The moment conditions are imposed on the individual summands and the weak dependence structure is expressed in terms of some uniformly mixing coefficients., Comment: 21 pages

Crossover is the process of recombining the genetic features of two parents. For many applications where crossover is applied to permutations, relevant genetic features are pairs of adjacent elements, also called edges in the permutation order. Recombination of edges without errors is thought to be an NP-hard problem, typically approximated by heuristics that either introduce new edges or are only able to produce a small variety of offspring. Here, we derive an algorithm for crossover of permutations that achieves perfect transmission of edges and produces a uniform sampling of all possible offspring, in quadratic average computation time. The algorithm and its derivation reveal a link between cycle crossover (CX) and edge assembly crossover (EAX), offering a new perspective on these well-established algorithms. We also describe a modification of the algorithm that generates the mathematically optimal offspring for the asymmetric travelling salesman problem.

In this paper, we give explicit rates in the central limit theorem and in the almost sure invariance principle for general R d-valued cocycles that appear in the study of the left random walk on linear groups. Our method of proof lies on a suitable martingale approximation and on a careful estimation of some coupling coefficients linked with the underlying Markov structure. Concerning the martingale part, the available results in the literature are not accurate enough to give almost optimal rates whether in the central limit theorem for the Wasserstein distance, or in the strong approximation. A part of this paper is devoted to circumvent this issue. We then exhibit near optimal rates both in the central limit theorem in terms of Wasserstein distance and in the almost sure invariance principle for R d-valued martingales with stationary increments having moments of order p $\in$]2, 3] (the case of sequences of reversed martingale differences is also considered). Note also that, as an application of our results for general R d-valued cocycles, a special attention is paid to the Iwasawa cocycle and the Cartan projection for reductive Lie groups.

Let (X k) be a strictly stationary sequence of random variables with values in some Polish space E and common marginal $\mu$, and (A k) k>0 be a sequence of Borel sets in E. In this paper, we give some conditions on (X k) and (A k) under which the events {X k $\in$ A k } satisfy the Borel-Cantelli (or strong Borel-Cantelli) property. In particular we prove that, if $\mu$(lim sup n A n) > 0, the Borel-Cantelli property holds for any absolutely regular sequence. In case where the A k 's are nested, we show, on some examples, that a rate of convergence of the mixing coefficients is needed. Finally we give extensions of these results to weaker notions of dependence, yielding applications to non-irreducible Markov chains and dynamical systems.

For a large class of quickly mixing dynamical systems, we prove that the error in the almost sure approximation with a Brownian motion is of order O((log n)^a) with a $\ge$ 2. Specifically, we consider nonuniformly expanding maps with exponential and stretched exponential decay of correlations, with one-dimensional H{\"o}lder continuous observables.

We establish some deviation inequalities, moment bounds and almost sure results for the Wasserstein distance of order p $\in$ [1, $\infty$) between the empirical measure of independent and identically distributed R d-valued random variables and the common distribution of the variables. We only assume the existence of a (strong or weak) moment of order rp for some r > 1, and we discuss the optimality of the bounds. Mathematics subject classification. 60B10, 60F10, 60F15, 60E15.

In this paper we develop non-stationary martingale techniques for dependent data. We shall stress the non-stationary version of the projective Maxwell-Woodroofe condition, which will be essential for obtaining maximal inequalities and functional central limit theorem for the following examples: nonstationary \r{ho}-mixing sequences, functions of linear processes with non-stationary innovations, quenched version of the functional central limit theorem for a stationary sequence, evolutions in random media such as a process sampled by a shifted Markov chain., Comment: 30 pages

Given a large sample covariance matrix $S_N=\frac 1n\Gamma_N^{1/2}Z_N Z_N^*\Gamma_N^{1/2}\, ,$ where $Z_N$ is a $N\times n$ matrix with i.i.d. centered entries, and $\Gamma_N$ is a $N\times N$ deterministic Hermitian positive semidefinite matrix, we study the location and fluctuations of $\lambda_{\max}(S_N)$, the largest eigenvalue of $S_N$ as $N,n\to\infty$ and $Nn^{-1} \to r\in(0,\infty)$ in the case where the empirical distribution $\mu^{\Gamma_N}$ of eigenvalues of $\Gamma_N$ is tight (in $N$) and $\lambda_{\max}(\Gamma_N)$ goes to $+\infty$. These conditions are in particular met when $\mu^{\Gamma_N}$ weakly converges to a probability measure with unbounded support on $\mathbb{R}^+$. We prove that asymptotically $\lambda_{\max}(S_N)\sim \lambda_{\max}(\Gamma_N)$. Moreover when the $\Gamma_N$'s are block-diagonal, and the following {\em spectral gap condition} is assumed:$$\limsup_{N\to\infty} \frac{\lambda_2(\Gamma_N)}{\lambda_{\max}(\Gamma_N)}<1,$$where $\lambda_2(\Gamma_N)$ is the second largest eigenvalue of $\Gamma_N$, we prove Gaussian fluctuations for $\lambda_{\max}(S_N)/\lambda_{\max}(\Gamma_N)$ at the scale $\sqrt{n}$.In the particular case where $Z_N$ has i.i.d. Gaussian entries and $\Gamma_N$ is the $N\times N$ autocovariance matrix of a long memory Gaussian stationary process $({\mathcal X}_t)_{t\in\mathbb{Z}}$, the columns of $\Gamma_N^{1/2} Z_N$ can be considered as $n$ i.i.d. samples of the random vector $({\mathcal X}_1,\dots,{\mathcal X}_N)^T$. We then prove that $\Gamma_N$ is similar to a diagonal matrix which satisfies all the required assumptions of our theorems, hence our results apply to this case.

We prove the one-dimensional almost sure invariance principle with essentially optimal rates for slowly (polynomially) mixing deterministic dynamical systems, such as Pomeau-Manneville intermittent maps, with H\"older continuous observables. Our rates have form $o(n^\gamma L(n))$, where $L(n)$ is a slowly varying function and $\gamma$ is determined by the speed of mixing. We strongly improve previous results where the best available rates did not exceed $O(n^{1/4})$. To break the $O(n^{1/4})$ barrier, we represent the dynamics as a Young-tower-like Markov chain and adapt the methods of Berkes-Liu-Wu and Cuny-Dedecker-Merlev\`ede on the Koml\'os-Major-Tusn\'ady approximation for dependent processes., Comment: 34 pages

In this paper we propose an alternative to the coupling of Berkes, Liu and Wu [1] to obtain strong approximations for partial sums of dependent sequences. The main tool is a new Rosen-thal type inequality expressed in terms of the coupling coefficients. These coefficients are well suited to some classes of Markov chains or dynamical systems, but they also give new results for smooth functions of linear processes.

The famous results of Koml\'os, Major and Tusn\'ady (see [15] and [17]) state that it is possible to approximate almost surely the partial sums of size n of i.i.d. centered random variables in L p (p > 2) by a Wiener process with an error term of order o(n 1/p). Very recently, Berkes, Liu and Wu [3] extended this famous result to partial sums associated with functions of an i.i.d. sequence, provided a condition on a functional dependence measure in L p is satisfied. In this paper, we adapt the method of Berkes, Liu and Wu to partial sums of functions of random iterates. Taking advantage of the Markovian setting, we shall give new dependent conditions, expressed in terms of a natural coupling (in L $\infty$ or in L 1), under which the strong approximation result holds with rate o(n 1/p). As we shall see our conditions are well adapted to a large variety of models, including left random walks on GL d (R), contracting iterated random functions, autoregressive Lipschitz processes, and some ergodic Markov chains. We also provide some examples showing that our L 1-coupling condition is in some sense optimal.

Using martingale methods, we obtain some upper bounds for large and moderate deviations of products of independent and identically distributed elements of GL d (R). We investigate all the possible moment conditions, from super-exponential moments to weak moments of order p \textgreater{} 1, to get a complete picture of the situation. We also prove a moderate deviation principle under an appropriate tail condition.

We consider Markov chains which are polynomially mixing, in a weak sense expressed in terms of the space of functions on which the mixing speed is controlled. In this context, we prove polynomial large and moderate deviations inequalities. These inequalities can be applied in various natural situations coming from probability theory or dynamical systems. Finally, we discuss examples from these various settings showing that our inequalities are sharp.

We study the Lp-integrated risk of some classical estimators of the density, when the observations are drawn from a strictly stationary sequence. The results apply to a large class of sequences, which can be non-mixing in the sense of Rosenblatt and long-range dependent. The main probabilistic tool is a new Rosenthal-type inequality for partial sums of BV functions of the variables. As an application, we give the rates of convergence of regular Histograms, when estimating the invariant density of a class of expanding maps of the unit interval with a neutral fixed point at zero. These Histograms are plotted in the section devoted to the simulations.

We prove a deviation bound for the maximum of partial sums of functions of $\alpha$-dependent sequences as defined in Dedecker, Gou{\"e}zel and Merlev{\`e}de (2010). As a consequence, we extend the Rosenthal inequality of Rio (2000) for $\alpha$-mixing sequences in the sense of Rosenblatt (1956) to the larger class of $\alpha$-dependent sequences. Starting from the deviation inequality, we obtain upper bounds for large deviations and an H{\"o}lderian invariance principle for the Donsker line. We illustrate our results through the example of intermittent maps of the interval, which are not $\alpha$-mixing in the sense of Rosenblatt.

In this paper we obtain a Bernstein type inequality for the sum of self-adjoint centered and geometrically absolutely regular random matrices with bounded largest eigenvalue. This inequality can be viewed as an extension to the matrix setting of the Bernstein-type inequality obtained by Merlev\`ede et al. (2009) in the context of real-valued bounded random variables that are geometrically absolutely regular. The proofs rely on decoupling the Laplace transform of a sum on a Cantor-like set of random matrices., Comment: 22 pages