Necessary and sufficient consistency conditions for a recursive kernel regression estimate

A recursive kernel estimate ∑_{i = 1}ⁿ Y_iK⧸(x − X_i)h_i)⧸∑_{j = 1}ⁿ K((x − X_j)⧸h_j) of a regression m(x) = E{Y|X = x} calculated from independent observations (X₁, Y₁),…, (X_n, Y_n) of a pair (X, Y) of random variables is examined. ForE|Y|^{1 + δ} < ∞, δ > 0, the estimate is weakly pointwise consistent for almost all (μ) x ∈ R^d, μ is the probability measure of X, if and only if∑_i−1ⁿ h_i^d I_{hi > ɛ } ⧸ ∑_{j = 1}ⁿ h_j^d → 0 as n → ∞, all ɛ > 0, and∑_{i = 1}^∞ h_i^d = ∞, d is the dimension of X. For E|Y|^{1 + δ} < ∞, δ > 0, the estimate is strongly pointwise consistent for almost all (μ) x ∈ R^d, if and only if the same conditions hold. ForE|Y|^{1 + δ} < ∞, δ > 0, weak and strong consistency are equivalent. Similar results are given for complete convergence.     

Vertical versus horizontal Poincaré inequalities on the Heisenberg group

Let ? = 〈a, b|a[a, b] = [a, b]a ∧ b[a, b] = [a, b]b〉 be the discrete Heisenberg group, equipped with the left-invariant word metric d _W (·, ·) associated to the generating set {a, b, a ^?1, b ^?1}. Letting B _n = {x ∈ ?: d _W (x, e _?) ? n} denote the corresponding closed ball of radius n ∈ ?, and writing c = [a, b] = aba ^?1 b ^?1, we prove that if (X, ‖ · ‖X) is a Banach space whose modulus of uniform convexity has power type q ∈ [2,∞), then there exists K ∈ (0, ∞) such that every f: ? → X satisfies $$\sum\limits_{k = 1}^{{n^2}} {\sum\limits_{x \in {B_n}} {\frac{{\left\| {f(x{c^k}) - f(x)} \right\|_X^q}}{{{k^{1 + q/2}}}}} } \leqslant K\sum\limits_{x \in {B_{21n}}} {(\left\| {f(xa) - f(x)} \right\|_X^q + \left\| {f(xb) - f(x)} \right\|_X^q)} $$ . It follows that for every n ∈ ? the bi-Lipschitz distortion of every f: B _n → X is at least a constant multiple of (log n)^1/q , an asymptotically optimal estimate as n → ∞.     

Minimal error difference formulas

The usual formula for the r^th difference of f(X), at intervals of h, may introduce an error of 2^rε, where ε is the |error| in f(X). When f(X) is either an exact polynomial of the n^th degree, or very closely approximated by one within a finite interval, say [?1, 1], the r^th difference, at X = X₀, is expressible as ∑ⁿ⁺¹_i=1 a_i f(X_i), where for certain points X_i within [?1, 1], depending upon (X₀, h), ∑ⁿ⁺¹_i=1 |a_i| may be very much less than 2^r. Nodes X_i that minimize ∑ⁿ⁺¹_i=1|a_i| are said to provide “minimal error difference formulas”. For very small h, close approximations to them are obtainable from similar derivative formulas. For other combinations (X₀, h), non-minimal formulas for equally spaced X_i's, with a_i's precomputed to higher accuracy than that in f(X), greatly reduce ∑ⁿ⁺¹_i=1|a_i| from 2^r, ensure its approach to zero with h, and in many cases also yield more decimals and significant figures than the direct differencing of f(X). For r = 1, simple conditions for the non-existence of any expression ∑ⁿ⁺¹_i=1 a_i f(X_i), which improves ∑ⁿ⁺¹_i=1|a_i| to be <2, are given for (X₀, h), expressed as h ≥ h₀ which depends upon X₀ and extrema of Chebyshev polynomials.     

Computer difference scheme for a singularly perturbed convection-diffusion equation

The Dirichlet problem for a singularly perturbed ordinary differential convection-diffusion equation with a perturbation parameter ? (that takes arbitrary values from the half-open interval (0, 1]) is considered. For this problem, an approach to the construction of a numerical method based on a standard difference scheme on uniform meshes is developed in the case when the data of the grid problem include perturbations and additional perturbations are introduced in the course of the computations on a computer. In the absence of perturbations, the standard difference scheme converges at an \(\mathcal{O}\) (δ _st ) rate, where δ _st = (? + N ^?1)^?1 N ^?1 and N + 1 is the number of grid nodes; the scheme is not ?-uniformly well conditioned or stable to perturbations of the data. Even if the convergence of the standard scheme is theoretically proved, the actual accuracy of the computed solution in the presence of perturbations degrades with decreasing ? down to its complete loss for small ? (namely, for ? = \(\mathcal{O}\) (δ^?2max _i,j |δa _i ^j | + δ^?1 max _{i, j} |δb _i ^j |), where δ = δ _st and δa _i ^j , δb _i ^j are the perturbations in the coefficients multiplying the second and first derivatives). For the boundary value problem, we construct a computer difference scheme, i.e., a computing system that consists of a standard scheme on a uniform mesh in the presence of controlled perturbations in the grid problem data and a hypothetical computer with controlled computer perturbations. The conditions on admissible perturbations in the grid problem data and on admissible computer perturbations are obtained under which the computer difference scheme converges in the maximum norm for ? ∈ (0, 1] at the same rate as the standard scheme in the absence of perturbations.     

On additive representation function of general sequences

Let 0 ≦ a ₁ < a ₂ < ? be an infinite sequence of integers and let r ₁(A, n) = |(i;j): a _i + a _j = n, i ≦ j|. We show that if d > 0 is an integer, then there does not exist n ₀ such that d ≦ r ₁ (A, n) ≦ d + [√2d + ½] for n > n ₀.     

Intersection properties of finite sets

Let X₁, X₂, …, X_m be finite sets. The present paper is concerned with the m² ? m intersection numbers |X_i ∩ X_j| (i ≠ j). We prove several theorems on families of sets with the same prescribed intersection numbers. We state here one of our conclusions that requires no further terminology. Let T₁, T₂, …, T_m be finite sets and let m ? 3. We assume that each of the elements in the set union T₁ ∪ T₂ ∪ … ∪ T_m occurs in at least two of the subsets T₁, T₂, …, T_m. We further assume that every pair of sets T_i and T_j (i ≠ j) intersect in at most one element and that for every such pair of sets there exists exactly one set T_k (k ≠ i, k ≠ j) such that T_k intersects both T_i and T_j. Then it follows that the integer m = 2m′ + 1 is odd and apart from the labeling of sets and elements there exist exactly m′ + 1 such families of sets. The unique family with the minimal number of elements is {1}, {2}, …, {m′}, {1}, {2}, …, {m′}, {1, 2, …, m′}.     

Sharp asymptotics of large deviations in ℝ d

Given a sequence {X₁}i=1,2,3,... of i.i.d. random variables taking values in ? ^d ,d≥2, letS _n =Σ _i=1 ⁿ X _t=1. For Λ a Borel set in ? ^d having smooth boundary, witha=inf_x∈ΛI(x) the minimal value of the large deviation rate functionI(x) over Λ, we find, under suitable hypotheses, asymptotic results asn→∞, of the form $$P(S_n \in n\Gamma ) = n^\gamma e^{ - na} (d_0 + o(1))$$ where the constant γ depends sensitively on the geometry of Λ and the dimensiond, and takes values ?∞<γ≤(d?2/2). For fixeda=inf_x∈ΛI(x), we construct examples having any specific γ in this range.     

A Functional Equation Of J.A. Baker Involving Integral Means

The functional equation $$f(x)={1\over 2}\int^{x+1}_{x-1}f(t)\ dt\ \ \ {\rm for}\ \ \ x\ \in\ {\rm R}$$ has the linear functions ?(x) = a + bx (a, b ∈ ?) as trivial solutions. It is shown that there are two kinds of nontrivial solutions, (i) ?(x) = eλ_i ^x (i = 1, 2, …), where the λ_i∈ ? are the fixed points of the map z ? sinh z, and (ii) C^∞-solutions ? for which the values in the interval [?1,1] can be prescribed arbitrarily, but with the provision that ?^(j)(? 1) = ?^(j)(0) = ?^(j)(1) = 0 for all j = 0, 1, 2 …     

Inequalities of Hlawka type for matrices

A generalized Hlawka's inequality says that for any n (\geqq 2) (\geqq 2) complex numbers¶ x₁, x₂, ..., x_n,¶¶ ?_i=1ⁿ|x_i - ?_j=1ⁿx_j| \leqq ?_i=1ⁿ|x_i| + (n - 2)|?_j=1ⁿx_j|. \sum_{i=1}^n\Bigg|x_i - \sum_{j=1}^{n}x_j\Bigg| \leqq \sum_{i=1}^{n}|x_i| + (n - 2)\Bigg|\sum_{j=1}^{n}x_j\Bigg|. ¶¶ We generalize this inequality to the trace norm and the trace of an n x n matrix A as¶¶ ||A - Tr A ||₁ \leqq ||A||₁ + (n - 2)| Tr A|. ||A - {\rm Tr} A ||_1\ \leqq ||A||_1 + (n - 2)| {\rm Tr} A|. ¶¶ We consider also the related inequalities for p-norms (1 \leqq p \leqq ￥) (1 \leqq p \leqq \infty) on matrices.     

Erdős-Rényi-Shepp laws and weighted sums of independent identically distributed random variables

LetX ₀,X ₁,X ₂,... be i.i.d. random variables withE(X ₀)=0,E(X ₀ ² )=1,E(exp{tX _o}<∞ (|t|<t ₀) and partial sumsS _n . Starting from Shepp's version of the well-known Erd?s-Rényi-Shepp law $$\mathop {\lim }\limits_{n \to \infty } \sup ([c\log n])^{ - 1} )(S_{n + [c\log n]} - S_n ) = \alpha {\text{a}}{\text{.s}}{\text{.}}$$ where α is a number depending uponc and the distribution ofX ₀, we show that other weighted sumsV(n)=Σa _j (n)X _j exhibit a similar lim sup behavior, if the weights satisfy certain regularity conditions. We also prove for such weighted sums certain versions of the classical Erd?s-Rényi law.     

Note on the local growth of iterated polynomials

The local behavior of the iterates of a real polynomial is investigated. The fundamental result may be stated as follows: THEOREM. Let x_i, for i=1, 2, ..., n+2, be defined recursively by x_i+1=f(x_i), where x₁ is an arbitrary real number and f is a polynomial of degree n. Let x_i+1?x_i≧1 for i=1, ..., n + 1. Then for all i, 1 ≦i≦n, and all k, 1≦k≦n+1?i, $$ - \frac{{2^{k - 1} }}{{k!}}< f\left[ {x_1 ,... + x_{i + k} } \right]< \frac{{x_{i + k + 1} - x_{i + k} + 2^{k - 1} }}{{k!}},$$ where f[x_i, ..., x_i+k] denotes the Newton difference quotient. As a consequence of this theorem, the authors obtain information on the local behavior of the solutions of certain nonlinear difference equations. There are several cases, of which the following is typical: THEOREM. Let {x_i}, i = 1, 2, 3, ..., be the solution of the nonlinear first order difference equation x_i+1=f(x_i) where x₁ is an arbitrarily assigned real number and f is the polynomial \(f(x) = \sum\limits_{j = 0}^n {a_j x^j } ,n \geqq 2\) . Let δ be positive with δ^n?1=|2^n?1/n!a_n|. Then, if n is even and a_n<0, there do not exist n + 1 consecutive increments Δx_i=x_i+1?x_i in the solution {x_i} with Δx_i≧δ. The special case in which the iterated polynomial has integer coefficients leads to a “nice” upper bound on a generalization of the van der Waerden numbers. Ap _k -sequence of length n is defined to be a strictly increasing sequence of positive integers {x ₁, ...,x _n } for which there exists a polynomial of degree at mostk with integer coefficients and satisfyingf(x _j )=x _j+1 forj=1, 2, ...,n?1. Definep _k (n) to be the least positive integer such that if {1, 2, ...,p _k (n)} is partitioned into two sets, then one of the two sets must contain ap _k -sequence of lengthn. THEOREM. p_n?2(n)≦(n!)^(n?2)!/2.     

Some results on λ‐designs with two block sizes

A λ‐design is a family ?? = {B₁, B₂, …, B_v} of subsets of X = {1, 2, …, v} such that |B_i∩B_j| = λ for all i≠jand not all B_i are of the same size. The only known example of λ‐designs (called type‐1 designs) are those obtained from symmetric designs by a certain complementation procedure. Ryser [J Algebra 10 (1968), 246–261] and Woodall [Proc London Math Soc 20 (1970), 669–687] independently conjectured that all λ‐designs are type‐1. Let g = gcd(r ? 1, r^* ? 1), where rand r^* are the two replication numbers. Ionin and Shrikhande [J Combin Comput 22 (1996), 135–142; J Combin Theory Ser A 74 (1996), 100–114] showed that λ‐designs with g = 1, 2, 3, 4 are type‐1 and that the Ryser–Woodall conjecture is true for λ‐designs on p + 1, 2p + 1, 3p + 1, 4p + 1 points, where pis a prime. Hein and Ionin [Codes and Designs—Proceedings of Conference honoring Prof. D. K. Ray‐Chaudhuri on the occasion of his 65th birthday, Ohio State University Mathematical Research Institute Publications, 10, Walter de Gruyter, Berlin, 2002, pp. 145–156] proved corresponding results for g = 5 and Fiala [Codes and Designs—Proceedings of Conference honoring Prof. D. K. Ray‐Chaudhuri on the occasion of his 65th birthday, Ohio State University Mathematical Research Institute Publications, 10, Walter de Gruyter, Berlin, 2002, pp. 109–124; Ars Combin 68 (2003), 17–32; Ars Combin, to appear] for g = 6, 7, and 8. In this article, we consider λ designs with exactly two block sizes. We show that in this case, the conjecture is true for g = 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, and for g = 10, 14, 18, 22 with v≠4λ ? 1. We also give two results on such λ‐designs on v = 9p + 1 and 12p + 1 points, where pis a prime. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:95‐110, 2011     

On a question of Sárközy on gaps of product sequences

Motivated by a question of Sárközy, we study the gaps in the product sequence B = A · A = {b ₁ < b ₂ < …} of all products a _i a _j with a _i , a _j ∈ A when A has upper Banach density α > 0. We prove that there are infinitely many gaps b _n+1 ? b _n ? α ^?3 and that for t ≥ 2 there are infinitely many t-gaps b _n+t ? b _n ? t ² α ^?4. Furthermore, we prove that these estimates are best possible.We also discuss a related question about the cardinality of the quotient set A/A = {a _i /a _j , a _i , a _j ∈ A} when A ? {1, …, N} and |A| = αN.     

Approximation of functions of finite variation by superpositions of a Sigmoidal function

The aim of this note is to generalize a result of Barron [1] concerning the approximation of functions, which can be expressed in terms of the Fourier transform, by superpositions of a fixed sigmoidal function. In particular, we consider functions of the type h(x) = ∫ℝ^d ƒ (〈t, x〉)dμ(t), where μ is a finite Radon measure on ℝ^d and ƒ : ℝ → ℂ is a continuous function with bounded variation in ℝ We show (Theorem 2.6) that these functions can be approximated in L₂-norm by elements of the set G_n = {Σ_i=0^staggeredn c_ig(〈a_i, x〉 + b_i) : a_iℝ^d, b_i, c_iℝ}, where g is a fixed sigmoidal function, with the error estimated by C/n^1/2, where C is a positive constant depending only on f. The same result holds true (Theorem 2.9) for f : ℝ → ℂ satisfying the Lipschitz condition under an additional assumption that ∫ℝ^d6t6e^d|u(t)| > ∞     

On the existence of diffusions with singular drift coefficient

Let L:be an operator in R~d,where the matrix(a) is bounded,Holder continuous and uniformly positive definite,and (b~t(x)) is Borel measurable.In this paper we prove the existence of L-diffusion under the hypothesis that where g_1(z)=1,g_2(z)=-ln|z|and g_c(z)=|z|~(2-d) for d≥3.     

On a Conjecture of E. Dittert

Let K_n denote the set of all n X n nonnegative matrices whose entries have sum n, and let φ be a real valued function defined on K_n by φ(X) = π_iⁿ⁼¹ n, + π_j=1^c_j⁻ⁿ per X for X E K_n with row sum vector (r₁,…, r_n) and column sum vector (c_l,hellip;, c_n). For the same X, let φ_ij(X)= π_k≠ir_k + π_1≠jc₁ - per X(i| j). A ϵK_n is called a φ-maximizing matrix if φ(A) > φ(X) for all X ϵ K_n. Dittert's conjecture asserts that J_n = [1/n]_n×n is the unique (φ-maximizing matrix on K_n. In this paper, the following are proved: (i) If A = [a_ij] is a φ-maximizing matrix on K_n then φ_ij(A) = φ (A) if a_ij > 0, and φ_ij (A) ⩽ φ (A)if aij = 0. (ii) The conjecture is true for n = 3.     

Block partitions of sequences

Given a sequence A = (a ₁, …, a _n ) of real numbers, a block B of A is either a set B = {a _i , a _i+1, …, a _j } where i ≤ j or the empty set. The size b of a block B is the sum of its elements. We show that when each a _i ∈ [0, 1] and k is a positive integer, there is a partition of A into k blocks B ₁, …, B _k with |b _i ?b _j | ≤ 1 for every i, j. We extend this result in several directions.     

A concentration function estimate and intersective sets from matrices

We give several sufficient conditions on an infinite integer matrix (d _ij ) for the set R = {Σ _{ij∈α, i>j} d _ij : α ? ?, |α| < ∞} to be a density intersective set, including the cases d _nj = j ⁿ (1 + O(1/n ^1+ε )) and \(0 < d_{nj} = o(\sqrt {n/\log n} )\). For the latter, a concentration function estimate that is of independent interest is applied to sums of sequences of 2-valued random variables whose means may grow as \(\sqrt {n/\log n} \).     

The optimal base of a matroid/with tree-type constraints

Let M be a matroid defined on a weighted finite set E=(e_1,…,e_n).l(e) is the weight of e∈E.P (X_1,…,X_m) is a set of subsets of E.X_i,X_j∈P,if X_i∩X_j≠(the empty set),then either X_i X_j or X_jX_i.For each X_i∈P,there are two associate nonnegative integers a_i and b_i with o_i≤b_i≤|X_i|.We call a base T of M a feasible base with respect to P(or simply call it a feasible base of M),if X_i∈P,a_i≤|X_i∩T|≤b_i.A base T' is called optimal if:i) This feasible,In this paper we present a polynomial algorithm to solve the optimal base problem.     

The inverse M-matrix problem

One aspect of the inverse M-matrix problem can be posed as follows. Given a positive n × n matrix A=(a_ij) which has been scaled to have unit diagonal elements and off-diagonal elements which satisfy 0 < y ? a_ij ? x < 1, what additional element conditions will guarantee that the inverse of A exists and is an M-matrix? That is, if A^?1=B=(b_ij), then b_ii> 0 and b_ij ? 0 for i≠_j. If n=2 or x=y no further conditions are needed, but if n ? 3 and y < x, then the following is a tight sufficient condition. Define an interpolation parameter s via x²=sy+(1?s)y²; then B is an M-matrix if s^?1 ? n?2. Moreover, if all off-diagonal elements of A have the value y except for a_ij=a_jj=x when i=n?1, n and 1 ? _j ? n?2, then the condition on both necessary and sufficient for B to be an M-matrix.