On the area and perimeter of a random convex hull in a bounded convex set

Suppose K is a compact convex set in ℝ² and X _i , 1≤i≤n, is a random sample of points in the interior of K. Under general assumptions on K and the distribution of the X _i we study the asymptotic properties of certain statistics of the convex hull of the sample. Received: 24 July 1996/Revised version: 24 February 1998     

Two-point concentration in random geometric graphs

A random geometric graph G _n is constructed by taking vertices X ₁,…,X _n ∈ℝ ^d at random (i.i.d. according to some probability distribution ν with a bounded density function) and including an edge between X _i and X _j if ‖X _i -X _j ‖ < r where r = r(n) > 0. We prove a conjecture of Penrose ([14]) stating that when r=r(n) is chosen such that nr ^d = o(lnn) then the probability distribution of the clique number ω(G _n ) becomes concentrated on two consecutive integers and we show that the same holds for a number of other graph parameters including the chromatic number χ(G _n ). The author was partially supported by EPSRC, the Department of Statistics, Bekkerla-Bastide fonds, Dr. Hendrik Muller’s Vaderlandsch fonds, and Prins Bernhard Cultuurfonds.     

Total Variation Distance for Poisson Subset Numbers

Let n be an integer and A₀,..., A_k random subsets of {1,..., n} of fixed sizes a₀,..., a_k, respectively chosen independently and uniformly. We provide an explicit and easily computable total variation bound between the distance from the random variable , the size of the intersection of the random sets, to a Poisson random variable Z with intensity λ = EW. In particular, the bound tends to zero when λ converges and for all j = 0,..., k, showing that W has an asymptotic Poisson distribution in this regime. Received February 24, 2005     

Limiting distribution of sums of nonnegative stationary random variables

Summary Let {X _n,j,−∞<j<∞∼,n≧1, be a sequence of stationary sequences on some probability space, with nonnegative random variables. Under appropriate mixing conditions, it is shown thatS _n=X_n,1+…+X _n,n has a limiting distribution of a general infinitely divisible form. The result is applied to sequences of functions {f _n(x)∼ defined on a stationary sequence {X _j∼, whereX _n.f=f_n(X_j). The results are illustrated by applications to Gaussian processes, Markov processes and some autoregressive processes of a general type. This paper represents results obtained at the Courant Institute of Mathematical Sciences, New York University, under the sponsorship of the National Sciences Foundation, Grant MCS 82-01119.     

On a problem of spencer

LetX ₁, ...,X _n be events in a probability space. Let ϱ_i be the probabilityX _i occurs. Let ϱ be the probability that none of theX _i occur. LetG be a graph on [n] so that for 1 ≦i≦n X _i is independent of ≈X _j ‖(i, j)∉G≈. Letf(d) be the sup of thosex such that if ϱ₁, ..., ϱ _n ≦x andG has maximum degree ≦d then ϱ>0. We showf(1)=1/2,f(d)=(d−1) ^d−1 d ^−d ford≧2. Hence df(d)=1/e. This answers a question posed by Spencer in [2]. We also find a sharp bound for ϱ in terms of the ϱ _i andG.     

Bounds on the convex label number of trees

A convex labelling of a tree is an assignment of distinct non-negative integer labels to vertices such that wheneverx, y andz are the labels of vertices on a path of length 2 theny≦(x+z)/2. In addition if the tree is rooted, a convex labelling must assign 0 to the root. The convex label number of a treeT is the smallest integerm such thatT has a convex labelling with no label greater thanm. We prove that every rooted tree (and hence every tree) withn vertices has convex label number less than 4n. We also exhibitn-vertex trees with convex label number 4n/3+o(n), andn-vertex rooted trees with convex label number 2n +o(n). The research by M. B. and A. W. was partly supported by NSF grant MCS—8311422.     

The Optimal Order for the p-th Moment of Sums of Independent Random Variables with Respect to Symmetric Norms and Related Combinatorial Estimates

For n independent random variables f₁, . . . ,f_n and a symmetric norm || ||_X on ℝⁿ, we show that for 1≤ p < ∞ Here is the disjoint sum of the f_i's and h* is the non-increasing rearrangement. Similar results (where L_p is replaced by a more general rearrangement invariant function space) were obtained first by Litvak, Gordon, Schütt and Werner for Orlicz spaces X and independently by S. Montgomery-Smith [22] for general X but without an explicit analysis of the order of growth for the constant in the upper estimate. The order is optimal and obtained from combinatorial estimates for doubly stochastic matrices. The result extends to Lorentz-norms l_{f, q} on ℝⁿ under mild assumptions on f. We give applications to the theory of noncommutative L_p spaces.     

On samples of independent random vectors in spaces of infinitely increasing dimension

We study the asymptotic behavior of a set of random vectors ξ_i, i = 1,..., m, whose coordinates are independent and identically distributed in a space of infinitely increasing dimension. We investigate the asymptotics of the distribution of the random vectors, the consistency of the sets M _m⁽ⁿ⁾ = ξ₁,..., ξ_m and X _n^λ = x ∈ X _n: ρ(x) ≤ λn, and the mutual location of pairs of vectors. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 12, pp. 1706–1711, December, 1998.     

Order of magnitude bounds for expectations of Δ2-functions of generalized random bilinear forms

Let Φ be a symmetric function, nondecreasing on [0,∞) and satisfying a Δ₂ growth condition, (X ₁,Y ₁), (X ₂,Y ₂),…,(X _n ,Y _n ) be arbitrary independent random vectors such that for any given i either Y _i =X _i or Y _i is independent of all the other variates. The purpose of this paper is to develop an approximation of

Mader’s Conjecture On Extremely Critical Graphs

A non-complete graph G is called an (n,k)-graph if it is n-connected but G—X is not (n−|X|+1)-connected for any X ⊂V (G) with |X|≤k. Mader conjectured that for k≥3 the graph K_2k+2−(1−factor) is the unique (2k,k)-graph(up to isomorphism). Here we prove this conjecture.     

Exact laws for sums of ratios of order statistics from the Pareto distribution

Consider independent and identically distributed random variables {X _nk, 1 ≤ k ≤ m, n ≤ 1} from the Pareto distribution. We select two order statistics from each row, X _n(i) ≤ X _n(j), for 1 ≤ i < j ≤ = m. Then we test to see whether or not Laws of Large Numbers with nonzero limits exist for weighted sums of the random variables R _ij = X _n(j)/X _n(i).     

Growth and Hölder conditions for the sample paths of Feller processes

Let (A,D(A)) be the infinitesimal generator of a Feller semigroup such that C _c ^∞(ℝ ⁿ )⊂D(A) and A|C _c ^∞(ℝ ⁿ ) is a pseudo-differential operator with symbol −p(x,ξ) satisfying |p(•,ξ)|_∞≤c(1+|ξ|²) and |Imp(x,ξ)|≤c ₀Rep(x,ξ). We show that the associated Feller process {X _t } _{t ≥0} on ℝ ⁿ is a semimartingale, even a homogeneous diffusion with jumps (in the sense of [21]), and characterize the limiting behaviour of its trajectories as t→0 and ∞. To this end, we introduce various indices, e.g., β_∞ ^x :={λ>0:lim _{|ξ|→∞ | x − y |≤2/|ξ|}|p(y,ξ)|/|ξ|^λ=0} or δ_∞ ^x :={λ>0:liminf _{|ξ|→∞ | x − y |≤2/|ξ| |ε|≤1}|p(y,|ξ|ε)|/|ξ|^λ=0}, and obtain a.s. (ℙ ^x ) that lim _{t →0} t ^−1/λ _{s ≤ t} |X _s −x|=0 or ∞ according to λ>β_∞ ^x or λ<δ_∞ ^x . Similar statements hold for the limit inferior and superior, and also for t→∞. Our results extend the constant-coefficient (i.e., Lévy) case considered by W. Pruitt [27]. Received: 21 July 1997 / Revised version: 26 January 1998     

Inequalities for sums of independent geometrical random variables

Summary We give a survey of known results regarding Schur-convexity of probability distribution functions. Then we prove that the functionF(p ₁,...,p_n;t)=P(X₁+...+X_n≤t) is Schur-concave with respect to (p ₁,...,p_n) for every realt, whereX _i are independent geometric random variables with parametersp _i. A generalization to negative binomial random variables is also presented.     

Complete convergence for arrays

Let {(X _nk , 1≤k≤n),n≥1}, be an array of rowwise independent random variables. We extend and generalize some recent results due to Hu, Móricz and Taylor concerning complete convergence, in the sense of Hsu and Robbins, of the sequence of rowwise arithmetic means.     

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.     

Limit theorems for a recursive maximum process with location-dependent periodic intensity-parameter

We investigate the recursive sequence Z _n : =  max {Z _n − 1,λ(Z _n − 1)X _n } where X _n is a sequence of iid random variables with exponential distributions and λ is a periodic positive bounded measurable function. We prove that the Césaro mean of the sequence λ(Z _n ) converges toward the essential minimum of λ. Subsequently we apply this result and obtain a limit theorem for the distributions of the sequence Z _n . The resulting limit is a Gumbel distribution.     

Embedding nearly-spanning bounded degree trees

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1 − ε)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d ≥ 2 and 0 < ε < 1, there exists a constant c = c(d, ε) such that a random graph G(n, c/n) contains almost surely a copy of every tree T on (1 − ε)n vertices with maximum degree at most d. We also prove that if an (n, D, λ)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most λ in their absolute values) has large enough spectral gap D/λ as a function of d and ε, then G has a copy of every tree T as above. Research supported in part by a USA-Israeli BSF grant, by NSF grant CCR-0324906, by a Wolfensohn fund and by the State of New Jersey. Research supported in part by USA-Israel BSF Grant 2002-133, and by grants 64/01 and 526/05 from the Israel Science Foundation. Research supported in part by NSF CAREER award DMS-0546523, NSF grant DMS-0355497, USA-Israeli BSF grant, and by an Alfred P. Sloan fellowship.     

Penultimate limiting forms in extreme value theory

Summary Let {X _n}_n≧1 be a sequence of independent, identically distributed random variables. If the distribution function (d.f.) ofM _n=max (X ₁,…,X _n), suitably normalized with attraction coefficients {α_n}_n≧1(α_n>0) and {b _n}_n≧1, converges to a non-degenerate d.f.G(x), asn→∞, it is of interest to study the rate of convergence to that limit law and if the convergence is slow, to find other d.f.'s which better approximate the d.f. of(M _n−b_n)/a_n thanG(x), for moderaten. We thus consider differences of the formF ⁿ(a_nx+b_n)−G(x), whereG(x) is a type I d.f. of largest values, i.e.,G(x)≡Λ(x)=exp (-exp(−x)), and show that for a broad class of d.f.'sF in the domain of attraction of Λ, there is a penultimate form of approximation which is a type II [Ф _α(x)=exp (−x^−α), x>0] or a type III [Ψ _α(x)= exp (−(−x)^α), x<0] d.f. of largest values, much closer toF ⁿ(a_nx+b_n) than the ultimate itself.     

Strengthening classical results on convergence rates in strong limit theorems

Let X₁, X₂, . . . be i.i.d. random variables, and set S_n=X₁+ . . . +X_n. Several authors proved convergence of series of the type f(ɛ)=∑_nc_nP(|S_n|>ɛa_n),ɛ>α, under necessary and sufficient conditions. We show that under the same conditions, in fact i.e. the finiteness of ∑_nc_nP(|S_n|>ɛa_n),ɛ>α, is equivalent to the convergence of the double sum ∑_k∑_nc_nP(|S_n|>ka_n). Two exceptional series required deriving necessary and sufficient conditions for E[sup_n|S_n|(logn)^η/n]<∞,0≤η≤1.