On the coupon collector's remainder term

Summary Each element in a finite population is assigned a bonus value, i.e. a real number. Elements are selected from by simple random sampling with replacement and with equal draw probabilities. Each time we receive a new element, i.e. an element which has not been previously selected, we receive the corresponding bonus. Let W _n denote the bonus sum after n selections. It is well known that W _n is approximately normally distributed under mild conditions. We give a remainder term estimate of the Berry-Esseen type for this normal distribution approximation.     

On the Influence of Weights on Extremes

Let X ₁, ..., X_n be an i.i.d. sequence of random variables, from an unknown distribution F, and X ₁ ^W , ... X _n ^W be a sample from , the weighted empirical distribution function of X ₁, ..., X_n. We define the order statistics X _1,n ^W ... X _n,n ^W of X ₁ ^W , ..., X _n ^W . Under suitable assumptions on weights, we study the influence of the maxima in the construction of limit theorems. We choose a resample size m(n) and we derive conditions on m(n) for the in probability and with probability 1 consistency of X _m(n),m(n) ^W . The presence of weights has an influence on the resample size and requires the use of new tools. When X _n,n is in the domain of attraction of an extreme value distribution, m(n) , and , as n , all our results hold.     

Sturmian Words and the Permutation that Orders Fractional Parts

A Sturmian word is a map W : {0,1} for which the set of {0, 1}-vectors F _n(W) {(W(i), W(i + 1),...,W(i + n – 1)) ^T : i } has cardinality exactly n + 1 for each positive integer n. Our main result is that the volume of the simplex whose n + 1 vertices are the n + 1 points in F _n(W) does not depend on W. Our proof of this motivates studying algebraic properties of the permutation _,n (where is any irrational and n is any positive integer) that orders the fractional parts {}, {2},...,{n}, i.e., 0 < {_,n (1)} < {_,n (2)} < ··· < {_,n (n)} < 1. We give a formula for the sign of _,n , and prove that for every irrational there are infinitely many n such that the order of _,n (as an element of the symmetric group S _n) is less than n.     

Weak invariance principles for weightedU-statistics

We prove that the distribution of a properly normalized weightedU-statisticU _n in i.i.d. random variables is close to the distribution of a certain functionV _n in i.i.d. standardized Gaussian random variables in the sense that their Lévy-Prokhorov distance tends to zero asn. This property is then used to determine the limit laws ofU _n under special assumptions on the kernel function. This generalizes a method due to Rotar' who proved similar results for random multilinear forms.     

Limit Theorems for Multiplicative Processes

Let W be a non-negative random variable with EW=1, and let {W _i } be a family of independent copies of W, indexed by all the finite sequences i=i ₁i _n of positive integers. For fixed r and n the random multiplicative measure ⁿ _r has, on each r-adic interval at nth level, the density with respect to the Lebesgue measure on [0,1]. If EW log Wr, the sequence { ⁿ _r } _n converges a.s. weakly to the Mandelbrot measure _r . For each fixed 1n, we study asymptotic properties for the sequence of random measures { ⁿ _r } _r as r. We prove uniform laws of large numbers, functional central limit theorems, a functional law of iterated logarithm, and large deviation principles. The function-indexed processes is a natural extension to a tree-indexed process at nth level of the usual smoothed partial-sum process corresponding to n=1. The results extend the classical ones for { ¹ _r } _r , and the recent ones for the masses of { _r } _r established in Ref. 23.     

On the Number of Appearances of a Word in a Sequence of I.I.D. Trials

Let X ₁,...,X _n be a sequence of i.i.d. random variables taking values in an alphabet =₁,...,_q,q 2, with probabilities P(X _a=_i)=p _i,a=1,...,n,i=1,...,q. We consider a fixed h-letter word W=w₁...w_h which is produced under the above scheme. We define by R(W) the number of appearances of W as Renewal (which is equal with the maximum number of non-overlapping appearances) and by N(W) the number of total appearances of W (overlapping ones) in the sequence X _{a 1} a1n under the i.i.d. hypothesis. We derive a bound on the total variation distance between the distribution (R(W)) of the r.v. R(W) and that of a Poisson with parameter E(R(W)). We use the Stein-Chen method and related results from Barbour et al. (1992), as well as, combinatorial results from Schbath (1995b) concerning the periodic structure of the word W. Analogous results are obtained for the total variation distance between the distribution of the r.v. N(W) and that of an appropriate Compound Poisson r.v. Related limit theorems are obtained and via numerical computations our bounds are presented in tables.     

Separation of hypersurfaces

We give a generalization of results obtained in [15]. LetK ⁿ denote the set of embedded hypersurfaces in ⁿ⁺¹; for all xSⁿ and MK ⁿ we denote by C _x ^M the apparent contour ofM in the directionx. Then we give a sufficient condition on WSⁿ such that the map _W ^{K n}:K ⁿ P(T Sⁿ) , defined by _W ^{K n} (M)={C _w ^M ¦ wW}, is injective.     

Explicit stationary distributions for compositions of random functions and products of random matrices

If (Y _n) _n ^=1/ is a sequence of i.i.d. random variables onE=(0,+) and iff is positive onE, this paper studies explicit examples of stationary distributions for the Markov chain (W _n) _n=0 defined byW _n=Y _nf(W _n-1). The case wheref is a Moebius function(ax+b)/(cx+d) leads to products of certain random (2,2) matrices and to interesting random continued fractions. These explicit examples are built with a naive idea by considering genral exponential families onE, especially the families of beta distributions of the first and second kind.     

Asymptotic Distribution of Extremes of Randomly Indexed Random Variables

Let {X _n} be a sequence of i.i.d. random variables and let {_k} be a sequence of random indexes. We study the problem of the existence of non-degenerated asymptotic distribution for min{X ₁,..., X _n}.     

Spitzer's Strong Law of Large Numbers in Nonseparable Banach Spaces

It is well known, that for the sums of i.i.d. random variables we have S _n/n 0 a.s. iff _n=1 1/n P(|S _n| > n) < holds for all > 0 (Spitzer's SLLN). The result is also known in separable Banach spaces. It will be shown, that this also holds in nonseparable (= not necessarily separable) Banach spaces without any measurability assumption. In the theory of empirical processes this gives a characterization of Glivenko-Cantelli classes.     

Remarks on a theorem of Burkholder and Gundy

Let (Y _n) be a sequence of i.i.d. random variables with zero mean such thatP(Y ₁0)>0. Consider the random walkS _n=Y₁+...+Y_n and an a.s. finite stopping time with respect to the -fieldsF _n=(Y₁,..., Y_n). In this paper we present a number of remarks on a theorem of Burkholder and Gundy concerning an estimate involvingE(sup _n1|Svn|^p).Dedicated to the memory of Professor József Mogyoródi.     

On the asymptotic behaviour of first passage times for transient random walk

Summary Let _x denote the time at which a random walk with finite positive mean first passes into (x, ), wherex0. This paper establishes the asymptotic behaviour of Pr { _x >n} asn for fixedx in two cases. In the first case the left hand tail of the step-distribution is regularly varying, and in the second the step-distribution satisfies a one-sided Cramér type condition. As a corollary, it follows that in the first case Pr { _x >n}/Pr{ ₀ >n} coincides with the limit of the same quantity for recurrent random walk satisfying Spitzer's condition, but in the second case the limit is more complicated.     

Asymptotic behavior of the dwell time distribution for a random walk on a positive semi-axis

Let ₁, ₂, ... be a sequence of independent identically distributed random variables with zero means. We consider the functional _n = _k=o ⁿ (S _k ) where S₁=0, S_k= _i=1 ^k _i (k1) and(x)=1 for x0,(x) = 0 for x<0. It is readily seen that _n is the time spent by the random walk S_n, n0, on the positive semi-axis after n steps. For the simplest walk the asymptotics of the distribution P (_n = k) for n and k, as well as for k = O(n) and k/n<1, was studied in [1]. In this paper we obtain the asymptotic expansions in powers of n^–1 of the probabilities P(h_n = nx) and P(nx_{1 n} nx₂) for 0<₁, x = k/n ₂<1, 0<₁x₁2₂<1.Translated from Matematicheskie Zametki, Vol. 15, No. 4, pp. 613–620, April, 1974.The author wishes to thank B. A. Rogozin for valuable discussions in the course of his work.     

Strong Laws for Martingale Differences and Independent Random Variables

A strong law of large numbers (SLLN) for martingale differences {X _n,_n,n1} permitting constant, random or hybrid normalizations, is obtained via a related SLLN for their conditional variances E{X _n ² |_n-1}n1. This, in turn, leads to martingale generalizations of known results for sums of independent random variables. Moreover, in the independent case, simple conditions are given for a generalized SLLN which contains the classical result of Kolmogorov when the variables are i.i.d.     

An explicit calculation of the mean of the perimeter of the convex hull of a plane random walk

If (X _n ) _n ⁼¹ is a sequence of i.i.d. random variables in the Euclidean plane such that we compute the mean of the perimeter of theconvex hull ofX ₁++X _k; 0kn}.     

On Piecewise-Constant Approximation of Continuous Functions of n Variables in Integral Metrics

We consider the approximation by piecewise-constant functions for classes of functions of many variables defined by moduli of continuity of the form (₁, ..., _n ) = ₁(₁) + ... + _n ( _n ), where _i ( _i ) are ordinary moduli of continuity that depend on one variable. In the case where _i ( _i ) are convex upward, we obtain exact error estimates in the following cases: (i) in the integral metric L ₂ for (₁, ..., _n ) = ₁(₁) + ... + _n ( _n ); (ii) in the integral metric L _p (p 1) for (₁, ..., _n ) = c ₁₁ + ... + c _{n n} ; (iii) in the integral metric L _{(2, ..., 2, 2r)} (r = 2, 3, ...) for (₁, ..., _n ) = ₁(₁) + ... + _{n – 1}( _{n – 1}) + c _{n n} .     

Future independent times and Markov chains

Summary A random timeT is a future independent time for a Markov chain (X _n ) ₀ ifT is independent of (X _T+n ) _n ^/ =0 and if (X _T+n ) _n ^/ =0 is a Markov chain with initial distribution and the same transition probabilities as (X _n ) ₀ . This concept is used (with the conditional stationary measure) to give a new and short proof of the basic limit theorem of Markov chains, improving somewhat the result in the null-recurrent case.This work was supported by the Swedish Natural Science Research Council and done while the author was visiting the Department of Statistics, Stanford University     

The law of the iterated logarithm for subsequences and characterization of the cluster set ofS n k/(2n k log logn k)1/2 in Banach spaces

LetS _n=X ₁+...+X _n, where {X _n;n=1, 2,...} is a sequence of i.i.d. random vectors with values in a Banach space and let be any infinite set of positive integers. In this paper we obtain the bounded and the compact laws of the iterated logarithm for {S _n;n}. We characterize the cluster set of {S _n/(2n log logn)^1/2;n}, for random vectors with mean zero, weak second moment, and satisfying certain additional conditions. Special situations, like type 2 Banach spaces and the real-valued case are also considered.     

Factorization,basic notions and applications

The idea to define an equivalence relation on the basic spaceW in terms of sample paths of some random processX _t (w) coinciding up to timet is the basis of the important concept of saturated filtration. Here we exploit the same idea to represent spaceW in the formW=W ×W, whereW is the space of all equivalence classes with respect to the above relation corresponding to a stopping time andW is an image ofW under some shifting operator. This representation allows us to work with spaceW ×W rather thanW and to investigate more precisely the properties of some random objects given onW.     

How large delays build up in a GI/G/1 queue

LetW _k denote the waiting time of customerk, k 0, in an initially empty GI/G/1 queue. Fixa> 0. We prove weak limit theorems describing the behaviour ofW _k /n, 0kn, given W_n >na. LetX have the distribution of the difference between the service and interarrival distributions. We consider queues for which Cramer type conditions hold forX, and queues for whichX has regularly varying positive tail.The results can also be interpreted as conditional limit theorems, conditional on large maxima in the partial sums of random walks with negative drift.Research supported by the NSF under Grant NCR 8710840 and under the PYI Award NCR 8857731.