Asymptotically minimax tests of composite hypotheses

Summary X ₁,,X> _n are independent, identically distributed random variables with common density function f(x¦ ₁ ,, _k , _k+1 ), assumed to satisfy certain standard regularity conditions. The k+1 parameters are unknown, and the problem is to test the hypothesis that _k+1 =b against the alternative that _k+1 =b+cn ^–1/2 . ₁ ,, _k are nuisance parameters. For this problem, the following artificial problem is temporarily substituted. It is known that ¦ ₁ -a _i ¦n ^–1/2 M(n) for i=1,,k, where a ₁ , ,a _k are known, and M(n) approaches infinity as n increases but n ^–1/2 M(n) approaches zero as n increases. A Bayes decision rule is constructed for this artificial problem, relative to the a priori distribution which assigns weight A to _k+1 =b, and weight 1-A to _k+1 =b+cn ^–1/2 , in each case the weight being spread uniformly over the possible values of ₁ ,, _k in the artificial problem. An analysis of the structure of the Bayes rule shows that if estimates of ₁ ,..., _k are substituted for a ₁ ..., a _k respectively, the resulting rule is a solution to the original problem, and this rule has the same asymptotic properties as a solution to the artificial problem as the Bayes rule for the artificial problem, no matter what the values a ₁ ..., a _k are.Research supported by the U.S. Air Force under Grant AF-AFOSR-68-1472.     

Optimal pairs of score vectors for positional scoring rules

Letw=(w ₁,,w _m ) andv=(v ₁,,v _m-1 ) be nonincreasing real vectors withw ₁>w _m andv ₁>v _m-1 . With respect to a lista ₁,,a _n of linear orders on a setA ofm3 elements, thew-score ofaA is the sum overi from 1 tom ofw _i times the number of orders in the list that ranka inith place; thev-score ofaA{b} is defined in a similar manner after a designated elementb is removed from everya _j .We are concerned with pairs (w, v) which maximize the probability that anaA with the greatestw-score also has the greatestv-score inA{b} whenb is randomly selected fromA{a}. Our model assumes that linear ordersa _j onA are independently selected according to the uniform distribution over them linear orders onA. It considers the limit probabilityP _m (w, v) forn that the element inA with the greatestw-score also has the greatestv-score inA{b}.It is shown thatP _m (m,v) takes on its maximum value if and only if bothw andv are linear, so thatw _i –w _i+1=w _i+1–w _i+2 forim–2, andv _i –v _i+1 =v _i+1 –v _i+2 forim–3. This general result for allm3 supplements related results for linear score vectors obtained previously form{3,4}.     

A basis for the type 〈n〉 hyperidentities of the medial variety of semigroups

Summary The medical varietyMV of semigroups is the variety defined by the medial identityxyzw = xzyw. This variety is known to satisfy the medial hyperidentitiesF(G(x ₁₁ ,, x _1n ),, G(x _n1 ,, x _nn )) = G(F(x ₁₁ ,, x _n1 ),, F(x _1n ,, x _nn )), forn 1. Taylor has observed in [2] thatMV also satisfies some other hyperidentities, which are not consequences of the medial ones. In [4] the author introduced a countably infinite family of binary hyperidentities called transposition hyperidentities, which are natural generalizations of then = 2 medial hyperidentity. It was shown that this family is irredundant, and that no finite basis is possible for theMV hyperidentities with one binary operation symbol.In this paper, we generalize the concept of a transposition hyperidentity, and extend it to cover arbitrary arityn 2. We show that theMV hyperidentities with onen-ary operation symbol have no finite basis, but do have a countably infinite basis consisting of these transposition hyperidentities.Research supported by NSERC of Canada.     

Knaster's problem on continuous maps of a sphere into Euclidean space

A survey of known results and additional new ones on Knaster's problem: on the standard sphere S^n–1Rⁿ find configurations of points A₁, , A_k, such that for any continuous map fS^n–1R^m one can find a rotation a of the sphere S^n–1 such that f(a(A₁)==f(a(A_k)) and some problems closely connected with it. We study the connection of Knaster's problem with equivariant mappings, with Dvoretsky's theorem on the existence of an almost spherical section of a multidimensional convex body, and we also study the set {a S0(n)f(a(A₁))==f(a(A_k))} of solutions of Knaster's problem for a fixed configuration of points A₁, , A_kS^n–1 and a map fS^n–1R^m in general position. Unsolved problems are posed.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 167, pp. 169–178, 1987.     

Penalty function versus non-penalty function methods for constrained nonlinear programming problems

The relative merits of using sequential unconstrained methods for solving: minimizef(x) subject tog _i (x) 0, i = 1, , m, h _j (x) = 0, j = 1, , p versus methods which handle the constraints directly are explored. Nonlinearly constrained problems are emphasized. Both classes of methods are analyzed as to parameter selection requirements, convergence to first and second-order Kuhn-Tucker Points, rate of convergence, matrix conditioning problems and computations required.This paper was presented at the 7th Mathematical Programming Symposium 1970, The Hague, The Netherlands.     

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.     

A distance constrainedp-facility location problem on the real line

LetV = {v ₁,, v _n } be a set ofn points on the real line (existing facilities). The problem considered is to locatep new point facilities,F ₁,, F _p , inV while satisfying distance constraints between pairs of existing and new facilities and between pairs of new facilities. Fori = 1, , p, j = 1, , n, the cost of locatingF _i at pointv _j isc _ij . The objective is to minimize the total cost of setting up the new facilities. We present anO(p ³ n ² logn) algorithm to solve the model.     

The complete figure for second order multiple integral problems in the calculus of variations

Notation Throughout this paper Greek indices, , , and Latin indicesi, j, h, k, assume the values 1, ,m, and 1, ,n respectively. The summation convention is operative in respect of both sets of indices.This work was supported by the South African Council for Scientific and Industrial Research.At time of writing Professor Grässer was Visiting Scholar at the University of Arizona, Tucson, Arizona.     

The Braided product of Ockham algebras

In this paper we introduce an algebraic concept of the product of Ockham algebras called the Braided product. We show that ifL _i MS(i=1, 2, ,n) then the Braided product ofL _i(i=1, 2, ,n) exists if and only ifL ₁, ,L _n have isomorphic skeletons.     

On a characterization of polynomials by divided differences

Summary We consider the functional equationf[x ₁,x ₂,, x _n ] =h(x ₁ + +x _n ) (x ₁,,x _n K, x _j x _k forj k), (D) wheref[x ₁,x ₂,,x _n ] denotes the (n – 1)-st divided difference off and prove Theorem. Let n be an integer, n 2, let K be a field, char(K) 2, with # K 8(n – 2) + 2. Let, furthermore, f, h: K K be functions. Then we have that f, h fulfil (D) if, and only if, there are constants a_j K, 0 j n (a := a_n, b := a_{n – 1}) such thatf = ax ⁿ +bx ^{n – 1} + +a ₀ and h = ax + b.     

A class of simplicial restart fixed point algorithms without an extra dimension

In an earlier paper we introduced an algorithm for approximating a fixed point of a mapping on the product space of unit simplices. Ideas of that paper are used to construct a class of triangulations ofR ⁿ. More precisely, for somek, 1 k n, and positive integersm ₁ , m_k with sumn, a triangulation ofR ⁿ is obtained by triangulating the cells which are formed by taking the product of given triangulations ofR ^mj, j = 1, ,k. The triangulation of each cell will be defined in relation to an arbitrarily chosen pointv inR ⁿ, being the starting point of the algorithm. Fork = n we obtain theK triangulation originally due to Todd. Each element of the class can be used to find a simplex which approximates a fixed point of a mapping onR ⁿ by generating a unique path of adjacent simplices of variable dimension starting with the pointv. We also give convergence conditions. It is indicated how in casek = n a connected set of fixed points can be generated. Moreover, we give some computational experience.     

Two-sided polynomial approximation of functions

Conditions are established when the collocation polynomials P_m(x) and P_M(x), m M, constructed respectively using the system of nodes x_j of multiplicities a_j 1, j = O,, n, and the system of nodes x_-r,,x_o,,x_n,,x_n+r1, r O, r₁ O, of multiplicities a_-r,,(a_o + y_o),,(a_n + y_n),,a_n+r1, a_j + y_j 1, are two sided-approximations of the function f on the intervals , x_j[, j = O,...,n + 1, and on unions of any number of these intervals. In this case, the polynomials P_m (x), P_M ^(l) (x) with l a_j are two-sided approximations of the function f⁽¹⁾ in the neighborhood of the node x_j and the integrals of the polynomials P_m(x), P_M(x) over D_j are two-sided approximations of the integral of the function f (over D_j). If the multiplicities a_j a_j + y_j of the nodes x_j are even, then this is also true for integrals over the set _j= _µ ^k D_j µ 1, k n. It is shown that noncollocation polynomials (Fourier polynomials, etc.) do not have these properties.Kiev University. Translated from Vychislitel'naya i Prikladnaya Matematika, No. 67, pp. 31–37, 1989.     

Infinitesimal obstructions to weakly mixing

Let ^t be the flow (parametrized with respect to arc length) of a smooth unit vector field v on a closed Riemannian manifold M ⁿ , whose orbits are geodesics. Then the (n-1)-plane field normal to v, v, is invariant under d ^t and, for each x M, we define a smooth real function _x (t) : (1 + _i (t)), where the _i(t) are the eigenvalues of AA ^T, A being the matrix (with respect to orthonormal bases) of the non-singular linear map d^2t , restricted to v at the point _x ^-t M ⁿ.Among other things, we prove the Theorem (Theorem II, below). Assume v is also volume preserving and that _x ^' (t) 0 for all x M and real t; then, if _x ^t : M M is weakly missng for some t, it is necessary that vx 0 at all x M.     

Mathematical expectations of functions of sums of a random number of independent terms

Conditions are found which must be imposed on a function g(x) in order that M g(₁+₂+ + _v < if M g(_i) < and M g(v) < ,, ₁, ₂, , _n, ... being non-negative and independent, being integral, and {_i} being identically distributed. The result is applied to the theory of branching processes.Translated from Matematicheskie Zametki, Vol. 3, No. 4, pp. 387–394, April, 1968.     

Large-Deviation Local Theorem for Additive Functionals of a Markov Gaussian Field. I

We prove a local limit theorem (LLT) on Cramer-type large deviations for sums S _V = _t V ( _t ), where _t , t Z , 1, is a Markov Gaussian random field, V Z , and is a bounded Borel function. We get an estimate from below for the variance of S _V and construct two classes of functions , for which the LLT of large deviations holds.     

Monomial gorenstein curves in A4 as set-theoretic complete intersections

It is shown that if the prime ideal ,, x₄], k an arbitrary field, has generic zero x_i=tⁿ _i, n_i positive integers with g.c.d. equal l, l i 4, then P(S) is a set-theoretic complete intersection if the numerical semigroup S=1,, n₄> is symmetric (i.e. if the extension of P(S) in k[[x₁,, x₄]] is a Gorenstein ideal).     

A preconditioner for constrained and weighted least squares problems with Toeplitz structure

We study methods for solving the constrained and weighted least squares problem min _x by the preconditioned conjugate gradient (PCG) method. HereW = diag (₁, , _m ) with _{1 m} 0, andA ^T = [T ₁ ^T , ,T _k ^T ] with Toeplitz blocksT _l R ^{n × n} ,l = 1, ,k. It is well-known that this problem can be solved by solving anaugmented linear 2 × 2 block linear systemM +Ax =b, A ^T = 0, whereM =W ^–1. We will use the PCG method with circulant-like preconditioner for solving the system. We show that the spectrum of the preconditioned matrix is clustered around one. When the PCG method is applied to solve the system, we can expect a fast convergence rate.Research supported by HKRGC grants no. CUHK 178/93E and CUHK 316/94E.     

On the automorphism conjecture for products of ordered sets

I. Rival and A. Rutkowski conjectured that the ratio of the number of automorphisms of an arbitrary poset to the number of order-preserving maps tends to zero as the size of the poset tends to infinity. We prove this hypothesis for direct products of arbitrary posets P=S ₁××S _n under the condition that max_i|S_i|=0(n/logn).     

Verschärfung einer Ungleichung von Ky Fan

Summary In this paper we prove the following:IfA _n ,G _n andH _n (resp.A _n ,G _n andH _n ) denote the arithmetic, geometric and harmonic means ofa ₁,, a _n (resp. 1 –a ₁,, 1 –a _n ) and ifa _i (0, 1/2],i = 1,,n, then(G _n /G _n ) ⁿ (A _n /A _n ) ^n-1 H _n /H _n , (^*) with equality holding forn = 1,2. Forn 3 equality holds if and only ifa ₁ = =a _n . The inequality (^*) sharpens the well-known inequality of Ky Fan:G _n /G _n A _n /A _n .

     

Über lineare Unabhängigkeit

It is the aim of the present work to prove, under appropriate conditions, lower estimates for the dimension of w ₁ + ... + w _m over , wherew ₁,...,w _m are given real numbers. In particular, if this dimension ism, i.e. ifw ₁,...,w _m are linearly independent over , we are also interested in a quantitative version of this fact. Our qualitative theorems generalize a result of Nesterenko. Its formulation is quite similar to the axiomatization of methods for algebraic independence, as it became usual during the last decade.