An estimate on the supremum of a nice class of stochastic integrals and U-statistics

Let a sequence of iid. random variables ξ ₁, . . . ,ξ _n be given on a space with distribution μ together with a nice class of functions f(x ₁, . . . ,x _k ) of k variables on the product space For all f ∈ we consider the random integral J _n,k (f) of the function f with respect to the k-fold product of the normalized signed measure where μ _n denotes the empirical measure defined by the random variables ξ ₁, . . . ,ξ _n and investigate the probabilities for all x>0. We show that for nice classes of functions, for instance if is a Vapnik–Červonenkis class, an almost as good bound can be given for these probabilities as in the case when only the random integral of one function is considered. A similar result holds for degenerate U-statistics, too. Supported by the OTKA foundation Nr. 037886     

The divergence of fluctuations for shape in first passage percolation

We consider the first passage percolation model on Z ^d for d ≥ 2. In this model, we assign independently to each edge the value zero with probability p and the value one with probability 1−p. We denote by T(0, ν) the passage time from the origin to ν for ν ∈ R ^d and It is well known that if p < p _c , there exists a compact shape B _d ⊂ R ^d such that for all > 0, t B _d (1 − ) ⊂ B(t) ⊂ tB _d (1 + ) and G(t)(1 − ) ⊂ B(t) ⊂ G(t)(1 + ) eventually w.p.1. We denote the fluctuations of B(t) from tB _d and G(t) by In this paper, we show that for all d ≥ 2 with a high probability, the fluctuations F(B(t), G(t)) and F(B(t), tB _d ) diverge with a rate of at least C log t for some constant C. The proof of this argument depends on the linearity between the number of pivotal edges of all minimizing paths and the paths themselves. This linearity is also independently interesting. Research supported by NSF grant DMS-0405150     

Order and algebra isomorphisms of spaces of regular operators

If E and F are real Banach lattices and there is an algebra and order isomorphism Φ:(E) →(F) between their respective ordered Banach algebras of regular operators then there is a linear order isomorphism U:E→F such that Φ(T) =UTU⁻¹ for all T ∈ (E).     

Asymptotic laws for regenerative compositions: gamma subordinators and the like

For a random closed set obtained by exponential transformation of the closed range of a subordinator, a regenerative composition of generic positive integer n is defined by recording the sizes of clusters of n uniform random points as they are separated by the points of . We focus on the number of parts K_n of the composition when is derived from a gamma subordinator. We prove logarithmic asymptotics of the moments and central limit theorems for K_n and other functionals of the composition such as the number of singletons, doubletons, etc. This study complements our previous work on asymptotics of these functionals when the tail of the Lévy measure is regularly varying at 0+. Research supported in part by N.S.F. Grant DMS-0071448     

On the disconnection of a discrete cylinder by a random walk

We investigate the large N behavior of the time the simple random walk on the discrete cylinder needs to disconnect the discrete cylinder. We show that when d≥2, this time is roughly of order N ^{2 d} and comparable to the cover time of the slice , but substantially larger than the cover timer of the base by the projection of the walk. Further we show that by the time disconnection occurs, a massive ``clogging' typically takes place in the truncated cylinders of height . These mechanisms are in contrast with what happens when d=1.     

Mean-value theorems for multiplicative functions on Beurling’s generalized integers (I)

Halász’s general mean-value theorem for multiplicative functions on ℕ is classical in probabilistic number theory. We extend this theorem to functions f, defined on a set of generalized integers associated with a set of generalized primes in Beurling’s sense, which satisfies Halász’s conditions, in particular,Assume that the distribution function N(x) of satisfieswith γ>γ₀, where ρ₁<ρ₂<···<ρ_m are constants with ρ_m≥1 and A₁,···,A_m are real constants with A_m>0. Also, assume that the Chebyshev function ψ(x) of satisfieswith M>M₀. Then the asymptoticimplieswhere τ is a positive constant with τ≥1 and L(u) is a slowly oscillating function with |L(u)|=1.     

Exceptional times and invariance for dynamical random walks

Consider a sequence of i.i.d. random variables. Associate to each X _i (0) an independent mean-one Poisson clock. Every time a clock rings replace that X-variable by an independent copy and restart the clock. In this way, we obtain i.i.d. stationary processes {X _i (t)} _{t ≥0} (i=1,2,···) whose invariant distribution is the law ν of X ₁(0). Benjamini et al. (2003) introduced the dynamical walk S _n (t)=X ₁(t)+···+X _n (t), and proved among other things that the LIL holds for n↦S _n (t) for all t. In other words, the LIL is dynamically stable. Subsequently (2004b), we showed that in the case that the X _i (0)'s are standard normal, the classical integral test is not dynamically stable. Presently, we study the set of times t when n↦S _n (t) exceeds a given envelope infinitely often. Our analysis is made possible thanks to a connection to the Kolmogorov ɛ-entropy. When used in conjunction with the invariance principle of this paper, this connection has other interesting by-products some of which we relate. We prove also that the infinite-dimensional process converges weakly in to the Ornstein–Uhlenbeck process in For this we assume only that the increments have mean zero and variance one. In addition, we extend a result of Benjamini et al. (2003) by proving that if the X _i (0)'s are lattice, mean-zero variance-one, and possess (2+ɛ) finite absolute moments for some ɛ>0, then the recurrence of the origin is dynamically stable. To prove this we derive a gambler's ruin estimate that is valid for all lattice random walks that have mean zero and finite variance. We believe the latter may be of independent interest. The research of D. Kh. is partially supported by a grant from the NSF.     

Matrix Representations for Positive Noncommutative Polynomials

In real semialgebraic geometry it is common to represent a polynomial q which is positive on a region R as a weighted sum of squares. Serious obstructions arise when q is not strictly positive on the region R. Here we are concerned with noncommutative polynomials and obtaining a representation for them which is valid even when strict positivity fails. Specifically, we treat a ``symmetric' polynomial q(x, h) in noncommuting variables, {x<sub>1</sub>, . . . , } and {h<sub>1</sub>, . . . , } for which q(X,H) is positive semidefinite whenever are tuples of selfadjoint matrices with ||X<sub>j</sub>|| ≤ 1 but H<sub>j</sub> unconstrained. The representation we obtain is a Gram representation in the variables h where P<sub>q</sub> is a symmetric matrix whose entries are noncommutative polynomials only in x and V is a ``vector' whose entries are polynomials in both x and h. We show that one can choose P_q such that the matrix P_q(X) is positive semidefinite for all ||X_j|| ≤ 1. The representation covers sum of square results ([Am. Math. (to appear); Linear Algebra Appl. 326 (2001), 193–203; Non commutative Sums of Squares, preprint]) when g_x = 0. Also it allows for arbitrary degree in h, rather than degree two, in the main result of [Matrix Inequalities: A Symbolic Procedure to Determine Convexity Automatically to appear IOET July 2003] when restricted to x-domains of the type ||X_j|| ≤ 1. Partially supported by NSF, DARPA and Ford Motor Co. Partially supported by NSF grant DMS-0140112 Partially supported by NSF grant DMS-0100367     

Inversion de l'espace et du temps des processus de Lévy stables

We proove a new duality relation between stable Lévy processes with index and those with index . This duality appears to be the trajectorial version of the duality of Zolotarev which concerns one dimensional stable laws. We give an application of this result to the behaviour of the paths at small and large times of the process ``conditioned to stay positive'. Mots-clefs: Lévy process Stable process Fluctuation identities Ladder process     

Positive Projective Space of a <Emphasis Type="Italic">C</Emphasis>*-Algebra with a Tracial Conditional Expectation

Let be a C*-algebra, a subalgebra of its center and Φ: → a tracial faithful conditional expectation. We define the positive projective space as the quotient where G⁺ is the space of positive invertible elements of , and if there exists g invertible in such that a′ = |g|²a. When is abelian, this space is a set of representatives for probability densities equivalent to a given one. The aim of this paper is to endow ℙ⁺ with differentiable structure, a linear connection and a Finsler metric. This is done in a way that given any pair of elements in ℙ⁺, there is a unique geodesic of this connection, which is the shortest curve joining such endpoints for the given metric. The metric space ℙ⁺ with the given geodesic distance is non positively curved.     

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     

Contractivity properties of Ornstein-Uhlenbeck semigroup for general commutation relations

We study a certain class of von Neumann algebras generated by selfadjoint elements ω_i=a_i+a_i⁺, where a_i, a_i⁺ satisfy the general commutation relations:We assume that operator T for which the constants are matrix coefficients satisfies the braid relation. Such algebras were investigated in [BSp] and [K] where the positivity of the Fock representation and factoriality were shown. In this paper we prove that T-Ornstein-Uhlenbeck semigroup U_t=Γ_T(e^−t), t>0 arising from the second quantization procedure is hyper- and ultracontractive. The optimal bounds for hypercontractivity are also discussed.This paper was partially supported by KBN grant no 2P03A00732 and also by RTN grant HPRN-CT-2002-00279.     

Isoperimetry for wreath products of Markov chains and multiplicity of selfintersections of random walks

We prove an isoperimetric inequality for wreath products of Markov chains with variable fibers. We use isoperimetric inequalities for wreath products to estimate the return probability of random walks on infinite groups and graphs, drift of random loops, the expected value E(exp(−tR _n )), where R _n is the number of distinct sites, visited up to the moment n, and, more generally, (where L _z,n is the number of visits of z up to the moment n and F(x, y) is some non-negative function).     

On the rank of abelian varieties over function fields

Let be a smooth projective curve defined over a number field k, A/k() an abelian variety and (τ, B) the k()/k-trace of A. We estimate how the rank of A(k())/τB(k) varies when we take a finite geometrically abelian cover defined over k. This work was partially supported by CNPq research grant 304424/2003-0, Pronex 41.96.0830.00 and CNPq Edital Universal 470099/2003-8. I would like to thank Douglas Ulmer for comments on how to treat the case of arbitrary ramification, but the conductor prime to the ramification locus, in the case of elliptic fibrations. I would also like to thank Marc Hindry for comments on the inequality comparing the conductors of A and A'. Finally, I also thank the referee for his comments and criticisms.     

Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations

Summary We introduce a class of n×n structured matrices which includes three well-known classes of generalized companion matrices: tridiagonal plus rank-one matrices (comrade matrices), diagonal plus rank-one matrices and arrowhead matrices. Relying on the structure properties of , we show that if A then A=RQ , where A=QR is the QR decomposition of A. This allows one to implement the QR iteration for computing the eigenvalues and the eigenvectors of any A with O(n) arithmetic operations per iteration and with O(n) memory storage. This iteration, applied to generalized companion matrices, provides new O(n²) flops algorithms for computing polynomial zeros and for solving the associated (rational) secular equations. Numerical experiments confirm the effectiveness and the robustness of our approach.The results of this paper were presented at the Workshop on Nonlinear Approximations in Numerical Analysis, June 22 – 25, 2003, Moscow, Russia, at the Workshop on Operator Theory and Applications (IWOTA), June 24 – 27, 2003, Cagliari, Italy, at the Workshop on Numerical Linear Algebra at Universidad Carlos III in Leganes, June 16 – 17, 2003, Leganes, Spain, at the SIAM Conference on Applied Linear Algebra, July 15 – 19, 2003, Williamsburg, VA and in the Technical Report [8]. This work was partially supported by MIUR, grant number 2002014121, and by GNCS-INDAM. This work was supported by NSF Grant CCR 9732206 and PSC CUNY Awards 66406-0033 and 65393-0034.     

Limit theorems for sums of random exponentials

We study limiting distributions of exponential sums as t→∞, N→∞, where (X_i) are i.i.d. random variables. Two cases are considered: (A) ess sup X_i = 0 and (B) ess sup X_i = ∞. We assume that the function h(x)= -log P{X_i>x} (case B) or h(x) = -log P {X_i>-1/x} (case A) is regularly varying at ∞ with index 1 < ϱ <∞ (case B) or 0 < ϱ < ∞ (case A). The appropriate growth scale of N relative to t is of the form , where the rate function H₀(t) is a certain asymptotic version of the function (case B) or (case A). We have found two critical points, λ₁<λ₂, below which the Law of Large Numbers and the Central Limit Theorem, respectively, break down. For 0 < λ < λ₂, under the slightly stronger condition of normalized regular variation of h we prove that the limit laws are stable, with characteristic exponent α = α (ϱ, λ) ∈ (0,2) and skewness parameter β ≡ 1.Research supported in part by the DFG grants 436 RUS 113/534 and 436 RUS 113/722.Mathematics Subject Classification (2000): 60G50, 60F05, 60E07     

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.     

Bootstrap percolation on the hypercube

In the bootstrap percolation on the n-dimensional hypercube, in the initial position each of the 2ⁿ sites is occupied with probability p and empty with probability 1−p, independently of the state of the other sites. Every occupied site remains occupied for ever, while an empty site becomes occupied if at least two of its neighbours are occupied. If at the end of the process every site is occupied, we say that the (initial) position spans the hypercube. We shall show that there are constants c₁,c₂>0 such that for the probability of spanning tends to 1 as n→∞, while for the probability tends to 0. Furthermore, we shall show that for each n the transition has a sharp threshold function. J. Balogh: work was done while at The University of Memphis, USA Research supported in part by NSF grant DMS0302804 Research supported in part by NSF grant ITR 0225610 and DARPA grant F33615-01-C-1900     

A local limit theorem for random walks conditioned to stay positive

We consider a real random walk S_n=X₁+...+X_n attracted (without centering) to the normal law: this means that for a suitable norming sequence a_n we have the weak convergence S_n/a_n⇒ϕ(x)dx, ϕ(x) being the standard normal density. A local refinement of this convergence is provided by Gnedenko's and Stone's Local Limit Theorems, in the lattice and nonlattice case respectively. Now let denote the event (S₁>0,...,S_n>0) and let S_n⁺ denote the random variable S_n conditioned on : it is known that S_n⁺/a_n ↠ ϕ⁺(x) dx, where ϕ⁺(x):=x exp (−x²/2)1_(x≥0). What we establish in this paper is an equivalent of Gnedenko's and Stone's Local Limit Theorems for this weak convergence. We also consider the particular case when X₁ has an absolutely continuous law: in this case the uniform convergence of the density of S_n⁺/a_n towards ϕ⁺(x) holds under a standard additional hypothesis, in analogy to the classical case. We finally discuss an application of our main results to the asymptotic behavior of the joint renewal measure of the ladder variables process. Unlike the classical proofs of the LLT, we make no use of characteristic functions: our techniques are rather taken from the so–called Fluctuation Theory for random walks.     

Translation invariant Gibbs states for the Ising model

We prove that all the translation invariant Gibbs states of the Ising model are a linear combination of the pure phases for any . This implies that the average magnetization is continuous for . Furthermore, combined with previous results on the slab percolation threshold [B2] this shows the validity of Pisztora's coarse graining [Pi] up to the critical temperature. We would like to thank C. Pfister and Y. Velenik for very useful comments.