A unified proof of Brooks’ theorem and Catlin’s theorem

Brooks’ theorem is a fundamental result in the theory of graph coloring. Catlin proved the following strengthening of Brooks’ theorem: Let d$d$ be an integer at least 3, and let G$G$ be a graph with maximum degree d$d$. If G$G$ does not contain _Kd+1$K_{d+1}$ as a subgraph, then G$G$ has a d$d$-coloring in which one color class has size α(G)$\alpha \left(G\right)$. Here α(G)$\alpha \left(G\right)$ denotes the independence number of G$G$. We give a unified proof of Brooks’ theorem and Catlin’s theorem.     

Limit theorems for occupation time fluctuations of branching systems II: Critical and large dimensions

We give functional limit theorems for the fluctuations of the rescaled occupation time process of a critical branching particle system in R^d${\mathbb{R}}^d$ with symmetric α$\alpha$-stable motion in the cases of critical and large dimensions, d=2α$d=2\alpha$ and d>2α$d>2\alpha$. In a previous paper [T. Bojdecki, L.G. Gorostiza, A. Talarczyk, Limit theorems for occupation time fluctuations of branching systems I: long-range dependence, Stochastic Process. Appl., this issue.] we treated the case of intermediate dimensions, α<d<2α$\alpha <d<2\alpha$, which leads to a long-range dependence limit process. In contrast, in the present cases the limits are generalized Wiener processes. We use the same space–time random field method of the previous paper, the main difference being that now the tightness requires a new approach and the proofs are more difficult. We also give analogous results for the system without branching in the cases d=α$d=\alpha$ and d>α$d>\alpha$.     

Moderate deviations for a random walk in random scenery

We investigate the cumulative scenery process associated with random walks in independent, identically distributed random sceneries under the assumption that the scenery variables satisfy Cramér’s condition. We prove moderate deviation principles in dimensions d≥2$d\ge 2$, covering all those regimes where rate and speed do not depend on the actual distribution of the scenery. For the case d≥4$d\ge 4$ we even obtain precise asymptotics for the probability of a moderate deviation, extending a classical central limit theorem of Kesten and Spitzer. For d≥3$d\ge 3$, an important ingredient in the proofs are new concentration inequalities for self-intersection local times of random walks, which are of independent interest, whilst for d=2$d=2$ we use a recent moderate deviation result for self-intersection local times, which is due to Bass, Chen and Rosen.     

Large deviations and phase transition for random walks in random nonnegative potentials

We establish large deviation principles and phase transition results for both quenched and annealed settings of nearest-neighbor random walks with constant drift in random nonnegative potentials on Z^d${\mathbb{Z}}^d$. We complement the analysis of M.P.W. Zerner [Directional decay of the Green’s function for a random nonnegative potential on Z^d${\mathbb{Z}}^d$, Ann. Appl. Probab. 8 (1996) 246–280], where a shape theorem on the Lyapunov functions and a large deviation principle in absence of the drift are achieved for the quenched setting.     

Limit theorems for occupation time fluctuations of branching systems I: Long-range dependence

We give a functional limit theorem for the fluctuations of the rescaled occupation time process of a critical branching particle system in R^d${\mathbb{R}}^d$ with symmetric α$\alpha$-stable motion and α<d<2α$\alpha <d<2\alpha$, which leads to a long-range dependence process involving sub-fractional Brownian motion. We also give an analogous result for the system without branching and d<α$d<\alpha$, which involves fractional Brownian motion. We use a space–time random field approach.     

A contact process with mutations on a tree

Consider the following stochastic model for immune response. Each pathogen gives birth to a new pathogen at rate λ$\lambda$. When a new pathogen is born, it has the same type as its parent with probability 1−r$1-r$. With probability r$r$, a mutation occurs, and the new pathogen has a different type from all previously observed pathogens. When a new type appears in the population, it survives for an exponential amount of time with mean 1, independently of all the other types. All pathogens of that type are killed simultaneously. Schinazi and Schweinsberg [R.B. Schinazi, J. Schweinsberg, Spatial and non-spatial stochastic models for immune response, Markov Process. Related Fields (2006) (in press)] have shown that this model on Z^d${\mathbb{Z}}^d$ behaves rather differently from its non-spatial version. In this paper, we show that this model on a homogeneous tree captures features from both the non-spatial version and the Z^d${\mathbb{Z}}^d$ version. We also obtain comparison results, between this model and the basic contact process on general graphs.     

An adaptive multiresolution method on dyadic grids: Application to transport equations

We propose a modified adaptive multiresolution scheme for solving d$d$-dimensional hyperbolic conservation laws which is based on cell-average discretization in dyadic grids. Adaptivity is obtained by interrupting the refinement at the locations where appropriate scale (wavelet) coefficients are sufficiently small. One important aspect of such a multiresolution representation is that we can use the same binary tree data structure for domains of any dimension. The tree structure allows us to succinctly represent the data and efficiently navigate through it. Dyadic grids also provide a more gradual refinement as compared with the traditional quad-trees (2D) or oct-trees (3D) that are commonly used for multiresolution analysis. We show some examples of adaptive binary tree representations, with significant savings in data storage when compared to quad-tree based schemes. As a test problem, we also consider this modified adaptive multiresolution method, using a dynamic binary tree data structure, applied to a transport equation in 2D domain, based on a second-order finite volume discretization.     

An invariance principle for stationary random fields under Hannan’s condition

We establish an invariance principle for a general class of stationary random fields indexed by Z^d${\mathbb{Z}}^d$, under Hannan’s condition generalized to Z^d${\mathbb{Z}}^d$. To do so we first establish a uniform integrability result for stationary orthomartingales, and second we establish a coboundary decomposition for certain stationary random fields. At last, we obtain an invariance principle by developing an orthomartingale approximation. Our invariance principle improves known results in the literature, and particularly we require only finite second moment.     

Markov jump random c.d.f.’s and their posterior distributions

In this article we introduce the class of Markov jump random c.d.f.’s as a sub-class of the Q$Q$-Markov prior distributions studied in R.M. Balan [Q$Q$-Markov random probability measures and their posterior distributions, Stochastic Process. Appl. 109 (2004) 296–316]. Our main result states that if the prior distribution of a sample is a Markov jump process, then the posterior distribution can also be viewed as the distribution of a Markov jump process, whose transition mechanism and infinitesimal behavior have been updated in the light of the new data.     

Random polarizations

We derive conditions under which random sequences of polarizations (two-point symmetrizations) on S^d${\mathbb{S}}^d$, R^d${\mathbb{R}}^d$, or H^d${\mathbb{H}}^d$ converge almost surely to the symmetric decreasing rearrangement. The parameters for the polarizations are independent random variables whose distributions need not be uniform. The proof of convergence hinges on an estimate for the expected distance from the limit that yields a bound on the rate of convergence. In the special case of i.i.d. sequences, almost sure convergence holds even for polarizations chosen at random from suitable small sets. As corollaries, we find bounds on the rate of convergence of Steiner symmetrizations that require no convexity assumptions, and show that full rotational symmetry can be achieved by randomly alternating Steiner symmetrizations in a finite number of directions that satisfy an explicit non-degeneracy condition. We also present some negative results on the rate of convergence and give examples where convergence fails.     

Optimal acceptance rates for Metropolis algorithms: Moving beyond 0.234

Recent optimal scaling theory has produced a condition for the asymptotically optimal acceptance rate of Metropolis algorithms to be the well-known 0.234 when applied to certain multi-dimensional target distributions. These d$d$-dimensional target distributions are formed of independent components, each of which is scaled according to its own function of d$d$. We show that when the condition is not met the limiting process of the algorithm is altered, yielding an asymptotically optimal acceptance rate which might drastically differ from the usual 0.234. Specifically, we prove that as d→∞$d\to \infty$ the sequence of stochastic processes formed by say the i^∗$i^{\ast }$th component of each Markov chain usually converges to a Langevin diffusion process with a new speed measure υ$\upsilon$, except in particular cases where it converges to a one-dimensional Metropolis algorithm with acceptance rule α^∗${\alpha }^{\ast }$. We also discuss the use of inhomogeneous proposals, which might prove to be essential in specific cases.     

On the concentration of Sinai’s walk

We consider Sinai’s random walk in a random environment. We prove that for an interval of time [1,n]$[1,n]$ Sinai’s walk sojourns in a small neighborhood of the point of localization for the quasi-totality of this amount of time. Moreover the local time at the point of localization normalized by n$n$ converges in probability to a well defined random variable of the environment. From these results we get applications to the favorite sites of the walk and to the maximum of the local time.     

Harness processes and harmonic crystals

In the Hammersley harness processes the R$\mathbb{R}$-valued height at each site i∈Z^d$i\in {\mathbb{Z}}^d$ is updated at rate 1 to an average of the neighboring heights plus a centered random variable (the noise). We construct the process “a la Harris” simultaneously for all times and boxes contained in Z^d${\mathbb{Z}}^d$. With this representation we compute covariances and show L²$L^2$ and almost sure time and space convergence of the process. In particular, the process started from the flat configuration and viewed from the height at the origin converges to an invariant measure. In dimension three and higher, the process itself converges to an invariant measure in L²$L^2$ at speed t^1−d/2$t^{1-d/2}$ (this extends the convergence established by Hsiao). When the noise is Gaussian the limiting measures are Gaussian fields (harmonic crystals) and are also reversible for the process.     

Multi-dimensional G-Brownian motion and related stochastic calculus under G-expectation

We develop a notion of nonlinear expectation–G$G$-expectation–generated by a nonlinear heat equation with infinitesimal generator G$G$. We first study multi-dimensional G$G$-normal distributions. With this nonlinear distribution we can introduce our G$G$-expectation under which the canonical process is a multi-dimensional G$G$-Brownian motion. We then establish the related stochastic calculus, especially stochastic integrals of Itô’s type with respect to our G$G$-Brownian motion, and derive the related Itô’s formula. We have also obtained the existence and uniqueness of stochastic differential equations under our G$G$-expectation.     

Directed graphs,decompositions, and spatial linkages

The decomposition of a linkage into minimal components is a central tool of analysis and synthesis of linkages. In this paper we prove that every pinned d$d$-isostatic (minimally rigid) graph (grounded linkage) has a unique decomposition into minimal strongly connected components (in the sense of directed graphs), or equivalently into minimal pinned isostatic graphs, which we call d$d$-Assur graphs. We also study key properties of motions induced by removing an edge in a d$d$-Assur graph — defining a sharper subclass of strongly d$d$-Assur graphs by the property that all inner vertices go into motion, for each removed edge. The strongly 3-Assur graphs are the central building blocks for kinematic linkages in 3-space and the 3-Assur graphs are components in the analysis of built linkages. The d$d$-Assur graphs share a number of key combinatorial and geometric properties with the 2-Assur graphs, including an associated lower block-triangular decomposition of the pinned rigidity matrix which provides modular information for extending the motion induced by inserting one driver in a bottom Assur linkage to the joints of the entire linkage. We also highlight some problems in combinatorial rigidity in higher dimensions (d≥3$d\ge 3$) which cause the distinction between d$d$-Assur and strongly d$d$-Assur which did not occur in the plane.