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     

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.     

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.     

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.     

A series expansion of fractional Brownian motion

Let B be a fractional Brownian motion with Hurst index H(0,1). Denote by the positive, real zeros of the Bessel function J_–H of the first kind of order –H, and let be the positive zeros of J_1–H. In this paper we prove the series representation where X₁,X₂,... and Y₁,Y₂,... are independent, Gaussian random variables with mean zero and and the constant c_H² is defined by c_H²=^–1(1+2H) sin H. We show that with probability 1, both random series converge absolutely and uniformly in t[0,1], and we investigate the rate of convergence.Mathematics Subject Classification (2000): 60G15, 60G18, 33C10     

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     

Non-commutative polynomials of independent Gaussian random matrices. The real and symplectic cases.

In [HT2] Haagerup and Thorbjo rnsen prove the following extension of Voiculescus random matrix model (cf. [V2, Theorem 2.2]): For each n , let X₁⁽ⁿ⁾,..., X_r⁽ⁿ⁾ be r independent complex self-adjoint random matrices from the class and let x₁,...,x_r be a semicircular system in a C*-probability space. Then for any polynomial p in r non-commuting variables the convergenceholds almost surely. We generalize this result to sets of independent Gaussian random matrices with real or symplectic entries (the GOE- and the GSE-ensembles) and random matrix ensembles related to these.This work was partially supported by MaPhySto – A Network in Mathematical Physics and Stochastics, funded by The Danish National Research Foundation.As a student of the PhD-school OP-ALG-TOP-GEO the author is partially supported by the Danish Research Training Council.Acknowledgement I would like to thank my advisor, Uffe Haagerup, with whom I had many enlightening discussions, and who made some important contributions to this paper. Also, thanks to Steen Thorbjørnsen who took time to answer several questions.     

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     

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     

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     

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     

The feasibility pump

In this paper we consider the NP-hard problem of finding a feasible solution (if any exists) for a generic MIP problem of the form min{c^Tx:Ax≥b,x_j integer ∀j ∈ }. Trivially, a feasible solution can be defined as a point x* ∈ P:={x:Ax≥b} that is equal to its rounding , where the rounded point is defined by := x*_j if j ∈ and := x*_j otherwise, and [·] represents scalar rounding to the nearest integer. Replacing “equal” with “as close as possible” relative to a suitable distance function Δ(x*, ), suggests the following Feasibility Pump (FP) heuristic for finding a feasible solution of a given MIP.We start from any x* ∈ P, and define its rounding . At each FP iteration we look for a point x* ∈ P that is as close as possible to the current by solving the problem min {Δ(x, ): x ∈ P}. Assuming Δ(x, ) is chosen appropriately, this is an easily solvable LP problem. If Δ(x*, )=0, then x* is a feasible MIP solution and we are done. Otherwise, we replace by the rounding of x*, and repeat.We report computational results on a set of 83 difficult 0-1 MIPs, using the commercial software ILOG-Cplex 8.1 as a benchmark. The outcome is that FP, in spite of its simple foundation, proves competitive with ILOG-Cplex both in terms of speed and quality of the first solution delivered. Interestingly, ILOG-Cplex could not find any feasible solution at the root node for 19 problems in our test-bed, whereas FP was unsuccessful in just 3 cases.     

Topologically transitive extensions of bounded operators

Let X be any Banach space and T a bounded operator on X. An extension of the pair (X,T) consists of a Banach space in which X embeds isometrically through an isometry i and a bounded operator on such that When X is separable, it is additionally required that be separable. We say that is a topologically transitive extension of (X, T) when is topologically transitive on , i.e. for every pair of non-empty open subsets of there exists an integer n such that is non-empty. We show that any such pair (X,T) admits a topologically transitive extension , and that when H is a Hilbert space, (H,T) admits a topologically transitive extension where is also a Hilbert space. We show that these extensions are indeed chaotic.Mathematics Subject Classification (2000): 47 A 16     

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.     

Simplicial complexes lying equivariantly over the affine building of GL(<Emphasis Type="Italic">N</Emphasis>)

Let G=GL(N,K), K a non-archimedean local field and X be the semisimple affine building of G over K. We construct a projective tower of G-sets with X(0)=X. They are obtained by using a minor modification in Bruhat and Tits original construction (an idea due to P. Schneider). Using the structure of X as an abstract building, we construct a projective tower of simplicial G-complexes such that, for each r, X_(r) is canonically a geometrical realization of X_r. In the case N=2, X_r has a natural two-sheeted covering _r and we show that the supercuspidal part of the cohomology space is characterized by a nice property.Mathematics Subject Classification (2000): 14R25, 20E42, 20G25, 55U10, 57S25     

Notes on subtlety and ineffability in P κ λ

A type of subtlety for P_κλ called “strongly subtle” is introduced to show almost ineffability is consistencywise stronger than Shelah property. The following are also shown: is strongly subtle” has rather strong consequences. (ii) The ideal is not strongly subtle} is not λ-saturated , and completely ineffable ideal is not precipitous. (iii) In case that λ^<κ=2^λ, almost λ-ineffability coincides with λ-ineffability. (iv) It is not provable that κ is λ^<κ-ineffable whenever κ is λ-ineffable.Research partially supported by “Grant-in-Aid for Scientific research (C), The Ministry of Education, Science, Sports and Culture of Japan 09640299”, and “Japan Society for the Promotion of Science 14540142”.The author is very grateful to the referee for his correcting many errors and helpful suggestions.     

-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     

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.     

Diophantine inequalities involving several power sums

Let denote the ring of power sums, i.e. complex functions of the form for some and _iA, where is a multiplicative semigroup. Moreover, let We consider Diophantine inequalities of the form where >1 is a quantity depending on the dominant roots of the power sums appearing as coefficients in F(n,y), and show that all its solutions have y parametrized by some power sums from a finite set. This is a continuation of the work of Corvaja and Zannier [4–6] and of the authors [10, 18] on such problems.Mathematics Subject Classification (2000):11D45,11D61Revised version: 6 May 2004     

Square functions and <Emphasis Type="Italic">H</Emphasis><Superscript>∞</Superscript> calculus on subspaces of <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> and on Hardy spaces

Let X be a (closed) subspace of L^p with 1≤p<∞, and let A be any sectorial operator on X. We consider associated square functions on X, of the form and we show that if A admits a bounded H^∞ functional calculus on X, then these square functions are equivalent to the original norm of X. Then we deduce a similar result when X=H¹(ℝ^N) is the usual Hardy space, for an appropriate choice of || ||_F. For example if N=1, the right choice is the sum for h ∈ H¹(ℝ), where H denotes the Hilbert transform.