A Remark on Self-Normalization for Dependent Random Variables

Let (X _t , t ∈ Z) be a stationary process, and let S _n = ∑_{1⩽ i⩽n} X _i . In this paper, we consider the central limit theorem for the self-normalized sequence S _n /U _n , where U _n ² = ∑_1⩽j⩽N Y _j ² , Y _j = ∑_{(j−1)m<i⩽jm} X _i , n = mN. We show how such a self-normalization works for AR(1) and MA(q) processes.__________Published in Lietuvos Matematikos Rinkinys, Vol. 45, No. 2, pp. 173–183, April–June, 2005.     

On improved estimators of the generalized variance

Treated in this paper is the problem of estimating with squared error loss the generalized variance | Σ | from a Wishart random matrix S: p × p W_p(n, Σ) and an independent normal random matrix X: p × k N(ξ, Σ I_k) with ξ(p × k) unknown. Denote the columns of X by X₍₁₎ ,…, X_(k) and set ψ⁽⁰⁾(S, X) = {(n − p + 2)!/(n + 2)!} | S |, ψ⁽ⁱ⁾(X, X) = min[ψ⁽ⁱ⁻¹⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!} | S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |] and Ψ⁽ⁱ⁾(S, X) = min[ψ⁽⁰⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!}| S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |], i = 1,…,k. Our result is that the minimax, best affine equivariant estimator ψ⁽⁰⁾(S, X) is dominated by each of Ψ⁽ⁱ⁾(S, X), i = 1,…,k and for every i, ψ⁽ⁱ⁾(S, X) is better than ψ⁽ⁱ⁻¹⁾(S, X). In particular, ψ^(k)(S, X) = min[{(n − p + 2)!/(n + 2)!} | S |, {(n − p + 2)!/(n + 2)!} | S + X₍₁₎X′₍₁₎|,…,| {(n − p + k + 2)!/(n + k + 2)!} | S + X₍₁₎X′₍₁₎ + + X_(k)X′_(k)|] dominates all other ψ's. It is obtained by considering a multivariate extension of Stein's result (Ann. Inst. Statist. Math. 16, 155–160 (1964)) on the estimation of the normal variance.     

A functional model for the tensor product of level 1 highest and level −1 lowest modules for the quantum affine algebra

Let V(Λ_i) (resp., V(−Λ_j)) be a fundamental integrable highest (resp., lowest) weight module of . The tensor product V(Λ_i)V(−Λ_j) is filtered by submodules , n≥0, n≡i−j mod 2, where v_iV(Λ_i) is the highest vector and is an extremal vector. We show that F_n/F_n+2 is isomorphic to the level 0 extremal weight module V(n(Λ₁−Λ₀)). Using this we give a functional realization of the completion of V(Λ_i)V(−Λ_j) by the filtration (F_n)_n≥0. The subspace of V(Λ_i)V(−Λ_j) of -weight m is mapped to a certain space of sequences (P_n,l)_{n≥0,n≡i−jmod2,n−2l=m}, whose members P_n,l=P_n,l(X₁,…,X_lz₁,…,z_n) are symmetric polynomials in X_a and symmetric Laurent polynomials in z_k, with additional constraints. When the parameter q is specialized to , this construction settles a conjecture which arose in the study of form factors in integrable field theory.     

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.     

Some New Results on Stochastic Comparisons of Spacings from Heterogeneous Exponential Distributions

Some new results are obtained on stochastic orderings between random vectors of spacings from heterogeneous exponential distributions and homogeneous ones. LetD₁, …, D_nbe the normalized spacings associated with independent exponential random variablesX₁, …,X_n, whereX_ihas hazard rateλ_i,i=1, 2, …, n. LetD*₁, …, D*_nbe the normalized spacings of a random sampleY₁, …, Y_nof sizenfrom an exponential distribution with hazard rateλ=∑ⁿ_i=1 λ_i/n. It is shown that for anyn2, the random vector (D₁, …, D_n) is greater than the random vector (D*₁, …, D*_n) in the sense of multivariate likelihood ratio ordering. It also follows from the results proved in this paper that for anyjbetween 2 andn, the survival function ofX_j:n−X_1:nis Schur convex.     

Approximation of elements of a generalized Orlicz sequence space by nonlinear, singular kernels

Let l be a generalized Orlicz sequence space generated by a modular (x) = ∑_{i − 0}^∞ _i(¦t_i¦), X = (t_i), with s-convex functions _i, 0 < s 1, and let K_w,j: R₊ → R₊ for j=0,1,2,…, w ε Wwhere is an abstract set of indices. Assuming certain singularity assumptions on the nonlinear kernel K_w,j and setting T_wx = ((T_wx)_i)_{i = 0}^∞, with (T_wx)_i = ∑_{j = 0}ⁱ K_{w,i − j}(¦t_j¦) for x = (t_j), convergence results: T_wx → x in l are obtained (both modular convergence and norm convergence), with respect to a filter of subsets of the set .     

Selection in Monotone Matrices and Computingkth Nearest Neighbors

Anm×nmatrix =(a_{i, j}), 1≤i≤mand 1≤j≤n, is called atotally monotonematrix if for alli₁, i₂, j₁, j₂, satisfying 1≤i₁<i₂≤m, 1≤j₁<j₂≤n.[formula]We present an[formula]time algorithm to select thekth smallest item from anm×ntotally monotone matrix for anyk≤mn. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for ageneralized row-selection problemin monotone matrices. Given a setS={p₁,…, p_n} ofnpoints in convex position and a vectork={k₁,…, k_n}, we also present anO(n^4/3log^c n) algorithm to compute thek_ith nearest neighbor ofp_ifor everyi≤n; herecis an appropriate constant. This algorithm is considerably faster than the one based on a row-selection algorithm for monotone matrices. If the points ofSare arbitrary, then thek_ith nearest neighbor ofp_i, for alli≤n, can be computed in timeO(n^7/5 log^c n), which also improves upon the previously best-known result.     

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.     

Counting cycles and finite dimensional L norms

We obtain sharp bounds for the number of n-cycles in a finite graph as a function of the number of edges, and prove that the complete graph is optimal in more ways than could be imagined. We prove sharp estimates on both ∑_i=1ⁿx_i^k and ∑_i=1ⁿ|x_i|^k, subject to the constraints that ∑_i=1ⁿx_i²=C and ∑_i=1ⁿx_i=0.     

Consistency of a recursive nearest neighbor regression function estimate

Let (X, Y) be an ^d × -valued random vector and let (X₁, Y₁),…,(X_N, Y_N) be a random sample drawn from its distribution. Divide the data sequence into disjoint blocks of length l₁, …, l_n, find the nearest neighbor to X in each block and call the corresponding couple (X_i^*, Y_i^*). It is shown that the estimate m_n(X) = Σ_{i = 1}ⁿ w_niY_i^*/Σ_{i = 1}ⁿ w_ni of m(X) = E{Y|X} satisfies E{|m_n(X) − m(X)|^p} 0 (p ≥ 1) whenever E{|Y|^p} < ∞, l_n ∞, and the triangular array of positive weights {w_ni} satisfies sup_{i ≤ n}w_ni/Σ_{i = 1}ⁿ w_ni 0. No other restrictions are put on the distribution of (X, Y). Also, some distribution-free results for the strong convergence of E{|m_n(X) − m(X)|^p|X₁, Y₁,…, X_N, Y_N} to zero are included. Finally, an application to the discrimination problem is considered, and a discrimination rule is exhibited and shown to be strongly Bayes risk consistent for all distributions.     

Rates of convergence for classes of functions: The non-i.i.d. case

Let X_i, i ≥ 1, be a sequence of φ-mixing random variables with values in a sample space (X, A). Let L(X_i) = P_(i) for all i ≥ 1 and let _n, n ≥ 1, be classes of real-valued measurable functions on (X, A). Given any function g on (X, A), let S_n(g) = Σ_{i = 1}ⁿ {g(X_i) − Eg(X_i)}. Under weak metric entropy conditions on _n and under growth conditions on both the mixing coefficients and the maximal variance V V(n) max_{i ≤ n} sup_{g n} ∫ g² dP_(i), we show that there is a numerical constant U < ∞ such that

Full-size image

a.s. ^*, where _{i = 1}^xP_(i) and H H(n) is the square root of the entropy of the class _n. Additionally, the rate of convergence H⁻¹(n/V)^1/2 cannot, in general, be improved upon. Applications of this result are considered.     

A note on asymptotic expansions for Markov chains using operator theory

We consider asymptotic expansions for sums S_n on the form S_n = ƒ₀(X₀) + ƒ(X₁, X₀) + … + ƒ(X_n, X_n−1), where X_i is a Markov chain. Under different ergodicity conditions on the Markov chain and certain conditional moment conditions on ƒ(X_i, X_i−1), a simple representation of the characteristic function of S_n is obtained. The representation is in term of the maximal eigenvalue of the linear operator sending a function g(x) into the function x → E(g(X_i)exp[itƒ(X_i, x)]|X_i−1 = x).     

Large deviations for heavy-tailed random sums of independent random variables with dominatedly varying tails

We prove large deviation results on the partial and random sums Sn = ∑i=1n Xi,n≥1; S(t) = ∑i=1N(t) Xi, t≥0, where {N(t);t≥0} are non-negative integer-valued random variables and {Xn;n≥1} are independent non-negative random variables with distribution, Fn, of Xn, independent of {N(t); t≥0}. Special attention is paid to the distribution of dominated variation.     

Random Quadratic Forms and the Bootstrap for U-Statistics

We study the bootstrap distribution for U-statistics with special emphasis on the degenerate case. For the Efron bootstrap we give a short proof of the consistency using Mallows′ metrics. We also study the i.i.d. weighted bootstrap [formula] where (X_i) and (ξ_i) are two i.i.d. sequences, independent of each other and where Eξ_i = 0, Var(ξ_i) = 1. It turns out that, conditionally given (X_i), this random quadratic form converges weakly to a Wiener-Ito double stochastic integral ∫¹₀ ∫¹₀h(F⁻¹(x), F⁻¹(y)) dW(x) dW(y). As a by-product we get an a.s. limit theorem for the eigenvalues of the matrix H_n=((1/n)h(X_i, X_j))_{1 ≤ i, j ≤ n}.     

Optimal broadcast on parallel locality models

In this paper matching upper and lower bounds for broadcast on general purpose parallel computation models that exploit network locality are proven. These models try to capture both the general purpose properties of models like the PRAM or BSP on the one hand, and to exploit network locality of special purpose models like meshes, hypercubes, etc., on the other hand. They do so by charging a cost l(|i−j|) for a communication between processors i and j, where l is a suitably chosen latency function.An upper bound T(p)=∑_i=0^loglogp2ⁱ·l(p^1/2i) on the runtime of a broadcast on a p processor H-PRAM is given, for an arbitrary latency function l(k).The main contribution of the paper is a matching lower bound, holding for all latency functions in the range from l(k)=Ω(logk/loglogk) to l(k)=O(log²k). This is not a severe restriction since for latency functions l(k)=O(logk/log¹⁺log(k)) with arbitrary >0, the runtime of the algorithm matches the trivial lower bound Ω(logp) and for l(k)=Θ(log¹⁺k) or l(k)=Θ(k), the runtime matches the other trivial lower bound Ω(l(p)). Both upper and lower bounds apply for other parallel locality models like Y-PRAM, D-BSP and E-BSP, too.     

Approximations of Two-Place Functions by Finite Sums of Terms with Separable Variables

It is known that if a smooth function h in two real variables x and y belongs to the class Σ_n of all sums of the form Σⁿ_k=1ƒ_k(x) g_k(y), then its (n + 1)th order "Wronskian" det[h_xⁱy^j]ⁿ_i,j=0 is identically equal to zero. The present paper deals with the approximation problem h(x, y) Σⁿ_k=1ƒ_k(x) g_k(y) with a prescribed n, for general smooth functions h not lying in Σ_n. Two natural approximation sums T=T(h) Σ_n, S=S(h) Σ_n are introduced and the errors |h-T|, |h-S| are estimated by means of the above mentioned Wronskian of the function h. The proofs utilize the technique of ordinary linear differential equations.     

A continuous function space with a Faber basis

Let be compact with #S=∞ and let C(S) be the set of all real continuous functions on S. We ask for an algebraic polynomial sequence (P_n)_n=0^∞ with deg P_n=n such that every fC(S) has a unique representation f=∑_i=0^∞ α_iP_i and call such a basis Faber basis. In the special case of , 0<q<1, we prove the existence of such a basis. A special orthonormal Faber basis is given by the so-called little q-Legendre polynomials. Moreover, these polynomials state an example with A(S_q)≠U(S_q)=C(S_q), where A(S_q) is the so-called Wiener algebra and U(S_q) is the set of all fC(S_q) which are uniquely represented by its Fourier series.     

Solving polynomial optimization problems via the truncated tangency variety and sums of squares

Let f,g_i,i=1,…,l,h_j,j=1,…,m, be polynomials on Rⁿ and S?{x∈Rⁿ∣g_i(x)=0,i=1,…,l,h_j(x)≥0,j=1,…,m}. This paper proposes a method for finding the global infimum of the polynomial f on the semialgebraic set S via sum of squares relaxation over its truncated tangency variety, even in the case where the polynomial f does not attain its infimum on S. Under a constraint qualification condition, it is demonstrated that: (i) The infimum of f on S and on its truncated tangency variety coincide; and (ii) A sums of squares certificate for nonnegativity of f on its truncated tangency variety. These facts imply that we can find a natural sequence of semidefinite programs whose optimal values converge, monotonically increasing to the infimum of f on S.     

On Approximate ℓ 1 Systems in Banach Spaces

Let X be a real Banach space and let (f(n)) be a positive nondecreasing sequence. We consider systems of unit vectors (x_i)^∞_i=1 in X which satisfy ∑_iA±x_i|A|−f(|A|), for all finite A and for all choices of signs. We identify the spaces which contain such systems for bounded (f(n)) and for all unbounded (f(n)). For arbitrary unbounded (f(n)), we give examples of systems for which [x_i] is H.I., and we exhibit systems in all isomorphs of ℓ₁ which are not equivalent to the unit vector basis of ℓ₁. We also prove that certain lacunary Haar systems in L₁ are quasi-greedy basic sequences.     

Tractability of Multivariate Integration for Weighted Korobov Classes

We study the worst-case error of multivariate integration in weighted Korobov classes of periodic functions of d coordinates. This class is defined in terms of weights γ_j which moderate the behavior of functions with respect to successive coordinates. We study two classes of quadrature rules. They are quasi-Monte Carlo rules which use n function values and in which all quadrature weights are 1/n and rules for which all quadrature weights are non-negative. Tractability for these two classes of quadrature rules means that the minimal number of function values needed to guarantee error in the worst-case setting is bounded by a polynomial in d and ⁻¹. Strong tractability means that the bound does not depend on d and depends polynomially on ⁻¹. We prove that strong tractability holds iff ∑^∞_j=1 γ_j<∞, and tractability holds iff lim sup_d→∞ ∑^d_j=1 γ_j/log d<∞. Furthermore, strong tractability or tractability results are achieved by the relatively small class of lattice rules. We also prove that if ∑^∞_j=1 γ^1/α_j<∞, where α measures the decay of Fourier coefficients in the weighted Korobov class, then for d1, n prime and δ>0 there exist lattice rules that satisfy an error bound independent of d and of order n^−α/2+δ. This is almost the best possible result, since the order n^−α/2 cannot be improved upon even for d=1. A corresponding result is deduced for weighted non-periodic Sobolev spaces: if ∑^∞_j=1 γ^1/2_j<∞, then for d1, n prime and δ>0 there exist shifted lattice rules that satisfy an error bound independent of d and of order n^−1+δ. We also check how the randomized error of the (classical) Monte Carlo algorithm depends on d for weighted Korobov classes. It turns out that Monte Carlo is strongly tractable iff ∑^∞_j=1 log γ_j<∞ and tractable iff lim sup_d→∞ ∑^d_j=1 log γ_j/log d<∞. Hence, in particular, for γ_j=1 we have the usual Korobov space in which integration is intractable for the two classes of quadrature rules in the worst-case setting, whereas Monte Carlo is strongly tractable in the randomized setting.