On the minimum number of disjoint pairs in a family of finite sets

The following conjecture of Katona is proved. Let X be a finite set of cardinality n, 1 ? m ? 2ⁿ. Then there is a family $\text{F}$, |$\text{F}$| = m, such that F ∈ $\text{F}$, G ? X, | G | > | F | implies G ∈ $\text{F}$ and $\text{F}$ minimizes the number of pairs (F₁, F₂), F₁, F₂ ∈ $\text{F}$ F₁ ∩ F₂ = ? over all families consisting of m subsets of X.     

Necessary and sufficient conditions for the Robbins-Monro method

This paper examines the relation between convergence of the Robbins-Monro iterates $\text{X}{}_{\mathrm{n+1}}\text{= X}{}_{\mathrm{n}}\text{?a}{}_{\mathrm{n}}\text{?(X}{}_{\mathrm{n}}\text{)+a}{}_{\mathrm{n}}\text{ξ}{}_{\mathrm{n}}\text{, ?(θ)=0}$, and the laws of large numbers S_n=a_nΣ^n?1_j=0ξ_j→0 as n→+∞. If a_n is decreasing at least as rapidly as c/n, then X_n→θw.p. 1 (resp. in L_p, p?1) implies S_n→0 w.p. 1 (resp. in L_p, p?1) as n→+∞. If a_n is decreasing at least as slowly as c?n and lim_n→+∞a_n=0, then S_n→0 w.p. 1 (resp. in L_p, p?2) implies X_n→θw.p. 1 (resp. in L_p, p?2) as n →+∞. Thus, there is equivalence in the frequently examined case $\text{a}{}_{\mathrm{n}}\text{?c?n}$. Counter examples show that the LLN must have the form of S_n, that the rate of decrease conditions are sharp, that the weak LLN is neither necessary nor sufficient for the convergence in probability of X_n to θ when $\text{a}{}_{\mathrm{n}}\text{?c?n}$.     

Bounds for the uniform deviation of empirical measures

If X₁,…,X_n are independent identically distributed R^d-valued random vectors with probability measure μ and empirical probability measure μ_n, and if $\text{a}$ is a subset of the Borel sets on R^d, then we show that P{sup_{A∈$\text{a}$}|μ_n(A)?μ(A)|≥ε} ≤ cs($\text{a}$, n²)e^?2n∈2, where c is an explicitly given constant, and s($\text{a}$, n) is the maximum over all (x₁,…,x_n) ∈ R^dn of the number of different sets in {{x₁…,x_n}∩A|A ∈$\text{a}$}. The bound strengthens a result due to Vapnik and Chervonenkis.     

Un probleme de partition de l'ensemble des parties a trois elements d'un ensemble fini

Let X be a set of n elements. Let $\text{T}$₃(X) be the set of all triples of X. We define a clique as a set of triples which intersect pairwise in two elements. In this paper we prove that if n?6, the minimum cardinality of a partition of $\text{T}$₃(X) into cliques is $\text{[}\text{1}\text{4}\text{(n?1)}{}^2\text{]}$.     

Some new results on the Littlewood-Offord problem

We consider the 2ⁿ sums of the form Σ?_ia_i with the a_i's vectors, | a_i | ? 1, and ?_i = 0, 1 for each i. We raise a number of questions about their distribution.We show that if the a_i lie in two dimensions, then at most $\text{n}\text{(}\text{n}\text{2}\text{)}$) sums can lie within a circle of diameter √3, and if n is even at most the sum of the three largest binomial coefficients can lie in a circle of diameter √5. These are best results under the indicated conditions.If two a's are more than 60° but less than 120° apart in direction, then the bound ($\text{n}\text{[}\text{n}\text{2}\text{]}$) on sums lying within a unit diameter sphere is improved to ($\text{n+1}\text{[}\text{n}\text{2}\text{]}\text{) ? 2(}\text{n?1}\text{[(n?}\text{1}\text{2}\text{)])}$.The method of Katona and Kleitman is shown to lead to a significant improvement on their two dimensional result.Finally, Lubell-type relations for sums lying in a unit diameter sphere are examined.     

Hermite series estimates of a probability density and its derivatives

The following estimate of the pth derivative of a probability density function is examined: $\text{Σ}{}_{\mathrm{k\; =\; 0}}{}^{\mathrm{N}}\text{a}\text{?}{}_{\mathrm{k}}\text{h}{}_{\mathrm{k}}\text{(x)}$, where h_k is the kth Hermite function and $\text{a}\text{?}{}_{\mathrm{k}}\text{= (}\text{(?1)}{}^{\mathrm{p}}\text{n}\text{)}$Σ_{i = 1}ⁿh_k^(p)(X_i) is calculated from a sequence X₁,…, X_n of independent random variables having the common unknown density. If the density has r derivatives the integrated square error converges to zero in the mean and almost completely as rapidly as O(n^?α) and O(n^?α log n), respectively, where $\text{α =}\text{2(r ? p)}\text{(2r + 1)}$. Rates for the uniform convergence both in the mean square and almost complete are also given. For any finite interval they are O(n^?β) and $\text{O(n}{}^{\mathrm{<mtext>?\beta </mtext><mtext>2</mtext>}}\text{log}\text{n)}$, respectively, where $\text{β =}\text{(2(r ? p) ? 1)}\text{(2r + 1)}$.     

Sufficient conditions for ergodicity and recurrence of Markov chains on a general state space

Let {X_n} be a ?-irreducible Markov chain on an arbitrary space. Sufficient conditions are given under which the chain is ergodic or recurrent. These extend known results for chains on a countable state space. In particular, it is shown that if the space is a normed topological space, then under some continuity conditions on the transition probabilities of {X_n} the conditions for ergodicity will be met if there is a compact set K and an ? > 0 such that $\text{E}\text{{6X}{}_{\mathrm{n+1}}\text{6 — 6X}{}_{\mathrm{n}}\text{6 ∣ X}{}_{\mathrm{n}}\text{= x} ? ??}$ whenever x lies outside K and $\text{E}\text{{6X}{}_{\mathrm{n+1}}\text{6 ∣ X}{}_{\mathrm{n}}\text{=x}}$ is bounded, x ∈ K; whilst the conditions for recurrence will be met if there exists a compact K with $\text{E}\text{{6X}{}_{\mathrm{n+1}}\text{6 ? 6X}{}_{\mathrm{n}}\text{6 ∣ X}{}_{\mathrm{n}}\text{= x} ? 0}$ for all x outside K. An application to queueing theory is given.     

General theorems on rates of convergence in distribution of random variables I. General limit theorems

Let (X_n)_n?$\text{N}$ be a sequence of real, independent, not necessarily identically distributed random variables (r.v.) with distribution functions F_Xn, and S_n = Σ_i=1ⁿX_i. The authors present limit theorems together with convergence rates for the normalized sums ?(n)S_n, where ?: $\text{N}$ → $\text{R}$⁺, ?(n) → 0, n → ∞, towards appropriate limiting r.v. X, the convergence being taken in the weak (star) sense. Thus higher order estimates are given for the expression ∝_$\text{R}$f(x) d[F_?(n)Sn(x) ? F_X(x)] which depend upon the normalizing function ?, decomposability properties of X and smoothness properties of the function f under consideration. The general theorems of this unified approach subsume O- and o-higher order error estimates based upon assumptions on associated moments. These results are also extended to multi-dimensional random vectors.     

Strong law for the bootstrap

Let X₁, X₂, X₃, … be i.i.d. r.v. with E|X₁| < ∞, E X₁ = μ. Given a realization X = (X₁,X₂,…) and integers n and m, construct Y_n,i, i = 1, 2, …, m as i.i.d. r.v. with conditional distribution $\text{P}{}^1\text{(Y}{}_{\mathrm{n,i}}\text{= X}{}_{\mathrm{j}}\text{) =}\text{1}\text{n}$ for 1 ? j ? n. ($\text{P}{}^1$ denotes conditional distribution given X). Conditions relating the growth rate of m with n and the moments of X₁ are given to ensure the almost sure convergence of $\text{(}\text{1}\text{m}\text{)Σ}{}^{\mathrm{m}}{}_{\mathrm{i=1}}\text{Y}{}_{\mathrm{n,i}}$ toμ. This equation is of some relevance in the theory of Bootstrap as developed by Efron (1979) and Bickel and Freedman (1981).     

On a problem of Chvátal and Erdös on hypergraphs containing no generalized simplex

Let X be an n-element set and $\text{T}$ a family of k-subsets of X. Let r be an integer, k > r ? 2. Suppose that $\text{T}$ does not contain r + 1 members having empty intersection such that any r of them intersect non-trivially. Chvátal and Erdös conjectured that for (r + 1) k ? rn we have |$\text{F}$|$\text{?}\text{n?1}\text{k?1}$. In this paper we first prove that This conjecture holds asymptotically (Theory 1). In Theorems 4 and 5 we prove it for r = 2, K ? 5, n > n_o(k); k ? 3r, n > n_o(k, r), respectively.     

A functional central limit theorem for ϱ-mixing sequences

In this note a functional central limit theorem for ?-mixing sequences of I. A. Ibragimov (Theory Probab. Appl.20 (1975), 135–141) is generalized to nonstationary sequences (X_n)_n ∈ $\text{N}$, satisfying some assumptions on the variances and the moment condition $\text{E |X}{}_{\mathrm{n}}\text{|}{}^{\mathrm{2\; +\; b}}\text{= O(n}{}^{\mathrm{<mtext>b</mtext><mtext>2</mtext><mtext>??</mtext>}}\text{)}$ for some b > 0, ? > 0.     

Classes of orderings of measures and related correlation inequalities. I. Multivariate totally positive distributions

A function f(x) defined on $\text{X}$ = $\text{X}$₁ × $\text{X}$₂ × … × $\text{X}$_n where each $\text{X}$_i is totally ordered satisfying f(x ∨ y) f(x ∧ y) ≥ f(x) f(y), where the lattice operations ∨ and ∧ refer to the usual ordering on $\text{X}$, is said to be multivariate totally positive of order 2 (MTP₂). A random vector Z = (Z₁, Z₂,…, Z_n) of n-real components is MTP₂ if its density is MTP₂. Classes of examples include independent random variables, absolute value multinormal whose covariance matrix Σ satisfies ?DΣ^?1D with nonnegative off-diagonal elements for some diagonal matrix D, characteristic roots of random Wishart matrices, multivariate logistic, gamma and F distributions, and others. Composition and marginal operations preserve the MTP₂ properties. The MTP₂ property facilitate the characterization of bounds for confidence sets, the calculation of coverage probabilities, securing estimates of multivariate ranking, in establishing a hierarchy of correlation inequalities, and in studying monotone Markov processes. Extensions on the theory of MTP₂ kernels are presented and amplified by a wide variety of applications.     

Coefficient inequalities for a subclass of starlike functions

A function f(z) = z ? ∑^∞_{n = 2}a_nzⁿ, a_n ? 0, analytic and univalent in the unit disk, is said to be in the family $\text{T}{}^1\text{(a, b)}$, a real and b ? 0, if $\text{¦(}\text{zf′}\text{f}\text{) ? a¦ ? b}$ for all z in the unit disk. A complete characterization is found for $\text{T}{}^1\text{(a, b)}$ when a ? 1. Also, sharp coefficient bounds are determined for certain subclasses of $\text{T}{}^1\text{(a, b)}$ when a < 1; however, examples are given to show that these bounds do not remain valid for the whole family.     

A note on the functional law of iterated logarithm for maxima of Gaussian sequences

Let {X_n, n ≥ 1} be a real-valued stationary Gaussian sequence with mean zero and variance one. Let M_n = max{X_t, i ≤ n} and H_n(t) = (M_[nt] ? b_n)a_n^?1 be the maximum resp. the properly normalised maximum process, where $\text{c}{}_{\mathrm{n}}\text{= (2}\text{log}\text{n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, $\text{a}{}_{\mathrm{n}}\text{=}\text{(}\text{log log}\text{n)}\text{c}{}_{\mathrm{n}}$ and $\text{b}{}_{\mathrm{n}}\text{= c}{}_{\mathrm{n}}\text{?}\text{1}\text{2}\text{(}\text{log}\text{(4π}\text{log}\text{n))}\text{c}{}_{\mathrm{n}}$. We characterize the almost sure limit functions of (H_n)_n≥3 in the set of non-negative, non-decreasing, right-continuous, real-valued functions on (0, ∞), if r(n) (log n)^3?Δ = O(1) for all Δ > 0 or if r(n) (log n)^2?Δ = O(1) for all Δ > 0 and r(n) convex and fulfills another regularity condition, where r(n) is the correlation function of the Gaussian sequence.     

Deterministic version of Wigner's semicircle law for the distribution of matrix eigenvalues

It is proved that Wigner's semicircle law for the distribution of eigenvalues of random matrices, which is important in the statistical theory of energy levels of heavy nuclei, possesses the following completely deterministic version. Let A_n=(a_ij), 1?i, ?n, be the nth section of an infinite Hermitian matrix, {λ⁽ⁿ⁾}_1?k?n its eigenvalues, and {u_k⁽ⁿ⁾}_1?k?n the corresponding (orthonormalized column) eigenvectors. Let $\text{v}{}^1{}_{\mathrm{n}}\text{=(a}{}_{\mathrm{n1}}\text{,a}{}_{\mathrm{n2}}\text{,?,a}{}_{\mathrm{n,n?1}}\text{)}$, put

$\text{X}{}_{\mathrm{n}}\text{(t)=[n(n-1)]}{}^{\mathrm{<mtext>-1</mtext><mtext>2</mtext>}}\text{∑}\text{k=1}\text{[(n-1)t]}\text{|v}{}_{\mathrm{n}}{}^1\text{u}{}_{\mathrm{f}}{}^{\mathrm{(n-1)}}\text{|}{}^2\text{,}\text{0?t?1}$

(bookeeping function for the length of the projections of the new row v¹_n of A_n onto the eigenvectors of the preceding matrix A_n?1), and let finally

$\text{F}{}_{\mathrm{n}}\text{(x)=n}{}^{-1}\text{(}\text{number of}\text{λ}{}_{\mathrm{k}}{}^{\mathrm{(n)}}\text{?x}\text{n}\text{,1?k?n)}$

(empirical distribution function of the eigenvalues of $\text{A}{}_{\mathrm{n}}\text{n}$. Suppose (i) $\text{lim}{}_{\mathrm{n}}\text{a}{}_{\mathrm{nn}}\text{n}\text{=0}$, (ii) lim_nX_n(t)=Ct(0<C<∞,0?t?1). Then

$\text{F}{}_{\mathrm{n}}\text{?W(·,C)}\text{(n→∞)}$

,where W is absolutely continuous with (semicircle) density

$\text{w(x,C)=}\text{(2Cπ)}{}^{-1}\text{(4C-x}{}^2{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{for}\text{|x|?2}\text{C}\text{0}\text{for}\text{|x|?2}\text{C}$

     

Embedding finite posets in cubes

In this paper we define the n-cube Q_n as the poset obtained by taking the cartesian product of n chains each consisting of two points. For a finite poset X, we then define dim₂X as the smallest positive integer n such that X can be embedded as a subposet of Q_n. For any poset X we then have log₂ |X| ? dim₂X ? |X|. For the distributive lattice $\text{L =}\text{2}{}^{\mathrm{X}}$, dim₂L = |X| and for the crown S^k_n, dim₂ (S^k_n) = n + k. For each k ? 2, there exist positive constants c₁ and c₂ so that for the poset X consisting of all one element and k-element subsets of an n-element set, the inequality c₁ log₂n < dim₂(X) < c₂ log₂n holds for all n with k < n. A poset is called Q-critical if dim₂ (X ? x) < dim₂(X) for every x ? X. We define a join operation ⊕ on posets under which the collection Q of all Q-critical posets which are not chains forms a semigroup in which unique factorization holds. We then completely determine the subcollection $\text{M}$ ? Q consisting of all posets X for which dim₂ (X) = |X|.     

Hilbertian and complemented finite-dimensional subspaces of Banach lattices and unitary ideals

Let 1 < p ? 2 ? q < ∞ and X be either a Banach lattice which is p-convex and q-concave or a unitary ideal of operators on l₂ which is modeled on a symmetric space which is p-convex and q-concave. If E ?X is any n-dimensional subspace, then both the distance from E to $\text{l}{}_2{}^{\mathrm{n}}$ and the relative projection constant of E in X are dominated by $\text{cn}{}^{\mathrm{<mtext>1</mtext><mtext>p</mtext><mtext>\; ?\; </mtext><mtext>1</mtext><mtext>q</mtext>}}$.     

Limiting distributions of two random sequences

For fixed p (0 ≤ p ≤ 1), let {L₀, R₀} = {0, 1} and X₁ be a uniform random variable over {L₀, R₀}. With probability p let {L₁, R₁} = {L₀, X₁} or = {X₁, R₀} according as $\text{X}{}_1\text{≥}\text{1}\text{2}\text{(L}{}_0\text{+ R}{}_0\text{)}\text{or}\text{<}\text{1}\text{2}\text{(L}{}_0\text{+ R}{}_0\text{)}$; with probability 1 ? p let {L₁, R₁} = {X₁, R₀} or = {L₀, X₁} according as $\text{X}{}_1\text{≥}\text{1}\text{2}\text{(L}{}_0\text{+ R}{}_0\text{)}\text{or}\text{<}\text{1}\text{2}\text{(L}{}_0\text{+ R}{}_0\text{)}$, and let X₂ be a uniform random variable over {L₁, R₁}. For n ≥ 2, with probability p let {L_n, R_n} = {L_{n ? 1}, X_n} or = {X_n, R_{n ? 1}} according as $\text{X}{}_{\mathrm{n}}\text{≥}\text{1}\text{2}\text{(L}{}_{\mathrm{n\; ?\; 1}}\text{+ R}{}_{\mathrm{n\; ?\; 1}}\text{)}\text{or}\text{<}\text{1}\text{2}\text{(L}{}_{\mathrm{n\; ?\; 1}}\text{+ R}{}_{\mathrm{n\; ?\; 1}}\text{)}$, with probability 1 ? p let {L_n, R_n} = {X_n, R_{n ? 1}} or = {L_{n ? 1}, X_n} according as $\text{X}{}_{\mathrm{n}}\text{≥}\text{1}\text{2}\text{(L}{}_{\mathrm{n\; ?\; 1}}\text{+ R}{}_{\mathrm{n\; ?\; 1}}\text{)}\text{or}\text{<}\text{1}\text{2}\text{(L}{}_{\mathrm{n\; ?\; 1}}\text{+ R}{}_{\mathrm{n\; ?\; 1}}\text{)}$, and let X_{n + 1} be a uniform random variable over {L_n, R_n}. By this iterated procedure, a random sequence {X_n}_{n ≥ 1} is constructed, and it is easy to see that X_n converges to a random variable Y_p (say) almost surely as n → ∞. Then what is the distribution of Y_p? It is shown that the Beta, (2, 2) distribution is the distribution of Y₁; that is, the probability density function of Y₁ is g(y) = 6y(1 ? y) I_0,1(y). It is also shown that the distribution of Y₀ is not a known distribution but has some interesting properties (convexity and differentiability).     

Limit distributions for the maxima of stationary Gaussian processes

Let {X_n} be a stationary Gaussian sequence with E{X₀} = 0, {X²₀} = 1 and E{X₀X_n} = rⁿ_n Let c_n = (2ln n)^{$\text{built1}\text{2}$}, b_n = c_n? $\text{1}\text{2}$c^-1_n ln(4π ln n), and set M_n = max_{0 ?k?n}X_k. A classical result for independent normal random variables is that

$\text{P[c}{}_{\mathrm{n}}\text{(M}{}_{\mathrm{n}}\text{?b}{}_{\mathrm{n}}\text{)?x]→exp[-e}{}^{\mathrm{-x}}\text{] as n → ∞ for all x.}$

Berman has shown that (1) applies as well to dependent sequences provided r_nlnn = o(1). Suppose now that {r_n} is a convex correlation sequence satisfying r_n = o(1), (r_nlnn)^-1 is monotone for large n and o(1). Then

$\text{P[r}{}_{\mathrm{n}}{}^{\mathrm{<mtext>-1</mtext><mtext>2</mtext>}}\text{(M}{}_{\mathrm{n}}\text{? (1?r}{}_{\mathrm{n}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{b}{}_{\mathrm{n}}\text{)?x] → Ф(x)}$

for all x, where Ф is the normal distribution function. While the normal can thus be viewed as a second natural limit distribution for {M_n}, there are others. In particular, the limit distribution is given below when r_n is (sufficiently close to) γ/ln n. We further exhibit a collection of limit distributions which can arise when r_n decays to zero in a nonsmooth manner. Continuous parameter Gaussian processes are also considered. A modified version of (1) has been given by Pickands for some continuous processes which possess sufficient asymptotic independence properties. Under a weaker form of asymptotic independence, we obtain a version of (2).     

Extreme value distribution for normalized sums from stationary Gaussian sequences

Let {X_i, i?0} be a sequence of independent identically distributed random variables with finite absolute third moment. Then Darling and Erdös have shown that

for -∞<t<∞ where and $\text{X}{}_{\mathrm{n}}\text{= (2 ln ln n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$. The result is extended to dependent sequences but assuming that {X_i} is a standard stationary Gaussian sequence with covariance function {r_i}. When {X_i} is moderately dependent (e.g. when $\text{v(∑}{}^{\mathrm{n}}{}_{\mathrm{i=1}}\text{X}{}_{\mathrm{i}}\text{) ? n}{}_{\mathrm{a}}\text{, 0 < a < 2)}$ we get

where H_a is a constant. In the strongly dependent case (e.g. when $\text{v(∑}{}^{\mathrm{n}}{}_{\mathrm{i=1}}\text{X}{}_{\mathrm{i}}\text{) ? n}{}^2\text{r(n))}$ we get

for-∞<t<∞.