On L 1 Bounds for Asymptotic Normality of Some Weakly Dependent Random Variables

In the present paper, we consider L ₁ bounds for asymptotic normality for the sequence of r.v.’s X ₁,X ₂,… (not necessarily stationary) satisfying the ψ-mixing condition. The L ₁ bounds have been obtained in terms of Lyapunov fractions which, in a particular case, under finiteness of the third moments of summands and the finiteness of ∑ _r≥1 r ² ψ(r), are of order O(n ^−1/2), where the function ψ participates in the definition of the ψ-mixing condition.      

When Some Complement of a Submodule Is a Summand

A module M is said to satisfy the C ₁₁ condition if every submodule of M has a (i.e., at least one) complement which is a direct summand. It is known that the C ₁ condition implies the C ₁₁ condition and that the class of C ₁₁-modules is closed under direct sums but not under direct summands. We show that if M = M ₁ ⊕ M ₂, where M has C ₁₁ and M ₁ is a fully invariant submodule of M, then both M ₁ and M ₂ are C ₁₁-modules. Moreover, the C ₁₁ condition is shown to be closed under formation of the ring of column finite matrices of size Γ, the ring of m-by-m upper triangular matrices and right essential overrings. For a module M, we also show that all essential extensions of M satisfying C ₁₁ are essential extensions of C ₁₁-modules constructed from M and certain subsets of idempotent elements of the ring of endomorphisms of the injective hull of M. Finally, we prove that if M is a C ₁₁-module, then so is its rational hull. Examples are provided to illustrate and delimit the theory.     

On the interpolation of some generalized function spaces of different anisotropy

In the paper, the interpolation properties of the spacesH _p ^s (v; ℝ _n ) of Sobolev-Liouville type and the spacesB _{p, q} ^s (μ ℝ _n ) of Nikol'skii-Besov type generated by functions of polynomial growth that are infinitely differentiable outside of the origin are studied. Interpolation formulas for the pairs {H(v _o ),H(v ₁)} and {B(μ₀),B(μ₁)} of spaces of the above types for which the anisotropies of the interpolated spaces do not depend on each other are proved. The investigated spaces, for certain specification of the generating functions, coincide with the classical (isotropic and anisotropic) Sobolev-Liouville and Nikol'skii-Besov spaces. Translated fromMatematicheskie Zametki, Vol. 62, No. 5, pp. 666–672, November, 1997. Translated by A. I. Shtern     

<Emphasis Type="Italic">G</Emphasis>-compactness and groups

Lascar described E _KP as a composition of E _L and the topological closure of E _L (Casanovas et al. in J Math Log 1(2):305–319). We generalize this result to some other pairs of equivalence relations. Motivated by an attempt to construct a new example of a non-G-compact theory, we consider the following example. Assume G is a group definable in a structure M. We define a structure M′ consisting of M and X as two sorts, where X is an affine copy of G and in M′ we have the structure of M and the action of G on X. We prove that the Lascar group of M′ is a semi-direct product of the Lascar group of M and G/G _L . We discuss the relationship between G-compactness of M and M′. This example may yield new examples of non-G-compact theories. The first author is supported by the Polish Goverment grant N N201 384134. The second author is supported by the Polish Goverment grant N201 032 32/2231.     

Interval Valued Intuitionistic （S, T）-fuzzy Hv-submodules

On the basis of the concept of the interval valued intuitionistic fuzzy sets introduced by K. Atanassov, the notion of interval valued intuitionistic fuzzy Hv-submodules of an Hv-module with respect to a t-norm T and an s-norm S is given and the characteristic properties are described. The homomorphic image and the inverse image are investigated. In particular, the connections between interval valued intuitionistic （S, T）-fuzzy Hv-submodules and interval valued intuitionistic （S, T）-fuzzy submodules are discussed.     

On products of unbounded operators

A symmetric operator X^ is attached to each operator X that leaves the domain of a given positive operator A invariant and makes the product AX symmetric. Some spectral properties of X^ are derived from those of X and, as a consequence, various conditions ensuring positivity of products of the form AX ₁ ... X _n are proved. The question of ^-complete positivity of the mapping p → Ap(X ₁,...,X _n) defined on complex polynomials in n variables is investigated. It is shown that the set ω is related to the McIntosh-Pryde joint spectrum of (X ₁,...,X _n) in case all the operators A, X ₁,...,X _n are bounded. Examples illustrating the theme of the paper are included. This revised version was published online in June 2006 with corrections to the Cover Date.     

<Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-mixed intersection bodies

In this paper the author first introduce a new concept of L _p -dual mixed volumes of star bodies which extends the classical dual mixed volumes. Moreover, we extend the notions of L _p intersection body to L _p -mixed intersection body. Inequalities for L _p -dual mixed volumes of L _p -mixed intersection bodies are established and the results established here provide new estimates for these type of inequalities. This work was supported by the Natural Science Foundation of Zhejiang Province of China (Grant No. Y605065) and the Foundation of the Education Department of Zhejiang Province of China (Grant No. 20050392)     

Arithmetical properties of the number of t-core partitions

Let Λ={λ ₁≥⋅⋅⋅≥λ _s ≥1} be a partition of an integer n. Then the Ferrers-Young diagram of Λ is an array of nodes with λ _i nodes in the ith row. Let λ _j ′ denote the number of nodes in column j in the Ferrers-Young diagram of Λ. The hook number of the (i,j) node in the Ferrers-Young diagram of Λ is denoted by H(i,j):=λ _i +λ _j ′−i−j+1. A partition of n is called a t-core partition of n if none of the hook numbers is a multiple of t. The number of t-core partitions of n is denoted by a(t;n). In the present paper, some congruences and distribution properties of the number of 2 ^t -core partitions of n are obtained. A simple convolution identity for t-cores is also given.      

Moments and Distribution of the Local Times of a Transient Random Walk on ℤ d

Consider an arbitrary transient random walk on ℤ ^d with d∈ℕ. Pick α∈[0,∞), and let L _n (α) be the spatial sum of the αth power of the n-step local times of the walk. Hence, L _n (0) is the range, L _n (1)=n+1, and for integers α, L _n (α) is the number of the α-fold self-intersections of the walk. We prove a strong law of large numbers for L _n (α) as n→∞. Furthermore, we identify the asymptotic law of the local time in a random site uniformly distributed over the range. These results complement and contrast analogous results for recurrent walks in two dimensions recently derived by Černy (Stoch. Proc. Appl. 117:262–270, 2007). Although these assertions are certainly known to experts, we could find no proof in the literature in this generality.      

On the ε-entropy of classes of holomorphic functions

Suppose thatB _R ^d is a ball of radiusR in ℂ ^d and σ is the standard measure on the unit sphere in ℂ ^d . ForR>1, 1≤p≤∞, and for the natural numbersl, d, byH _R ⁰ (l, p, d) we denote the class of functionsf holomorphic inB _R ^d and such that in the homogeneous polynomial expansion of the firstl summands the zero and radial derivatives of orderl belong to the closed unit ball of the Hardy spaceH ^p (B _R ^d ). In this paper an asymptotic formula for the ε-entropy of the classH _R ⁰ (l, p, d) in the spacesL ^p (σ), 1≤p<∞, and is obtained. Translated fromMatematicheskie Zametki, Vol. 68, No. 2, pp. 286–293, August, 2000.     

On the Hardness of Computing Intersection,Union and Minkowski Sum of Polytopes

For polytopes P ₁,P ₂⊂ℝ ^d , we consider the intersection P ₁∩P ₂, the convex hull of the union CH(P ₁∪P ₂), and the Minkowski sum P ₁+P ₂. For the Minkowski sum, we prove that enumerating the facets of P ₁+P ₂ is NP-hard if P ₁ and P ₂ are specified by facets, or if P ₁ is specified by vertices and P ₂ is a polyhedral cone specified by facets. For the intersection, we prove that computing the facets or the vertices of the intersection of two polytopes is NP-hard if one of them is given by vertices and the other by facets. Also, computing the vertices of the intersection of two polytopes given by vertices is shown to be NP-hard. Analogous results for computing the convex hull of the union of two polytopes follow from polar duality. All of the hardness results are established by showing that the appropriate decision version, for each of these problems, is NP-complete.     

The maximum of a Lévy process reflected at a general barrier

We investigate the reflection of a Lévy process at a deterministic, time-dependent barrier and in particular properties of the global maximum of the reflected Lévy process. Under the assumption of a finite Laplace exponent, ψ(θ)$\psi \left(\theta \right)$, and the existence of a solution θ^∗>0${\theta }^{\ast }>0$ to ψ(θ)=0$\psi \left(\theta \right)=0$ we derive conditions in terms of the barrier for almost sure finiteness of the maximum. If the maximum is finite almost surely, we show that the tail of its distribution decays like Kexp(−θ^∗x)$Kexp(-{\theta }^{\ast }x)$. The constant K$K$ can be completely characterized, and we present several possible representations. Some special cases where the constant can be computed explicitly are treated in greater detail, for instance Brownian motion with a linear or a piecewise linear barrier. In the context of queuing and storage models the barrier has an interpretation as a time-dependent maximal capacity. In risk theory the barrier can be interpreted as a time-dependent strategy for (continuous) dividend pay out.     

Limitations of learning in automata-based systems

In this article, we aim to analyze the limitations of learning in automata-based systems by introducing the L⁺$L^{+}$ algorithm to replicate quasi-perfect learning, i.e., a situation in which the learner can get the correct answer to any of his queries. This extreme assumption allows the generalization of any limitations of the learning algorithm to less sophisticated learning systems. We analyze the conditions under which the L⁺$L^{+}$ infers the correct automaton and when it fails to do so. In the context of the repeated prisoners’ dilemma, we exemplify how the L⁺$L^{+}$ may fail to learn the correct automaton. We prove that a sufficient condition for the L⁺$L^{+}$ algorithm to learn the correct automaton is to use a large number of look-ahead steps. Finally, we show empirically, in the product differentiation problem, that the computational time of the L⁺$L^{+}$ algorithm is polynomial on the number of states but exponential on the number of agents.     

Rates of Best Uniform Rational Approximation of Analytic Functions by Ray Sequences of Rational Functions

In this paper, problems related to the approximation of a holomorphic function f on a compact subset E of the complex plane C by rational functions from the class of all rational functions of order (n,m) are considered. Let ρ _n,m = ρ _n,m (f;E) be the distance of f in the uniform metric on E from the class . We obtain results characterizing the rate of convergence to zero of the sequence of the best rational approximation { ρ _n,m(n) } _n=0 ^∞ , m(n)/n → θ ∈ (0,1] as n → ∞ . In particular, we give an upper estimate for the liminf _{n →∞} ρ _n,m(n) ^1/(n+m(n)) in terms of the solution to a certain minimum energy problem with respect to the logarithmic potential. The proofs of the results obtained are based on the methods of the theory of Hankel operators. June 16, 1997. Date revised: December 1, 1997. Date accepted: December 1, 1997. Communicated by Ronald A. DeVore.     

Superconvergence of Legendre projection methods for the eigenvalue problem of a compact integral operator

In this paper, we consider the Galerkin and collocation methods for the eigenvalue problem of a compact integral operator with a smooth kernel using the Legendre polynomials of degree ≤n. We prove that the error bounds for eigenvalues are of the order O(n^−2r) and the gap between the spectral subspaces are of the orders O(n^−r) in L₂-norm and O(n^1/2−r) in the infinity norm, where r denotes the smoothness of the kernel. By iterating the eigenvectors we show that the iterated eigenvectors converge with the orders of convergence O(n^−2r) in both L₂-norm and infinity norm. We illustrate our results with numerical examples.     

On a class of equilibrium problems in the real axis

In a series of seminal papers, Thomas J. Stieltjes (1856-1894) gave an elegant electrostatic interpretation for the zeros of classical families of orthogonal polynomials, such as Jacobi, Hermite and Laguerre polynomials. More generally, he extended this approach to the zeros of polynomial solutions of certain second-order linear differential equations (Lamé equations), the so-called Heine-Stieltjes polynomials.In this paper, a class of electrostatic equilibrium problems in R, where the free unit charges x₁,…,x_n∈R are in presence of a finite family of “attractors” (i.e., negative charges) z₁,…,z_m∈C?R, is considered and its connection with certain class of Lamé-type equations is shown. In addition, we study the situation when both n→∞ and m→∞, by analyzing the corresponding (continuous) equilibrium problem in presence of a certain class of external fields.     

Block-Coordinate Gradient Descent Method for?Linearly Constrained Nonsmooth Separable Optimization

We consider the problem of minimizing the weighted sum of a smooth function f and a convex function P of n real variables subject to m linear equality constraints. We propose a block-coordinate gradient descent method for solving this problem, with the coordinate block chosen by a Gauss-Southwell-q rule based on sufficient predicted descent. We establish global convergence to first-order stationarity for this method and, under a local error bound assumption, linear rate of convergence. If f is convex with Lipschitz continuous gradient, then the method terminates in O(n ²/ε) iterations with an ε-optimal solution. If P is separable, then the Gauss-Southwell-q rule is implementable in O(n) operations when m=1 and in O(n ²) operations when m>1. In the special case of support vector machines training, for which f is convex quadratic, P is separable, and m=1, this complexity bound is comparable to the best known bound for decomposition methods. If f is convex, then, by gradually reducing the weight on P to zero, the method can be adapted to solve the bilevel problem of minimizing P over the set of minima of f+δ _X , where X denotes the closure of the feasible set. This has application in the least 1-norm solution of maximum-likelihood estimation. This research was supported by the National Science Foundation, Grant No. DMS-0511283.     

Multivariate Gini Indices

Two extensions of the univariate Gini index are considered:R_D, based on expected distance between two independent vectors from the same distribution with finite meanμ ^d; andR_V, related to the expected volume of the simplex formed fromd+1 independent such vectors. A new characterization ofR_Das proportional to a univariate Gini index for a particular linear combination of attributes relates it to the Lorenz zonoid. TheLorenz zonoidwas suggested as a multivariate generalization of the Lorenz curve.R_Vis, up to scaling, the volume of the Lorenz zonoid plus a unit cube of full dimension. Whend=1, bothR_DandR_Vequal twice the area between the usual Lorenz curve and the line of zero disparity. Whend>1, they are different, but inherit properties of the univariate Gini index and are related via the Lorenz zonoid:R_Dis proportional to the average of the areas of some two-dimensioned projections of the lift zonoid, whileR_Vis the average of the volumes of projections of the Lorenz zonoid over all coordinate subspaces.