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.     

On the Rate of Convergence of Two Bernstein–Bézier Type Operators for Bounded Variation Functions, II

The rates of convergence of two Bernstein–Bézier type operators B^(α)_n and L^(α)_n for functions of bounded variation have been studied for the case α1 by the author and A. Piriou (1998, J. Approx. Theory95, 369–387). In this paper the other case 0<α<1 is treated and asymptotically optimal estimations of B^(α)_n and L^(α)_n for functions of bounded variation are obtained. Besides, some interesting behaviors of the operators B^(α)_n and L^(α)_n (α>0) for monotone functions and functions of bounded variation are also given.     

Subdivision Schemes and Refinement Equations with Nonnegative Masks

We consider the two-scale refinement equation f(x)=∑^N_n=0 c_nf(2x−n) with ∑_n c_2n=∑_n c_2n+1=1 where c₀, c_N≠0 and the corresponding subdivision scheme. We study the convergence of the subdivision scheme and the cascade algorithm when all c_n0. It has long been conjectured that under such an assumption the subdivision algorithm converge, and the cascade algorithm converge uniformly to a continuous function, if and only if only if 0<c₀, c_N<1 and the greatest common divisor of S={n: c_n>0} is 1. We prove the conjecture for a large class of refinement equations.     

Error bounds for least squares approximation by polynomials

Let f ε Cⁿ⁺¹[−1, 1] and let H[f](x) be the nth degree weighted least squares polynomial approximation to f with respect to the orthonormal polynomials q_k associated with a distribution dα on [−1, 1]. It is shown that if q_n+1/q_n max(q_n+1(1)/q_n(1), −q_n+1(−1)/q_n(−1)), then f − H[f] f^{n + 1} · q_n+1/q_{n + 1}^{(n + 1)}, where · denotes the supremum norm. Furthermore, it is shown that in the case of Jacobi polynomials with distribution (1 − t)^α (1 + t)^β dt, α, β > −1, the condition on q_n+1/q_n is satisfied when either max(α,β) −1/2 or −1 < α = β < −1/2.     

The Asymptotic Behavior of a Family of Sequences via Tauberian Theorems

We study the asymptotic behavior of a family of sequences defined by the following nonlinear induction relation c₀ = 1 and c_n ∑^k_{j = 1} r_jc_[n/mj] + ∑^k_{j = k + 1} r_jc_{[(n + 1)^1/mj] − 1} for n ≥ 1, where the r_j are real positive numbers and m_j are integers greater than or equal to 2. Depending on the fact that ∑^k_{j = 1} r_j is greater or lower than 1, we prove that c_n/n^α or c_n/(ln n)^α goes to some finite limit for some explicit α. Our study is based on Tauberian theorems and extends a result of Erdös et al.     

Spectral properties of some Jacobi matrices with double weights

We study the spectral properties of Jacobi matrices with the weights satisfying λ_2n−1=λ_2n=n^a or λ_2n=λ_2n+1=n^a, a>0. We show that for a=1 these are cases of spectral phase transitions in a. We use a new method of estimating transfer matrix products to describe the absolutely continuous part of these operators. For a=1 the existence of a spectral gap is proved. We also show how the results for double weights can be used for the spectral analysis of the Jacobi matrices related to some birth and death processes, previously studied by Janas and Naboko.     

Nonparametric Approach for Non-Gaussian Vector Stationary Processes

Suppose that {z(t)} is a non-Gaussian vector stationary process with spectral density matrixf(λ). In this paper we consider the testing problemH: ∫^π_−π K{f(λ)} dλ=cagainstA: ∫^π_−π K{f(λ)} dλ≠c, whereK{·} is an appropriate function andcis a given constant. For this problem we propose a testT_nbased on ∫^π_−π K{f(λ)} dλ=c, wheref(λ) is a nonparametric spectral estimator off(λ), and we define an efficacy ofT_nunder a sequence of nonparametric contiguous alternatives. The efficacy usually depnds on the fourth-order cumulant spectraf₄^Zofz(t). If it does not depend onf₄^Z, we say thatT_nis non-Gaussian robust. We will give sufficient conditions forT_nto be non-Gaussian robust. Since our test setting is very wide we can apply the result to many problems in time series. We discuss interrelation analysis of the components of {z(t)} and eigenvalue analysis off(λ). The essential point of our approach is that we do not assume the parametric form off(λ). Also some numerical studies are given and they confirm the theoretical results.     

Lp Markov–Bernstein Inequalities on All Arcs of the Circle

Let 0<p<∞ and 0α<β2π. We prove that for n1 and trigonometric polynomials s_n of degree n, we have

Full-size image

cn^p ∫^β_α |s_n(θ)|^p dθ, where c is independent of α, β, n, s_n. The essential feature is the uniformity in [α,β] of the estimate and the fact that as [α,β] approaches [0,2π], we recover the L_p Markov inequality. The result may be viewed as the complete L_p form of Videnskii's inequalities, improving earlier work of the second author.     

On the uniform modulus of continuity of certain discrete approximation operators

For a certain class of discrete approximation operators B_n^f defined on an interval I and including, e.g., the Bernstein polynomials, we prove that for all f ε C(I), the ordinary moduli of continuity of B_n^f and f satisfy ω(B_n^f; h) cω(f; h), N = 1,2,…, 0 < h < ∞, with a universal constant c > 0. A similar result is shown to hold for a different modulus of continuity which is suitable for functions of polynomial growth on unbounded intervals. Some special operators are discussed in this connection.     

On the Paper "Asymptotics for the Moments of Singular Distributions"

In their 1993 paper, W. Goh and J. Wimp derive interesting asymptotics for the moments c_n(α) ≡ c_n = ∫¹₀tⁿdα(t), N = 0, 1, 2, ..., of some singular distributions α (with support [0, 1]), which contain oscillatory terms. They suspect, that this is a general feature of singular distributions and that this behavior provides a striking contrast with what happens for absolutely continuous distributions. In the present note, however, we give an example of an absolutely continuous measure with asymptotics of moments containing oscillatory terms, and an example of a singular measure having very regular asymptotic behavior of its moments. Finally, we give a short proof of the fact that the drop-off rate of the moments is exactly the local measure dimension about 1 (if it exists).     

Mappings of finite distortion: the degree of regularity

This paper investigates the self-improving integrability properties of the so-called mappings of finite distortion. Let K(x)1 be a measurable function defined on a domain ΩRⁿ, n2, and such that exp(βK(x))L_loc¹(Ω), β>0. We show that there exist two universal constants c₁(n),c₂(n) with the following property: Let f be a mapping in W_loc^1,1(Ω,Rⁿ) with |Df(x)|ⁿK(x)J(x,f) for a.e. xΩ and such that the Jacobian determinant J(x,f) is locally in L¹ log^−c₁(n)βL. Then automatically J(x,f) is locally in L¹ log^c₂(n)βL(Ω). This result constitutes the appropriate analog for the self-improving regularity of quasiregular mappings and clarifies many other interesting properties of mappings of finite distortion. Namely, we obtain novel results on the size of removable singularities for bounded mappings of finite distortion, and on the area distortion under this class of mappings.     

Asymmetric Binary Covering Codes

An asymmetric binary covering code of length n and radius R is a subset of the n-cube Q_n such that every vector xQ_n can be obtained from some vector c by changing at most R 1's of c to 0's, where R is as small as possible. K⁺(n,R) is defined as the smallest size of such a code. We show K⁺(n,R)Θ(2ⁿ/n^R) for constant R, using an asymmetric sphere-covering bound and probabilistic methods. We show K⁺(n,n− )= +1 for constant coradius iff n ( +1)/2. These two results are extended to near-constant R and , respectively. Various bounds on K⁺ are given in terms of the total number of 0's or 1's in a minimal code. The dimension of a minimal asymmetric linear binary code ([n,R]⁺-code) is determined to be min{0,n−R}. We conclude by discussing open problems and techniques to compute explicit values for K⁺, giving a table of best-known bounds.     

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.     

Linear birth and death models and associated Laguerre and Meixner polynomials

We study birth and death processes with linear rates λ_n = n + α + c + 1, μ_{n + 1} = n + c, n 0 and μ₀ is either zero or c. The spectral measures of both processes are found using generating functions and the integral transforms of Laplace and Stieltjes. The corresponding orthogonal polynomials generalize Laguerre polynomials and the choice μ₀ = c generates the associated Laguerre polynomials of Askey and Wimp. We investigate the orthogonal polynomials in both cases and give alternate proofs of some of the results of Askey and Wimp on the associated Laguerre polynomials. We also identify the spectra of the associated Charlier and Meixner polynomials as zeros of certain transcendental equations.     

Bounds on margin distributions in learning problems

Let be a probability space and let P_n be the empirical measure based on i.i.d. sample (X₁,…,X_n) from P. Let be a class of measurable real valued functions on For define F_f(t):=P{ft} and F_n,f(t):=P_n{ft}. Given γ(0,1], define _n,γ(δ):=1/(n^1−γ/2δ^γ). We show that if the L₂(P_n)-entropy of the class grows as ^−α for some α(0,2), then, for all and all δ(0,Δ_n), Δ_n=O(n^1/2),

and

where and c(σ)↓1 as σ↓0 (the above inequalities hold for any fixed σ(0,1] with a high probability). Also, define

Then for all

uniformly in and with probability 1 (for the above ratio is bounded away from 0 and from ∞). The results are motivated by recent developments in machine learning, where they are used to bound the generalization error of learning algorithms. We also prove some more general results of similar nature, show the sharpness of the conditions and discuss the applications in learning theory.     

On the sequence of powers of a stochastic matrix with large exponent

We consider the class of primitive stochastic n×n matrices A, whose exponent is at least (n²−2n+2)/2+2. It is known that for such an A, the associated directed graph has cycles of just two different lengths, say k and j with k>j, and that there is an α between 0 and 1 such that the characteristic polynomial of A is λⁿ−αλ^n−j−(1−α)λ^n−k. In this paper, we prove that for any mn, if α1/2, then A^m+k−A^m_∞A^m−1w^T_∞, where 1 is the all-ones vector and w^T is the left-Perron vector for A, normalized so that w^T1=1. We also prove that if jn/2, n31 and , then A^m+j−A^m_∞A^m−1w^T_∞ for all sufficiently large m. Both of these results lead to lower bounds on the rate of convergence of the sequence A^m.     

Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property

In this paper we discuss the problem of finding optimal prefix-free codes for unequal letter costs, a variation of the classical Huffman coding problem. Our problem consists of finding a minimal cost prefix-free code in which the encoding alphabet consists of unequal cost (length) letters, with lengths α and β. The most efficient algorithm known previously requires O(n^{2 + max(α, β)}) time to construct such a minimal-cost set of n codewords, provided α and β are integers. In this paper we provide an O(n^max(α, β)) time algorithm. Our improvement comes from the use of a more sophisticated modeling of the problem, combined with the observation that the problem possesses a “Monge property” and that the SMAWK algorithm on monotone matrices can therefore be applied.     

Discrete time parametric models with long memory and infinite variance

We study a large class of infinite variance time series that display long memory. They can be represented as linear processes (infinite order moving averages) with coefficients that decay slowly to zero and with innovations that are in the domain of attraction of a stable distribution with index 1 < α < 2 (stable fractional ARIMA is a particular example). Assume that the coefficients of the linear process depend on an unknown parameter vector β which is to be estimated from a series of length n. We show that a Whittle-type estimator β_n for β is consistent (β_n converges to the true value β₀ in probability as n → ∞), and, under some additional conditions, we characterize the limiting distribution of the rescaled differences (n/logn)^1/ga(β_n − β₀).     

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.     

Representations for the first associated q-classical orthogonal polynomials

Let {p_k(x; q)} be any system of the q-classical orthogonal polynomials, and let be the corresponding weight function, satisfying the q-difference equation D_q(σ)=τ, where σ and τ are polynomials of degree at most 2 and exactly 1, respectively. Further, let {p_k⁽¹⁾(x;q)} be associated polynomials of the polynomials {p_k(x; q)}. Explicit forms of the coefficients b_n,k and c_n,k in the expansions

are given in terms of basic hypergeometric functions. Here _k(x) equals x^k if σ⁺(0)=0, or (x;q)_k if σ⁺(1)=0, where σ⁺(x)σ(x)+(q−1)xτ(x). The most important representatives of those two classes are the families of little q-Jacobi and big q-Jacobi polynomials, respectively.Writing the second-order nonhomogeneous q-difference equation satisfied by p_n−1⁽¹⁾(x;q) in a special form, recurrence relations (in k) for b_n,k and c_n,k are obtained in terms of σ and τ.