Strong consistency of the mean on randomly deleted sets

Suppose 0t ₁<t ₂<... are fixed points in time. At timet _k , a unit with magnitudeX _k and lifetimeL _k enters a population or is placed into a system. Suppose that theX _k 's are i.i.d. withEX ₁=, theL _k 's are i.i.d., and that theX _k 's andL _k 's are independent. In this paper we find conditions under which the continuous time process Avr{X _k :t _k t<t _k +L _k } is almost surely convergent to . We also demonstrate the sharpness of these conditions.     

Upper-Lower Class Tests for Weighted i.i.d. Sequences and Martingales

We study the upper-lower class behavior of weighted sums ∑ _k=1 ⁿ a _k X _k , where X _k are i.i.d. random variables with mean 0 and variance 1. In contrast to Feller’s classical results in the case of bounded X _j , we show that the refined LIL behavior of such sums depends not on the growth properties of (a _n ) but on its arithmetical distribution, permitting pathological behavior even for bounded (a _n ). We prove analogous results for weighted sums of stationary martingale difference sequences. These are new even in the unweighted case and complement the sharp results of Einmahl and Mason obtained in the bounded case. Finally, we prove a general upper-lower class test for unbounded martingales, improving several earlier results in the literature.     

Correlations of functions of normal variables

Let (X₁, X₂,…, X_k, Y₁, Y₂,…, Y_k) be multivariate normal and define a matrix C by C_ij = cov(X_i, Y_j). If (i) (X₁,…, X_k) = (Y₁,…, Y_k) and (ii) C is symmetric positive definite, then 0 < varf(X₁,…, X_k) < ∞ corr(f(X₁,…, X_k),f(Y₁,…, Y_k)) > 0. Condition (i) is necessary for the conclusion. The sufficiency of (i) and (ii) follows from an infinite-dimensional version, which can also be applied to a pair of jointly normal Brownian motions.     

On the Expected Number of Shadow Vertices of the Convex Hull of Random Points

Leta₁, . . . ,a_mbe independent random points in ⁿthat are independent and identically distributed spherically symmetrical in ⁿ. Moreover, letXbe the random polytope generated as the convex hull ofa₁, . . . ,a_mand letL_kbe an arbitraryk-dimensional subspace of ⁿwith 2 ≤k≤n− 1. LetX_kbe the orthogonal projection image ofXinL_k. We call those vertices ofXwhose projection images inL_kare vertices ofX_kshadow vertices ofXwith respect to the subspaceL_k. We derive a distribution independent sharp upper bound for the expected number of shadow vertices ofXinL_k.     

Asymptotic distribution of the log-likelihood function for stochastic processes

Summary Let X ₀, X ₁,, X _nbe r.v.'s coming from a stochastic process whose finite dimensional distributions are of known functional form except that they involve a k-dimensional parameter. From the viewpoint of statistical inference, it is of interest to obtain the asymptotic distributions of the log-likelihood function and also of certain other r.v.'s closely associated with the likelihood function. The probability measures employed for this purpose depend, in general, on the sample size n. These problems are resolved provided the process satisfies some quite general regularity conditions. The results presented herein generalize previously obtained results for the case of Markovian processes, and also for i.n.n.i.d. r.v.'s. The concept of contiguity plays a key role in the various derivations.This research was supported by the National Science Foundation, Grant MCS76-11620, and a grant by the National Research Foundation of Greece     

Constructing Hierarchical Set Systems

In this note, it is shown that by applying ranking procedures to data that allow, for any three objects a₁, a₂, b in a collection X of objects of interest, to make consistent decisions about which of the two objects a₁ or a₂ is more similar to b, a family of cluster systems can be constructed that start with the associated Apresjan Hierarchy and keep growing until, for k = #X–1, the full set of all subsets of X is reached. Various ideas regarding canonical modifications of the similarity values so that these cluster systems contain as many clusters as possible for small values of k (and in particular for k := 0) and/or are rooted at a specific element in X, possible applications, e.g. concerning (i) the comparison of distinct dissimilarity data defined on the same set X or (ii) diversity optimization, and new tasks arising in ranking statistics are also discussed.Received November 15, 2003     

The k-record processes are i.i.d.

Let X ₁, X ₂, ... be i.i.d. positive random variables, and let _n be the initial rank of X _n (that is, the rank of X _n among X ₁, ..., X _n). Those observations whose initial rank is k are collected into a point process N ^k on ⁺, called the k-record process. The fact that {itN^k; k=1, 2, ... are independent and identically distributed point processes is the main result of the paper. The proof, based on martingales, is very rapid. We also show that given N ¹, ..., N ^k, the lifetimes in rank k of all observations of initial rank at most k are independent geometric random variables.These results are generalised to continuous time, where the analogue of the i.i.d. sequence is a time-space Poisson process. Initially, we think of this Poisson process as having values in ⁺, but subsequently we extend to Poisson processes with values in more general Polish spaces (for example, Brownian excursion space) where ranking is performed using real-valued attributes.     

Waiting time problems for a sequence of discrete random variables

Let X ₁, X ₂,... be a sequence of nonnegative integer valued random variables.For each nonnegative integer i, we are given a positive integer k _i . For every i = 0, 1, 2,..., E _i denotes the event that a run of i of length k _i occurs in the sequence X ₁, X ₂,.... For the sequence X ₁, X ₂,..., the generalized pgf's of the distributions of the waiting times until the r-th occurrence among the events % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D% aebbfv3ySLgzGueE0jxyaibaiiYdd9qrFfea0dXdf9vqai-hEir8Ve% ea0de9qq-hbrpepeea0db9q8as0-LqLs-Jirpepeea0-as0Fb9pgea% 0lrP0xe9Fve9Fve9qapdbaqaaeGacaGaaiaabeqaamaabaabcaGcba% WaaiWabeaacaWGfbWaaSbaaSqaaiaadMgaaeqaaaGccaGL7bGaayzF% aaWaa0baaSqaaiaadMgacqGH9aqpcaaIWaaabaGaeyOhIukaaaaa!43D8!\[\left\{ {E_i } \right\}_{i = 0}^\infty\]are obtained. Though our situations are general, the results are very simple. For the special cases that X's are i.i.d. and {0, 1}-valued, the corresponding results are consistent with previously published results.This research was partially supported by the ISM Cooperative Research Program (90-ISM-CRP-11) of the Institute of Statistical Mathematics.     

A function with prescribed initial derivatives in different Banach spaces

Let X₀ ? X₁ ? ··· ? X_p be Banach spaces with continuous injection of X_k into X_{k + 1} for 0 ? k ? p ? 1, and with X₀ dense in X_p. We seek a function u: [0, 1] → X₀ such that its kth derivative u^(k), k = 0, 1,…, p, is continuous from [0, 1] into x_k, and satisfies the initial condition u^(k)(0) = a_k?X_k. It is shown that such a function exists if and only if the initial values a₀, a₁, …, a_p satisfy a certain condition reminiscent of interpolation theory. This condition always holds when p = 1; when p ? 2, the spaces X_k (k = 0, 1, …, p) may or may not be such that the desired function exists for any given initial values a_k?X_k.     

Characterization of conditional covariance and unified theory in the problem of ordering random variables

Under the assumption that a (p+q)-dimensional row vector (Y, X) is elliptically contoured distributed, the conditional covariance of Y given X=x is characterized in the context of correctly ordering the coordinates Y _k 's of Y based on X. This is an answer to a conjecture implicit in Portnoy (1982). Moreover some unified theory is presented for the problem of ordering Y _k 's based on X. An essential tool is the decreasing in transposition (D. T.) function theory of Hollander et al. (1977, Ann. Statist., 5(4), 722–733).     

The reverse spelling of an FPrt-universal word in two letters

ForX a set the expression Prt(X) denotes the composition monoid of all functionsf X ×X. Fork a positive integer the letterk denotes also the set of all nonnegative integers less thank. Whenk > 1 the expression r_k denotes the connected injective element {<i, i + 1>i k – 1} in Prt (k). We show for every word w=w(x,y) in a two-letter alphabet that if the equation w(x, y)=r_k has a solution =y) ²Prt(k) then ¯w(x,y)=r_k also has a solution in²Prt(k), where ¯w is the word obtained by spelling the wordw backwards. It is a consequence of this theorem that if for every finite setX and for everyf Prt(X) the equation w(x,y)=f has a solution in²Prt(X) then for every suchX andf the equation ¯w(x, y)=f has a solution in²Prt(X).Presented by J. Mycielski.     

Distance in stratified graphs

A graph G is stratified if its vertex set is partitioned into classes, called strata. If there are k strata, then G is k-stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color X in a stratified graph G, the X-eccentricity e _X(v) of a vertex v of G is the distance between v and an X-colored vertex furthest from v. The minimum X-eccentricity among the vertices of G is the X-radius rad_X G of G and the maximum X-eccentricity is the X-diameter diam_X G. It is shown that for every three positive integers a, b and k with ab, there exist a k-stratified graph G with rad_X G = a and diam_X G = b. The number s _X denotes the minimum X-eccetricity among the X-colored vertices of G. It is shown that for every integer t with rad_X G t diam_X G, there exist at least one vertex v with e _X(v) = t; while if rad_X G t s _X, then there are at least two such vertices. The X-center C _X(G) is the subgraph induced by those vertices v with e _X(v) = rad_X G and the X-periphery P _X (G) is the subgraph induced by those vertices v with e _X(G) = diam_X G. It is shown that for k-stratified graphs H ₁, H ₂,..., H _k with colors X ₁, X ₂,..., X _k and a positive integer n, there exists a k-stratified graph G such that C X _i(G) H _i (1 ; i ; k1) and for i j. Those k-stratified graphs that are peripheries of k-stratified graphs are characterized. Other distance-related topics in stratified graphs are also discussed.     

On product representations of powers, I

The solvability of the equation a₁a₂ … a_k = x², a₁, a₂, …, a_k ε is studied for fixed k and ‘dense’ sets of positive integers. In particular, it is shown that if k is even and k 4, and is of positive upper density, then this equation can be solved.     

On the fluctuations of independent copies of moving maxima

Let {X_n, n1} be a sequence of independent random variables (r.v.'s) with a common distribution function (d.f.) F. Define the moving maxima Y_k(n)=max(X_n−k(n)+1,X_n−k(n)+2,…,X_n), where {k(n), n1} is a sequence of positive integers. Let Y_k(n)¹ and Y_k(n)² be two independent copies of Y_k(n). Under certain conditions on F and k(n), the set of almost sure limit points of the vector consisting of properly normalised Y_k(n)¹ and Y_k(n)² is obtained.     

A packing problem its application to Bose's families

We propose and study the following problem: given X ⊂ Z_n, construct a maximum packing of dev X (the development of X), i.e., a maximum set of pairwise disjoint translates of X. Such a packing is optimal when its size reaches the upper bound . In particular, it is perfect when its size is exactly equal to i.e. when it is a partition of Z_n. We apply the above problem for constructing Bose's families. A (q, k) Bose's family (BF) is a nonempty family F of subsets of the field GF(q) such that: (i) each member of F is a coset of the kth roots of unity for k odd (the union of a coset of the (k - 1)th roots of unity and zero for k even); (ii) the development of F, i.e., the incidence structure , is a semilinear space. A (q, k)-BF is optimal when its size reaches the upper bound . In particular, it is perfect when its size is exactly equal to ; in this case the (q, k)-BF is a (q, k, 1) difference family and its development is a linear space. If the set of (q, k)-BF's is not empty, there is a bijection preserving maximality, optimality, and perfectness between this set with the set of packings of dev X, where X is a suitable -subset of Z_n, for k odd, for k even. © 1996 John Wiley & Sons, Inc.     

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.     

A Nim-like Game and Dynamic Recurrence Relations

The nim-like game 〈n, f; X, Y〉 is defined by an integer n ≥ 2 a constraint function f, and two players and X and Y. Players X and Y alternate taking coins from a pile of n coins, with X taking the first turn. The winner is the one who takes the last coin. On the kth turn, a player may remove t_k coins, where 1 ≤ t₁ ≤ n ? 1 and 1 ≤ t_k ≤ max{1, f(t_k?1) for k > 1. Let the set S_f = {1} ∪ {n| there is a winning strategy for Y in the nim-like game 〈n, f; X, Y〉}. In this paper, an algorithm is provided to construct the set S_f = {a₁, a₂,…} in an increasing sequence when the function f(x) is monotonic. We show that if the function f(x) is linear, then there exist integers n₀ and m such that a_n+1 = a_n + a_n?m for n > n₀ and we give upper and lower bounds for m (dependent on f. A duality is established between the asymptotic order of the sequence of elements in S_f and the degree of the function f(x). A necessary and sufficient condition for the sequence {a₀, a₁, a₂,…} of elements in S_f to satisfy a regular recurrence relation is described as well.     

Inequalities for probability contents of convex sets via geometric average

It is shown that: If (X₁, X₂) is a permutation invariant central convex unimodal random vector and if A is a symmetric (about 0) permutation invariant convex set then P{(aX₁, X₂/a) A} is nondecreasing as a varies from )+ to 1 and is non-increasing as a varies from 1 to ∞ (that is, P{(a₁X₁, a₂X₂) ε A} is a Schur-concave function of (log a₁, log a₂). Some extensions of this result for the n-dimensional case are discussed. Applications are given for elliptically contoured distributions and scale parameter families.     

p-Norm bounds on the expectation of the maximum of a possibly dependent sample

Let X₁, X₂,…, X_n be identically distributed possibly dependent random variables with finite pth absolute moment assumed without loss of generality to be equal to 1. Denote the order statistics by X_1:n, X_2:n,…, X_n:n. Bounds are derived for E(X_n:n) when it is assumed that the X_i's are (i) arbitrarily dependent and (ii) independent. The effect of assuming a symmetric common distribution for the X_i's is discussed. Analogous bounds are described for the expected range of the sample. Bounds on expectations of general linear combinations of order statistics are described in the independent case.     

Extreme value limit laws in the nonidentically distributed case

LetX ₁, ...,X _n be independent random variables, letF _i be the distribution function ofX _i (1≦i≦n) and letX _1n ≦... ≦X _nn be the corresponding order statistics. We consider the statisticsX _kn, wherek=k(n),k/n → 1 andn−k → ∞. Under some additional restrictions concerning the behaviour of the sequences {a _n>0,b _n,k(n),F _n} we characterize the class of all distribution functionsH such that Prob{(X _kn −b _n )/a _n <x)}→H. Dedicated to the Memory of N. V. Smirnov (1900–1966)