On the almost sure central limit theorem for randomly indexed sums

Let {S_n, n ≥ 1} be partial sums of independent identically distributed random variables. The almost sure version of CLT is generalized on the case of randomly indexed sums {S_Nn, n ≥ 1}, where {N_n, n ≥ 1} is a sequence of positive integer‐valued random variables independent of {S_n, n ≥ 1}. The affects of nonrandom centering and norming are considered too (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Matrix Measures, Random Moments, and Gaussian Ensembles

We consider the moment space M_n\mathcal{M}_{n} corresponding to p×p real or complex matrix measures defined on the interval [0,1]. The asymptotic properties of the first k components of a uniformly distributed vector (S_1,n, ... , S_n,n)^* ~ U (M_n)(S_{1,n}, \dots , S_{n,n})^{*} \sim\mathcal{U} (\mathcal{M}_{n}) are studied as n→∞. In particular, it is shown that an appropriately centered and standardized version of the vector (S _1,n ,…,S _k,n )^∗ converges weakly to a vector of k independent p×p Gaussian ensembles. For the proof of our results, we use some new relations between ordinary moments and canonical moments of matrix measures which are of their own interest. In particular, it is shown that the first k canonical moments corresponding to the uniform distribution on the real or complex moment space M_n\mathcal{M}_{n} are independent multivariate Beta-distributed random variables and that each of these random variables converges in distribution (as the parameters converge to infinity) to the Gaussian orthogonal ensemble or to the Gaussian unitary ensemble, respectively.     

The Weak Convergence for Functions of Negatively Associated Random Variables

Let {X_n, n1} be a sequence of stationary negatively associated random variables, S_j(l)=∑^l_i=1 X_j+i, S_n=∑ⁿ_i=1 X_i. Suppose that f(x) is a real function. Under some suitable conditions, the central limit theorem and the weak convergence for sums are investigated. Applications to limiting distributions of estimators of Var S_n are also discussed.     

On the Distribution of the Sum of n Non-Identically Distributed Uniform Random Variables

The distribution of the sum of independent identically distributed uniform random variables is well-known. However, it is sometimes necessary to analyze data which have been drawn from different uniform distributions. By inverting the characteristic function, we derive explicit formulae for the distribution of the sum of n non-identically distributed uniform random variables in both the continuous and the discrete case. The results, though involved, have a certain elegance. As examples, we derive from our general formulae some special cases which have appeared in the literature.     

Coherent random allocations, and the Ewens-Pitman formula

Assume that there is a random number K of positive integer random variables S₁, …, S_K that are conditionally independent given K and all have identical distributions. A random integer partition N = S₁ + S₂ + … + S_K arises, and we denote by P_N the conditional distribution of this partition for a fixed value of N. We prove that the distributions {P_N} _N=1 ^∞ form a partition structure in the sense of Kingman if and only if they are governed by the Ewens-Pitman Formula. The latter generalizes the celebrated Ewens sampling formula, which has numerous applications in pure and applied mathematics. The distributions of the random variables K and S_j belong to a family of integer distributions with two real parameters, which we call quasi-binomial. Hence every Ewens-Pitman distribution arises as a result of a two-stage random procedure based on this simple class of integer distributions. Bibliography: 25 titles. This paper is an edited and actualized version of the unpublished PDMI preprint 21/1995. Further development of the ideas of this work can be found in [21, 25]. A number of detected misprints was fixed without notice, the bibliography was extended beyond the original 19 references, and a few comments were added as footnotes. (Comments by Alexander Gnedin.) __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 325, 2005, pp. 127–145.     

Berry–Esseen Bound for a Sample Sum from a Finite Set of Independent Random Variables

Let {X ₁,...,X _N} be a set of N independent random variables, and let S _n be a sum of n random variables chosen without replacement from the set {X ₁,...,X _N} with equal probabilities. In this paper we give an estimate of the remainder term for the normal approximation of S _n under mild conditions.     

Large deviations for functionals of stationary processes

Summary Let (S _n ) be a sequence ofR ^d -valued random variables adapted to the internal history of a stationary sequence of random elements (X _n ). We formulate conditions under which the principle of large deviations holds true for the sequence (S _n ).     

Long and short paths in uniform random recursive dags

In a uniform random recursive k-directed acyclic graph, there is a root, 0, and each node in turn, from 1 to n, chooses k uniform random parents from among the nodes of smaller index. If S _n is the shortest path distance from node n to the root, then we determine the constant σ such that S _n /log n→σ in probability as n→∞. We also show that max _1≤i≤n S _i /log n→σ in probability.     

Random walks generated by area preserving maps with zero Lyapounov exponents

We study the asymptotic limit distributions of Birkhoff sums S_n of a sequence of random variables of dynamical systems with zero entropy and Lebesgue spectrum type. A dynamical system of this family is a skew product over a translation by an angle α. The sequence has long memory effects. It comes that when α/π is irrational the asymptotic behavior of the moments of the normalized sums S_n/f_n depends on the properties of the continuous fraction expansion of α. In particular, the moments of order k, , are finite and bounded with respect to n when α/π has bounded continuous fraction expansion. The consequences of these properties on the validity or not of the central limit theorem are discussed.     

On the Rate of Decay of the Concentration Function of the Sum of Independent Random Variables

Let X₁, ... , X_n be i.i.d. integral valued random variables and S_n their sum. In the case when X₁ has a moderately large tail of distribution, Deshouillers, Freiman and Yudin gave a uniform upper bound for max _{k ∊ ℤ} Pr{S_n = k} (which can be expressed in term of the Lévy Doeblin concentration of S_n), under the extra condition that X₁ is not essentially supported by an arithmetic progression. The first aim of the paper is to show that this extra condition cannot be simply ruled out. Secondly, it is shown that if X₁ has a very large tail (larger than a Cauchy-type distribution), then the extra arithmetic condition is not sufficient to guarantee a uniform upper bound for the decay of the concentration of the sum S_n. Proofs are constructive and enhance the connection between additive number theory and probability theory.À Jean-Louis Nicolas, avec amitié et respect2000 Mathematics Subject Classification: Primary—60Fxx, 60Exx, 11Pxx, 11B25     

A Review of White Noise Analysis from a Probabilistic Standpoint

The main notions and tools from white noise analysis are set up on the basis of the calculus of Gaussian random variables and the S -transform. A new proof of the formula for the S -transform of Itô integrals is given. Moreover, measurability and the martingale property with respect to the Brownian filtration are characterized in terms of the S-transform. This allows the extension of these notions to random variables and processes, respectively, in the space of Hida distributions.     

The Arcsine Law

Let N _n denote the number of positive sums in the first n trials in a random walk (S _i) and let L _n denote the first time we obtain the maximum in S ₀,..., S _n. Then the classical equivalence principle states that N _n and L _n have the same distribution and the classical arcsine law gives necessary and sufficient condition for (1/n) L _n or (1/n) N _n to converge in law to the arcsine distribution. The objective of this note is to provide a simple and elementary proof of the arcsine law for a general class of integer valued random variables (T _n) and to provide a simple an elementary proof of the equivalence principle for a general class of integer valued random vectors (N _n, L _n).     

The problem of identification of parameters by the distribution of the maximum random variable

Suppose that X₁, X₂,…, X_n are independently distributed according to certain distributions. Does the distribution of the maximum of {X₁, X₂,…, X_n} uniquely determine their distributions? In the univariate case, a general theorem covering the case of Cauchy random variables is given here. Also given is an affirmative answer to the above question for general bivariate normal random variables with non-zero correlations. Bivariate normal random variables with nonnegative correlations were considered earlier in this context by T. W. Anderson and S. G. Ghurye.     

A limit theorem for the moments of sums of independent random variables

Forn≧1, letS _n=ΣX _n,i (1≦i≦r _n <∞), where the summands ofS _n are independent random variables having medians bounded in absolute value by a finite number which is independent ofn. Letf be a nonnegative function on (− ∞, ∞) which vanishes and is continuous at the origin, and which satisfies, for some for allt≧1 and all values ofx. Theorem.For centering constants c _n,let S _n − c _n converge in distribution to a random variable S. (A)In order that Ef(S_n − c_n) converge to a limit L, it is necessary and sufficient that there exist a common limit (B)If L exists, then L<∞ if and only if R<∞, and when L is finite, L=Ef(S)+R. Applications are given to infinite series of independent random variables, and to normed sums of independent, identically distributed random variables.     

Characterizing and Generating Bivariate Empirical Rank Distributions Satisfying Certain Positive Dependence Concepts

Abstract

This article introduces an approach for characterizing the classes of empirical distributions that satisfy certain positive dependence notions. Mathematically, this can be expressed as studying certain subsets of the class S_N of permutations of 1, …, N, where each subset corresponds to some positive dependence notions. Explicit techniques for it-eratively characterizing subsets of S_N that satisfy certain positive dependence concepts are obtained and various counting formulas are given. Based on these techniques, graph-theoretic methods are used to introduce new and more efficient algorithms for constructively generating and enumerating the elements of various of these subsets of S_N. For example, the class of positively quadrant dependent permutations in S_N is characterized in this fashion.     

Improved boolean formulas for the Ramsey graphs

In the theory of the random graphs, there are properties of graphs such that almost all graphs satisfy the property, but there is no effective way to find examples of such graphs. By the well-known results of Razborov, for some of these properties, e.g., some Ramsey property, there are Boolean formulas in ACC representing the graphs satisfying the property and having exponential number of vertices with respect to the number of variables of the formula. Razborov's proof is based on a probabilistic distribution on formulas of n variables of size approximately nd² log d, where d is a polynomial in n, and depth 3 in the basis { ∧, ⊕} with the following property: The restriction of the formula randomly chosen from the distribution to any subset A of the Boolean cube {0, 1}ⁿ of size at most d has almost uniform distribution on the functions A → {0, 1}. We show a modified probabilistic distribution on Boolean formulas which is defined on formulas of size at most nd log² d and has the same property of the restrictions to sets of size at most d as the original one. This allows us to obtain formulas the complexity of which is a polynomial of a smaller degree in n than in Razborov's paper while the represented graphs satisfy the same properties.     

Lower-Bound Estimates for Poisson-Type Approximations

Let S = w ₁ S ₁ + w ₂ S ₂ + ⋯ + w _N S _N . Here S _j is a sum of identically distributed random variables with weight w _j > 0. We consider the cases where S _j is a sum of independent random variables, the sum of independent lattice variables, or has the Markov binomial distribution. Apart from the general case, we investigate the case of symmetric random variables. Distribution of S is approximated by a compound Poisson distribution, by a second-order asymptotic expansion, and by a signed exponential measure. Lower bounds for the accuracy of approximations in uniform metric are established. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 45, No. 4, pp. 501–524, October–December, 2005.     

Spectral theory of minimax estimation

The set ofS ₁-estimates of solutions of systems of linear equations with random parameters is found. It is proved that the maximal eigenvalue in the goodness criterion is not simple. For the purpose of finding estimates from theS ₁ set, the perturbation formulas for eigenvalues and formulas for distribution density of random matrices are used.     

The birth of the giant component

Limiting distributions are derived for the sparse connected components that are present when a random graph on n vertices has approximately 1/2n edges. In particular, we show that such a graph consists entirely of trees, unicyclic components, and bicyclic components with probability approaching √2/3 cosh √5/18 ≈ 0.9325 as n→∞. The limiting probability that it is consists of trees, unicyclic components, and at most one another component is approximately 0.9957; the limiting probability that it is planar lies between 0.987 and 0.9998. When a random graph evolves and the number of edges passes 1/2n, its components grow in cyclic complexity according to an interesting Markov process whose asymptotic structure is derived. The probability that there never is more than a single component with more edges than vertices, throughout the veolution, approaches 5 π/18 ≈ 0.8727. A “uniform” model of random graphs, which allows self-loops and multiple edges, is shown to lead to formulas that are substanitially simpler than the analogous formulas for the classical random graphs of Erdõs and Rényi. The notions of “excess” and “deficiency,” which are significant characteristics of the generating function as well as of the graphs themselves, lead to a mathematically attractive structural theory for the uniform model. A general approach to the study of stopping configurations makes it possible to sharpen previously obtained estimates in a uniform manner and often to obtain closed forms for the constants of interest. Empirical results are presented to complement the analysis, indicating the typical behavior when n is near 2oooO. © 1993 John Wiley & Sons, Inc.