The fluctuations of the overlap in the Hopfield model with finitely many patterns at the critical temperature

We investigate the limiting fluctuations of the order parameter in the Hopfield model of spin glasses and neural networks with finitely many patterns at the critical temperature 1/β _c = 1. At the critical temperature, the measure-valued random variables given by the distribution of the appropriately scaled order parameter under the Gibbs measure converge weakly towards a random measure which is non-Gaussian in the sense that it is not given by a Dirac measure concentrated in a Gaussian distribution. This remains true in the case of β = β _N →β _c = 1 as N→∞ provided β _N converges to β _c = 1 fast enough, i.e., at speed ?(1/). The limiting distribution is explicitly given by its (random) density. Received: 12 May 1998 / Revised version: 14 October 1998     

Asymptotic independence of maximum waiting times for increasing alphabet

For everyk≥1 consider the waiting time until each pattern of lengthk over a fixed alphabet of sizen appears at least once in an infinite sequence of independent, uniformly distributed random letters. Lettingn→∞ we determine the limiting finite dimensional joint distributions of these waiting times after suitable normalization and provide an estimate for the rate of convergence. It will turn out that these waiting times are getting independent. Research supported by the Hungarian National Foundation for Scientific Research, Grant No. 1905.     

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     

On the asymptotics of the eigenvalue counting function for random recursive Sierpinski gaskets

We consider natural Laplace operators on random recursive affine nested fractals based on the Sierpinski gasket and prove an analogue of Weyl’s classical result on their eigenvalue asymptotics. The eigenvalue counting function N(λ) is shown to be of order λ ^ds/2 as λ→∞ where we can explicitly compute the spectral dimension d _s . Moreover the limit N(λ) λ ^−ds/2 will typically exist and can be expressed as a deterministic constant multiplied by a random variable. This random variable is a power of the limiting random variable in a suitable general branching process and has an interpretation as the volume of the fractal. Received: 22 January 1999 / Revised version: 2 September 1999 /?Published online: 30 March 2000     

Ordered overlaps in disordered mean-field models

Let M(N) be a sequence of integers with M→∞ as N→∞ and M=o(N). For bounded i.i.d. r.v. ξ _i ^k and bounded i.i.d. r.v. σ _i , we study the large deviation of the family of (ordered) scalar products X ^k =N ⁻¹∑ _{i =1} ^N σ _i ξ _i ^k ,k≤M, under the distribution conditioned on the ξ _i ^k 's. To get a full large deviation principle, it is necessary to specify also the total norm(∑ _{k ≤ M} (X ^k )²)^1/2, which turns to be associated with some extra Gaussian distribution. Our results apply to disordered, mean-field systems, including generalized Hopfield models in the regime of a sublinear number of patterns. We build also a class of examples where this norm is the crucial order parameter. Received: 6 April 1999 / Revised version: 29 May 2000 /?Published online: 24 July 2001     

On the regularity of the distribution of the maximum of one-parameter Gaussian processes

The main result in this paper states that if a one-parameter Gaussian process has C ^2k paths and satisfies a non-degeneracy condition, then the distribution of its maximum on a compact interval is of class C ^k . The methods leading to this theorem permit also to give bounds on the successive derivatives of the distribution of the maximum and to study their asymptotic behaviour as the level tends to infinity. Received: 14 May 1999 / Revised version: 18 October 1999 / Published online: 14 December 2000     

On the Constants in the Meyer Inequality

 We study the growth of the constants in the Meyer inequality as p → 1 and p → ∞. Both constants grow, within constant factors, like (p − 1)⁻¹ and like p respectively. Received August 10, 2001; in revised form February 5, 2002     

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     

Diagnostic tests for local coalescences of variables in Boolean functions

The article studies diagnostic tests for local k -fold coalescences of variables in Boolean functions f( [(x)\tilde]ⁿ )( 1 ￡ k ￡ n,  1 ￡ t ￡ 2^2k ) f\left( {{{\tilde{x}}^n}} \right)\left( {1 \leq k \leq n,\;1 \leq t \leq {2^{{2^k}}}} \right) . Upper and lower bounds are proved for the Shannon function of the length of the diagnostic test for local k -fold coalescences generated by the system of functions F_t^k \Phi_t^k . The Shannon function of the length of a complete diagnostic test for local k -fold coalescences behaves asymptotically as 2 ^k (n − k + 1) for n → ∞, k → ∞.     

The diameter of random regular graphs

We give asymptotic upper and lower bounds for the diameter of almost everyr-regular graph onn vertices (n → ∞).     

Automorphisms of random graphs with specified vertices

Conditions are found under which the expected number of automorphisms of a large random labelled graph with a given degree sequence is close to 1. These conditions involve the probability that such a graph has a given subgraph. One implication is that the probability that a random unlabelledk-regular simple graph onn vertices has only the trivial group of automorphisms is asymptotic to 1 asn → ∞ with 3≦k=O(n ^1/2−c). In combination with previously known results, this produces an asymptotic formula for the number of unlabelledk-regular simple graphs onn vertices, as well as various asymptotic results on the probable connectivity and girth of such graphs. Corresponding results for graphs with more arbitrary degree sequences are obtained. The main results apply equally well to graphs in which multiple edges and loops are permitted, and also to bicoloured graphs. Research of the second author supported by U. S. National Science Foundation Grant MCS-8101555, and by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowships Scheme. Current address: Mathematics Department, University of Auckland, Auckland, New Zealand.     

Universality of random matrices and local relaxation flow

Consider the Dyson Brownian motion with parameter β, where β=1,2,4 corresponds to the eigenvalue flows for the eigenvalues of symmetric, hermitian and quaternion self-dual ensembles. For any β≥1, we prove that the relaxation time to local equilibrium for the Dyson Brownian motion is bounded above by N ^−ζ for some ζ>0. The proof is based on an estimate of the entropy flow of the Dyson Brownian motion w.r.t. a “pseudo equilibrium measure”. As an application of this estimate, we prove that the eigenvalue spacing statistics in the bulk of the spectrum for N×N symmetric Wigner ensemble is the same as that of the Gaussian Orthogonal Ensemble (GOE) in the limit N→∞. The assumptions on the probability distribution of the matrix elements of the Wigner ensemble are a subexponential decay and some minor restriction on the support.     

Existence of equilibrium states of systems of hard spheres in the Boltzmann-Enskog limit within the frame work of the grand canonical ensemble

We study equilibrium states of systems of hard spheres in the Boltzmann-Enskog limit (d→0, 1/v→∞ (z→∞), and d ³ (1/v)=const (d ³ z=const)). For this purpose, we use the Kirkwood-Salsburg equations. We prove that, in the Boltzmann-Enskog limit, solutions of these equations exist and the limit distribution functions are constant. By using the cluster and compatibility conditions, we prove that all distribution functions are equal to the product of one-particle distribution functions, which can be represented as power series in z=d ³ z with certain coefficients. Institute of Mathematics, Ukrainian Academy of Sciences, Kiev. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 49, No. 1, pp. 112–121, January, 1997.     

N/V-limit for stochastic dynamics in continuous particle systems

We provide an N/V-limit for the infinite particle, infinite volume stochastic dynamics associated with Gibbs states in continuous particle systems on ℝ ^d ,d≥1. Starting point is an N-particle stochastic dynamic with singular interaction and reflecting boundary condition in a subset Λ⊂ℝ ^d with finite volume (Lebesgue measure) V=|Λ|<∞. The aim is to approximate the infinite particle, infinite volume stochastic dynamic by the above N-particle dynamic in Λ as N→∞ and V→∞ such that N/V→ρ, where ρ is the particle density. First we derive an improved Ruelle bound for the canonical correlation functions under an appropriate relation between N and V. Then tightness is shown by using the Lyons–Zheng decomposition. The equilibrium measures of the accumulation points are identified as infinite volume canonical Gibbs measures by an integration by parts formula and the accumulation points themselves are identified as infinite particle, infinite volume stochastic dynamics via the associated martingale problem. Assuming a property closely related to Markov uniqueness and weaker than essential self-adjointness, via Mosco convergence techniques we can identify the accumulation points as Markov processes and show uniqueness. I.e., all accumulation corresponding to one invariant canonical Gibbs measure coincide. The proofs work for general repulsive interaction potentials ϕ of Ruelle type and all temperatures, densities, and dimensions d≥1, respectively. ϕ may have a nontrivial negative part and infinite range as e.g. the Lennard–Jones potential. Additionally, our result provides as a by-product an approximation of grand canonical Gibbs measures by finite volume canonical Gibbs measures with empty boundary condition.     

Large deviation principles for Euclidean functionals and other nearly additive processes

We prove a large deviation principle for a process indexed by cubes of the multidimensional integer lattice or Euclidean space, under approximate additivity and regularity hypotheses. The rate function is the convex dual of the limiting logarithmic moment generating function. In some applications the rate function can be expressed in terms of relative entropy. The general result applies to processes in Euclidean combinatorial optimization, statistical mechanics, and computational geometry. Examples include the length of the minimal tour (the traveling salesman problem), the length of the minimal matching graph, the length of the minimal spanning tree, the length of the k-nearest neighbors graph, and the free energy of a short-range spin glass model. Received: 3 April 1999 / Revised version: 23 June 1999 / Published online: 8 May 2001     

Dense Packing of Patterns in a Permutation

We study the length L _k of the shortest permutation containing all patterns of length k. We establish the bounds e ⁻² k ² < L _k ≤ (2/3 + o(1))k ². We also prove that as k → ∞, there are permutations of length (1/4 + o(1))k ² containing almost all patterns of length k. Received January 2, 2007     

Uniform in bandwidth consistency of kernel estimators of the tail index

We consider a class of kernel estimators [^(t)]_n,h\hat{\tau}_{n,h} of the tail index of a Pareto-type distribution, which generalizes and includes the classical Hill estimator [^(a)]_n,k\hat{a}_{n,k}. It is well-known that [^(a)]_n,k\hat{a}_{n,k} is a consistent estimator of the tail index if and only if k→ ∞ and k/n→0. Under suitable assumptions on the kernel, [^(t)] _n,h\hat{\tau} _{n,h} is consistent whenever the bandwidth is taken to be a sequence of non-random numbers satisfying h _n →0 and nh _n → ∞. We extend this result and prove the consistency uniformly over a certain range of bandwidths. This permits the treatment of estimators of the tail index based upon data-dependent bandwidths, which are often used in practice. In the process, we establish a uniform in bandwidth result for kernel-type regression estimators with a fixed design, which will likely be of separate interest.     

Application of a Bernstein type inequality to rational interpolation in the Dirichlet space

We prove a Bernstein type inequality involving the Bergman and Hardy norms for rational functions in the unit disk \mathbb D {\mathbb D} that have at most n poles all of which are outside the disk \frac1r \mathbb D \frac{1}{r} {\mathbb D} , 0 < r < 1. The asymptotic sharpness of this inequality is shown as n → ∞ and r → 1—. We apply our Bernstein type inequality to an efficient Nevanlinna–Pick interpolation problem in the standard Dirichlet space constrained by the H2-nom. Bibliography: 14 titles.     

Random coin tossing

Summary. A sequence of heads and tails is produced by repeatedly selecting a coin from two possible coins, and tossing it. The second coin is tossed at renewal times in a renewal process, and the first coin is tossed at all other times. The first coin is fair (Prob(heads)=1/2), and the second coin is known either to be fair, or to have known biasθ∈(0,1] (Prob(heads) ). Letting u _k := Prob (There is a renewal at time k), we show that if ∑ _{k =0} ^∞ u _k ²=∞, we can determine, using only the sequence of heads and tails produced, if the second coin had bias θ or 0. If , we show that this is not possible. Received: 20 November 1996 / In revised form: 20 February 1997