Search

The following learning problem arises naturally in various applications: Given a finite sample from a categorical or count time series, can we learn a function of the sample that (nearly) maximizes the probability of correctly guessing the values of a given portion of the data using the values from the remaining parts? Unlike the classical task of estimating conditional probabilities in a stochastic process, our approach avoids explicitly estimating these probabilities. We propose a non-parametric guessing function with a learning rate that is independent of the alphabet size. Our analysis focuses on a broad class of time series models that encompasses finite-order Markov chains, some hidden Markov chains, Poisson regression for count process, and one-dimensional Gibbs measures. Additionally, we establish a minimax lower bound for the rate of convergence of the risk associated with our guessing problem. This lower bound matches the upper bound achieved by our estimator up to a logarithmic factor, demonstrating its near-optimality., Comment: 21 pages, submitted

We consider a general class of birth-and-death processes with state space $\{0,1,2,3,\ldots\}$ which describes the size of a population going eventually to extinction with probability one. We obtain the complete spectrum of the generator of the process killed at $0$ in the large population limit, that is, we scale the process by a parameter $K$, and take the limit $K\to+\infty$. We assume that the differential equation $\mathrm{d} x/\mathrm{d} t=b(x)-d(x)$ describing the infinite population limit (in any finite-time interval) has a repulsive fixed point at $0$, and an attractive fixed point $x_*>0$. We prove that, asymptotically, the spectrum is the superposition of two spectra. One is the spectrum of the generator of an Ornstein-Uhlenbeck process, which is $n(b'(x_*)-d'(x_*))$, $n\ge 0$. The other one is the spectrum of a continuous-time binary branching process conditioned on non-extinction, and is given by $n(d'(0)-b'(0))$, $n\ge 1$. A major difficulty is that different scales and function spaces are involved. We work at the level of the eigenfunctions that we split over different regions, and study their asymptotic dependence on $K$ in each region. In particular, we prove that the spectral gap goes to $\min\big\{b'(0)-d'(0),\,d'(x_*)-b'(x_*)\big\}$. This work complements a previous work of ours in which we studied the approximation of the quasi-stationary distribution and of the mean time to extinction., Comment: 42 pages, 1 figure, submitted

In this short essay, we show how computer experiments, and especially visualization, allowed for the investigation and discovery of phenomena which would have passed unnoticed. We shall also highlight the importance of interactivity between the computer and the user. We do this by surveying several historical examples from mathematics and the physical sciences. Many pictures, and even hyperlinks to online interactive numerical experiments, are provided. Needless to say that we do not claim to be exhaustive, and that the chosen examples reflect our taste as well as our limited knowledge. Hyperlinks to several online interactive digital experiments are provided., Comment: 27 pages, 29 figures, and hyperlinks to online interactive digital experiments

For a general class of lattice-spin systems, we prove that an abstract Gaussian concentration bound implies positivity of lower relative entropy density. As a consequence we obtain uniqueness of translation-invariant Gibbs measures from the Gaussian concentration bound in this general setting. This extends earlier results from [Chazottes-Moles-REdig-Ugalde] with a different and very short proof., Comment: 13 pages. Submitted

We consider spin-flip dynamics of configurations in $\{-1,1\}^{\mathbb{Z}^d}$, and study the time evolution of concentration inequalities. For "weakly interacting" dynamics we show that the Gaussian concentration bound is conserved in the course of time and it is satisfied by the unique stationary Gibbs measure. Next we show that, for a general class of translation-invariant spin-flip dynamics, it is impossible to evolve in finite time from a low-temperature Gibbs state towards a measure satisfying the Gaussian concentration bound. Finally, we consider the time evolution of the weaker uniform variance bound, and show that this bound is conserved under a general class of spin-flip dynamics., Comment: 25 pages, to appear in J. Stat. Phys. (2021)

We construct finite-range interactions on $\mathcal{S}^{\mathbb{Z}^2}$, where $\mathcal{S}$ is a finite set, for which the associated equilibrium states (i.e., the shift-invariant Gibbs states) fail to converge as temperature goes to zero. More precisely, if we pick any one-parameter family $(\mu_\beta)_{\beta>0}$ in which $\mu_\beta$ is an equilibrium state at inverse temperature $ \beta$ for this interaction, then $\lim_{\beta\to\infty}\mu_\beta$ does not exist. This settles a question posed by the first author and Hochman who obtained such a non-convergence behavior when $d\geq 3$, $d$ being the dimension of the lattice., Comment: 25 pages, 8 figures

We consider equilibrium states (that is, shift-invariant Gibbs measures) on the configuration space $S^{\mathbb{Z}^d}$ where $d\geq 1$ and $S$ is a finite set. We prove that if an equilibrium state for a shift-invariant uniformly summable potential satisfies a Gaussian concentration bound, then it is unique. Equivalently, if there exist several equilibrium states for a potential, none of them can satisfy such a bound., Comment: 24 pages. Accepted for publication in J. Stat. Phys. (2020). Some typos have been corrected. Proposition 2.2 has been strengthened: if a Gaussian concentration bound holds then the measure is mixing, not only ergodic

We obtain optimal Gaussian concentration bounds (GCBs) for stochastic chains of unbounded memory (SCUMs) on countable alphabets. These stochastic processes are also known as "chains with complete connections" or "$g$-measures". We consider two different conditions on the kernel: (1) when the sum of its oscillations is less than one, or (2) when the sum of its variations is finite, i.e., belongs to $\ell^1(\mathbb{N})$. We also obtain explicit constants as functions of the parameters of the model. The proof is based on maximal coupling. Our conditions are optimal in the sense that we exhibit examples of SCUMs that do not have GCB and for which the sum of oscillations is strictly larger than one, or the variation belongs to $\ell^{1+\epsilon}(\mathbb{N})$ for any $\epsilon > 0$. These examples are based on the existence of phase transitions. We also extend the validity of GCB to a class of functions which can depend on infinitely many coordinates. We illustrate our results by three applications. First, we derive a Dvoretzky-Kiefer-Wolfowitz type inequality which gives a uniform control on the fluctuations of the empirical measure. Second, in the finite-alphabet case, we obtain an upper bound on the $\bar{d}$-distance between two stationary SCUMs and, as a by-product, we obtain new (explicit) bounds on the speed of Markovian approximation in $\bar{d}$. Third, we obtain exponential rate of convergence for Birkhoff sums of a certain class of observables., Comment: 33 pages. The main difference with the first version is that Theorem 3.2 now holds for countably infinite alphabets. We corrected many typos and improved the presentation

We study a class of multi-species birth-and-death processes going almost surely to extinction and admitting a unique quasi-stationary distribution (qsd for short). When rescaled by $K$ and in the limit $K\to+\infty$, the realizations of such processes get close, in any fixed finite-time window, to the trajectories of a dynamical system whose vector field is defined by the birth and death rates. Assuming that this dynamical has a unique attracting fixed point, we analyzed in a previous work what happens for large but finite $K$, especially the different time scales showing up. In the present work, we are mainly interested in the following question: Observing a realization of the process, can we determine the so-called engineering resilience? To answer this question, we establish two relations which intermingle the resilience, which is a macroscopic quantity defined for the dynamical system, and the fluctuations of the process, which are microscopic quantities. Analogous relations are well known in nonequilibrium statistical mechanics. To exploit these relations, we need to introduce several estimators which we control for times between $\log K$ (time scale to converge to the qsd) and $\exp(K)$ (time scale of mean time to extinction)., Comment: This is, up to layout details, the published version (2020) in the Journal de l'\'Ecole polytechnique. See https://jep.centre-mersenne.org/item/JEP_2020__7__943_0/

We consider the behavior of the Gaussian concentration bound (GCB) under stochastic time evolution. More precisely, we consider a Markovian diffusion process on $\mathbb{R}^d$ and start the process from an initial distribution $\mu$ that satisfies GCB. We then study the question whether GCB is preserved under the time-evolution, and if yes, how the constant behaves as a function of time. In particular, if for the constant we obtain a uniform bound, then we can also conclude properties of the stationary measure(s) of the diffusion process. This question, as well as the methodology developed in the paper allows to prove Gaussian concentration via semigroup interpolation method, for measures which are not available in explicit form. We provide examples of conservation of GCB, loss of GCB in finite time, and loss of GCB at infinity. We also consider diffusions ``coming down from infinity'' for which we show that, from any starting measure, at positive times, GCB holds. Finally we consider a simple class of non-Markovian diffusion processes with drift of Ornstein-Uhlenbeck type, and general bounded predictable variance., Comment: 47 pages. This is an improved version, with new results (see Section 3). To appear in Markov Processes and Related Fields (2021)

We consider the full shift $T:\Omega\to\Omega$ where $\Omega=A^{\mathbb N}$, $A$ being a finite alphabet. For a class of potentials which contains in particular potentials $\phi$ with variation decreasing like $O(n^{-\alpha})$ for some $\alpha>2$, we prove that their corresponding equilibrium state $\mu_\phi$ satisfies a Gaussian concentration bound. Namely, we prove that there exists a constant $C>0$ such that, for all $n$ and for all separately Lipschitz functions $K(x_0,\ldots,x_{n-1})$, the exponential moment of $K(x,\ldots,T^{n-1}x)-\int K(y,\ldots,T^{n-1}y)\, \mathrm{d}\mu_\phi(y)$ is bounded by $\exp\big(C\sum_{i=0}^{n-1}\mathrm{Lip}_i(K)^2\big)$. The crucial point is that $C$ is independent of $n$ and $K$. We then derive various consequences of this inequality. For instance, we obtain bounds on the fluctuations of the empirical frequency of blocks, the speed of convergence of the empirical measure, and speed of Markov approximation of $\mu_\phi$. We also derive an almost-sure central limit theorem., Comment: 29 pages, new title, Corollary 3.10 (Markov approximation) was improved (we obtained the optimal decay rate), and we corrected a few typos. Accepted at Nonlinearity

Let $(X_k)_{k\geq 0}$ be a stationary and ergodic process with joint distribution $\mu$ where the random variables $X_k$ take values in a finite set $\mathcal{A}$. Let $R_n$ be the first time this process repeats its first $n$ symbols of output. It is well-known that $\frac{1}{n}\log R_n$ converges almost surely to the entropy of the process. Refined properties of $R_n$ (large deviations, multifractality, etc) are encoded in the return-time $L^q$-spectrum defined as \[ \mathcal{R}(q)=\lim_n\frac{1}{n}\log\int R_n^q \,d\mu\quad (q\in\mathbb{R}) \] provided the limit exists. We consider the case where $(X_k)_{k\geq 0}$ is distributed according to the equilibrium state of a potential $\varphi:\mathcal{A}^{\mathbb{N}}\to\mathbb{R}$ with summable variation, and we prove that \[ \mathcal{R}(q) = \begin{cases} P((1-q)\varphi) & \text{for}\;\; q\geq q_\varphi^*\\ \sup_\eta \int \varphi \, d\eta & \text{for}\;\; q

Functional responses are widely used to describe interactions and resources exchange between individuals in ecology. The form given to functional responses dramatically affects the dynamics and stability of populations and communities. Despite their importance, functional responses are generally considered with a phenomenological approach, without clear mechanistic justifications from individual traits and behaviors. Here, we develop a bottom-up stochastic framework grounded in Renewal Theory showing how functional responses emerge from the level of the individuals through the decomposition of interactions into different activities. Our framework has many applications for conceptual, theoretical and empirical purposes. First, we show how the mean and variance of classical functional responses are obtained with explicit ecological assumptions, for instance regarding foraging behaviors. Second, we give examples in specific ecological contexts, such as in nuptial-feeding species or size dependent handling times. Finally, we demonstrate how to analyze data with our framework, especially highlighting that observed variability in the number of interactions can be used to infer parameters and compare functional response models., Comment: 37 pages, 7 figures, to appear in the Journal of the Royal Society Interface

We consider a class of birth-and-death processes describing a population made of $d$ sub-populations of different types which interact with one another. The state space is $\mathbb{Z}_+^d$ (unbounded). We assume that the population goes almost surely to extinction, so that the unique stationary distribution is the Dirac measure at the origin. These processes are parametrized by a scaling parameter $K$ which can be thought as the order of magnitude of the total size of the population at time $0$. For any fixed finite time span, it is well-known that such processes, when renormalized by $K$, are close, in the limit $K\to+\infty$, to the solutions of a certain differential equation in $\mathbb{R}_+^d$ whose vector field is determined by the birth and death rates. We consider the case where there is a unique attractive fixed point (off the boundary of the positive orthant) for the vector field (while the origin is repulsive). What is expected is that, for $K$ large, the process will stay in the vicinity of the fixed point for a very long time before being absorbed at the origin. To precisely describe this behavior, we prove the existence of a quasi-stationary distribution (qsd). In fact, we establish a bound for the total variation distance between the process conditioned to non-extinction before time $t$ and the qsd. This bound is exponentially small in $t$, for $t\gg \log K$. As a by-product, we obtain an estimate for the mean time to extinction in the qsd. We also quantify how close is the law of the process (not conditioned to non-extinction) either to the Dirac measure at the origin or to the qsd, for times much larger than $\log K$ and much smaller than the mean time to extinction, which is exponentially large as a function of $K$. Let us stress that we are interested in what happens for finite $K$. We obtain results much beyond what large deviation techniques could provide., Comment: 51 pages, 3 figures. Accepted at the Annales de l'Institut H. Poincar\'e

We consider Gibbs measures on the configuration space $S^{\mathbb{Z}^d}$, where mostly $d\geq 2$ and $S$ is a finite set. We start by a short review on concentration inequalities for Gibbs measures. In the Dobrushin uniqueness regime, we have a Gaussian concentration bound, whereas in the Ising model (and related models) at sufficiently low temperature, we control all moments and have a stretched-exponential concentration bound. We then give several applications of these inequalities whereby we obtain various new results. Amongst these applications, we get bounds on the speed of convergence of the empirical measure in the sense of Kantorovich distance, fluctuation bounds in the Shannon-McMillan-Breiman theorem, fluctuation bounds for the first occurrence of a pattern, as well as almost-sure central limit theorems., Comment: 58 pages. Some typos corrected. Section 7.4 improved (better bound in the lemma). A point in Section 8.3 was clarified about epsilon-entropy. To appear in J. Stat. Phys

We study a general class of birth-and-death processes with state space $\mathbb{N}$ that describes the size of a population going to extinction with probability one. This class contains the logistic case. The scale of the population is measured in terms of a `carrying capacity' $K$. When $K$ is large, the process is expected to stay close to its deterministic equilibrium during a long time but ultimately goes extinct. Our aim is to quantify the behavior of the process and the mean time to extinction in the quasi-stationary distribution as a function of $K$, for large $K$. We also give a quantitative description of this quasi-stationary distribution. It turns out to be close to a Gaussian distribution centered about the deterministic long-time equilibrium, when $K$ is large. Our analysis relies on precise estimates of the maximal eigenvalue, of the corresponding eigenvector and of the spectral gap of a self-adjoint operator associated with the semigroup of the process., Comment: 48 pages, corrected typos, more details. To appear in Probab. Th. & Rel. Fields (2015)

We introduce the multiplicative Ising model and prove basic properties of its thermodynamic formalism such as existence of pressure and entropies. We generalize to one-dimensional "layer-unique" Gibbs measures for which the same results can be obtained. For more general models associated to a $d$-dimensional multiplicative invariant potential, we prove a large deviation theorem in the uniqueness regime for averages of multiplicative shifts of general local functions. This thermodynamic formalism is motivated by the statistical properties of multiple ergodic averages., Comment: 26 pages, 1 figure. To appear in the Electronic Journal of Probability

We show that the problem of tiling the Euclidean plane with a finite set of polygons (up to translation) boils down to prove the existence of zeros of a non-negative convex function defined on a finite-dimensional simplex. This function is a generalisation, in the framework of branched surfaces, of the Thurston semi-norm originally defined for compact $3$-manifolds., Comment: 14 pages, 5 figures. To appear in Geometria Dedicata

We start by reviewing recent probabilistic results on ergodic sums in a large class of (non-uniformly) hyperbolic dynamical systems. Namely, we describe the central limit theorem, the almost-sure convergence to the gaussian and other stable laws, and large deviations. Next, we describe a new branch in the study of probabilistic properties of dynamical systems, namely concentration inequalities. They allow to describe the fluctuations of very general observables and to get bounds rather than limit laws. We end up with two sections: one gathering various open problems, notably on random dynamical systems, coupled map lattices and the so-called nonconventional ergodic averages; and another one giving pointers to the literature about moderate deviations, almost-sure invariance principle, etc., Comment: 42 pages, 3 figures. This is a survey with a list of open problems. A new section was added

We study the so-called nonconventional averages in the context of lattice spin systems, or equivalently random colourings of the integers. For i.i.d. colourings, we prove a large deviation principle for the number of monochromatic arithmetic progressions of size two in the box $[1,N]\cap \N$, as $N\to\infty$, with an explicit rate function related to the one-dimensional Ising model. For more general colourings, we prove some bounds for the number of monochromatic arithmetic progressions of arbitrary size, as well as for the maximal progression inside the box $[1,N]\cap \N$. Finally, we relate nonconventional sums along arithmetic progressions of size greater than two to statistical mechanics models in dimension larger than one., Comment: 18 pages, 3 figures. A new section was added on arithmetic progressions of length larger than 2 and statistical mechanics models on Z^d, d>1. To appear in Indagationes Mathematicae (2012)

We obtain bounds on fluctuations of two entropy estimators for a class of one-dimensional Gibbs measures on the full shift. They are the consequence of a general exponential inequality for Lipschitz functions of n variables. The first estimator is based on empirical frequencies of blocks scaling logarithmically with the sample length. The second one is based on the first appearance of blocks within typical samples., Comment: 12 pages, minor corrections made. To appear in Nonlinearity

We consider Markov random fields of discrete spins on the lattice $\Zd$. We use a technique of coupling of conditional distributions. If under the coupling the disagreement cluster is "sufficiently" subcritical, then we prove the Poincar\'e inequality. In the whole subcritical regime, we have a weak Poincar\'e inequality and corresponding polynomial upper bound for the relaxation of the associated Glauber dynamics., Comment: 21 pages, a few corrections made. To appear in Indagationes Mathematicae (special issue in the memory of F. Takens)

Let $\Sigma$ be a finite alphabet, $\Omega=\Sigma^{\mathbb{Z}^{d}}$ equipped with the shift action, and $\mathcal{I}$ the simplex of shift-invariant measures on $\Omega$. We study the relation between the restriction $\mathcal{I}_n$ of $\mathcal{I}$ to the finite cubes $\{-n,...,n\}^d\subset\mathbb{Z}^d$, and the polytope of "locally invariant" measures $\mathcal{I}_n^{loc}$. We are especially interested in the geometry of the convex set $\mathcal{I}_n$ which turns out to be strikingly different when $d=1$ and when $d\geq 2$. A major role is played by shifts of finite type which are naturally identified with faces of $\mathcal{I}_n$, and uniquely ergodic shifts of finite type, whose unique invariant measure gives rise to extreme points of $\mathcal{I}_n$, although in dimension $d\geq 2$ there are also extreme points which arise in other ways. We show that $\mathcal{I}_n=\mathcal{I}_n^{loc}$ when $d=1$, but in higher dimension they differ for $n$ large enough. We also show that while in dimension one $\mathcal{I}_n$ are polytopes with rational extreme points, in higher dimensions every computable convex set occurs as a rational image of a face of $\mathcal{I}_n$ for all large enough $n$., Comment: 20 pages, 3 figures, to appear in Ergod. Th. & Dynam. Sys

We study the number of visits to balls B_r(x), up to time t/mu(B_r(x)), for a class of non-uniformly hyperbolic dynamical systems, where mu is the SRB measure. Outside a set of `bad' centers x, we prove that this number is approximately Poissonnian with a controlled error term. In particular, when r-->0, we get convergence to the Poisson law for a set of centers of mu-measure one. Our theorem applies for instance to the H\'enon attractor and, more generally, to systems modelled by a Young tower whose return-time function has a exponential tail and with one-dimensional unstable manifolds. Along the way, we prove an abstract Poisson approximation result of independent interest., Comment: 41 pages, to appear in Ergod. Th. & Dynam. Sys

We exhibit Lipschitz (and hence H\"older) potentials on the full shift $\{0,1\}^{\mathbb{N}}$ such that the associated Gibbs measures fail to converge as the temperature goes to zero. Thus there are "exponentially decaying" interactions on the configuration space $\{0,1\}^{\mathbb Z}$ for which the zero-temperature limit of the associated Gibbs measures does not exist. In higher dimension, namely on the configuration space $\{0,1\}^{\mathbb{Z}^{d}}$, $d\geq3$, we show that this non-convergence behavior can occur for finite-range interactions, that is, for locally constant potentials., Comment: The statement of Theorem 1.2 is more accurate and some new comment follow it

Let $A$ be a finite set and $\phi:A^Z\to R$ be a locally constant potential. For each $\beta>0$ ("inverse temperature"), there is a unique Gibbs measure $\mu_{\beta\phi}$. We prove that, as $\beta\to+\infty$, the family $(\mu_{\beta\phi})_{\beta>0}$ converges (in weak-$^*$ topology) to a measure we characterize. It is concentrated on a certain subshift of finite type which is a finite union of transitive subshifts of finite type. The two main tools are an approximation by periodic orbits and the Perron-Frobenius Theorem for matrices \'a la Birkhoff. The crucial idea we bring is a "renormalization" procedure which explains convergence and provides a recursive algorithm to compute the weights of the ergodic decomposition of the limit., Comment: A typo was corrected in the matrix of section 6.2. This typo was left in the published version

We obtain moment and Gaussian bounds for general Lipschitz functions evaluated along the sample path of a Markov chain. We treat Markov chains on general (possibly unbounded) state spaces via a coupling method. If the first moment of the coupling time exists, then we obtain a variance inequality. If a moment of order 1+epsilon of the coupling time exists, then depending on the behavior of the stationary distribution, we obtain higher moment bounds. This immediately implies polynomial concentration inequalities. In the case that a moment of order 1+epsilon is finite uniformly in the starting point of the coupling, we obtain a Gaussian bound. We illustrate the general results with house of cards processes, in which both uniform and non-uniform behavior of moments of the coupling time can occur., Comment: Electron. J. Probab. (2009). A little mistake, indicated by A. Guillin, was corrected in Theorem 7.1, see Remark 7.1

Let $\Delta\subsetneq\V$ be a proper subset of the vertices $\V$ of the defining graph of an irreducible and aperiodic shift of finite type $(\Sigma_{A}^{+},\S)$. Let $\Sigma_{\Delta}$ be the subshift of allowable paths in the graph of $\Sigma_{A}^{+}$ which only passes through the vertices of $\Delta$. For a random point $x$ chosen with respect to an equilibrium state $\mu$ of a H\"older potential $\phi$ on $\Sigma_{A}^{+}$, let $\tau_{n}$ be the point process defined as the sum of Dirac point masses at the times $k>0$, suitably rescaled, for which the first $n$-symbols of $\S^k x$ belong to $\Delta$. We prove that this point process converges in law to a marked Poisson point process of constant parameter measure. The scale is related to the pressure of the restriction of $\phi$ to $\Sigma_{\Delta}$ and the parameters of the limit law are explicitly computed., Comment: 21 pages, submitted

Let $\Delta\subsetneq\V$ be a proper subset of the vertices $\V$ of the defining graph of an aperiodic shift of finite type $(\Sigma_{A}^{+},\S)$. Let $\Delta_{n}$ be the union of cylinders in $\Sigma_{A}^{+}$ corresponding to the points $x$ for which the first $n$-symbols of $x$ belong to $\Delta$ and let $\mu$ be an equilibrium state of a H\"older potential $\phi$ on $\Sigma_{A}^{+}$. We know that $\mu(\Delta_{n})$ converges to zero as $n$ diverges. We study the asymptotic behaviour of $\mu(\Delta_{n})$ and compare it with the pressure of the restriction of $\phi$ to $\Sigma_{\Delta}$. The present paper extends some results in \cite{CCC} to the case when $\Sigma_{\Delta}$ is irreducible and periodic. We show an explicit example where the asymptotic behaviour differs from the aperiodic case., Comment: Companion of the paper "Poisson processes for subsystems of finite type in symbolic dynamics"

Our goal is to present the basic results on one-dimensional Gibbs and equilibrium states viewed as special invariant measures on symbolic dynamical systems, and then to describe without technicalities a sample of results they allowed to obtain for certain differentiable dynamical systems. We hope that this contribution will illustrate the symbiotic relationship between ergodic theory and statistical mechanics, and also information theory., Comment: There is a second edition of the "Encyclopedia of Complexity and System Science (Springer)" in preparation. We took the opportunity to complete the reference list which contained preprints which are now published articles

This paper has been withdrawn. It will be split into two separate papers. New results will be added in both papers., Comment: This paper has been withdrawn

For a map of the unit interval with an indifferent fixed point, we prove an upper bound for the variance of all observables of $n$ variables $K:[0,1]^n\to\R$ which are componentwise Lipschitz. The proof is based on coupling and decay of correlation properties of the map. We then give various applications of this inequality to the almost-sure central limit theorem, the kernel density estimation, the empirical measure and the periodogram., Comment: 26 pages, submitted

This paper has been withdrawn by the authors due to an error in the main theorem., Comment: This paper has been withdrawn

We define the epsilon-distortion complexity of a set as the shortest program, running on a universal Turing machine, which produces this set at the precision epsilon in the sense of Hausdorff distance. Then, we estimate the epsilon-distortion complexity of various central Cantor sets on the line generated by iterated function systems (IFS's). In particular, the epsilon-distortion complexity of a C^k Cantor set depends, in general, on k and on its box counting dimension, contrarily to Cantor sets generated by polynomial IFS or random affine Cantor sets.

The purpose of this article is to construct a toolbox, in Dynamical Systems, to support the idea that ``whenever we can prove a limit theorem in the classical sense for a dynamical system, we can prove a suitable almost-sure version based on an empirical measure with log-average''. We follow three different approaches: martingale methods, spectral methods and induction arguments. Our results apply among others to Axiom A maps or flows, to systems inducing a Gibbs-Markov map and to the stadium billiard., Comment: 41 pages; submitted v2: replaced the argument for Gibbs-Markov maps with a general spectral argument

We introduce estimators for the entropy production of a Gibbsian process based on the observation of a single or two typical trajectories. These estimators are built with adequate hitting and return times. We then study their convergence and fluctuation properties. This provides statisticals test for the irreversibility of Gibbsian processes., Comment: 16 pages; Corrected version; To appear in Nonlinearity

We present a new and simple approach to concentration inequalities for functions around their expectation with respect to non-product measures, i.e., for dependent random variables. Our method is based on coupling ideas and does not use information inequalities. When one has a uniform control on the coupling, this leads to exponential concentration inequalities. When such a uniform control is no more possible, this leads to polynomial or stretched-exponential concentration inequalities. Our abstract results apply to Gibbs random fields, in particular to the low-temperature Ising model which is a concrete example of non-uniformity of the coupling., Comment: New corrected version; 22 pages; 1 figure; New result added: stretched-exponential inequality

In this paper, we apply Devroye inequality to study various statistical estimators and fluctuations of observables for processes. Most of these observables are suggested by dynamical systems. These applications concern the co-variance function, the integrated periodogram, the correlation dimension, the kernel density estimator, the speed of convergence of empirical measure, the shadowing property and the almost-sure central limit theorem. We proved in \cite{CCS} that Devroye inequality holds for a class of non-uniformly hyperbolic dynamical systems introduced in \cite{young}. In the second appendix we prove that, if the decay of correlations holds with a common rate for all pairs of functions, then it holds uniformly in the function spaces. In the last appendix we prove that for the subclass of one-dimensional systems studied in \cite{young} the density of the absolutely continuous invariant measure belongs to a Besov space., Comment: 33 pages; companion of the paper math.DS/0412166; corrected version; to appear in Nonlinearity

In this paper, we prove an inequality, which we call "Devroye inequality", for a large class of non-uniformly hyperbolic dynamical systems (M,f). This class, introduced by L.-S. Young, includes families of piece-wise hyperbolic maps (Lozi-like maps), scattering billiards (e.g., planar Lorentz gas), unimodal and H{\'e}non-like maps. Devroye inequality provides an upper bound for the variance of observables of the form K(x,f(x),...,f^{n-1}(x)), where K is any separately Holder continuous function of n variables. In particular, we can deal with observables which are not Birkhoff averages. We will show in \cite{CCS} some applications of Devroye inequality to statistical properties of this class of dynamical systems., Comment: Corrected version; To appear in Nonlinearity

This letter is a comment on an article by T.C. Halsey and M.H. Jensen in Nature about using recurrence times as a reliable tool to estimate multifractal dimensions of strange attractors. Our aim is to emphasize that in the recent mathematical literature (not cited by these authors), there are positive as well as negative results about the use of such techniques. Thus one may be careful in using this tool in practical situations (experimental data)., Comment: This is a very short and non-technical note written after an article published in Nature by T.C. Halsey and M.H. Jensen

The entropy of an ergodic finite-alphabet process can be computed from a single typical sample path x_1^n using the entropy of the k-block empirical probability and letting k grow with $n$ roughly like log n. We further assume that the distribution of the process is a g-measure; g-measures form a large class of Gibbs measures. We prove large deviation principles for conditional, non-conditional and relative k(n)-block empirical entropies., Comment: 19 pages; revised version; to appear in Nonlinearity

Consider a H\"older continuous potential $\phi$ defined on the full shift $A^\nn$, where $A$ is a finite alphabet. Let $X\subset A^\nn$ be a specified sofic subshift. It is well-known that there is a unique Gibbs measure $\mu_\phi$ on $X$ associated to $\phi$. Besides, there is a natural nested sequence of subshifts of finite type $(X_m)$ converging to the sofic subshift $X$. To this sequence we can associate a sequence of Gibbs measures $(\mu_{\phi}^m)$. In this paper, we prove that these measures weakly converge at exponential speed to $\mu_\phi$ (in the classical distance metrizing weak topology). We also establish a strong mixing property (ensuring weak Bernoullicity) of $\mu_\phi$. Finally, we prove that the measure-theoretic entropy of $\mu_\phi^m$ converges to the one of $\mu_\phi$ exponentially fast. We indicate how to extend our results to more general subshifts and potentials. We stress that we use basic algebraic tools (contractive properties of iterated matrices) and symbolic dynamics., Comment: 18 pages, no figures

Motivated by entropy estimation from chaotic time series, we provide a comprehensive analysis of hitting times of cylinder sets in the setting of Gibbsian sources. We prove two strong approximation results from which we easily deduce pointwise convergence to entropy, lognormal fluctuations, precise large deviation estimates and an explicit formula for the hitting-time multifractal spectrum. It follows from our analysis that the hitting time of a $n$-cylinder fluctuates in the same way as the inverse measure of this $n$-cylinder at "small scales", but in a different way at "large scales". In particular, the Renyi entropy differs from the hitting-time spectrum, contradicting a naive ansatz. This phenomenon was recently numerically observed for return times that are more difficult to handle theoretically. The results we obtain for return times, though less complete, improve the available ones., Comment: 22 pages. To be published in Discrete and Cont. Dynam. Syst. B

We study the time of $n$th return of orbits to some given (union of) rectangle(s) of a Markov partition of an Axiom A diffeomorphism. Namely, we prove the existence of a scaled generating function for these returns with respect to any Gibbs measure (associated to a Holderian potential). As a by-product, we derive precise large deviation estimates and a central limit theorem for Birkhoff averages of Poincare cycles. We emphasize that we look at the limiting behavior in term of number of visits (the size of the visited set is kept fixed). Our approach relies on the spectral properties of a one-parameter family of induced transfer operators on unstable leaves crossing the visited set., Comment: 17 pages; submitted

We continue our study of exponential law for occurrences and returns of patterns in the context of Gibbsian random fields. For the low temperature plus phase of the Ising model, we prove exponential laws with error bounds for occurrence, return, waiting and matching times. Moreover we obtain a Poisson law for the number of occurrences of large cylindrical events and a Gumbel law for the maximal overlap between two independent copies. As a by-product, we derive precise fluctuation results for the logarithm of waiting and return times. The main technical tool we use, in order to control mixing, is disagreement percolation., Comment: This work is a natural continuation of the paper math.PR/0310355; corrected version; to appear in J. Stat. Phys

We study the distribution of the occurrence of rare patterns in sufficiently mixing Gibbs random fields on the lattice $\mathbb{Z}^d$, $d\geq 2$. A typical example is the high temperature Ising model. This distribution is shown to converge to an exponential law as the size of the pattern diverges. Our analysis not only provides this convergence but also establishes a precise estimate of the distance between the exponential law and the distribution of the occurrence of finite patterns. A similar result holds for the repetition of a rare pattern. We apply these results to the fluctuation properties of occurrence and repetition of patterns: We prove a central limit theorem and a large deviation principle., Comment: To appear in Commun. Math. Phys

We study the induced measure obtained from a 1-step Markov measure, supported by a topological Markov chain, after the mapping of the original alphabet onto another one. We give sufficient conditions for the induced measure to be a Gibbs measure (in the sense of Bowen) when the factor system is again a topological Markov chain. This amounts to constructing, when it does exist, the induced potential and proving its Holder continuity. This is achieved through a matrix method. We provide examples and counterexamples to illustrate our results., Comment: 4 latex figures