Theorems of large deviations in the multivariate invariance principle

Let B be a real separable Banach space with norm |ß|_B, X, X₁, X₂, … be a sequence of centered independent identically distributed random variables taking values in B. Let s_n = s_n(t), 0 ≤ t ≤ 1 be the random broken line such that s_n(0) = 0, s_n(k/n) = n^−1/2 Σ_i=1^k X_i for n = 1, 2, … and k = 1, …, n. Denote |s_n|_B = sup_{0 ≤ t ≤ 1} |s_n(t)|_B and assume that w(t), 0 ≤ t ≤ 1 is the Wiener process such that covariances of w(1) and X are equal. We show that under appropriate conditions P(|s_n|_B > r) = P(|w|_B > r)(1 + o(1)) and give estimates of the remainder term. The results are new already in the case of B having finite dimension.     

Counting cycles and finite dimensional L norms

We obtain sharp bounds for the number of n-cycles in a finite graph as a function of the number of edges, and prove that the complete graph is optimal in more ways than could be imagined. We prove sharp estimates on both ∑_i=1ⁿx_i^k and ∑_i=1ⁿ|x_i|^k, subject to the constraints that ∑_i=1ⁿx_i²=C and ∑_i=1ⁿx_i=0.     

A sufficient condition for pairing problem of generators in symmetrizable Kac–Moody algebras

In a symmetrizable Kac–Moody algebra g(A), let α=∑_i=1ⁿk_iα_i be an imaginary root satisfying k_i>0 and α,α_i<0 for i=1,2,…,n. In this paper, it is proved that for any x_αg_α{0}, satisfying [x_α,f_n]≠0 and [x_α,f_i]=0 for i=1,2,…,n−1, there exists a vector y such that the subalgebra generated by x_α and y contains g′(A), the derived subalgebra of g(A).     

Selection in Monotone Matrices and Computingkth Nearest Neighbors

Anm×nmatrix =(a_{i, j}), 1≤i≤mand 1≤j≤n, is called atotally monotonematrix if for alli₁, i₂, j₁, j₂, satisfying 1≤i₁<i₂≤m, 1≤j₁<j₂≤n.[formula]We present an[formula]time algorithm to select thekth smallest item from anm×ntotally monotone matrix for anyk≤mn. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for ageneralized row-selection problemin monotone matrices. Given a setS={p₁,…, p_n} ofnpoints in convex position and a vectork={k₁,…, k_n}, we also present anO(n^4/3log^c n) algorithm to compute thek_ith nearest neighbor ofp_ifor everyi≤n; herecis an appropriate constant. This algorithm is considerably faster than the one based on a row-selection algorithm for monotone matrices. If the points ofSare arbitrary, then thek_ith nearest neighbor ofp_i, for alli≤n, can be computed in timeO(n^7/5 log^c n), which also improves upon the previously best-known result.     

Complexity results for scheduling tasks with discrete starting times

Suppose that n independent tasks are to be scheduled without preemption on a set of identical parallel processors. Each task T_i requires a given execution time τ_i and it may be started for execution on any processor at any of its prescribed starting times s_i1, s_i2, …, s_iki, with k_i ≤ k for some fixed integer k. We first prove that the problem of finding a feasible schedule on a single processor is NP-complete in the strong sense even when τ_i ε {τ, τ′} and k_i ≤ 3 for 1 ≤ i ≤ n. The same problem is, however, shown to be solvable in O(n log n) time, provided s_iki − s_i1 < τ_i for 1 ≤ i ≤ n. We then show that the problem of finding a feasible schedule on an arbitrary number of processors is strongly NP-complete even when τ_i ε {τ, τ′}, k_i = 2 and s_i2 − s_i1 = δ < τ_i for 1 ≤ i ≤ n. Finally a special case with k_i = 2 and s_i2 − s_i1 = 1, 1 ≤ i ≤ n, of the above multiprocessor scheduling problem is shown to be solvable in polynomial time.     

A self-normalized Erd s—Rényi type strong law of large numbers

The original Erd s—Rényi theorem states that max_0kn∑^k+[clogn]_i=k+1X_i/[clogn]→α(c),c>0, almost surely for i.i.d. random variables {X_n, n1} with mean zero and finite moment generating function in a neighbourhood of zero. The latter condition is also necessary for the Erd s—Rényi theorem, and the function α(c) uniquely determines the distribution function of X₁. We prove that if the normalizing constant [c log n] is replaced by the random variable ∑^k+[clogn]_i=k+1(X²_i+1), then a corresponding result remains true under assuming only the exist first moment, or that the underlying distribution is symmetric.     

Permanence and global stability in a Lotka-Volterra predator-prey system with delays

Consider the permanence and global asymptotic stability of models governed by the following Lotka-Volterra-type system:

, with initial conditions

x_i(t) = φ_i(t) ≥ o, t ≤ t₀, and φ_i(t₀) > 0. 1 ≤ i ≤n

. We define x₀(t) = x_n+1(t)≡0 and suppose that φ_i(t), 1 ≤ i ≤ n, are bounded continuous functions on [t₀, + ∞) and γ_i, α_i, c_i > 0,γ_i,j ≥ 0, for all relevant i,j.Extending a technique of Saito, Hara and Ma[1] for n = 2 to the above system for n ≥ 2, we offer sufficient conditions for permanence and global asymptotic stability of the solutions which improve the well-known result of Gopalsamy.     

Algebraic Approaches to Periodic Arithmetical Maps

A residue class a + n with weight λ is denoted by λ, a, n. For a finite system = {λ_s, a_s, n_s}^k_{s = 1} of such triples, the periodic map w (x) = ∑_{ns|x − as} λ_s is called the covering map of . Some interesting identities for those with a fixed covering map have been known; in this paper we mainly determine all those functions f : Ω → such that ∑^k_{s = 1} λ_sf(a_s + n_s ) depends only on w where Ω denotes the family of all residue classes. We also study algebraic structures related to such maps f, and periods of arithmetical functions ψ(x) = ∑^k_{s = 1} λ_se^2πia_sx/n_s and ω(x) = |{1 ≤ s ≤ k : (x + a_s, n_s) = 1}|.     

On subspace arrangements of type

Let denote the subspace arrangement formed by all linear subspaces in given by equations of the form

₁x_i1=₂x_i2==_kx_ik,

where 1i₁<<i_kn and (₁,…,_k){+1,−1}^k.Some important topological properties of such a subspace arrangement depend on the topology of its intersection lattice. In a previous work on a larger class of subspace arrangements by Björner and Sagan (J. Algebraic Combin. 5 (1996) 291–314) the topology of the intersection lattice turned out to be a particularly interesting and difficult case.We prove in this paper that Pure(Π_n,k^±) is shellable, hence that Π_n,k^± is shellable for k>n/2. Moreover, we prove that unless i≡n−2 (mod k−2) or i≡n−3 (mod k−2), and that is free abelian for i≡n−2 (mod k−2). In the special case of Π_2k,k^± we determine homology completely. Our tools are generalized lexicographic shellability, as introduced in Kozlov (Ann. Combin. 1 (1997) 67–90), and a spectral sequence method for the computation of poset homology first used in Hanlon (Trans. Amer. Math. Soc. 325 (1991) 1–37).We state implications of our results on the cohomology of the complements of the considered arrangements.     

Uniform bound in the central limit theorem for Banach space valued dependent random variables

Let F be a Banach space with a sufficiently smooth norm. Let (X_i)_i≤n be a sequence in L_F², and T be a Gaussian random variable T which has the same covariance as X = Σ_i≤nX_i. Assume that there exists a constant G such that for s, δ≥0, we have P(sTs+δ)Gδ. (*) We then give explicit bounds of Δ(X) = sup_i|P(|X|≤t)−P(|T|≤t)| in terms of truncated moments of the variables X_i. These bounds hold under rather mild weak dependence conditions of the variables. We also construct a Gaussian random variable that violates (^*).     

On improved estimators of the generalized variance

Treated in this paper is the problem of estimating with squared error loss the generalized variance | Σ | from a Wishart random matrix S: p × p W_p(n, Σ) and an independent normal random matrix X: p × k N(ξ, Σ I_k) with ξ(p × k) unknown. Denote the columns of X by X₍₁₎ ,…, X_(k) and set ψ⁽⁰⁾(S, X) = {(n − p + 2)!/(n + 2)!} | S |, ψ⁽ⁱ⁾(X, X) = min[ψ⁽ⁱ⁻¹⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!} | S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |] and Ψ⁽ⁱ⁾(S, X) = min[ψ⁽⁰⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!}| S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |], i = 1,…,k. Our result is that the minimax, best affine equivariant estimator ψ⁽⁰⁾(S, X) is dominated by each of Ψ⁽ⁱ⁾(S, X), i = 1,…,k and for every i, ψ⁽ⁱ⁾(S, X) is better than ψ⁽ⁱ⁻¹⁾(S, X). In particular, ψ^(k)(S, X) = min[{(n − p + 2)!/(n + 2)!} | S |, {(n − p + 2)!/(n + 2)!} | S + X₍₁₎X′₍₁₎|,…,| {(n − p + k + 2)!/(n + k + 2)!} | S + X₍₁₎X′₍₁₎ + + X_(k)X′_(k)|] dominates all other ψ's. It is obtained by considering a multivariate extension of Stein's result (Ann. Inst. Statist. Math. 16, 155–160 (1964)) on the estimation of the normal variance.     

Uniform Estimates for a Class of Evolution Equations

L^∞ estimates are derived for the oscillatory integral ∫⁺₀^∞e^{−i(xλ + (1/m) tλm)}a(λ) dλ, where 2 ≤ m and (x, t) × ₊. The amplitude a(λ) can be oscillatory, e.g., a(λ) = e^{it (λ)} with (λ) a polynomial of degree ≤ m − 1, or it can be of polynomial type, e.g., a(λ) = (1 + λ)^k with 0 ≤ k ≤ (m − 2). The estimates are applied to the study of solutions of certain linear pseudodifferential equations, of the generalized Schrödinger or Airy type, and of associated semilinear equations.     

Strong and weak convergence theorems for asymptotically nonexpansive mappings

Suppose K is a nonempty closed convex nonexpansive retract of a real uniformly convex Banach space E with P as a nonexpansive retraction. Let T :K→E be an asymptotically nonexpansive nonself-map with sequence {k_n}_n1[1,∞), limk_n=1, F(T):={xK: Tx=x}≠. Suppose {x_n}_n1 is generated iteratively by

where {α_n}_n1(0,1) is such that ε<1−α_n<1−ε for some ε>0. It is proved that (I−T) is demiclosed at 0. Moreover, if ∑_n1(k_n²−1)<∞ and T is completely continuous, strong convergence of {x_n} to some x^*F(T) is proved. If T is not assumed to be completely continuous but E also has a Fréchet differentiable norm, then weak convergence of {x_n} to some x^*F(T) is obtained.     

Schur functions and the invariant polynomials characterizing U(n) tensor operators

We give a direct formulation of the invariant polynomials _μG_q⁽ⁿ⁾(, Δ_i,;, x_{i,i + 1},) characterizing U(n) tensor operators p, q, …, q, 0, …, 0 in terms of the symmetric functions S_λ known as Schur functions. To this end, we show after the change of variables Δ_i = γ_i − δ_i and x_{i, i + 1} = δ_i − δ_{i + 1} that_μG_q⁽ⁿ⁾(,Δ_i;, x_{i, i + 1},) becomes an integral linear combination of products of Schur functions S_α(, γ_i,) · S_β(, δ_i,) in the variables {γ₁,…, γ_n} and {δ₁,…, δ_n}, respectively. That is, we give a direct proof that _μG_q⁽ⁿ⁾(,Δ_i,;, x_{i, i + 1},) is a bisymmetric polynomial with integer coefficients in the variables {γ₁,…, γ_n} and {δ₁,…, δ_n}. By making further use of basic properties of Schur functions such as the Littlewood-Richardson rule, we prove several remarkable new symmetries for the yet more general bisymmetric polynomials _μ^mG_q⁽ⁿ⁾(γ₁,…, γ_n; δ₁,…, δ_m). These new symmetries enable us to give an explicit formula for both _μ^mG₁⁽ⁿ⁾(γ; δ) and ₁G₂⁽ⁿ⁾(γ; δ). In addition, we describe both algebraic and numerical integration methods for deriving general polynomial formulas for _μ^mG_q⁽ⁿ⁾(γ; δ).     

Precise asymptotics in some strong limit theorems for multidimensionally indexed random variables

Consider Z₊^d (d2)—the positive d-dimensional lattice points with partial ordering , let {X_k,kZ₊^d} be i.i.d. random variables with mean 0, and set S_n=∑_knX_k, nZ₊^d. We establish precise asymptotics for ∑_n|n|^r/p−2P(|S_n||n|^1/p), and for

Full-size image

, (0δ1) as 0, and for

Full-size image

as .     

L∞-upper bound of L2-projections onto splines at a geometric mesh

For an integer k 1 and a geometric mesh (qⁱ)_−∞^∞ with q ε (0, ∞), let M_i,k(x): = k[q^{i + k}](· − x)₊^{k − 1}, N_i,k(x): = (q^{i + k} − qⁱM_i,k(x)/k, and let A_k(q) be the Gram matrix (∝M_i,kN_j,k)_i,jεz. It is known that A_k(q)⁻¹_∞ is bounded independently of q. In this paper it is shown that A_k(q)⁻¹_∞ is strictly decreasing for q in [1, ∞). In particular, the sharp upper bound and lower bound for A_k (q)⁻¹ are obtained: for all q ε (0, ∞).     

An asymptotic minimax risk bound for estimation of a linear functional relationship

We consider estimation of the parameter B in a multivariate linear functional relationship X_i=ξ_i+ξ_1i, Y_i=Bξ_i+ξ_2i, i=1,…,n, where the errors (ζ_1i^′, ζ_2i^′) are independent standard normal and (ξ_i, i ) is a sequence of unknown nonrandom vectors (incidental parameters). If there are no substantial a priori restrictions on the infinite sequence of incidental parameters then asymptotically the model is nonparametric but does not fit into common settings presupposing a parameter from a metric function space. A special result of the local asymptotic minimax type for the m.1.e. of B is proved. The accuracy of the normal approximation for the m.l.e. of order n^−1/2 is also established.     

Free resolutions in multivariable operator theory

Let be the complex polynomial ring in d variables. A contractive -module is Hilbert space equipped with an action such that for any ,

||z₁ξ₁+z₂ξ++z_dξ_d||²||ξ₁||²+||ξ₂||²++||ξ_d||².

Such objects have been shown to be useful for modeling d-tuples of mutually commuting operators acting on a Hilbert space. There is a subclass of the category of contractive modules whose members play the role of free objects. Given a contractive -module, one can construct a free resolution, i.e. an exact sequence of partial isometries of the following form:

(*)

where is a free module for each i0. The notion of a localization of a free resolution will be defined, in which for each λB_d there is a vector space complex of linear maps derived from (*):

We shall show that the homology of this complex is isomorphic to the homology of the Koszul complex of the d-tuple (¹,²,…,^d), of where ⁱ is the ith coordinate function of a Möbius transform on B_d such that (λ)=0.     

On numerical improvement of Gauss–Legendre quadrature rules

Among all integration rules with n points, it is well-known that n-point Gauss–Legendre quadrature rule∫₋₁¹f(x) dx∑_i=1ⁿw_if(x_i)has the highest possible precision degree and is analytically exact for polynomials of degree at most 2n−1, where nodes x_i are zeros of Legendre polynomial P_n(x), and w_i's are corresponding weights.In this paper we are going to estimate numerical values of nodes x_i and weights w_i so that the absolute error of introduced quadrature rule is less than a preassigned tolerance ε₀, say ε₀=10⁻⁸, for monomial functionsf(x)=x^j, j=0,1,…,2n+1.(Two monomials more than precision degree of Gauss–Legendre quadrature rules.) We also consider some conditions under which the new rules act, numerically, more accurate than the corresponding Gauss–Legendre rules. Some examples are given to show the numerical superiority of presented rules.     

On the Behaviour of Zeros of Jacobi Polynomials

Denote by x_n,k(α,β) and x_n,k(λ)=x_n,k(λ−1/2,λ−1/2) the zeros, in decreasing order, of the Jacobi polynomial P^(α,β)_n(x) and of the ultraspherical (Gegenbauer) polynomial C^λ_n(x), respectively. The monotonicity of x_n,k(α,β) as functions of α and β, α,β>−1, is investigated. Necessary conditions such that the zeros of P^(a,b)_n(x) are smaller (greater) than the zeros of P^(α,β)_n(x) are provided. A. Markov proved that x_n,k(a,b)<x_n,k(α,β) (x_n,k(a,b)>x_n,k(α,β)) for every n and each k, 1kn if a>α and b<β (a<α and b>β). We prove the converse statement of Markov's theorem. The question of how large the function f_n(λ) could be such that the products f_n(λ)x_n,k(λ), k=1,…,[n/2] are increasing functions of λ, for λ>−1/2, is also discussed. Elbert and Siafarikas proved that f_n(λ)=(λ+(2n²+1)/(4n+2))^1/2 obeys this property. We establish the sharpness of their result.