Universality of critical behaviour in a class of recurrent random walks

Let X₀=0, X₁, X₂,.. be an aperiodic random walk generated by a sequence ₁, ₂,... of i.i.d. integer-valued random variables with common distribution p(·) having zero mean and finite variance. For anN-step trajectory and a monotone convex functionV: withV(0)=0, define Further, let be the set of all non-negative paths compatible with the boundary conditionsX₀=a, X_N=b. We discuss asymptotic properties of under the probability distribution N and 0, Z^a,b_N,+, being the corresponding normalization. If V(·) grows not faster than polynomially at infinity, define H() to be the unique solution to the equation Our main result reads that as 0, the typical height of X_[, ^N] scales as H() and the correlations along decay exponentially on the scale H()². Using a suitable blocking argument, we show that the distribution tails of the rescaled height decay exponentially with critical exponent 3/2. In the particular case of linear potential V(·), the characteristic length H() is proportional to ^-1/3 as 0.Mathematics Subject Classification (2000):60G50, 60K35; 82B27, 82B41     

On the exact Hausdorff dimension of the set of Liouville numbers

Let denote the set of Liouville numbers. For a dimension function h, we write () for the h-dimensional Hausdorff measure of . In this paper we locate the exact cut-point at which the Hausdorff measure of drops from infinity to zero. Namely, if h is a dimension function that increases faster than any power function near 0, then ()=, and if h is a dimension function that increases slower than some power function near 0, then ()=0. This answers a question asked by R. D. Mauldin.Mathematics Subject Classification (2000): 28A80     

Cumulants are universal homomorphisms into Hausdorff groups

This is a contribution to the theory of sums of independent random variables at an algebraico-analytical level: Let Prob denote the convolution semigroup of all probability measures on with all moments finite, topologized by polynomially weighted total variation. We prove that the cumulant sequence regarded as a function from Prob into the additive topological group ofall real sequences, is universal among continuous homomorphisms from Prob into Hausdorff topological groups, in the usual sense that every other such homomorphism factorizes uniquely through . An analogous result, referring to just the first cumulants,holds for the semigroup of all probability measures with existing rth moments. In particular, there is no nontrivial continuous homomorphism from the convolution semigroup of all probability measures, topologized by the total variation metric, into any Hausdorff topological group.Mathematics Subject Classification (2000): 60B15, 60E10, 60G50     

Isoperimetric inequalities and random walks on quotients of graphs and buildings

Let be a Euclidean or hyperbolic building and let GAut be a locally compact unimodular group, which acts strongly transitively on . We use graphs , quasi-isometric to , to study asymptotic properties of quotients , where is a discrete subgroup of G. If G has Kazhdans property (T) we show that such quotients satisfy strong isoperimetric inequalities. This yields new examples of graphs with positive Cheeger constant. Such graphs cannot be bi-Lipschitz embedded into Hilbert space. Moreover, simple random walks on such quotients are shown to be recurrent if and only if is a uniform lattice in G.Mathematics Subject Classification (1991): 11E95, 22E40, 22E50, 51E24, 60G50in final form: 10 October 2003     

What is so special with the powerset operation?

The powerset operator, , is an operator which (1) sends sets to sets,(2) is defined by a positive formula and (3) raises the cardinality of its argument, i.e., |(x)|>|x|. As a consequence of (3), has a proper class as least fixed point (the universe itself). In this paper we address the questions: (a) How does contribute to the generation of the class of all positive operators? (b) Are there other operators with the above properties, independent of ? Concerning (a) we show that every positive operator is a combination of the identity, powerset, and almost constant operators. This enables one to define what a -independent operator is. Concerning (b) we show that every -independent bounded positive operator is not -like.Mathematics Subject Classification (2000): Primary 03E05, secondary 03E20     

Path regularity for Feller semigroups via Gaussian kernel estimates and generalizations to arbitrary semigroups on <Emphasis Type="Italic">C</Emphasis><Subscript>0</Subscript>

Given γ ∈ (−1,1), we present a dyadic growth condition on the finite dimensional distributions of operator semigroups on C₀(E which - for γ>0 and Feller semigroups - assures that the corresponding Feller process has paths in local Hölder spaces and in weighted Besov spaces of order γ. We show that, for operator semigroups satisfying Gaussian kernel estimates of order m>1, condition holds for all and even for all in the case of Feller semigroups. Such Gaussian kernel estimates are typical for Feller semigroups on fractals of walk dimension m and for semigroups generated by elliptic operators on ℝ^D of order m≥D.     

Prediction for discrete time series

Let {X_n} be a stationary and ergodic time series taking values from a finite or countably infinite set Assume that the distribution of the process is otherwise unknown. We propose a sequence of stopping times _n along which we will be able to estimate the conditional probability P(=x|X₀,...,) from data segment (X₀,...,) in a pointwise consistent way for a restricted class of stationary and ergodic finite or countably infinite alphabet time series which includes among others all stationary and ergodic finitarily Markovian processes. If the stationary and ergodic process turns out to be finitarily Markovian (among others, all stationary and ergodic Markov chains are included in this class) then almost surely. If the stationary and ergodic process turns out to possess finite entropy rate then _n is upperbounded by a polynomial, eventually almost surely.Mathematics Subject Classification (2000): 62G05, 60G25, 60G10     

Non-abelian class field theory for arithmetic surfaces

Let be a regular arithmetic surface. Assume that for all irreducible curves there are given open normal subgroups of ₁(C), which fulfill a compatibility condition at all closed points x . We then show that these data uniquely determine a normal subgroup of ₁(). This is used to construct abelian class field theory for arithmetic surfaces using only K₀ and K₁ groups of local and global fields.Mathematics Subject Classification (2000): 14G40, 11R37, 14H25     

Selector processes on classes of sets

Consider the random subset X of ℕ obtained by selecting independently each integer with a probability δ. Consider a finite class of finite sets. We describe a combinatorial quantity that is of the same order as We then give a related result allowing to compute the supremum of the empirical process on a class of sets. Work partially supported by an NSF grant.     

New dependence coefficients. Examples and applications to statistics

To measure the dependence between a real-valued random variable X and a -algebra , we consider four distances between the conditional distribution function of X given and the distribution function of X. The coefficients obtained are weaker than the corresponding mixing coefficients and may be computed in many situations. In particular, we show that they are well adapted to functions of mixing sequences, iterated random functions and dynamical systems. Starting from a new covariance inequality, we study the mean integrated square error for estimating the unknown marginal density of a stationary sequence. We obtain optimal rates for kernel estimators as well as projection estimators on a well localized basis, under a minimal condition on the coefficients. Using recent results, we show that our coefficients may be also used to obtain various exponential inequalities, a concentration inequality for Lipschitz functions, and a Berry-Esseen type inequality.Mathematics Subject Classification (2000): 62G07, 60J10, 60E15, 37C30     

Exceptional points of an endomorphism of the projective plane

Let f an endomorphism of of degree >1. We show how to obtain a bound (depending only on n) on the number of codimension-two subspaces in which are completely invariant for f (where L is completely invariant for f means that f^–1(L)=L set-theoretically).     

Normal subgroup growth in free class-2-nilpotent groups

Let F_2,d denote the free class-2-nilpotent group on d generators. We compute the normal zeta functions prove that they satisfy local functional equations and determine their abscissae of convergence and pole orders.     

Labelling classes by sets

Let Q be an equivalence relation whose equivalence classes, denoted Q[x], may be proper classes. A function L defined on Field(Q) is a labelling for Q if and only if for all x,L(x) is a set andL is a labelling by subsets for Q if and only ifBG denotes Bernays-Gödel class-set theory with neither the axiom of foundation, AF, nor the class axiom of choice, E. The following are relatively consistent with BG. (1) E is true but there is an equivalence relation with no labelling.(2) E is true and every equivalence relation has a labelling, but there is an equivalence relation with no labelling by subsets.This research was partially supported by Fondecyt 1980855 and by Fondecyt 1040846     

The largest eigenvalue of small rank perturbations of Hermitian random matrices

We compute the limiting eigenvalue statistics at the edge of the spectrum of large Hermitian random matrices perturbed by the addition of small rank deterministic matrices. We consider random Hermitian matrices with independent Gaussian entries M _ij ,i≤j with various expectations. We prove that the largest eigenvalue of such random matrices exhibits, in the large N limit, various limiting distributions depending on both the eigenvalues of the matrix and its rank. This rank is also allowed to increase with N in some restricted way. An erratum to this article is available at .     

On the exact Hausdorff dimension of the set of Liouville numbers. II

Let denote the set of Liouville numbers. For a dimension function h, we write for the h-dimensional Hausdorff measure of . In previous work, the exact ``cut-point' at which the Hausdorff measure of drops from infinity to zero has been located for various classes of dimension functions h satisfying certain rather restrictive growth conditions. In the paper, we locate the exact ``cut-point' at which the Hausdorff measure of drops from infinity to zero for all dimension functions h. Namely, if h is a dimension function for which the function increases faster than any power function near 0, then , and if h is a dimension function for which the function increases slower than some power function near 0, then . This provides a complete characterization of all Hausdorff measures of without assuming anything about the dimension function h, and answers a question asked by R. D. Mauldin. We also show that if then does not have σ-finite measure. This answers another question asked by R. D. Mauldin. This work was done while Dave L. Renfro was at the Department of Mathematics at Central Michigan University.     

Distributions diophantiennes et théorème limite local sur

We study the speed of convergence of n^d/2fd^*n in the local limit theorem on under very general conditions upon the function f and the distribution . We show that this speed is at least of order and we give a simple characterization (in diophantine terms) of those measures for which this speed (and the full local Edgeworth expansion) holds for smooth enough f. We then derive a uniform local limit theorem for moderate deviations under a mild moment assumption. This in turn yields other limit theorems when f is no longer assumed integrable but only bounded and Lipschitz or Hölder. We finally give an application to equidistribution of random walks.     

-measures for branching exit Markov systems and their applications to differential equations

Semilinear equations Lu=(u) where L is an elliptic differential operator and is a positive function can be investigated by using (L,)-superdiffusions. In a special case u=u² a powerful probabilistic tool – the Brownian snake – introduced by Le Gall was successfully applied by him and his school to get deep results on solutions of this equation. Some of these results (but not all of them) were extended by Dynkin and Kuznetsov to general equations by applying superprocesses. An important role in the theory of the Brownian snake and its applications is played by measures _x on the space of continuous paths. Our goal is to introduce analogous measures related to superprocesses (and to general branching exit Markov systems). They are defined on the space of measures and we call them -measures. Using -measures allows to combine some advantages of Brownian snakes and of superprocesses as tools for a study of semilinear PDEs.Partially supported by National Science Foundation Grant DMS-0204237 and DMS-9971009Mathematics Subject Classification (2000): Primary 31C15, Secondary 35J65, 60J60     

Equations of low-degree projective surfaces with three-divisible sets of cusps

We determine the equations of surfaces of degrees 6 carrying a minimal, non-empty, three-divisible set of cusps.Mathematics Subject Classification (2000): 14J25, 14J17Supported by the DFG Schwerpunktprogramm Global methods in complex geometry. The second author is supported by a Fellowship of the Foundation for Polish Science and KBN Grant No. 2 P03A 016 25.     

Linear phase transition in random linear constraint satisfaction problems

Our model is a generalized linear programming relaxation of a much studied random K-SAT problem. Specifically, a set of linear constraints on K variables is fixed. From a pool of n variables, K variables are chosen uniformly at random and a constraint is chosen from also uniformly at random. This procedure is repeated m times independently. We are interested in whether the resulting linear programming problem is feasible. We prove that the feasibility property experiences a linear phase transition, when n and m = cn for a constant c. Namely, there exists a critical value c^* such that, when c < c^*, the problem is feasible or is asymptotically almost feasible, as n, but, when c>c^*, the distance to feasibility is at least a positive constant independent of n. Our result is obtained using the combination of a powerful local weak convergence method developed in Aldous [Ald92], [Ald01], Aldous and Steele [AS03], Steele [Ste02] and martingale techniques. By exploiting a linear programming duality, our theorem implies the following result in the context of sparse random graphs G(n, cn) on n nodes with cn edges, where edges are equipped with randomly generated weights. Let (n, c) denote maximum weight matching in G(n, cn). We prove that when c is a constant and n , the limit lim_n (n, c)/n, exists, with high probability. We further extend this result to maximum weight b-matchings also in G(n, cn).     

A convex/log-concave correlation inequality for Gaussian measure and an application to abstract Wiener spaces

This paper deals with a generalization of a result due to Brascamp and Lieb which states that in the space of probabilities with log-concave density with respect to a Gaussian measure on this Gaussian measure is the one which has strongest moments. We show that this theorem remains true if we replace x by a general convex function. Then, we deduce a correlation inequality for convex functions quite better than the one already known. Finally, we prove results concerning stochastic analysis on abstract Wiener spaces through the notion of approximate limit.Mathematics Subject Classification (2000): Primary: 28C20, 60E15, 60H05Revised version: 20 February 2004