Expansions for von Mises functionals

Summary Berry-Esseen results and expansions are derived for the distribution function of von Mises functionals of order r under moment conditions and conditions on the smoothness of the limit distribution.The results apply to goodness-of-fit statistics — as well as to the central limit theorem in L ^2p,p2, the rate of convergence being O(n ^–1) for centered balls, provided a fourth moment exists.Research sponsored in part under Office of Naval Research. Contract Number N00014-80-C-0163.     

Halfspace range search: An algorithmic application ofk-sets

Given a fixed setS ofn points inE ³ and a query plane, the halfspace range search problem asks for the retrieval of all points ofS on a chosen side of. We prove that withO(n(logn)⁸ (loglogn)⁴) storage it is possible to solve this problem inO(k+logn) time, wherek is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the total number ofj-sets (j=1, ...,k) realized by a set ofn points inE ³ isO(nk ⁵); ak-set is any subset ofS of sizek which can be separated from the rest ofS by a plane.Supported in part by NSF grants MCS 83-03925 and the Office of Naval Research and the Defense Advanced Research Projects Agency under contract N00014-83-K-0146 and ARPA Order No. 4786.Supported in part by Joint Services Electronics Program under Contract N00014-79-C-0424.     

Methods of conjugate directions versus quasi-Newton methods

It is shown that algorithms for minimizing an unconstrained functionF(x), x E ⁿ , which are solely methods of conjugate directions can be expected to exhibit only ann or (n–1) step superlinear rate of convergence to an isolated local minimizer. This is contrasted with quasi-Newton methods which can be expected to exhibit every step superlinear convergence. Similar statements about a quadratic rate of convergence hold when a Lipschitz condition is placed on the second derivatives ofF(x). Research was supported in part by Army Research Office, Contract Number DAHC 19-69-C-0017 and the Office of Naval Research, Contract Number N00014-71-C-0116 (NR 047-99).     

Asymptotic Formulae and Divisor Problems

We investigate the asymptotic behaviour of the summatory functions of _z(n, ), _k(n, ) z ⁽ⁿ⁾ and _k(n, ) z ⁽ⁿ⁾.     

Optimal radius of convergence of interpolatory iterations for operator equations

The convergence of the class of direct interpolatory iterationsI _n for a simple zero of a non-linear operatorF in a Banach space of finite or infinite dimension is studied.A general convergence result is established and used to show that ifF is entire the radius of convergence goes to infinity withn while ifF is analytic in a ball of radiusR the radius of convergence increases to at leastR/2 withn.The research was supported in part by the National Science Foundation under Grant MCS 75-222-55 and the office of Naval Research under Contract N00014-76-C-0370, NR 044-422.     

Triple Positive Solutions for Multipoint Conjugate Boundary Value Problems

For the nth order nonlinear differential equation y ⁽ⁿ⁾(t)=f(y(t)), t [0,1], satisfying the multipoint conjugate boundary conditions, y ^(j)(a_i) = 0,1 i k, 0 j n _i - 1, 0 =a ₁ < a ₂ < < a _k = 1, and _i=1 ^k n _i =n, where f: [0, ) is continuous, growth condtions are imposed on f which yield the existence of at least three solutions that belong to a cone.     

Law of the iterated logarithm for perturbed empirical distribution functions evaluated at a random point for nonstationary random variables

We consider perturbed empirical distribution functions , where {Ginn, n1} is a sequence of continuous distribution functions converging weakly to the distribution function of unit mass at 0, and {X _{i, i}1} is a non-stationary sequence of absolutely regular random variables. We derive the almost sure representation and the law of the iterated logarithm for the statistic whereU _n is aU-statistic based onX ₁,...,X _n . The results obtained extend or generalize the results of Nadaraya,⁽⁷⁾ Winter,⁽¹⁶⁾ Puri and Ralescu,^(9,10) Oodaira and Yoshihara,⁽⁸⁾ and Yoshihara,⁽¹⁹⁾ among others.Research supported by the Office of Naval Research Contract N00014-91-J-1020.     

Maximal order for quadratures usingn evaluations

The problem is to find approximationsI (f; h) to the integralI(f; h)= ₀ ^h f. Such an approximation has local orderp ifI(f; h)–I (f; h)=O(h ^p ) ash0. Let(n) denote the maximal local order possible for a method usingn evaluations of a function or its derivatives. We show that (n)=2n+1 if the information used is Hermitian. This is conjectured to be true in general. The conjecture is established for all methods using three or fewer evaluations.This research was supported in part by the National Science Foundation under Grant MCS75-222-55 and the Office of Naval Research under Contract N00014-76-C-0370, NR 044-422. Numerical results reported in this paper were obtained through the computing facilities of the University of Maryland.     

The numerical solution of boundary value problems for second order functional differential equations by finite differences

The boundary value problem , 0 <t < 1,x(0)=x(1)=0, is considered. Hereg:R ²R ¹ andF:C[0, 1] C[0, 1]. The solutionx is approximated using finite differences. For a large class of problems it is proved that the approximate solutions exist and converge tox. The method is illustrated by the numerical example.Sponsored by the Mathematics Research Center, United States Army, Madison, Wisconsin, under Contract No.: DA-31-124-ARO-D-462, and the Office of Naval Research under Contract No.: N00014-67-A-0128-0004. The computations were supported by the University of Wisconsin Grants Committee.     

Higher order asymptotic theory for normalizing transformations of maximum likelihood estimators

Suppose thatX _n =(X ₁,...X _n) is a collection ofm-dimensional random vectorsX _i forming a stochastic process with a parameter . Let be the MLE of . We assume that a transformationA( ) of has thek-thorder Edgeworth expansion (k=2,3). IfA extinguishes the terms in the Edgeworth expansion up tok-th-order (k2), then we say thatA is thek-th-order normalizing transformation. In this paper, we elucidate thek-th-order asymptotics of the normalizing transformations. Some conditions forA to be thek-th-order normalizing transformation will be given. Our results are very general, and can be applied to the i.i.d. case, multivariate analysis and time series analysis. Finally, we also study thek-th-order asymptotics of a modified signed log likelihood ratio in terms of the Edgeworth approximation.Research supported by the Office of Naval Research Contract N00014-91-J-1020.     

Random Walks Crossing High Level Curved Boundaries

Let {S _n} be a random walk, generated by i.i.d. increments X _i which drifts weakly to in the sense that as n . Suppose k0, k1, and E|X ₁|^1\k = if k>1. Then we show that the probability that S. crosses the curve nan ^K before it crosses the curve n –an ^k tends to 1 as a . This intuitively plausible result is not true for k = 1, however, and for 1/2 <k<1, the converse results are not true in general, either. More general boundaries g(n) than g(n) = n ^k are also considered, and we also prove similar results for first passages out of regions like { (n, y): n1, |y| (a + n) ^k } as a .     

Solution manifolds and submanifolds of parametrized equations and their discretization errors

Summary The paper concerns solution manifolds of nonlinear parameterdependent equations (1)F(u, )=y₀ involving a Fredholm operatorF between (infinite-dimensional) Banach spacesX=Z× andY, and a finitedimensional parameter space . Differntial-geometric ideas are used to discuss the connection between augmented equations and certain onedimensional submanifolds produced by numerical path-tracing procedures. Then, for arbitrary (finite) dimension of , estimates of the error between the solution manifold of (1) and its discretizations are developed. These estimates are shown to be applicable to rather general nonlinear boundaryvalue problems for partial differential equations.This work was in part supported by the U.S. Air Force Office of Scientific Research under Grant 80-0176, the National Science Foundation under Grant MCS-78-05299, and the Office of Naval Research under Contract N-00014-80-C-0455     

Implicitly defined optimization problems

This paper considers the solution of the problem: inff[y, x(y)] s.t.y [y, x(y)] E ^k , wherex(y) solves: minF(x, y) s.t.x R(x, y) E ⁿ . In order to obtain local solutions, a first-order algorithm, which uses {dx(y)/dy} for solving a special case of the implicitly definedy-problem, is given. The derivative is obtained from {dx(y, r)/dy}, wherer is a penalty function parameter and {x(y, r)} are approximations to the solution of thex-problem given by a sequential minimization algorithm. Conditions are stated under whichx(y, r) and {dx(y, r)/dy} exist. The computation of {dx(y, r)/dy} requires the availability of _y F(x, y) and the partial derivatives of the other functions defining the setR(x, y) with respect to the parametersy.Research sponsored by National Science Foundation Grant ECS-8709795 and Office of Naval Research Contract N00014-89-J-1537. We thank the referees for constructive comments on an earlier version of this paper.     

Explicit matchings in the middle levels of the Boolean lattice

New classes of explicit matchings for the bipartite graph (k) consisting of the middle two levels of the Boolean lattice on 2k+1 elements are constructed and counted. This research is part of an ongoing effort to show that (k) is Hamiltonian.Supported by Office of Naval Research contract N00014-85K-0494.Supported by National Science Foundation grant DMS-8041281.     

Fibers in Ore Extensions

Let R be a finitely generated commutative algebra over an algebraically closed field k and let A=R[t;,] be the Ore extension with respect to an automorphism and a -derivation . We view A as the coordinate ring of an affine noncommutative space X. The inclusion RA gives an affine map : XSpecR, and X is a noncommutative analogue of A ¹×SpecR. We define the fiber X _p of over a closed point pSpecR as a certain full subcategory ModX _p of ModA. The category ModX _p has the following structure. If p has infinite -orbit, then ModX _p is equivalent to the category of graded modules over the polynomial ring k[x] with degx=1. If p is not fixed by , but has finite -orbit, say of size n, then ModX _p is equivalent to the representations of the quiver à _n–1 with the arrows all going in the same direction. If p is fixed by , then ModX _p is equivalent to either Modk or Modk[x]. It is also shown that X is the disjoint union of the fibers X _p in a certain sense.     

An invariance principle for the local time of a recurrent random walk

Summary Let (S _j ) be a lattice random walk, i.e. S _j =X ₁ +...+X _j , where X ₁,X ₂,... are independent random variables with values in the integer lattice and common distribution F, and let , the local time of the random walk at k before time n. Suppose EX ₁=0 and F is in the domain of attraction of a stable law G of index > 1, i.e. there exists a sequence a(n) (necessarily of the form n ¹l(n), where l is slowly varying) such that S _n /a(n) G. Define , where c(n)=a(n/log log n) and [x] = greatest integer x. Then we identify the limit set of {g _n (, ·) n1} almost surely with a nonrandom set in terms of the I-functional of Donsker and Varadhan.The limit set is the one that Donsker and Varadhan obtain for the corresponding problem for a stable process. Several corollaries are then derived from this invariance principle which describe the asymptotic behavior of L _n (, ·) as n.Research partially supported by NSF Grant #MCS 78-01168. These results were announced at the Fifteenth European Meeting of Statisticians, Palermo, Italy (September, 1982)     

Limit Theorems for the Maximum Terms of a Sequence of Random Variables with Marginal Geometric Distributions

Let X _n1 ^* , ... X _nn ^* be a sequence of n independent random variables which have a geometric distribution with the parameter p _n = 1/n, and M _n ^* = \max\{X _n1 ^* , ... X _nn ^* }. Let Z ₁, Z₂, Z₃, ... be a sequence of independent random variables with the uniform distribution over the set N _n = {1, 2, ... n}. For each j N _n let us denote X _nj = min{k : Z_k = j}, M _n = max{X_n1, ... X_nn}, and let S _n be the 2nd largest among X _n1, X_n2, ... X_nn. Using the methodology of verifying D(u_n) and D'(u_n) mixing conditions we prove herein that the maximum M _n has the same type I limiting distribution as the maximum M _n ^* and estimate the rate of convergence. The limiting bivariate distribution of (S_n, M_n) is also obtained. Let _n, _n N_n, , and T _n = min{M(A_n), M(B_n)}. We determine herein the limiting distribution of random variable T _n in the case _n , _n/_n > 0, as n .     

Algorithms for optimization problems with exclusion constraints

This paper proposes algorithms for minimizing a continuously differentiable functionf(x): ⁿ subject to the constraint thatx does not lie in specified bounded subsets of ⁿ . Such problems arise in a variety of applications, such as tolerance design of electronic circuits and obstacle avoidance in the selection of trajectories for robot arms. Such constraints have the form . The function is not continuously differentiable. Algorithms based on the use of generalized gradients have considerable disadvantages because of the local concavity of at points where the set {j|g ^j (x)=(x)} has more than one element. Algorithms which avoid these disadvantrages are presented, and their convergence is established.This research was sponsored in part by the National Science Foundation under Grant ECS-81-21149, the Air Force Office of Scientific Research (AFSC), United States Air Force under Contract F49620-79-C-0178, the Office of Naval Research under Grant N00014-83-K-0602, the Air Force Office of Scientific Research under Grant AFOSR-83-0361, and the Semiconductor Research Consortium under Grant SRC-82-11-008.     

Norming operators for generalized domains of attraction

A sequence of independent and identically distributed random vectorsX _n on ^k is said to belong to the generalized domain of attraction of a nondegenerate random vectorY on ^k provided that there exist linear operatorsA _n on ^k and nonrandom constantsb _n ^k such that the centered and normalized partial sumsA _n (X ₁++X _n –b _n converge in distribution toY. In this paper we show that the sequence of norming operatorsA _n can always be chosen to vary regularly.Partially supported by NSF Grant DMS-91-03131 at Albion College.     

Homotopies for computation of fixed points on unbounded regions

Givenf: R ⁿ R ^n* with some conditions, our aim is to compute a fixed pointx f(x) off; hereR ⁿ isn-dimensional Euclidean space andR ^n* is the collection of nonempty subsets ofR ⁿ . A typical application of the algorithm can be motivated as follows: Beginning with the constant mapf ₀:R ⁿ {0} R ⁿ and its fixed pointx ₀ = 0, we deformf _t ast tof f and follow the pathx _t of fixed points off _t . Cluster points of thex _t 's ast are fixed points off. This research was supported in part by Army Research Office-Durham Contract DAHC-04-71-C-0041 and by National Science Foundation Grant GK-5695.