Some large deviation results for sparse random graphs

Summary. We obtain a large deviation principle (LDP) for the relative size of the largest connected component in a random graph with small edge probability. The rate function, which is not convex in general, is determined explicitly using a new technique. The proof yields an asymptotic formula for the probability that the random graph is connected. We also present an LDP and related result for the number of isolated vertices. Here we make use of a simple but apparently unknown characterisation, which is obtained by embedding the random graph in a random directed graph. The results demonstrate that, at this scaling, the properties `connected' and `contains no isolated vertices' are not asymptotically equivalent. (At the threshold probability they are asymptotically equivalent.) Received: 14 November 1996 / In revised form: 15 August 1997     

One-sided local large deviation and renewal theorems in the case of infinite mean

Summary. If {S _n ,n≧0} is an integer-valued random walk such that S _n /a _n converges in distribution to a stable law of index α∈ (0,1) as n→∞, then Gnedenko’s local limit theorem provides a useful estimate for P{S _n =r} for values of r such that r/a _n is bounded. The main point of this paper is to show that, under certain circumstances, there is another estimate which is valid when r/a _n → +∞, in other words to establish a large deviation local limit theorem. We also give an asymptotic bound for P{S _n =r} which is valid under weaker assumptions. This last result is then used in establishing some local versions of generalized renewal theorems. Received: 9 August 1995 / In revised form: 29 September 1996     

Zeno's walk: A random walk with refinements

Summary. A self-modifying random walk on is derived from an ordinary random walk on the integers by interpolating a new vertex into each edge as it is crossed. This process converges almost surely to a random variable which is totally singular with respect to Lebesgue measure, and which is supported on a subset of having Hausdorff dimension less than , which we calculate by a theorem of Billingsley. By generating function techniques we then calculate the exponential rate of convergence of the process to its limit point, which may be taken as a bound for the convergence of the measure in the Wasserstein metric. We describe how the process may viewed as a random walk on the space of monotone piecewise linear functions, where moves are taken by successive compositions with a randomly chosen such function. Received: 20 November 1995 / In revised form: 14 May 1996     

Brownian motion and random walk perturbed at extrema

Let b _t be Brownian motion. We show there is a unique adapted process x _t which satisfies dx _t = db _t except when x _t is at a maximum or a minimum, when it receives a push, the magnitudes and directions of the pushes being the parameters of the process. For some ranges of the parameters this is already known. We show that if a random walk close to b _t is perturbed properly, its paths are close to those of x _t . Received: 15 October 1997 / Revised version: 18 May 1998     

Slowdown and neutral pockets for a random walk in random environment

We consider a d-dimensional random walk in random environment for which transition probabilities at each site are either neutral or present an effective drift “pointing to the right”. We obtain large deviation estimates on the probability that the walk moves in a too slow ballistic fashion, both under the annealed and quenched measures. These estimates underline the key role of large neutral pockets of the medium in the occurrence of slowdowns of the walk. Received: 12 March 1998 / Revised version: 19 February 1999     

Random walk on upper triangular matrices mixes rapidly

We present an upper bound O(n ² ) for the mixing time of a simple random walk on upper triangular matrices. We show that this bound is sharp up to a constant, and find tight bounds on the eigenvalue gap. We conclude by applying our results to indicate that the asymmetric exclusion process on a circle indeed mixes more rapidly than the corresponding symmetric process. Received: 25 January 1999 / Revised version: 17 September 1999 / Published online: 14 June 2000     

Rates of convergence of random walk on distance regular graphs

When run on any non-bipartite q-distance regular graph from a family containing graphs of arbitrarily large diameter d, we show that d steps are necessary and sufficient to drive simple random walk to the uniform distribution in total variation distance, and that a sharp cutoff phenomenon occurs. For most examples, we determine the set on which the variation distance is achieved, and the precise rate at which it decays. The upper bound argument uses spectral methods – combining the usual Cauchy-Schwarz bound on variation distance with a bound on the tail probability of a first-hitting time, derived from its generating function. Received: 2 April 1997 / Revised version: 10 May 1998     

Measure concentration for a class of random processes

Summary.   Let X={X _i } _{i =−∞} ^∞ be a stationary random process with a countable alphabet and distribution q. Let q ^∞(·|x _{− k} ⁰) denote the conditional distribution of X ^∞=(X ₁,X ₂,…,X _n ,…) given the k-length past:

The problem of the most visited site in random environment

We prove that the process of the most visited site of Sinai's simple random walk in random environment is transient. The rate of escape is characterized via an integral criterion. Our method also applies to a class of recurrent diffusion processes with random potentials. It is interesting to note that the corresponding problem for the usual symmetric Bernoulli walk or for Brownian motion remains open. Received: 17 April 1998     

Riccati-based preconditioner for computing invariant subspaces of large matrices

Summary. This paper introduces and analyzes the convergence properties of a method that computes an approximation to the invariant subspace associated with a group of eigenvalues of a large not necessarily diagonalizable matrix. The method belongs to the family of projection type methods. At each step, it refines the approximate invariant subspace using a linearized Riccati's equation which turns out to be the block analogue of the correction used in the Jacobi-Davidson method. The analysis conducted in this paper shows that the method converges at a rate quasi-quadratic provided that the approximate invariant subspace is close to the exact one. The implementation of the method based on multigrid techniques is also discussed and numerical experiments are reported. Received June 15, 2000 / Revised version received January 22, 2001 / Published online October 17, 2001     

Slowdown estimates and central limit theorem for random walks in random environment

This work is concerned with asymptotic properties of multi-dimensional random walks in random environment. Under Kalikow’s condition, we show a central limit theorem for random walks in random environment on ℤ ^d , when d≥2. We also derive tail estimates on the probability of slowdowns. These latter estimates are of special interest due to the natural interplay between slowdowns and the presence of traps in the medium. The tail behavior of the renewal time constructed in [25] plays an important role in the investigation of both problems. This article also improves the previous work of the author [24], concerning estimates of probabilities of slowdowns for walks which are neutral or biased to the right. Received May 31, 1999 / final version received January 18, 2000?Published online April 19, 2000     

Concavity estimates for a class of nonlinear elliptic equations in two dimensions

We study solutions of the nonlinear elliptic equation on a bounded domain in . It is shown that the set of points where the graph of the solution has negative Gauss curvature always extends to the boundary, unless it is empty. The meethod uses an elliptic equation satisfied by an auxiliary function given by the product of the Hessian determinant and a suitable power of the solutions. As a consequence of the result, we give a new proof for power concavity of solutions to certain semilinear boundary value problems in convex domains. Received: 12 January 2000; in final form: 15 March 2001 / Published online: 4 April 2002     

Computing the generalized singular values/vectors of large sparse or structured matrix pairs

Summary. We present a numerical algorithm for computing a few extreme generalized singular values and corresponding vectors of a sparse or structured matrix pair . The algorithm is based on the CS decomposition and the Lanczos bidiagonalization process. At each iteration step of the Lanczos process, the solution to a linear least squares problem with as the coefficient matrix is approximately computed, and this consists the only interface of the algorithm with the matrix pair . Numerical results are also given to demonstrate the feasibility and efficiency of the algorithm. Received April 1, 1994 / Revised version received December 15, 1994     

Stability and error estimates for the $\theta$-method for strongly monotone and infinitely stiff evolution equations

Summary.   For evolution equations with a strongly monotone operator we derive unconditional stability and discretization error estimates valid for all . For the -method, with , we prove an error estimate , if , where is the maximal integration step for an arbitrary choice of sequence of steps and with no assumptions about the existence of the Jacobian as well as other derivatives of the operator , and an optimal estimate under some additional relation between neighboring steps. The first result is an improvement over the implicit midpoint method , for which an order reduction to sometimes may occur for infinitely stiff problems. Numerical tests illustrate the results. Received March 10, 1999 / Revised version received April 3, 2000 / Published online February 5, 2001     

Biased random walks on Galton–Watson trees

Summary. We consider random walks with a bias toward the root on the family tree T of a supercritical Galton–Watson branching process and show that the speed is positive whenever the walk is transient. The corresponding harmonic measures are carried by subsets of the boundary of dimension smaller than that of the whole boundary. When the bias is directed away from the root and the extinction probability is positive, the speed may be zero even though the walk is transient; the critical bias for positive speed is determined. Received: 7 July 1995 / In revised form: 9 January 1996     

Diffusion processes on graphs: stochastic differential equations,large deviation principle

Ito's rule is established for the diffusion processes on the graphs. We also consider a family of diffusions processes with small noise on a graph. Large deviation principle is proved for these diffusion processes and their local times at the vertices. Received: 12 February 1997 / Revised version: 3 March 1999     

A law of the iterated logarithm for heavy-tailed random vectors

For a random vector belonging to the (generalized) domain of operator semistable attraction of some nonnormal law we prove various variants of Chover's law of the iterated logarithm for the partial sum. Furthermore we also derive some large deviation results necessary for the proof of our main theorems. Received: 30 September 1998 / Revised version: 28 May 1999     

Generalized block Lanczos methods for large unsymmetric eigenproblems

Generalized block Lanczos methods for large unsymmetric eigenproblems are presented, which contain the block Arnoldi method, and the block Arnoldi algorithms are developed. The convergence of this class of methods is analyzed when the matrix A is diagonalizable. Upper bounds for the distances between normalized eigenvectors and a block Krylov subspace are derived, and a priori theoretical error bounds for Ritz elements are established. Compared with generalized Lanczos methods, which contain Arnoldi's method, the convergence analysis shows that the block versions have two advantages: First, they may be efficient for computing clustered eigenvalues; second, they are able to solve multiple eigenproblems. However, a deep analysis exposes that the approximate eigenvectors or Ritz vectors obtained by general orthogonal projection methods including generalized block methods may fail to converge theoretically for a general unsymmetric matrix A even if corresponding approximate eigenvalues or Ritz values do, since the convergence of Ritz vectors needs more sufficient conditions, which may be impossible to satisfy theoretically, than that of Ritz values does. The issues of how to restart and to solve multiple eigenproblems are addressed, and some numerical examples are reported to confirm the theoretical analysis. Received July 7, 1994 / Revised version received March 1, 1997     

A central limit theorem for stationary random fields

Summary. We prove a central limit theorem for strictly stationary random fields under a projective assumption. Our criterion is similar to projective criteria for stationary sequences derived from Gordin's theorem about approximating martingales. However our approach is completely different, for we establish our result by adapting Lindeberg's method. The criterion that it provides is weaker than martingale-type conditions, and moreover we obtain as a straightforward consequence, central limit theorems for α-mixing or φ-mixing random fields. Received: 19 February 1997 / In revised form: 2 September 1997