A parallel selection algorithm

The problem of selecting thekth largest or smallest element of {x _i +y _j |x _i X andy _j Y i,j} whereX=(x ₁,x ₂, ..,x _n ) andY=(y ₁,y ₂, ...,y _n ) are two arrays ofn elements each, is considered. Certain improvements to an existing algorithm are proposed. An algorithm requiringO(logk·logn) units of time on a Shared Memory Model of a parallel computer havingO(n ^1+1/) processors is presented where is a pre-assigned constant lying between 1 and 2.     

A structure theorem for sum form functional equations

Summary It is proved that, iff _ij:]0, 1[ C (i = 1, ,k;j = 1, ,l) are measurable, satisfy the equation (1) (with some functionsg _it, h_jt:]0, 1[ C), then eachf _ij is in a linear space (called Euler space) spanned by the functionsx x ^j(logx) ^k (x ]0, 1[;j = 1, ,M;k = 0, ,m _j – 1), where ₁, , _M are distinct complex numbers andm ₁, , m_M natural numbers. The dimension of this linear space is bounded by a linear function ofN.     

Random polytopes in thed-dimensional cube

LetC ^d be the set of vertices of ad-dimensional cube,C ^d ={(x ₁, ...,x _d ):x _i =±1}. Let us choose a randomn-element subsetA(n) ofC ^d . Here we prove that Prob (the origin belongs to the convA(2d+x2d))=(x)+o(1) ifx is fixed andd . That is, for an arbitrary>0 the convex hull of more than (2+)d vertices almost always contains 0 while the convex hull of less than (2-)d points almost always avoids it.     

Cross-monotone subsequences

Two finite real sequences (a ₁,...,a _k ) and (b ₁,...,b _k ) are cross-monotone if each is nondecreasing anda _i+1–a _i b _i+1–b _i for alli. A sequence (₁,..., _n ) of nondecreasing reals is in class CM(k) if it has disjointk-term subsequences that are cross-monotone. The paper shows thatf(k), the smallestn such that every nondecreasing (₁,..., _n ) is in CM(k), is bounded between aboutk ²/4 andk ₂/2. It also shows thatg(k), the smallestn for which all (₁,..., _n ) are in CM(k)and eithera _k b ₁ orb _k a ₁, equalsk(k–1)+2, and thath(k), the smallestn for which all (₁,..., _n ) are in CM(_k)and eithera ₁b ₁...a _k b _k orb ₁a ₁...b _k a _k , equals 2(k–1)²+2.The results forf andg rely on new theorems for regular patterns in (0, 1)-matrices that are of interest in their own right. An example is: Every upper-triangulark ²×k ² (0, 1)-matrix has eitherk 1's in consecutive columns, each below its predecessor, ork 0's in consecutive rows, each to the right of its predecessor, and the same conclusion is false whenk ² is replaced byk ²–1.     

LAN of extreme order statistics

Consider an iid sampleZ ₁,...,Z _n with common distribution functionF on the real line, whose upper tail belongs to a parametric family {F : }. We establish local asymptotic normality (LAN) of the loglikelihood process pertaining to the vector(Z _n–i+1n ) _i=1 ^k of the upperk=k(n) _n order statistics in the sample, if the family {F :} is in a neighborhood of the family of generalized Pareto distributions. It turns out that, except in one particular location case, thekth-largest order statisticZ _n–k+1n is the central sequence generating LAN. This implies thatZ _n–k+1n is asymptotically sufficient and that asymptotically optimal tests for the underlying parameter can be based on the single order statisticZ _n–k+1n . The rate at whichZ _n–k+1n becomes asymptotically sufficient is however quite poor.     

Asymptotic behavior of general M-estimates for regression and scale with random carriers

Summary Let (xini, y _i be a sequence of independent identically distributed random variables, where x _i R ^p and y _i R, and let R ^p be an unknown vector such that y _i =x _i +u _i (^*), where u _i is independent of x _i and has distribution function F(u/), where >0 is an unknown parameter. This paper deals with a general class of M-estimates of regression and scale, ( ^*,^*), defined as solutions of the system: , where r= (y _i –x _i ^1*/)^*, with R ^p ×RR and RR. This class contains estimators of (, ) proposed by Huber, Mallows and Krasker and Welsch. The consistency and asymptotic normality of the general M-estimators are proved assuming general regularity conditions on and and assuming the joint distribution of (x _i , y _i ) to fulfill the model (^*) only approximately.     

On construction ofk-wise independent random variables

A 0–1probability space is a probability space (, 2,P), where the sample space -{0, 1} ⁿ for somen. A probability space isk-wise independent if, whenY _i is defined to be theith coordinate or the randomn-vector, then any subset ofk of theY _i 's is (mutually) independent, and it is said to be a probability spacefor p ₁,p ₂, ...,p _n ifP[Y _i =1]=p _i .We study constructions ofk-wise independent 0–1 probability spaces in which thep _i 's are arbitrary. It was known that for anyp ₁,p ₂, ...,p _n , ak-wise independent probability space of size always exists. We prove that for somep ₁,p ₂, ...,p _n [0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachp _i =k/n has size (n _k ). For a very large degree of independence —k=[n], for >1/2- and allp _i =1/2, we prove a lower bound on the size of . We also give explicit constructions ofk-wise independent 0–1 probability spaces.This author was supported in part by NSF grant CCR 9107349.This research was supported in part by the Israel Science Foundation administered by the lsrael Academy of Science and Humanities and by a grant of the Israeli Ministry of Science and Technology.     

Lattice Polytopes Associated to Certain Demazure Modules of sl n + 1

Let w be an element of the Weyl group of sl _{n + 1}. We prove that for a certain class of elements w (which includes the longest element w₀ of the Weyl group), there exist a lattice polytope R ^l(w) , for each fundamental weight _i of sl _{n + 1}, such that for any dominant weight = _{i = 1} ⁿ a _{i i} , the number of lattice points in the Minkowski sum _w = _{i = 1} ⁿ a _{i i} ^w is equal to the dimension of the Demazure module E _w (). We also define a linear map A ^w : R ^l(w) P _Z R where P denotes the weight lattice, such that char E _w () = e e^–A(x) where the sum runs through the lattice points x of ^w .     

Hodge decompositions of Loday symbols inK-theory and cyclic homology

In this paper, we study the Hodge decompositions ofK-theory and cyclic homology induced by the operations ^k and ^k , and in particular the decomposition of the Loday symbols x,y, ...z. Except in special cases, these Loday symbols do not have pure Hodge index. InK _n (A) they can project into every componentK _n ⁽ⁱ⁾ for 2in, and the projection of the Loday symbol x,y, ...,z intoK _n ⁽ⁿ⁾ is a multiple of the generalized Dennis-Stein symbol x,y, ...,z. Our calculations disprove conjectures of Beilinson and Soulé inK-theory, and of Gerstenhaber and Schack in Hochschild homology.Partially supported by National Security Agency grant MDA904-90-H-4019.Partially supported by National Science Foundation grant DMS-8803497.     

On convergence subsystems of orthonormal systems

It is proved that for any sequence {R _k} _k=1 of real numbers satisfyingR _kk (k1) andR _k=o(k log₂ k),k, there exists an orthonormal system {n _k(x)} _n=1 ,x (0;1), such that none of its subsystems {n _k(x)} _k=1 withn _kR_k (k1) is a convergence subsystem.     

Dual-orthogonal polynomials

Let (x, ) and (x,) be two functions,x[a, b] and { _j } _j=1 and { _j } _j=1 be two sequences where _{i j} and _{i j} whenij. We define the vector spacesU _k =span{(x, _j )} _j=1 ^k andV _k =span{(x, _j )} _j=1 ^k where we assume thatdim(U _k )=dim(V _k )=k,k1. We then look for the generalized polynomialsp _m xU _m+1\U _m so that _a ^b p _m (x)(x, _j )d(x)=0,j=1,2,...,m. If such generalized polynomials exist for allm1 we say that {p _m } _m=1 is a dual-orthogonal polynomial sequence from {(x, _j )} _j=1 to {(x, _j )} _j=1 with respect to the distribution (x),x[a, b]. In this article we present existence theorems for dual-orthogonal polynomials, explicit formulae forp _m(x), theorems about the zeros ofp _m(x), and, in the end, a Gauss-type quadrature formula for dual-orthogonal polynomials.     

On the existence of wave operators for the Klein-Gordon equation

The problem of existence of wave operators for the Klein-Gordon equation ( _t ² –+²+iV_1t+V₂)u(x,t)=0 (x R ⁿ,t R, n3, >0) is studied where V₁ and V₂ are symmetric operators in L₂(R ⁿ) and it is shown that conditions similar to those of Veseli-Weidmann (Journal Functional Analysis 17, 61–77 (1974)) for a different class of operators are also sufficient for the Klein-Gordon equation.     

Smoothness of solutions of a nonlinear ode

Smoothness of aC -functionf is measured by (Carleman) sequence {M _k} ₀ ; we sayfC _M [0, 1] if|f ^(k) (t)|CR ^k M _k,k=0, 1, ... withC, R>0. A typical statement proven in this paper isTHEOREM: Let u, b be two C -functions on [0, 1]such that (a) u=u ²+b, (b) |b ^(k) (t)|CR ^k (k!) , >1,k_–.Then |u^(k)(t)|C₁R^k((k–1)!),k_–.The first author acknowledges the hospitality of Mathematical Research Institute of the Ohio State University during his one month visit there in the spring of 1999     

On asymptotically efficient estimation for a semiparametric regression model

1.IntroductionConsiderthemodelY=X"0 g(T) E,(1'1)whereX"~(xl,',xo)areexplanatoryvariablesthatenterlinearly,Pisakx1vectorofunknownparameters,Tisanotherexplanatoryvariablesthatentersinanonlinearfashion,g')isanunknownsmoothfunctionofTinR',(X,T)andeareindependent,andeistheerrorwithmean0andvariancea2.Trangesoveranondegeneratecompact1-dimensionalilltervalC*;withoutlossofgenerality,C*=[0,1].Chenl2]discussedasymptoticnormalityofestimatorsP.of0byusingpiecewisepolynthacaltoapproximateg.Speckmanls…     

Cubature formulae which are exact on spacesP,intermediate betweenP k andQ k′

Summary In this paper we search, from the orthogonal polynomial theory, for conditions which allow to obtain cubature formulae on compacts of ⁿ , with weight function, and which are exact on the spaceR( _{k 1}, k₂, ..., k_n) of all polynomials of degree k _i respectively to each variablex _i , 1in.     

Percentage Points of the Largest Among Student's T Random Variable

Let us consider k( 2) independent random variables U₁, . . . ,U_k where U_i is distributed as the Student's t random variable with a degree of freedom m_i, i=1, . . . ,k. Here, m₁, . . . ,m_k are arbitrary positive integers. We denote m=(m₁, . . . ,m_k) and U_k:k=max {U₁, . . . ,U_k}, the largest Student's t random variable. Having fixed 0< <1, let a a(k,) and h_m h_m (k,) be two positive numbers for which we can claim that (i) ^k(a)–^k(–a)=1–, and (ii) P{–h_m U_k:k h_m}=1–. Then, we proceed to derive a Cornish–Fisher expansion (Theorem 3.1) of the percentage point h_m. This expansion involves a as well as expressions such as _i=1 ^k m_i ^–1, _i=1 ^km_i ^–2, and _i=1 ^k m_i ^–3. The corresponding approximation of h_m is shown to be remarkably accurate even when k or m₁, . . . ,m_k are not very large.     

A strong law for weighted sums of i.i.d. random variables

A strong law is proved for weighted sumsS _n=a _in X _i whereX _i are i.i.d. and {a _in} is an array of constants. When sup(n ^–1|a _in | ^q )^1/q <, 1<q andX _i are mean zero, we showE|X| ^p <,p ^l+q ^–1=1 impliesS _n /n 0. Whenq= this reduces to a result of Choi and Sung who showed that when the {a _in} are uniformly bounded,EX=0 andE|X|< impliesS _n /n 0. The result is also true whenq=1 under the additional assumption that lim sup |a _in |n ^–1 logn=0. Extensions to more general normalizing sequences are also given. In particular we show that when the {a _in} are uniformly bounded,E|X|^1/< impliesS _n /n 0 for >1, but this is not true in general for 1/2<<1, even when theX _i are symmetric. In that case the additional assumption that (x ^1/ log^1/–1 x)P(|X|x)0 asx provides necessary and sufficient conditions for this to hold for all (fixed) uniformly bounded arrays {a _in}.     

Convergence of the steepest descent method for minimizing quasiconvex functions

To minimize a continuously differentiable quasiconvex functionf: ⁿ , Armijo's steepest descent method generates a sequencex ^k+1 =x ^k –t _k f(x ^k ), wheret _k >0. We establish strong convergence properties of this classic method: either , s.t. ; or arg minf = , x ^k andf(x ^k ) inff. We also discuss extensions to other line searches.The research of the first author was supported by the Polish Academy of Sciences. The second author acknowledges the support of the Department of Industrial Engineering, Hong Kong University of Science and Technology.We wish to thank two anonymous referees for their valuable comments. In particular, one referee has suggested the use of quasiconvexity instead of convexity off.     

Approximate maximum likelihood estimation in linear regression

The application of the ML method in linear regression requires a parametric form for the error density. When this is not available, the density may be parameterized by its cumulants ( _i ) and the ML then applied. Results are obtained when the standardized cumulants ( _i ) satisfy _i = _i+2/ ₂ ^(i+2)/2 =O(v ⁱ ) asv 0 fori>0.Research financed in part by the Research Center of the Athens University of Economics and Business.     

A Distance-Regular Graph with Strongly Closed Subgraphs

Let be a distance-regular graph of diameter d, valency k and r := maxi | (c _i,b _i) = (c ₁,b ₁). Let q be an integer with r + 1 q d – 1.In this paper we prove the following results: Theorem 1 Suppose for any pair of vertices at distance q there exists a strongly closed subgraph of diameter q containing them. Then for any integer i with 1 i q and for any pair of vertices at distance i there exists a strongly closed subgraph of diameter i containing them. Theorem 2 If r 2, then c _2r+3 1.As a corollary of Theorem 2 we have d k ²(r + 1) if r 2.