Global nonparametric estimation of conditional quantile functions and their derivatives

Let (X, Y) be a random vector such that X is d-dimensional, Y is real valued, and θ(X) is the conditional αth quantile of Y given X, where α is a fixed number such that 0 < α < 1. Assume that θ is a smooth function with order of smoothness p > 0, and set r = (p − m)/(2p + d), where m is a nonnegative integer smaller than p. Let T(θ) denote a derivative of θ of order m. It is proved that there exists estimate of T(θ), based on a set of i.i.d. observations (X₁, Y₁), …, (X_n, Y_n), that achieves the optimal nonparametric rate of convergence n^−r in L_q-norms (1 ≤ q < ∞) restricted to compacts under appropriate regularity conditions. Further, it has been shown that there exists estimate of T(θ) that achieves the optimal rate (n/log n)^−r in L_∞-norm restricted to compacts.     

Bivariate Tensor-Product B-Splines in a Partly Linear Model

In some applications, the mean or median response is linearly related to some variables but the relation to additional variables are not easily parameterized. Partly linear models arise naturally in such circumstances. Suppose that a random sample {(T_i, X_i, Y_i),i=1, 2, …, n} is modeled byY_i=X^T_iβ₀+g₀(T_i)+error_i, whereY_iis a real-valued response,X_iR^pandT_iranges over a unit square, andg₀is an unknown function with a certain degree of smoothness. We make use of bivariate tensor-product B-splines as an approximation of the functiong₀and consider M-type regression splines by minimization of ∑ⁿ_i=1 ρ(Y_i−X^T_iβ−g_n(T_i)) for some convex functionρ. Mean, median and quantile regressions are included in this class. We show under appropriate conditions that the parameter estimate ofβachieves its information bound asymptotically and the function estimate ofg₀attains the optimal rate of convergence in mean squared error. Our asymptotic results generalize directly to higher dimensions (for the variableT) provided that the functiong₀is sufficiently smooth. Such smoothness conditions have often been assumed in the literature, but they impose practical limitations for the application of multivariate tensor product splines in function estimation. We also discuss the implementation of B-spline approximations based on commonly used knot selection criteria together with a simulation study of both mean and median regressions of partly linear models.     

Quasicomplete factorizations of rational matrix functions

It is shown that within the class ofn×n rational matrix functions which are analytic at infinity with valueW()=I _n, any rational matrix functionW is the productW=W ₁...W _p of rational matrix functionsW ₁,...,W _p of McMillan degree one. Furthermore, such a factorization can be established with a number of factors not exceeding 2(W)–1, where (W) denotes the McMillan degree ofW.     

Preconditioners for block Toeplitz systems based on circulant preconditioners

We study the numerical solution of a block system T _m,n x=b by preconditioned conjugate gradient methods where T _m,n is an m×m block Toeplitz matrix with n×n Toeplitz blocks. These systems occur in a variety of applications, such as two-dimensional image processing and the discretization of two-dimensional partial differential equations. In this paper, we propose new preconditioners for block systems based on circulant preconditioners. From level-1 circulant preconditioner we construct our first preconditioner q ₁(T _m,n ) which is the sum of a block Toeplitz matrix with Toeplitz blocks and a sparse matrix with Toeplitz blocks. By setting selected entries of the inverse of level-2 circulant preconditioner to zero, we get our preconditioner q ₂(T _m,n ) which is a (band) block Toeplitz matrix with (band) Toeplitz blocks. Numerical results show that our preconditioners are more efficient than circulant preconditioners.     

Nondeterminism of Linear Operators and Lower Entropy Estimates

Let u be a (bounded, linear) operator from a Hilbert space ℋ into the Banach space C(T), the space of continuous functions on the compact metric space T. We introduce and investigate numbers τ _n (u), n≥1, measuring the degree of determinism of the operator u. The slower τ _n (u) decreases, the less determined are functions in the range of u by their values on a certain set of points. It is shown that n ^−1/2 τ _n (u)≤2e _n (u), where e _n (u) are the (dyadic) entropy numbers of u. Furthermore, we transform the notion of strong local nondeterminism from the language of stochastic processes into that of linear operators. This property, together with a lower entropy estimate for the compact space T, leads to a lower estimate for τ _n (u), hence also for e _n (u). These results are used to prove sharp lower entropy estimates for some integral operators, among them, Riemann–Liouville operators with values in C(T) for some fractal set T. Some multi-dimensional extensions are treated as well.      

A reversal index for tournament matrices *

Given a tournament matrix T, its reversal indexi_R (T), is the minimum k such that the reversal of the orientation of k arcs in the directed graph associated with T results in a reducible matrix. We give a formula for i_R (T) in terms of the score vector of T which generalizes a simple criterion for a tournament matrix to be irreducible. We show that i_R (T)≤[(n?1)/2] for any tournament matrix T of order n, with equality holding if and only if T is regular or almost regular, according as n is odd or even. We construct, for each k between 1 and [(n?1)/2], a tournament matrix of order n whose reversal index is k. Finally, we suggest a few problems.     

Some Remarks on the Number of Solutions to the Equation f(X1) + … + f(Xn) = 0

Let S, T be finite sets, and let f be a function from S to T. Fix an element t in T, and let c_n denote the number of n-tuples (X₁,…,X_n) satisfying f(X₁) + … + f(X_n) = t here + denotes any binary operation on T. The sequence c₁, c₂,… satisfies a linear recurrence relation of degree at most |T|.     

Asymptotic behavior of self-normalized trimmed sums: Nonnormal limits II

Let {X _j} be independent, identically distributed random variables which are symmetric about the origin and have a continuous nondegenerate distributionF. Let {X _n(1),...,X _n(n)} denote the arrangement of {X ₁,...,X _n} in decreasing order of magnitude, so that with probability one, |X _n(1)|>|X _n(2)|>...> |X _n(n)|. For initegersr _n such thatr _n/n0, define the self-normalized trimmed sumT _n= _i=rn ⁿ X _n(i)/{ _i=rn ⁿ X _n ² (i)}^1/2. Hahn and Weiner⁽⁶⁾ showed that under a probabilistically meaningful analytic condition generalizing the asymptotic normality criterion forT _n, various nonnormal limit laws forT _n arise which are represented by means of infinite random series. The analytic condition is now extended and the previous approach is refined to obtain limits which are mixtures of a normal, a Rademacher, and a law represented by a more general random series. Each such limit law actually arises as can be seen from the construction of a single distribution whose correspondingL(T _n ) generates all of the law along different subsequences, at least if {r _n} grows sufficiency fast. Another example clarifies the limitations of the basic approach.     

Second-order linearity of the general signed-rank statistic

Let X₁,…, X_n be i.i.d. random variables symmetric about zero. Let R_i(t) be the rank of |X_i − tn^−1/2| among |X₁ − tn^−1/2|,…, |X_n − tn^−1/2| and T_n(t) = Σ_{i = 1}ⁿφ((n + 1)⁻¹R_i(t))sign(X_i − tn^−1/2). We show that there exists a sequence of random variables V_n such that sup_{0 ≤ t ≤ 1} |T_n(t) − T_n(0) − tV_n| → 0 in probability, as n → ∞. V_n is asymptotically normal.     

The optimal form of selection principles for functions of a real variable

Let T be a nonempty set of real numbers, X a metric space with metric d and X^T the set of all functions from T into X. If fX^T and n is a positive integer, we set , where the supremum is taken over all numbers a₁,…,a_n,b₁,…,b_n from T such that a₁b₁a₂b₂a_nb_n. The sequence is called the modulus of variation of f in the sense of Chanturiya. We prove the following pointwise selection principle: If a sequence of functions is such that the closure in X of the set is compact for each tT and

(∗)

then there exists a subsequence of , which converges in X pointwise on T to a function fX^T satisfying lim_n→∞ν(n,f)/n=0. We show that condition (*) is optimal (the best possible) and that all known pointwise selection theorems follow from this result (including Helly's theorem). Also, we establish several variants of the above theorem for the almost everywhere convergence and weak pointwise convergence when X is a reflexive separable Banach space.     

Criteria for Convergence of the Number of Near Maxima for Long Tails

Let M_n denote the maximum of a random sample of size n and K_n(a) be the number of near maxima, i.e. the number of sample observations in the fixed-width window (M_n – a, M_n]. There is a known integral criterion for almost sure convergence (to unity) of K_n(a), and we establish a similar criterion for complete convergence. We obtain simple but quite general sufficient conditions on the survivor function for satisfying the integral criteria. Further insight is obtained by seeking the rate at which P(K_n(a > 1)) tends to zero.AMS 2000 Subject Classification. 62G30, 60F15     

Subspaces where an immanant is convertible into its conjugate ∗

Let n≥5 and let be an irreducible nonlinear character of S_n such that whenever σ is a transposition or a cycle of length three; furthermore let T_n be the (0, 1)-matrix of order n that has ones exactly on and below the upper neighbours of the main diagonal and denote by E_ij the matrix of order n with 1 in position (i, j) and 0 elsewhere.

Given i,jε{1,…,n}, with i+1<j, we prove that if j?i≠3, then in the subspace M_n (T_n +E_ij there exist matrices for which the immanant is not convertible into the immanant by sign-affixing. Abusing language, we say that the space is -inconvertible, and show that spaces M_n (T_n +E₂₅ ) and M_n (T_n +E_n?3,n ). We also state some sufficient fonditions for the subspace M_n (T_n ) to be external convertible.

With some exceptions our theorems say that the coordinate subspaces found for the conversion of the permanent into the determinant by Gibson around 1970 are also best possible for other immanants.     

THE REGULARITY DEGREE AND EPIMORPHISMS IN THE CATEGORY OF COMMUTATIVE RINGS

Elements of the universal (von Neumann) regular ring T(R) of a commutative semiprime ring R can be expressed as a sum of products of elements of R and quasi-inverses of elements of R. The maximum number of terms required is called the regularity degree, an invariant for R measuring how R sits in T(R). It is bounded below by 1 plus the Krull dimension of R. For rings with finitely many primes and integral extensions of noetherian rings of dimension 1, this number is precisely the regularity degree.

For each n ≥ 1, one can find a ring of regularity degree n + 1. This shows that an infinite product of epimorphisms in the category of commutative rings need not be an epimorphism.

Finite upper bounds for the regularity degree are found for noetherian rings R of finite dimension using the Wiegand dimension theory for Patch R. These bounds apply to integral extensions of such rings as well.     

Generating Sets of Finite Transformation Semigroups PK(n,r) and K (n,r)

Let P _n and T _n be the partial transformation and the full transformation semigroups on the set {1,…, n}, respectively. In this paper we find necessary and sufficient conditions for any set of partial transformations of height r in the subsemigroup PK(n, r) = {α ∈P _n : |im (α)| ≤r} of P _n to be a (minimal) generating set of PK(n, r); and similarly, for any set of full transformations of height r in the subsemigroup K(n, r) = {α ∈T _n : |im (α)| ≤r} of T _n to be a (minimal) generating set of K(n, r) for 2 ≤ r ≤ n ? 1.     

Maximum hitting time for random walks on graphs

For x and y vertices of a connected graph G, let T_G(x, y) denote the expected time before a random walk starting from x reaches y. We determine, for each n > 0, the n-vertex graph G and vertices x and y for which T_G(x, y) is maximized. the extremal graph consists of a clique on ?(2n + 1)/3?) (or ?)(2_n ? 2)/3?) vertices, including x, to which a path on the remaining vertices, ending in y, has been attached; the expected time T_G(x, y) to reach y from x in this graph is approximately 4_n³/27.     

Approximations of spectra of Schrödinger operators with complex potentials on ℝd

We study spectral approximations of Schrödinger operators T = ?Δ+Q with complex potentials on Ω = ?^d, or exterior domains Ω??^d, by domain truncation. Our weak assumptions cover wide classes of potentials Q for which T has discrete spectrum, of approximating domains Ω_n, and of boundary conditions on ?Ω_n such as mixed Dirichlet/Robin type. In particular, Re Q need not be bounded from below and Q may be singular. We prove generalized norm resolvent convergence and spectral exactness, i.e. approximation of all eigenvalues of T by those of the truncated operators T_n without spectral pollution. Moreover, we estimate the eigenvalue convergence rate and prove convergence of pseudospectra. Numerical computations for several examples, such as complex harmonic and cubic oscillators for d = 1,2,3, illustrate our results.     

Maximum likelihood estimation of a change-point in the distribution of independent random variables: General multiparameter case

In a sequence ofn independent random variables the pdf changes fromf(x, 0) tof(x, 0 + δv_n⁻¹) after the firstnλ variables. The problem is to estimateλ (0, 1 ), where 0 and δ are unknownd-dim parameters andv_n → ∞ slower thann^1/2. Let_n denote the maximum likelihood estimator (mle) ofλ. Analyzing the local behavior of the likelihood function near the true parameter values it is shown under regularity conditions that ifn_n²(− λ) is bounded in probability asn → ∞, then it converges in law to the timeT_(δjδ)^1/2 at which a two-sided Brownian motion (B.M.) with drift1/2(δ′Jδ)^1/2ton(−∞, ∞) attains its a.s. unique minimum, whereJ denotes the Fisher-information matrix. This generalizes the result for small change in mean of univariate normal random variables obtained by Bhattacharya and Brockwell (1976,Z. Warsch. Verw. Gebiete37, 51–75) who also derived the distribution ofT_μ forμ > 0. For the general case an alternative estimator is constructed by a three-step procedure which is shown to have the above asymptotic distribution. In the important case of multiparameter exponential families, the construction of this estimator is considerably simplified.     

The non-projective part of the Lie module for the symmetric group

The Lie module of the group algebra F\mathfrakS_n{{F\mathfrak{S}_n}} of the symmetric group is known to be not projective if and only if the characteristic p of F divides n. We show that in this case its non-projective summands belong to the principal block of F\mathfrakS_n{{F\mathfrak{S}_n}} . Let V be a vector space of dimension m over F, and let L ⁿ (V) be the n-th homogeneous part of the free Lie algebra on V; this is a polynomial representation of GL _m (F) of degree n, or equivalently, a module of the Schur algebra S(m, n). Our result implies that, when m ≥ n, every summand of L ⁿ (V) which is not a tilting module belongs to the principal block of S(m, n), by which we mean the block containing the n-th symmetric power of V.     

The size Ramsey number of trees with bounded degree

The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(T_nd, T_nd) ? c · d² · n and c · n³ ? r?(K_n, T_nd) ? c(d)·n³ log n for every tree T_nd on n vertices. and maximal degree at most d and a complete graph K_n on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.