No description available.

This thesis is divided into two parts: In the first one (Chapters 1 and 2), we deal with problems arising from quantitative homogenization of the random elliptic operator in divergence form $-\\nabla \\cdot a \\nabla$. In Chapter 1 we study existence and stochastic bounds for the Green function $G$ associated to $-\\nabla \\cdot a \\nabla$ in the case of systems. Without assuming any regularity on the coefficient field $a= a(x)$, we prove that for every (measurable) uniformly elliptic tensor field $a$ and for almost every point $y \\in \\mathbb^d$, there exists a unique Green\'s function centred in $y$ associated to the vectorial operator $-\\nabla \\cdot a\\nabla $ in $\\mathbb{R}^d$, $d> 2$. In addition, we prove that if we introduce a shift-invariant ensemble $\\langle\\cdot \\rangle$ over the set of uniformly elliptic tensor fields, then $\\nabla G$ and its mixed derivatives $\\nabla \\nabla G$ satisfy optimal pointwise $L^1$-bounds in probability. Chapter 2 deals with the homogenization of $-\\nabla \\cdot a \\nabla$ to $-\\nabla \\ah \\nabla$ in the sense that we study the large-scale behaviour of $a$-harmonic functions in exterior domains $\\{ |x| > r \\}$ by comparing them with functions which are $\\ah$-harmonic. More precisely, we make use of the first and second-order correctors to compare an $a$-harmonic function $u$ to the two-scale expansion of suitable $\\ah$-harmonic function $u_h$. We show that there is a direct correspondence between the rate of the sublinear growth of the correctors and the smallness of the relative homogenization error $u- u_h$. The theory of stochastic homogenization of elliptic operators admits an equivalent probabilistic counterpart, which follows from the link between parabolic equations with elliptic operators in divergence form and random walks. This allows to reformulate the problem of homogenization in terms of invariance principle for random walks. The second part of thesis (Chapters 3 and 4) focusses on this interplay between probabilistic and analytic approaches and aims at exploiting it to study invariance principles in the case of degenerate random conductance models and systems of interacting particles. In Chapter 3 we study a random conductance model where we assume that the conductances are independent, stationary and bounded from above but not uniformly away from $0$. We give a simple necessary and sufficient condition for the relaxation of the environment seen by the particle to be diffusive in the sense of every polynomial moment. As a consequence, we derive polynomial moment estimates on the corrector which imply that the discrete elliptic operator homogenises or, equivalently, that the random conductance model satisfies a quenched invariance principle. In Chapter 4 we turn to a more complicated model, namely the symmetric exclusion process. We show a diffusive upper bound on the transition probability of a tagged particle in this process. The proof relies on optimal spectral gap estimates for the dynamics in finite volume, which are of independent interest. We also show off-diagonal estimates of Carne-Varopoulos type.

Recent years have seen progress in the analysis of the heat kernel for certain reversible random walks in random environments. In particular the work of Barlow(2004) showed that the heat kernel for the random walk on the infinite component of supercritical bond percolation behaves in a Gaussian fashion. This heat kernel control was then used to prove a quenched functional central limit theorem. Following this work several examples have been analysed with anomalous heat kernel behaviour and, in some cases, anomalous scaling limits. We begin by generalizing the first result - looking for sufficient conditions on the geometry of the environment that ensure standard heat kernel upper bounds hold. We prove that these conditions are satisfied with probability one in the case of the random walk on continuum percolation and use the heat kernel bounds to prove an invariance principle. The random walk on dynamic environment is then considered. It is proven that if the environment evolves ergodically and is, in a certain sense, geometrically d-dimensional then standard on diagonal heat kernel bounds hold. Anomalous lower bounds on the heat kernel are also proven - in particular the random conductance model is shown to be "more anomalous" in the dynamic case than the static. Finally, the reflected random walk amongst random conductances is considered. It is shown in one dimension that under the usual scaling, this walk converges to reflected Brownian motion.

This thesis focuses on applications of classical tools from probability theory and convex analysis such as limit theorems to problems in theoretical computer science, specifically to pseudorandomness and learning theory. At first look, limit theorems, pseudorandomness and learning theory appear to be disparate subjects. However, as it has now become apparent, there's a strong connection between these questions through a third more abstract question: what do random objects look like. This connection is best illustrated by the study of the spectrum of Boolean functions which directly or indirectly played an important role in a plethora of results in complexity theory. The current thesis aims to take this program further by drawing on a variety of fundamental tools, both classical and new, in probability theory and analytic geometry. Our research contributions broadly fall into three categories. Probability Theory: The central limit theorem is one of the most important results in all of probability and richly studied topic. Motivated by questions in pseudorandomness and learning theory we obtain two new limit theorems or invariance principles. The proofs of these new results in probability, of interest on their own, have a computer science flavor and fall under the niche category of techniques from theoretical computer science with applications in pure mathematics. Pseudorandomness: Derandomizing natural complexity classes is a fundamental problem in complexity theory, with several applications outside complexity theory. Our work addresses such derandomization questions for natural and basic geometric concept classes such as halfspaces, polynomial threshold functions (PTFs) and polytopes. We develop a reasonably generic framework for obtaining pseudorandom generators (PRGs) from invariance principles and suitably apply the framework to old and new invariance principles to obtain the best known PRGs for these complexity classes. Learning Theory: Learning theory aims to understand what functions can be learned efficiently from examples. As developed in the seminal work of Linial, Mansour and Nisan (1994) and strengthened by several follow-up works, we now know strong connections between learning a class of functions and how sensitive to noise, as quantified by average sensitivity and noise sensitivity, the functions are. Besides their applications in learning, bounding the average and noise sensitivity has applications in hardness of approximation, voting theory, quantum computing and more. Here we address the question of bounding the sensitivity of polynomial threshold functions and intersections of halfspaces and obtain the best known results for these concept classes.

No description available.

This thesis is divided into two parts: In the first one (Chapters 1 and 2), we deal with problems arising from quantitative homogenization of the random elliptic operator in divergence form $-\\nabla \\cdot a \\nabla$. In Chapter 1 we study existence and stochastic bounds for the Green function $G$ associated to $-\\nabla \\cdot a \\nabla$ in the case of systems. Without assuming any regularity on the coefficient field $a= a(x)$, we prove that for every (measurable) uniformly elliptic tensor field $a$ and for almost every point $y \\in \\mathbb{R}^d$, there exists a unique Green\''s function centred in $y$ associated to the vectorial operator $-\\nabla \\cdot a\\nabla $ in $\\mathbb^d$, $d> 2$. In addition, we prove that if we introduce a shift-invariant ensemble $\\langle\\cdot \\rangle$ over the set of uniformly elliptic tensor fields, then $\\nabla G$ and its mixed derivatives $\\nabla \\nabla G$ satisfy optimal pointwise $L^1$-bounds in probability. Chapter 2 deals with the homogenization of $-\\nabla \\cdot a \\nabla$ to $-\\nabla \\ah \\nabla$ in the sense that we study the large-scale behaviour of $a$-harmonic functions in exterior domains $\\$ by comparing them with functions which are $\\ah$-harmonic. More precisely, we make use of the first and second-order correctors to compare an $a$-harmonic function $u$ to the two-scale expansion of suitable $\\ah$-harmonic function $u_h$. We show that there is a direct correspondence between the rate of the sublinear growth of the correctors and the smallness of the relative homogenization error $u- u_h$. The theory of stochastic homogenization of elliptic operators admits an equivalent probabilistic counterpart, which follows from the link between parabolic equations with elliptic operators in divergence form and random walks. This allows to reformulate the problem of homogenization in terms of invariance principle for random walks. The second part of thesis (Chapters 3 and 4) focusses on this interplay between probabilistic and analytic approaches and aims at exploiting it to study invariance principles in the case of degenerate random conductance models and systems of interacting particles. In Chapter 3 we study a random conductance model where we assume that the conductances are independent, stationary and bounded from above but not uniformly away from $0$. We give a simple necessary and sufficient condition for the relaxation of the environment seen by the particle to be diffusive in the sense of every polynomial moment. As a consequence, we derive polynomial moment estimates on the corrector which imply that the discrete elliptic operator homogenises or, equivalently, that the random conductance model satisfies a quenched invariance principle. In Chapter 4 we turn to a more complicated model, namely the symmetric exclusion process. We show a diffusive upper bound on the transition probability of a tagged particle in this process. The proof relies on optimal spectral gap estimates for the dynamics in finite volume, which are of independent interest. We also show off-diagonal estimates of Carne-Varopoulos type.

Cette thèse est dévolue à l'étude de certaines propriétés asymptotiques du processus autorégressif d'ordre p. Ce dernier qualifie communément une suite aléatoire $(Y_{n})$ définie sur $\dN$ ou $\dZ$ et entièrement décrite par une combinaison linéaire de ses $p$ valeurs passées, perturbée par un bruit blanc $(\veps_{n})$. Tout au long de ce mémoire, nous traitons deux problématiques majeures de l'étude de tels processus : l'\textit{autocorrélation résiduelle} et la \textit{stationnarité}. Nous proposons en guise d'introduction un survol nécessaire des propriétés usuelles du processus autorégressif. Les deux chapitres suivants sont consacrés aux conséquences inférentielles induites par la présence d'une autorégression significative dans la perturbation $(\veps_{n})$ pour $p=1$ tout d'abord, puis pour une valeur quelconque de $p$, dans un cadre de stabilité. Ces résultats nous permettent d'apposer un regard nouveau et plus rigoureux sur certaines procédures statistiques bien connues sous la dénomination de \textit{test de Durbin-Watson} et de \textit{H-test}. Dans ce contexte de bruit autocorrélé, nous complétons cette étude par un ensemble de principes de déviations modérées liées à nos estimateurs. Nous abordons ensuite un équivalent en temps continu du processus autorégressif. Ce dernier est décrit par une équation différentielle stochastique et sa solution est plus connue sous le nom de \textit{processus d'Ornstein-Uhlenbeck}. Lorsque le processus d'Ornstein-Uhlenbeck est lui-même engendré par une diffusion similaire, cela nous permet de traiter la problématique de l'autocorrélation résiduelle dans le processus à temps continu. Nous inférons dès lors quelques propriétés statistiques de tels modèles, gardant pour objectif le parallèle avec le cas discret étudié dans les chapitres précédents. Enfin, le dernier chapitre est entièrement dévolu à la problématique de la stationnarité. Nous nous plaçons dans le cadre très général où le processus autorégressif possède une tendance polynomiale d'ordre $r$ tout en étant engendré par une marche aléatoire intégrée d'ordre $d$. Les résultats de convergence que nous obtenons dans un contexte d'instabilité généralisent le \textit{test de Leybourne et McCabe} et certains aspects du \textit{test KPSS}. De nombreux graphes obtenus en simulations viennent conforter les résultats que nous établissons tout au long de notre étude. / This thesis is devoted to the study of some asymptotic properties of the $p-$th order \textit{autoregressive process}. The latter usually designates a random sequence $(Y_{n})$ defined on $\dN$ or $\dZ$ and completely described by a linear combination of its $p$ last values and a white noise $(\veps_{n})$. All through this manuscript, one is concerned with two main issues related to the study of such processes: \textit{serial correlation} and \textit{stationarity}. We intend, by way of introduction, to give a necessary overview of the usual properties of the autoregressive process. The two following chapters are dedicated to inferential consequences coming from the presence of a significative autoregression in the disturbance $(\veps_{n})$ for $p=1$ on the one hand, and then for any $p$, in the stable framework. These results enable us to give a new light on some statistical procedures such as the \textit{Durbin-Watson test} and the \textit{H-test}. In this autocorrelated noise framework, we complete the study by a set of moderate deviation principles on our estimates. Then, we tackle a continuous-time equivalent of the autoregressive process. The latter is described by a stochastic differential equation and its solution is the well-known \textit{Ornstein-Uhlenbeck process}. In the case where the Ornstein-Uhlenbeck process is itself driven by an Ornstein-Uhlenbeck process, one deals with the serial correlation issue for the continuous-time process. Hence, we infer some statistical properties of such models, keeping the parallel with the discrete-time framework studied in the previous chapters as an objective. Finally, the last chapter is entirely devoted to the stationarity issue. We consider the general autoregressive process with a polynomial trend of order $r$ driven by a random walk of order $d$. The convergence results in the unstable framework generalize the \textit{Leybourne and McCabe test} and some angles of the \textit{KPSS test}. Many graphs obtained by simulations come to strengthen the results established all along the study.