Normal limit theorems for symmetric random matrices

Using the machinery of zonal polynomials, we examine the limiting behavior of random symmetric matrices invariant under conjugation by orthogonal matrices as the dimension tends to infinity. In particular, we give sufficient conditions for the distribution of a fixed submatrix to tend to a normal distribution. We also consider the problem of when the sequence of partial sums of the diagonal elements tends to a Brownian motion. Using these results, we show that if O _n is a uniform random n×n orthogonal matrix, then for any fixed k>0, the sequence of partial sums of the diagonal of O ^k _n tends to a Brownian motion as n→∞. Received: 3 February 1998 / Revised version: 11 June 1998     

A generalized strong law of large numbers

Strong laws of large numbers have been stated in the literature for measurable functions taking on values on different spaces. In this paper, a strong law of large numbers which generalizes some previous ones (like those for real-valued random variables and compact random sets) is established. This law is an example of a strong law of large numbers for Borel measurable nonseparably valued elements of a metric space. Received: 24 February 1998 / Revised version: 3 January 1999     

The high temperature case for the random K-sat problem

We give a completely rigorous proof that the replica-symmetric solution holds at high enough temperature for the random K-sat problem. The most notable feature of this problem is that the order parameter of the system is a function and not a number. Received: 21 April 1998 / Revised version: 24 April 2000 / Published online: 21 December 2000     

Hölder continuity for spatial and path processes via spectral analysis

For ν(dθ), a σ-finite Borel measure on R ^d , we consider L ²(ν(dθ))-valued stochastic processes Y(t) with te property that Y(t)=y(t,·) where y(t,θ)=∫ ^t ₀ e ^{−λ(θ)( t − s )} dm(s,θ) and m(t,θ) is a continuous martingale with quadratic variation [m](t)=∫ ^t ₀ g(s,θ)ds. We prove timewise H?lder continuity and maximal inequalities for Y and use these results to obtain Hilbert space regularity for a class of superrocesses as well as a class of stochastic evolutions of the form dX=AXdt+GdW with W a cylindrical Brownian motion. Maximal inequalities and H?lder continuity results are also provenfor the path process _t (τ)≗Y(τt∧t). Received: 25 June 1999 / Revised version: 28 August 2000 /?Published online: 9 March 2001     

Vertex algebras and the cohomology ring structure of Hilbert schemes of points on surfaces

Using vertex algebra techniques, we determine a set of generators for the cohomology ring of the Hilbert schemes of points on an arbitrary smooth projective surface over the field of complex numbers. Received: 28 November 2000 / Published online: 23 May 2002     

Simultaneous Packing and Covering in the Euclidean Plane

 In this article we study the simultaneous packing and covering constants of two-dimensional centrally symmetric convex domains. Besides an identity result between translative case and lattice case and a general upper bound, exact values for some special domains are determined. Similar to Mahler and Reinhardt’s result about packing densities, we show that the simultaneous packing and covering constant of an octagon is larger than that of a circle. (Received 17 January 2001; in revised form 13 July 2001)     

Packing of Incongruent Circles on the Sphere

 In this paper we provide an upper bound to the density of a packing of circles on the sphere, with radii selected from a given finite set. This bound is precise, e.g. for the system of incircles of Archimedean tilings (4, 4, n) with n ? 6. A generalisation to the weighted density of packing is applied to problems of solidity of a packing of circles. The simple concept of solidity was introduced by L. Fejes Toóth [6]. In particular, it is proved that the incircles of the faces of the Archimedean tilings (4,6,6), (4,6,8) and (4, 6, 10) form solid packings. (Received 21 August 2000; in revised form 21 March 2001)     

Anisotropic branching random walks on homogeneous trees

Symmetric branching random walk on a homogeneous tree exhibits a weak survival phase: For parameter values in a certain interval, the population survives forever with positive probability, but, with probability one, eventually vacates every finite subset of the tree. In this phase, particle trails must converge to the geometric boundaryΩ of the tree. The random subset Λ of the boundary consisting of all ends of the tree in which the population survives, called the limit set of the process, is shown to have Hausdorff dimension no larger than one half the Hausdorff dimension of the entire geometric boundary. Moreover, there is strict inequality at the phase separation point between weak and strong survival except when the branching random walk is isotropic. It is further shown that in all cases there is a distinguished probability measure μ supported by Ω such that the Hausdorff dimension of Λ∩Ω_μ, where Ω_μ is the set of μ-generic points of Ω, converges to one half the Hausdorff dimension of Ω_μ at the phase separation point. Exact formulas are obtained for the Hausdorff dimensions of Λ and Λ∩Ω_μ, and it is shown that the log Hausdorff dimension of Λ has critical exponent 1/2 at the phase separation point. Received: 30 June 1998 / Revised version: 10 March 1999     

On homogenization of time-dependent random flows

We study a diffusion with a random, time dependent drift. We prove the invariance principle when the spectral measure of the drift satisfies a certain integrability condition. This result generalizes the results of [13, 7]. Received: 25 February 2000 / Revised version: 11 December 2000 /?Published online: 14 June 2001     

A non-uniform Berry–Esseen bound via Stein's method

This paper is part of our efforts to develop Stein's method beyond uniform bounds in normal approximation. Our main result is a proof for a non-uniform Berry–Esseen bound for independent and not necessarily identically distributed random variables without assuming the existence of third moments. It is proved by combining truncation with Stein's method and by taking the concentration inequality approach, improved and adapted for non-uniform bounds. To illustrate the technique, we give a proof for a uniform Berry–Esseen bound without assuming the existence of third moments. Received: 2 March 2000 / Revised version: 20 July 2000 / Published online: 26 April 2001     

Biased random walks on directed trees

Summary. We define directed rooted labeled and unlabeled trees and find measures on the space of directed rooted unlabeled trees which are invariant with respect to transition probabilities corresponding to a biased random walk on a directed rooted labeled tree. We use these to calculate the speed of a biased random walk on directed rooted labeled trees. The results are mainly applied to directed trees with recurrent subtrees, where the random walker cannot escape. Received: 12 March 1997/ In revised form: 11 December 1997     

On the distributions of the lengths of the longest monotone subsequences in random words

We consider the distributions of the lengths of the longest weakly increasing and strongly decreasing subsequences in words of length N from an alphabet of k letters. (In the limit as k→∞ these become the corresponding distributions for permutations on N letters.) We find Toeplitz determinant representations for the exponential generating functions (on N) of these distribution functions and show that they are expressible in terms of solutions of Painlevé V equations. We show further that in the weakly increasing case the generating unction gives the distribution of the smallest eigenvalue in the k×k Laguerre random matrix ensemble and that the distribution itself has, after centering and normalizing, an N→∞ limit which is equal to the distribution function for the largest eigenvalue in the Gaussian Unitary Ensemble of k×k hermitian matrices of trace zero. Received: 9 September 1999 / Revised version: 24 May 2000 / Published online: 24 January 2001     

Anomalous behaviour for the random corrections to the cumulants of random walks in fluctuating random media

The Central Limit Theorem for a model of discrete-time random walks on the lattice ℤ^ν in a fluctuating random environment was proved for almost-all realizations of the space-time nvironment, for all ν > 1 in [BMP1] and for all ν≥ 1 in [BBMP]. In [BMP1] it was proved that the random correction to the average of the random walk for ν≥ 3 is finite. In the present paper we consider the cases ν = 1,2 and prove the Central Limit Theorem as T→∞ for the random correction to the first two cumulants. The rescaling factor for theaverage is for ν = 1 and (ln T), for ν=2; for the covariance it is , ν = 1,2. Received: 25 November 1999 / Revised version: 7 June 2000 / Published online: 15 February 2001     

Minkowski Arrangements of Spheres

Let be a non-negative number not greater than 1. Consider an arrangement of (not necessarily congruent) spheres with positive homogenity in the n-dimensional Euclidean space, i.e., in which the infimum of the radii of the spheres divided by the supremum of the radii of the spheres is a positive number. With each sphere S of associate a concentric sphere of radius times the radius of S. We call this sphere the -kernel of S. The arrangement is said to be a Minkowski arrangement of order if no sphere of overlaps the -kernel of another sphere. The problem is to find the greatest possible density of n-dimensional Minkowski sphere arrangements of order . In this paper we give upper bounds on for .     

Two-point concentration in random geometric graphs

A random geometric graph G _n is constructed by taking vertices X ₁,…,X _n ∈ℝ ^d at random (i.i.d. according to some probability distribution ν with a bounded density function) and including an edge between X _i and X _j if ‖X _i -X _j ‖ < r where r = r(n) > 0. We prove a conjecture of Penrose ([14]) stating that when r=r(n) is chosen such that nr ^d = o(lnn) then the probability distribution of the clique number ω(G _n ) becomes concentrated on two consecutive integers and we show that the same holds for a number of other graph parameters including the chromatic number χ(G _n ). The author was partially supported by EPSRC, the Department of Statistics, Bekkerla-Bastide fonds, Dr. Hendrik Muller’s Vaderlandsch fonds, and Prins Bernhard Cultuurfonds.     

Equilibrium fluctuations of asymmetric simple exclusion processes in dimension d≥3

We consider an asymmetric exclusion process in dimension d≥ 3 under diffusive rescaling starting from the Bernoulli product measure with density 0 < α < 1. We prove that the density fluctuation field Y ^N _t converges to a generalized Ornstein–Uhlenbeck process, which is formally the solution of the stochastic differential equatin dY _t = ?Y _t dt + dB ^∇ _t , where ? is a second order differential operator and B ^∇ _t is a mean zero Gaussian field with known covariances. Received: 31 May 1999 / Revised version: 15 June 2000 / Published online: 24 January 2001     

On the area and perimeter of a random convex hull in a bounded convex set

Suppose K is a compact convex set in ℝ² and X _i , 1≤i≤n, is a random sample of points in the interior of K. Under general assumptions on K and the distribution of the X _i we study the asymptotic properties of certain statistics of the convex hull of the sample. Received: 24 July 1996/Revised version: 24 February 1998     

The Expected Volume of a Tetrahedron whose Vertices are Chosen at Random in the Interior of a Cube

We calculate E[V ₄(C)], the expected volume of a tetrahedron whose vertices are chosen randomly (i.e. independently and uniformly) in the interior of C, a cube of unit volume. We find

Discrete isoperimetric and Poincaré-type inequalities

We study some discrete isoperimetric and Poincaré-type inequalities for product probability measures μ ⁿ on the discrete cube {0, 1} ⁿ and on the lattice Z ⁿ . In particular we prove sharp lower estimates for the product measures of boundaries of arbitrary sets in the discrete cube. More generally, we characterize those probability distributions μ on Z which satisfy these inequalities on Z ⁿ . The class of these distributions can be described by a certain class of monotone transforms of the two-sided exponential measure. A similar characterization of distributions on R which satisfy Poincaré inequalities on the class of convex functions is proved in terms of variances of suprema of linear processes. Received: 30 April 1997 / Revised version: 5 June 1998     

Remarks on my paper: packing of incongruent circles on the sphere

The paper [3] contains an upper bound to the weighted density of a packing of circles on the unit sphere with radii from a given finite set. This bound is attained by many packings and has applications to problems of solidity. In the present note it is shown that a certain condition imposed on the set of admissible radii can be removed by modifying the original proof of the theorem.