A uniform bound for the deviation of empirical distribution functions

If X₁, …, X_n are independent R^d-valued random vectors with common distribution function F, and if F_n is the empirical distribution function for X₁, …, X_n, then, among other things, it is shown that P{sup_x F_n(x) ε} 2e²(2n)^de^−2nε2 for all nε² ≥ d². The inequality remains valid if the X_i are not identically distributed and F(x) is replaced by Σ_iP{X_i ≤ x}/n.     

Local polynomial fitting under association

We consider the estimation of multivariate regression functions r(x₁,…,x_d) and their partial derivatives up to a total order p1 using high-order local polynomial fitting. The processes {Y_i,X_i} are assumed to be (jointly) associated. Joint asymptotic normality is established for the estimates of the regression function r and all its partial derivatives up to the total order p. Expressions for the bias and variance/covariance matrix (of the asymptotic distribution) are given.     

A central limit theorem for generalized multilinear forms

Let X₁, …, X_n be independent random variables and define for each finite subset I {1, …, n} the σ-algebra = σ{X_i : i ε I}. In this paper -measurable random variables W_I are considered, subject to the centering condition E(W_I ) = 0 a.s. unless I J. A central limit theorem is proven for d-homogeneous sums W(n) = Σ_{I = d}W_I, with var W(n) = 1, where the summation extends over all (_n^d) subsets I {1, …, n} of size I = d, under the condition that the normed fourth moment of W(n) tends to 3. Under some extra conditions the condition is also necessary.     

Robust M-estimators of location vectors

Let X₁,…,X_n be i.i.d. random vectors in R^m, let θεR^m be an unknown location parameter, and assume that the restriction of the distribution of X₁−θ to a sphere of radius d belongs to a specified neighborhood of distributions spherically symmetric about 0. Under regularity conditions on and d, the parameter θ in this model is identifiable, and consistent M-estimators of θ (i.e., solutions of Σ_i=1ⁿψ(|X_i− |)(X_i− )=0) are obtained by using “re-descenders,” i.e., ψ's wh satisfy ψ(x)=0 for x≥c. An iterative method for solving for is shown to produce consistent and asymptotically normal estimates of θ under all distributions in . The following asymptotic robustness problem is considered: finding the ψ which is best among the re-descenders according to Huber's minimax variance criterion.     

On a generalization of a theorem of Erdős and Fuchs

Let A={a₁,a₂,…}(a₁<a₂<) be an infinite sequence of nonnegative integers, let k≥2 be a fixed integer and denote by r_k(A,n) the number of solutions of a_i1+a_i2++a_ik≤n. Montgomery and Vaughan proved that r₂(A,n)=cn+o(n^1/4) cannot hold for any constant c>0. In this paper, we extend this result to k>2.     

Minimax estimation of the mean of spherically symmetric distributions under general quadratic loss

For X one observation on a p-dimensional (p ≥ 4) spherically symmetric (s.s.) distribution about θ, minimax estimators whose risks dominate the risk of X (the best invariant procedure) are found with respect to general quadratic loss, L(δ, θ) = (δ − θ)′ D(δ − θ) where D is a known p × p positive definite matrix. For C a p × p known positive definite matrix, conditions are given under which estimators of the form δ_a,r,C,D(X) = (I − (ar(|X|²)) D^−1/2CD^1/2 |X|⁻²)X are minimax with smaller risk than X. For the problem of estimating the mean when n observations X₁, X₂, …, X_n are taken on a p-dimensional s.s. distribution about θ, any spherically symmetric translation invariant estimator, δ(X₁, X₂, …, X_n), with have a s.s. distribution about θ. Among the estimators which have these properties are best invariant estimators, sample means and maximum likelihood estimators. Moreover, under certain conditions, improved robust estimators can be found.     

On a family of sequences defined recursively in (II)

This paper is a second part to previous work (see Finite Fields Appl. 9 (2003) 211). Different conjectures stated there are proven here. We are concerned with sequences (x_i)_i1 in such that the continued fraction expansion [x₁T,x₂T,…,x_nT,…] in is algebraic over . These algebraic elements correspond in some way to quadratic real numbers for which the continued fraction expansion is well known.     

Almost poised basic hypergeometric series

Given a basic hypergeometric series with numerator parametersa ₁,a ₂, ...,a _r and denominator parametersb ₂, ...,b _r, we say it isalmost poised ifb _i, =a ₁ q ^δ,i a _i,δ_i = 0, 1 or 2, for 2 ≤i ≤r. Identities are given for almost poised series withr = 3 andr = 5 when a₁, =q ⁻²ⁿ. Partially supported by N.S.F. Grant No. DMS-8521580.     

On the enumeration of parking functions by leading terms

Let x=(x₁,…,x_n) be a sequence of positive integers. An x-parking function is a sequence (a₁,…,a_n) of positive integers whose non-decreasing rearrangement b₁b_n satisfies b_ix₁++x_i. In this paper we give a combinatorial approach to the enumeration of (a,b,…,b)-parking functions by their leading terms, which covers the special cases x=(1,…,1), (a,1,…,1), and (b,…,b). The approach relies on bijections between the x-parking functions and labeled rooted forests. To serve this purpose, we present a simple method for establishing the required bijections. Some bijective results between certain sets of x-parking functions of distinct leading terms are also given.     

L1-optimal estimates for a regression type function in R

Let X₁, X₂, …, X_n be random vectors that take values in a compact set in R^d, d ≥ 1. Let Y₁, Y₂, …, Y_n be random variables (“the responses”) which conditionally on X₁ = x₁, …, X_n = x_n are independent with densities f(y | x_i, θ(x_i)), i = 1, …, n. Assuming that θ lives in a sup-norm compact space Θ_q,d of real valued functions, an optimal L₁-consistent estimator of θ is constructed via empirical measures. The rate of convergence of the estimator to the true parameter θ depends on Kolmogorov's entropy of Θ_q,d.     

On a conjecture of J. Pelikán

There exist infinitely many finite sequences (a₁, …, a_n) (a_i {0, 1}) such that Φ_{i = 1}^{n − k} a_ia_{i + k} is odd for each k = 0, 1, …, n − 1.     

Two New Classes of Difference Families

A Z-cyclic triplewhist tournament for 4n+1 players, or briefly a TWh(4n+1), is equivalent to a n-set {(a_i, b_i, c_i, d_i) | i=1, …, n} of quadruples partitioning Z_4n+1−{0} with the property that ⁿ_i=1 {±(a_i−c_i), ±(b_i−d_i)}=ⁿ_i=1 {±(a_i−b_i), ±(c_i−d_i)}=ⁿ_i=1 {±(a_i−d_i), ±(b_i−c_i)}=Z_4n+1−{0}. The existence problem for Z-cyclic TWh(p)'s with p a prime has been solved for p1 (mod 16). I. Anderson et al. (1995, Discrete Math.138, 31–41) treated the case of p≡5 (mod 8) while Y. S. Liaw (1996, J. Combin. Des.4, 219–233) and G. McNay (1996, Utilitas Math.49, 191–201) treated the case of p≡9 (mod 16). In this paper, besides giving easier proofs of these authors' results, we solve the problem also for primes p≡1 (mod 16). The final result is the existence of a Z-cyclic TWh(v) for any v whose prime factors are all≡1 (mod 4) and distinct from 5, 13, and 17.     

Characterization of generalized convex functions by their best approximation in sign-monotone norms

Let {u₀, u₁,… u_{n − 1}} and {u₀, u₁,…, u_n} be Tchebycheff-systems of continuous functions on [a, b] and let f ε C[a, b] be generalized convex with respect to {u₀, u₁,…, u_{n − 1}}. In a series of papers ([1], [2], [3]) D. Amir and Z. Ziegler discuss some properties of elements of best approximation to f from the linear spans of {u₀, u₁,…, u_{n − 1}} and {u₀, u₁,…, u_n} in the L_p-norms, 1 p ∞, and show (under different conditions for different values of p) that these properties, when valid for all subintervals of [a, b], can characterize generalized convex functions. Their methods of proof rely on characterizations of elements of best approximation in the L_p-norms, specific for each value of p. This work extends the above results to approximation in a wider class of norms, called “sign-monotone,” [6], which can be defined by the property: ¦ f(x)¦ ¦ g(x)¦,f(x)g(x) 0, a x b, imply f g . For sign-monotone norms in general, there is neither uniqueness of an element of best approximation, nor theorems characterizing it. Nevertheless, it is possible to derive many common properties of best approximants to generalized convex functions in these norms, by means of the necessary condition proved in [6]. For {u₀, u₁,…, u_n} an Extended-Complete Tchebycheff-system and f ε C⁽ⁿ⁾[a, b] it is shown that the validity of any of these properties on all subintervals of [a, b], implies that f is generalized convex. In the special case of f monotone with respect to a positive function u₀(x), a converse theorem is proved under less restrictive assumptions.     

Multi-Dimensional Pattern Matching with Dimensional Wildcards: Data Structures and Optimal On-Line Search Algorithms

We introduce a new multidimensional pattern matching problem that is a natural generalization of string matching, a well studied problem[1]. The motivation for its algorithmic study is mainly theoretical. LetA[1:n₁,…,1:n_d] be a text matrix withN = n₁…n_dentries andB[1:m₁,…,1:m_r] be a pattern matrix withM = m₁…m_rentries, whered ≥ r ≥ 1 (the matrix entries are taken from an ordered alphabet Σ). We study the problem of checking whether somer-dimensional submatrix ofAis equal toB(i.e., adecisionquery).Acan be preprocessed andBis given on-line. We define a new data structure for preprocessingAand propose CRCW-PRAM algorithms that build it inO(log N) time withN²/n_maxprocessors, wheren_max = max(n₁,…,n_d), such that the decision query forBtakesO(M) work andO(log M) time. By using known techniques, we would get the same preprocessing bounds but anO((^d_r)M) work bound for the decision query. The latter bound is undesirable since it can depend exponentially ond; our bound, in contrast, is independent ofdand optimal. We can also answer, in optimal work, two further types of queries: (a) anenumerationquery retrieving all ther-dimensional submatrices ofAthat are equal toBand (b) anoccurrencequery retrieving only the distinct positions inAthat correspond to all of these submatrices. As a byproduct, we also derive the first efficient sequential algorithms for the new problem.     

A linear algorithm for nonhomogeneous spectra of numbers

Given a sequence of integers [a_i]_i=1ⁿ, an O(n) iterative algorithm is presented which decides whether there exist real numbers α and β such that a_i = [iα + β] (1 ? i ? n). In fact, the linear algorithm computes the partial quotients of the continued fraction expansions of $\text{d}$ and $\text{d}$ such that $\text{d < α <}\text{d}$ if and only if a_i = [iα + β] (1 ? i ? n) for suitable β = β(α).     

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⁽ⁿ⁾(γ; δ).     

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).     

A Minimax Problem Admitting the Equioscillation Characterization of Bernstein and Erd?s

This paper shows that under certain conditions a solution of the minimax problem min_{a<x1<…<xn<b} max_1in+1 f_i(x₁, …, x_n) admits the equioscillation characterizations of Bernstein and Erd s and has strong uniqueness. This problem includes as a particular example the optimal Lagrange interpolation problem.     

Persistence, contractivity and global stability in logistic equations with piecewise constant delays

We establish sufficient conditions for the persistence and the contractivity of solutions and the global asymptotic stability for the positive equilibrium N^*=1/(a+∑_i=0^mb_i) of the following differential equation with piecewise constant arguments:

where r(t) is a nonnegative continuous function on [0,+∞), r(t)0, ∑_i=0^mb_i>0, b_i0, i=0,1,2,…,m, and a+∑_i=0^mb_i>0. These new conditions depend on a,b₀ and ∑_i=1^mb_i, and hence these are other type conditions than those given by So and Yu (Hokkaido Math. J. 24 (1995) 269–286) and others. In particular, in the case m=0 and r(t)≡r>0, we offer necessary and sufficient conditions for the persistence and contractivity of solutions. We also investigate the following differential equation with nonlinear delay terms:

where r(t) is a nonnegative continuous function on [0,+∞), r(t)0, 1−ax−g(x,x,…,x)=0 has a unique solution x^*>0 and g(x₀,x₁,…,x_m)C¹[(0,+∞)×(0,+∞)××(0,+∞)].     

On Rado numbers for

For all integers m3 and all natural numbers a₁,a₂,…,a_m−1, let n=R(a₁,a₂,…,a_m−1) represent the least integer such that for every 2-coloring of the set {1,2,…,n} there exists a monochromatic solution to

a₁x₁+a₂x₂++a_m−1x_m−1=x_m.