An improved asymptotic analysis of the expected number of pivot steps required by the simplex algorithm

Leta ₁ ...,a _m be i.i.d. points uniformly on the unit sphere in ⁿ ,m n 3, and letX:= {x ⁿ |a _i ^T x1} be the random polyhedron generated bya ₁, ...,a _m . Furthermore, for linearly independent vectorsu, in ⁿ , letS _u , (X) be the number of shadow vertices ofX inspan(u,). The paper provides an asymptotic expansion of the expectation value¯S _n,m := _in4 ¹ E(S _u, ) for fixedn andm .¯S _n,m equals the expected number of pivot steps that the shadow vertex algorithm — a parametric variant of the simplex algorithm — requires in order to solve linear programming problems of type max u ^T ,xX, if the algorithm will be started with anX-vertex solving the problem max ^T ,x X. Our analysis is closely related to Borgwardt's probabilistic analysis of the simplex algorithm. We obtain a refined asymptotic analysis of the expected number of pivot steps required by the shadow vertex algorithm for uniformly on the sphere distributed data.     

Positivity Preserving Forms have the Fatou Property

We prove that if (,D) is a positivity preserving form on L ² (E;m), and if (u _n)_n is a sequence in D() converging m-almost everywhere to u L ² (E;m), then (u,u) lim inf_n (u _n ,u _n ).     

The distribution of the likelihood ratio for mixtures of densities from the one-parameter exponential family

We here consider testing the hypothesis ofhomogeneity against the alternative of a two-component mixture of densities. The paper focuses on the asymptotic null distribution of 2 log _n , where _n is the likelihood ratio statistic. The main result, obtained by simulation, is that its limiting distribution appears pivotal (in the sense of constant percentiles over the unknown parameter), but model specific (differs if the model is changed from Poisson to normal, say), and is not at all well approximated by the conventional ₍₂₎ ² -distribution obtained by counting parameters. In Section 3, the binomial with sample size parameter 2 is considered. Via a simple geometric characterization the case for which the likelihood ratio is 1 can easily be identified and the corresponding probability is found. Closed form expressions for the likelihood ratio _n are possible and the asymptotic distribution of 2 log _n is shown to be the mixture giving equal weights to the one point distribution with all its mass equal to zero and the ²-distribution with 1 degree of freedom. A similar result is reached in Section 4 for the Poisson with a small parameter value (0.1), although the geometric characterization is different. In Section 5 we consider the Poisson case in full generality. There is still a positive asymptotic probability that the likelihood ratio is 1. The upper precentiles of the null distribution of 2 log _n are found by simulation for various populations and shown to be nearly independent of the population parameter, and approximately equal to the (1–2)100 percentiles of ₍₁₎ ² . In Sections 6 and 7, we close with a study of two continuous densities, theexponential and thenormal with known variance. In these models the asymptotic distribution of 2 log _n is pivotal. Selected (1–) 100 percentiles are presented and shown to differ between the two models.     

On discrete and continuous norms in Paley-Wiener spaces and consequences for exponential frames

It is well known that for certain sequences {t_n}_n the usual L^p norm ·_p in the Paley-Wiener space PW ^p is equivalent to the discrete norm f_p,{tn}:=( _n=– |f(t_n)|^p)^1/p for 1 p = < and f_,{tn}:=sup _n|f(t_n| for p=). We estimate f_p from above by Cf_p, _n and give an explicit value for C depending only on p, , and characteristic parameters of the sequence {t_n}_n. This includes an explicit lower frame bound in a famous theorem of Duffin and Schaeffer.     

A functional inequality for real-analytic functions

Summary Forf ( C ⁿ() and 0 t x letJ _n (f, t, x) = (–1)ⁿ f(–x)f ⁽ⁿ⁾(t) +f(x)f ⁽ⁿ⁾ (–t). We prove that the only real-analytic functions satisfyingJ _n (f, t, x) 0 for alln = 0, 1, 2, are the exponential functionsf(x) = c e ^x,c, . Further we present a nontrivial class of real-analytic functions satisfying the inequalitiesJ ₀ (f, x, x) 0 and ₀ ^x (x – t)^{n – 1}J_n(f, t, x)dt 0 (n 1).     

Comparison results for the lower tail of Gaussian seminorms

Let =( _n ) be i.i.d.N(0, 1) random variables andq(x), q(x):R [0, ) be seminorms. We investigate necessary and sufficient conditions that the ratio ofP(q()<) andP(q()<) goes to a positive constant as 0⁺. We give satisfactory answers forl ₂-norms and also some results for sup-norms andl _p-norms. Some applications are given to the rate of escape of infinite dimensional Brownian motion, and we give the lower tail of the Ornstein-Uhlenbeck process and a weighted Brownian bridge under theL ₂-norms.     

A Bernstein result for energy minimizing hypersurfaces

We show that there are no entire, positive, stable solutions in ⁿ of the Euler equation corresponding to the singular variational integral ,>0, if+n<5.236.... Furthermore we prove a related result for smooth boundaries of least-energy |x _n+1||D _U | in ⁿ⁺¹.     

Angular limits of holomorphic functions which satisfy an integrability condition

Let (–1,1), let 2/(1–)p<, letp denote the Hölder conjugate ofp, and let be an open arc of the unit circle. It is shown that, iff is a holomorphic function on the unit disc such that: (i) (1–|z|)log⁺|f(z)| isL ^p -integrable on the sector {r:0f has an infinite asymptotic value has -finite (2–(1+)p)-dimensional Hausdorff, measure, thenf has finite angular limits on a subset of of positive linear measure. In fact, a stronger conclusion will be established.     

Stability and Attraction to Normality for Lévy Processes at Zero and at Infinity

We prove some limiting results for a Lévy process X _t as t0 or t, with a view to their ultimate application in boundary crossing problems for continuous time processes. In the present paper we are mostly concerned with ideas related to relative stability and attraction to the normal distribution on the one hand and divergence to large values of the Lévy process on the other. The aim is to find analytical conditions for these kinds of behaviour which are in terms of the characteristics of the process, rather than its distribution. Some surprising results occur, especially for the case t0; for example, we may have X _t /t ^P + (t0) (weak divergence to +), whereas X _t /t a.s. (t0) is impossible (both are possible when t), and the former can occur when the negative Lévy spectral component dominates the positive, in a certain sense. Almost sure stability of X _t , i.e., X _t tending to a nonzero constant a.s. as t or as t0, after normalisation by a non-stochastic measurable function, reduces to the same type of convergence but with normalisation by t, thus is equivalent to strong law behaviour. Boundary crossing problems which are amenable to the methods we develop arise in areas such as sequential analysis and option pricing problems in finance.     

Fast Summation of Power Series with Coefficients Analytic at Infinity

We propose a fast summation algorithm for slowly convergent power series of the form _{j=j 0} z ^j _j j _i=1 ^s (j+ _i )^– _i , where R, _i 0 and _i C, 1is, are known parameters, and _j =(j), being a given real or complex function, analytic at infinity. Such series embody many cases treated by specific methods in the recent literature on acceleration. Our approach rests on explicit asymptotic summation, started from the efficient numerical computation of the Laurent coefficients of . The effectiveness of the resulting method, termed ASM (Asymptotic Summation Method), is shown by several numerical tests.     

A characterization of subgroups of the orthogonal group

LetG be a subgroup of the general linear group GL_n(K), where charK 2. Put Kⁿ =V. AssumeG is generated by the setS of all elements inG for which dimV( – 1) = 1, and suppose ²=1_V for each inS. If {V(–1)¦S} contains a simplex, if – 1_V G, and if inG is a product of dim v(–1) elements inS wheneverV(–1) is not contained in the kernel of–1, thenG is a subgroup of an orthogonal group.This research was supported in part by NSERC Canada grant A7251.To Helmut Mäurer on his 60th birthday     

Rates of convergence and optimal spectral bandwidth for long range dependence

Summary For a realization of lengthn from a covariance stationary discrete time process with spectral density which behaves like ^1–2H as 0+ for 1/2<H<1 (apart from a slowly varying factor which may be of unknown form), we consider a discrete average of the periodogram across the frequencies 2j/n,j=1,..., m, wherem andm/n0 asn. We study the rate of convergence of an analogue of the mean squared error of smooth spectral density estimates, and deduce an optimal choice ofm.     

Mappings that preserve cones in Lobachevskii space

Let ⁿ be n-dimensional Lobachevskii space, and {l_x:x ⁿ} be a family of lines, parallel to a linel ₀, 0ⁿ (in a given direction). Let {c_x:Xⁿ} be a family of circular cones in ⁿ of opening with axes l_X and vertex X. Then, iff:ⁿⁿ(n>2) is a bijective mapping andf(C_x)=C _f(x), it follows thatf is a motion in the space ⁿ.Translated from Matematicheskie Zametki, Vol. 13, No. 5, pp. 687–694, May, 1973.     

On a problem of Erdös and Alladi

We give an estimate for the quantity {f(n):nx, p(n)y}, wherep(n) denotes the greatest prime factor ofn andf belongs to a certain class of multiplicative functions. As an application, we show that for the Moebius function, ({(n):nx, p(n)y}) ({1:nx, p(n)y})^–1 tends to zero, asx, uniformly iny2, and thus settle a conjecture of Erdös.Supported by a grant from the Deutsche Forschungsgesellschaft.     

Fibred links and a construction of real singularities via complex geometry

This note gives a method for constructing real analytic maps from ²ⁿ into ², with an isolated critical point at 0 ²ⁿ , for alln>1. This provides infinite families of real singularities which fiber a la Milnor.Research partially supported by CONACYT, Mexico, grant 1206-E92103.     

Estimation of the Multivariate Normal Precision Matrix under the Entropy Loss

Let X ₁, , X _n (n > p) be a random sample from multivariate normal distribution N _p (, ), where R ^p and is a positive definite matrix, both and being unknown. We consider the problem of estimating the precision matrix ^–1. In this paper it is shown that for the entropy loss, the best lower-triangular affine equivariant minimax estimator of ^–1 is inadmissible and an improved estimator is explicitly constructed. Note that our improved estimator is obtained from the class of lower-triangular scale equivariant estimators.     

The central limit theorem for Chébli-Trimèche hypergroups

Let (S _nn>-1) be a random walk on a hypergroup ( ₊ , *), i.e., a Markov chain with transition kernelN(x, A) = _x * (A), where is a fixed probability measure on ₊ such that the second moment exists. Then depending on the growth of the hypergroup two situations can occur: when ( ₊ , *) is of exponential growth then it is shown thatS _n is asymptotically normal. In the case of polynomial growth {more precisely, if the densityA of the Haar measure of ( ₊ , *) satisfies lim[A()/A()]=}, the normalized variablesS _n/[n Var()/(+1)]^1/2 converge to a Rayleigh distribution with parameter .     

On Asymptotic Structure,the Szlenk Index and UKK Properties in Banach Spaces

Let B be a separable Banach space and let X=B ^* be separable. We prove that if B has finite Szlenk index (for all > 0) then B can be renormed to have the weak* uniform Kadec-Klee property. Thus if > 0 there exists () > 0 so that if x _n is a sequence in the ball of X converging ^* to x so that . In addition we show that the norm can be chosen so that () c^p for some p < and c >0.     

Über den algorithmischen Nachweis von Ungleichungen I

We shall develop a method to prove inequalities in a unified manner. The idea is as follows: It is quite often possible to find a continuous functional : ⁿ , such that the left- and the right-hand side of a given inequality can be written in the form (u)(v) for suitable points,v=v(u). If one now constructs a map ^{n n} , which is functional increasing (i.e. for each x ⁿ (which is not a fixed point of ) the inequality (x)<((x)) should hold) one specially gets the chain (u)( u))( ²(u))... ⁿ (u)). Under quite general conditions one finds that the sequence { ⁿ (u)} _n converges tov=v(u). As a consequence one obtains the inequality (u)(v).     

On feasible sets defined through Chebyshev approximation

LetZ be a compact set of the real space with at leastn + 2 points;f,h1,h2:Z continuous functions,h1,h2 strictly positive andP(x,z),x(x ₀,...,x _n ) ⁿ⁺¹,z , a polynomial of degree at mostn. Consider a feasible setM {x ⁿ⁺¹z Z, –h ₂(z) P(x, z)–f(z)h ₁(z)}. Here it is proved the null vector 0 of ⁿ⁺¹ belongs to the compact convex hull of the gradients ± (1,z,...,z ⁿ ), wherez Z are the index points in which the constraint functions are active for a givenx* M, if and only ifM is a singleton.This work was partially supported by CONACYT-MEXICO.