Self-intersection local time for Gaussian ′( )-processes: Existence, path continuity and examples

In this paper we develop a criterion for existence or non-existence of self-intersection local time (SILT) for a wide class of Gaussian ′( ^d)-valued processes, we show that quite generally the SILT process has continuous paths, and we give several examples which illustrate existence of SILT for different ranges of dimensions (e.g., d ≤ 3, d ≤ 7 and 5 ≤ d ≤ 11 in the Brownian case). Some of the examples involve branching and exhibit “dimension gaps”. Our results generalize the work of Adler and coauthors, who studied the special case of “density processes” and proved that SILT paths are cadlag in the Brownian case making use of a “particle picture” approximation (this technique is not available for our general formulation).     

Complexity results for scheduling tasks with discrete starting times

Suppose that n independent tasks are to be scheduled without preemption on a set of identical parallel processors. Each task T_i requires a given execution time τ_i and it may be started for execution on any processor at any of its prescribed starting times s_i1, s_i2, …, s_iki, with k_i ≤ k for some fixed integer k. We first prove that the problem of finding a feasible schedule on a single processor is NP-complete in the strong sense even when τ_i ε {τ, τ′} and k_i ≤ 3 for 1 ≤ i ≤ n. The same problem is, however, shown to be solvable in O(n log n) time, provided s_iki − s_i1 < τ_i for 1 ≤ i ≤ n. We then show that the problem of finding a feasible schedule on an arbitrary number of processors is strongly NP-complete even when τ_i ε {τ, τ′}, k_i = 2 and s_i2 − s_i1 = δ < τ_i for 1 ≤ i ≤ n. Finally a special case with k_i = 2 and s_i2 − s_i1 = 1, 1 ≤ i ≤ n, of the above multiprocessor scheduling problem is shown to be solvable in polynomial time.     

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.     

Maximum Likelihood Estimation of Means and Variances from Normal Populations Under Simultaneous Order Restrictions

For k normal populations with unknown means μ_i and unknown variances σ²_i, i = 1, ..., k, assume that there are some order restrictions among the means and variances, respectively, for example, simple order restrictions: μ₁ ≤ μ₂ ≤ ... ≤ μ_k and σ²₁ ≥ σ²₂ ≥ ... ≥ σ²_k > 0. Some properties of maximum likelihood estimation of μ_is and σ²_i are discussed and an algorithm of obtaining the maximum likelihood estimators under the order restrictions is proposed.     

Weak Limits for Multivariate Random Sums

Let {Xi, i1} be a sequence of i.i.d. random vectors inRd, and letνp, 0<p<1, be a positive, integer valued random variable, independent ofXis. Theν-stable distributions are the weak limits of properly normalized random sums ∑νpi=1 Xiasνp ∞ andpνp ν. We study the properties ofν-stable laws through their representation via stable laws. In particular, we estimate their tail probabilities and provide conditions for finiteness of their moments.     

On weighted Lebesgue function type sums

Let I be a finite or infinite interval and dμ a measure on I. Assume that the weight function w(x)>0, w^′(x) exists, and the function w^′(x)/w(x) is non-increasing on I. Denote by ℓ_k's the fundamental polynomials of Lagrange interpolation on a set of nodes x₁<x₂<<x_n in I. The weighted Lebesgue function type sum for 1≤i<j≤n and s≥1 is defined by

In this paper the exact lower bounds of S_n(x) on a “big set” of I and are obtained. Some applications are also given.     

Generating random correlation matrices based on partial correlations

A d-dimensional positive definite correlation matrix R=(ρ_ij) can be parametrized in terms of the correlations ρ_i,i+1 for i=1,…,d-1, and the partial correlations ρ_{ij|i+1,…j-1} for j-i2. These parameters can independently take values in the interval (-1,1). Hence we can generate a random positive definite correlation matrix by choosing independent distributions F_ij, 1i<jd, for these parameters. We obtain conditions on the F_ij so that the joint density of (ρ_ij) is proportional to a power of det(R) and hence independent of the order of indices defining the sequence of partial correlations. As a special case, we have a simple construction for generating R that is uniform over the space of positive definite correlation matrices. As a byproduct, we determine the volume of the set of correlation matrices in -dimensional space. To prove our results, we obtain a simple remarkable identity which expresses det(R) as a function of ρ_i,i+1 for i=1,…,d-1, and ρ_{ij|i+1,…j-1} for j-i2.     

An Asymptotic Property of Schachermayer's Space under Renorming

Let X be a Banach space with closed unit ball B. Given k , X is said to be k-β, respectively, (k + 1)-nearly uniformly convex ((k + 1)-NUC), if for every ε > 0 there exists δ, 0 < δ < 1, so that for every x B and every ε-separated sequence (x_n) B there are indices (n_i)^k_{i = 1}, respectively, (n_i)^{k + 1}_{i = 1}, such that (1/(k + 1))||x + ∑^k_{i = 1} x_ni|| ≤ 1 − δ, respectively, (1/(k + 1))||∑^{k + 1}_{i = 1} x_ni|| ≤ 1 − δ. It is shown that a Banach space constructed by Schachermayer is 2-β, but is not isomorphic to any 2-NUC Banach space. Modifying this example, we also show that there is a 2-NUC Banach space which cannot be equivalently renormed to be 1-β.     

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.     

On nonautonomous linear systems of differential and difference equations with -symmetric coefficient matrices

Let denote the set of continuous n×n matrices on an interval . We say that is a nontrivial k-involution if where ζ=e^-2πi/k, d₀+d₁++d_k-1=n, and with . We say that is R-symmetric if R(t)A(t)R^-1(t)=A(t), , and we show that if A is R-symmetric then solving x^′=A(t)x or x^′=A(t)x+f(t) reduces to solving k independent d_ℓ×d_ℓ systems, 0ℓk-1. We consider the asymptotic behavior of the solutions in the case where . Finally, we sketch analogous results for linear systems of difference equations.     

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.     

A random CLT for dependent random variables

We introduce a new condition for {Y_τn} to have the same asymptotic distribution that {Y_n} has, where {Y_n} is a sequence of random elements of a metric space (S, d) and {τ_n} is a sequence of random indices. The condition on {Y_n} is that max_iDnd(Y_i, Y_an)→^p0 as n → ∞, where D_n = {i: |k_i−k_an| ≤ δ_ank_an} and {δ_n} is a nonincreasing sequence of positive numbers. The condition on {τ_n} is that P(|(k_τn/k_an)−1| > δ_an) → 0 as n → ∞. Under these conditions, we will show that d(Y_τn, Y_an) → ^P0 and apply this result to the CLT for a general class of sequences of dependent random variables.     

On the Strong Law of Large Numbers and the Law of the Logarithm for Weighted Sums of Independent Random Variables with Multidimensional Indices

Let (X, X ; ^d} be a field of independent identically distributed real random variables, 0 < p < 2, and {a _, ; ( , ) ^d × ^d, ≤ } a triangular array of real numbers, where ^d is the d-dimensional lattice. Under the minimal condition that sup _, |a _, | < ∞, we show that | |^{− 1/p} ∑ _≤ a _, X → 0 a.s. as | | → ∞ if and only if E(|X|^p(L|X|)^{d − 1}) < ∞ provided d ≥ 2. In the above, if 1 ≤ p < 2, the random variables are needed to be centered at the mean. By establishing a certain law of the logarithm, we show that the Law of the Iterated Logarithm fails for the weighted sums ∑ _≤ a _, X under the conditions that EX = 0, EX² < ∞, and E(X²(L|X|)^{d − 1}/L₂|X|) < ∞ for almost all bounded families {a _, ; ( , ) ^d × ^d, ≤ of numbers.     

Uniform Estimates for a Class of Evolution Equations

L^∞ estimates are derived for the oscillatory integral ∫⁺₀^∞e^{−i(xλ + (1/m) tλm)}a(λ) dλ, where 2 ≤ m and (x, t) × ₊. The amplitude a(λ) can be oscillatory, e.g., a(λ) = e^{it (λ)} with (λ) a polynomial of degree ≤ m − 1, or it can be of polynomial type, e.g., a(λ) = (1 + λ)^k with 0 ≤ k ≤ (m − 2). The estimates are applied to the study of solutions of certain linear pseudodifferential equations, of the generalized Schrödinger or Airy type, and of associated semilinear equations.     

A general framework of compactly supported splines and wavelets

Let {V_k} be a nested sequence of closed subspaces that constitute a multiresolution analysis of L²( ). We characterize the family Φ = {φ} where each φ generates this multiresolution analysis such that the two-scale relation of φ is governed by a finite sequence. In particular, we identify the ε Φ that has minimum support. We also characterize the collection Ψ of functions η such that each η generates the orthogonal complementary subspaces W_k of V_k, . In particular, the minimally supported ψ ε Ψ is determined. Hence, the “B-spline” and “B-wavelet” pair (, ψ) provides the most economical and computational efficient “spline” representations and “wavelet” decompositions of L² functions from the “spline” spaces V_k and “wavelet” spaces W_k, k . A very general duality principle, which yields the dual bases of both {(·−j):j and {η(·−j):j } for any η ε Ψ by essentially interchanging the pair of two-scale sequences with the pair of decomposition sequences, is also established. For many filtering applications, it is very important to select a multiresolution for which both and ψ have linear phases. Hence, “non-symmetric” and ψ, such as the compactly supported orthogonal ones introduced by Daubechies, are sometimes undesirable for these applications. Conditions on linear-phase φ and ψ are established in this paper. In particular, even-order polynomial B-splines and B-wavelets φ_m and ψ_m have linear phases, but the odd-order B-wavelet only has generalized linear phases.     

On subspace arrangements of type

Let denote the subspace arrangement formed by all linear subspaces in given by equations of the form

₁x_i1=₂x_i2==_kx_ik,

where 1i₁<<i_kn and (₁,…,_k){+1,−1}^k.Some important topological properties of such a subspace arrangement depend on the topology of its intersection lattice. In a previous work on a larger class of subspace arrangements by Björner and Sagan (J. Algebraic Combin. 5 (1996) 291–314) the topology of the intersection lattice turned out to be a particularly interesting and difficult case.We prove in this paper that Pure(Π_n,k^±) is shellable, hence that Π_n,k^± is shellable for k>n/2. Moreover, we prove that unless i≡n−2 (mod k−2) or i≡n−3 (mod k−2), and that is free abelian for i≡n−2 (mod k−2). In the special case of Π_2k,k^± we determine homology completely. Our tools are generalized lexicographic shellability, as introduced in Kozlov (Ann. Combin. 1 (1997) 67–90), and a spectral sequence method for the computation of poset homology first used in Hanlon (Trans. Amer. Math. Soc. 325 (1991) 1–37).We state implications of our results on the cohomology of the complements of the considered arrangements.     

Moment methods in two point Padé approximation

In the separable Hilbert space (H, ·, ·) the following “operator moment problem” is solved: given a complex sequence (c_k)_{k ε Z} generated by a meromorphic function f, find T ε B(H) and u₀ ε H such that T^ku₀, u₀ = c_k (k ε Z). If the sequence (c_k)_{k ε Z} is “normal,” an adapted form of Vorobyev's method of moments yields a sequence of two point Padé approximants to f. A sufficient condition for convergence of this sequence of approximants is given.     

Theorems of large deviations in the multivariate invariance principle

Let B be a real separable Banach space with norm |ß|_B, X, X₁, X₂, … be a sequence of centered independent identically distributed random variables taking values in B. Let s_n = s_n(t), 0 ≤ t ≤ 1 be the random broken line such that s_n(0) = 0, s_n(k/n) = n^−1/2 Σ_i=1^k X_i for n = 1, 2, … and k = 1, …, n. Denote |s_n|_B = sup_{0 ≤ t ≤ 1} |s_n(t)|_B and assume that w(t), 0 ≤ t ≤ 1 is the Wiener process such that covariances of w(1) and X are equal. We show that under appropriate conditions P(|s_n|_B > r) = P(|w|_B > r)(1 + o(1)) and give estimates of the remainder term. The results are new already in the case of B having finite dimension.     

Prophet inequalities for parallel processes

Generalizations of prophet inequalities for single sequences are obtained for optimal stopping of several parallel sequences of independent random variables. For example, if {X_{i, j}, 1 ≤ i ≤ n, 1 ≤ j < ∞} are independent non-negative random variables, then

Full-size image

and this bound is best possible. Applications are made to comparisons of the optimal expected returns of various alternative methods of stopping of parallel processes.     

Twice Q-polynomial distance-regular graphs are thin

Let Γ be a distance-regular graph of diameter d 3. For each vertex χ of Γ, let T(χ) denote the subconstituent algebra for Γ with respect to χ. An irreducible T(χ)-module W is said to be thin if dim E_i^*(χ) W 1 for 0 i d, where E_i^*(χ) is the projection onto the ith subconstituent for Γ with respect to χ. The graph Γ is said to be thin if, for each vertex χ of Γ, very irreducible T(χ)-module is thin. Our main result is the following Theorem: If Γ has two Q-polynomial structures, then Γ is thin.