Conditions for finite moments of waiting times inG/G/1 queues

We find conditions for E(W ) to be finite whereW is the stationary waiting time random variable in a stableG/G/1 queue with dependent service and inter-arrival times.Supported in part by KBN under grant 640/2/9, and at the Center for Stochastic Processes, Department of Statistics at the University of North Carolina Chapel Hill by the Air Force Office of Scientific Research Grant No. 91-0030 and the Army Research Office Grant No. DAAL09-92-G-0008.     

Diffusion equation techniques in stochastic monotonicity and positive correlations

Summary A diffusion equation approach is investigated for the study of stochastic monotonicity, positive correlations and the preservation of Lipschitz functions. Necessary and sufficient conditions are given for diffusion semigroups to be stochastically monotonic and to preserve the class of positively correlated measures. Applications are given which discuss the shape of the ground state for Schrödinger operators-+V with FKG potentialsV.Research supported by NSF Grant DMS 8807816.Research supported by NSF grant DMS 8701212 and Air Force Office of Scientific Research Contract No. F49620 85C 0144.Written while visiting, Center for Stochastic Processes, University of North Carolina.     

Asymptotic behavior of eigenvalues and random updating schemes

For a stochastic matrix (Q _ij ^T ) _i,j=1 ^M withQ _ij ^T exp(–U(ij)/T) at the off-diagonal positions, we develop an algorithm to evaluate the asymptotic convergence rate of all eigenvalues ofQ _ij ^T asT 0 using Ventcel's optimal graphs. As an application we can compare the convergence rates of some random updating schemes used in image processing.This research was partially supported by the National Science Council, Taiwan and Air Force Office of Scientific Research Contract No. F49620 S5C 0144, and was completed while Tzuu-Shuh Chiang was visiting the Center for Stochastic Processes, Department of Statistics, University of North Carolina, Chapel Hill, NC 27599-3260, USA.     

Doeblin's big limit theorem

Doeblin regarded his paper(²) as his hardest work. The big limit is that ofP(ⁿ)(x, E) asn tends to infinity, in a measurable non-topologized space. An exposition of part one of this paper was published in Ref. 1. This is the exposition of part two, which contains some reparation as well as clarification.Doeblin's great contributions to probability theory were remembered at a conference 50 Years after Doeblin: Developments in the Theory of Markov Chains, Markov Processes and Sums of Random Variables held at Blaubeuren. Germany November 2–7, 1991. Professor Chung contributed this article to further celebrate this occasion. The editor thanks him.     

Polynomial inequalities representing polyhedra

Our main result is that every n-dimensional polytope can be described by at most 2n–1 polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an n-dimensional pointed polyhedral cone we prove the bound 2n–2 and for arbitrary polyhedra we get a constructible representation by 2n polynomial inequalities.Supported by the DFG Research Center Mathematics for key technologies (FZT 86) in Berlin.     

Large deviations for empirical measures with degenerate limiting distribution

Summary This paper studies the large deviations of the empirical measure associated withn independent random variables with a degenerate limiting distribution asn. A large deviations principle — quite unlike the classical Sanov type results — is established for such empirical measures in a general Polish space setting. This result is applied to the large deviations for the empirical process of a system of interacting particles, in which the diffusion coefficient vanishes as the number of particles tends to infinity. A second way in which the present example differs from previous work on similar weakly interacting systems is that there is a singularity in the mean-field type interaction.     

On the Value of a Random Minimum Weight Steiner Tree

Consider a complete graph on n vertices with edge weights chosen randomly and independently from an exponential distribution with parameter 1. Fix k vertices and consider the minimum weight Steiner tree which contains these vertices. We prove that with high probability the weight of this tree is (1+o(1))(k-1)(log n-log k)/n when k =o(n) and n.* Research supported in part by NSF grant DSM9971788 Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting IBM T. J. Watson Research Center.     

Intersection queries in sets of disks

In this paper we develop some new data structures for storing a set of disks that can answer different types of intersection queries efficiency. If the disks are non-intersecting we obtain a linear size data structure that can report allk disks intersecting a query line segment in timeO(n ⁺ +k), wheren is the number of disks,=log₂(1+5)–1 0.695, and is an arbitrarily small positive constant. If the segment is a full line, the query time becomesO(n +k). For intersecting disks we obtain anO(n logn) size data structure that can answer an intersection query in timeO(n ^2/3 log² n+k). We also present a linear size data structure for ray shooting queries, whose query time isO(n ).The research of the first two authors was supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). The work of the third author was supported byDimacs (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center — NSF-STC88-09648.     

Strong approximation of semimartingales and statistical processes

Summary As an application of general convergence results for semimartingales, exposed in their book Limit Theorems for Stochastic Processes, Jacod and Shiryaev obtained a fundamental result on the convergence of likelihood ratio processes to a Gaussian limit. We strengthen this result in a quantitative sense and show that versions of the likelihood ratio processes can be defined on the space of the limiting experiment such that we get pathwise almost sure approximations with respect to the uniform metric. The approximations are considered under both sequences of measures, the hypothesisP ⁿ and the alternative . A consequence is e.g. an estimate for the speed of convergence in the Prohorov metric. New approximation techniques for stochastic processes are developed.This article was processed by the author using the L^AT_EX style filepljourIm from Springer-Verlag.     

The upper envelope of piecewise linear functions: Tight bounds on the number of faces

This note proves that the maximum number of faces (of any dimension) of the upper envelope of a set ofn possibly intersectingd-simplices ind+1 dimensions is (n ^d (n)). This is an extension of a result of Pach and Sharir [PS] who prove the same bound for the number ofd-dimensional faces of the upper envelope.This work was supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by the National Science Foundation under Grant CCR-8714565. Research on the presented result was partially carried out while the author worked for the IBM T. J. Watson Research Center at Yorktown Height, New York, USA.     

A parallel algorithm for the eigenvalues and eigenvectors of a general complex matrix

Summary A new parallel Jacobi-like algorithm is developed for computing the eigenvalues of a general complex matrix. Most parallel methods for this problem typically display only linear convergence, Sequential norm-reducing algorithms also exist and they display quadratic convergence in most cases. The new algorithm is a parallel form of the norm-reducing algorithm due to Eberlein. It is proven that the asymptotic convergence rate of this algorithm is quadratic. Numerical experiments are presented which demonstrate the quadratic convergence of the algorithm and certain situations where the convergence is slow are also identified. The algorithm promises to be very competitive on a variety of parallel architectures. In particular, the algorithm can be implemented usingn ²/4 processors, takingO(n log² n) time for random matrices.This research was supported by the Office of Naval Research under Contract N00014-86-k-0610 and by the U.S. Army Research Office under Contract DAAL 03-86-K-0112. A portion of this research was carried out while the author was visiting RIACS, Nasa Ames Research Center     

An upper bound on the number of planarK-sets

Given a setS ofn points, a subsetX of sizek is called ak-set if there is a hyperplane that separatesX fromS–X. We prove thatO(nk/log*k) is an upper bound for the number ofk-sets in the plane, thus improving the previous bound of Erdös, Lovász, Simmons, and Strauss by a factor of log*k.The research of J. Pach was supported in part by NSF Grant CCR-8901484 and by Grant OTKA-1418 from the Hungarian Foundation for Scientific Research. The research of W. Steiger and E. Szemerédi was supported in part by NSF Grant CCR-8902522. All authors express gratitude to the NSF DIMACS Center at Rutgers.     

Oblique Interactions between Internal Solitary Waves

In this paper, we study the oblique interaction of weakly, nonlinear, long internal gravity waves in both shallow and deep fluids. The interaction is classified as weak when where Δ₁=|c_m/c_n?cosδ|, Δ₂=|c_n/c_m?cosδ|,c_m,n, are the linear, long wave speeds for waves with mode numbers m, n, δ is the angle between the respective propagation directions, and α measures the wave amplitude. In this case, each wave is governed by its own Kortweg-de Vries (KdV) equation for a shallow fluid, or intermediate long-wave (ILW) equation for a deep fluid, and the main effect of the interaction is an 0(α) phase shift. A strong interaction (I) occurs when Δ_1,2 are 0(α), and this case is governed by two coupled Kadomtsev-Petviashvili (KP) equations for a shallow fluid, or two coupled two-dimensional ILW equations for deep fluids. A strong interaction (II) occurs when Δ₁ is 0(α), and (or vice versa), and in this case, each wave is governed by its own KdV equation for a shallow fluid, or ILW equation for a deep fluid. The main effect of the interaction is that the phase shift associated with Δ₁ leads to a local distortion of the wave speed of the mode n. When the interacting waves belong to the same mode (i.e., m = n) the general results simplify and we show that for a weak interaction the phase shift for obliquely interacting waves is always negative (positive) for (1/2+cosδ)>0(<0), while the interaction term always has the same polarity as the interacting waves.     

Statistical Inference for Stochastic Processes

Table of Contents

Statistical Inference for Stochastic Processes     

The number of edges of many faces in a line segment arrangement

We show that the maximum number of edges boundingm faces in an arrangement ofn line segments in the plane isO(m ^2/3 n ^2/3+n(n)+nlogm). This improves a previous upper bound of Edelsbrunner et al. [5] and almost matches the best known lower bound which is (m ^2/3 n ^2/3+n(n)). In addition, we show that the number of edges bounding anym faces in an arrangement ofn line segments with a total oft intersecting pairs isO(m ^2/3 t ^1/3+n(t/n)+nmin{logm,logt/n}), almost matching the lower bound of (m ^2/3 t ^1/3+n(t/n)) demonstrated in this paper.Work on this paper by the first and fourth authors has been partially supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484. Work by the first author has also been supported by an AT&T Bell Laboratories Ph.D. scholarship at New York University and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center (NSF-STC88-09648). Work by the second author has been supported by NSF under Grants CCR-87-14565 and CCR-89-21421. Work by the fourth author has additionally been supported by grants from the U.S.-Israeli Binational Science Foundation, the NCRD (the Israeli National Council for Research and Development) and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli National Academy of Sciences.     

Call for Papers: Bayesian Inference for Stochastic Processes

Call for Papers

Call for Papers: Bayesian Inference for Stochastic Processes     

An optimization problem on subsets of the symmetric positive-semidefinite matrices

Motivated by the metricsstress problem in multidimensional scaling, the authors consider the more general problem of minimizing a strictly convex function on a particular subset ofR ^{n × n} . The subset in question is the intersection of a linear subspace with the symmetric positive-semidefinite matrices of rank p. Because of the rank restriction, this subset is not convex. Several equivalent formulations of this problem are derived, and the advantages and disadvantages of each formulation are discussed.Part of this research was conducted while the authors were visitors at the Center for Research on Parallel Computation, Rice University, Houston, Texas. The first author was partially supported by National Science Foundation Grant RII-89-05080.     

Counting facets and incidences

We show thatm distinct cells in an arrangement ofn planes in ³ are bounded byO(m ^2/3 n+n ²) faces, which in turn yields a tight bound on the maximum number of facets boundingm cells in an arrangement ofn hyperplanes in ^d , for everyd3. In addition, the method is extended to obtain tight bounds on the maximum number of faces on the boundary of all nonconvex cells in an arrangement of triangles in ³. We also present a simpler proof of theO(m ^2/3 n ^d/3+n ^d–1) bound on the number of incidences betweenn hyperplanes in ^d andm vertices of their arrangement.Work on this paper was supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center Grant NSF-STC88-09648, and by NSA Grant MDA 904-89-H-2030.     

Energy functional depending on elastic strain and chemical composition

In this paper we deal with energy functionals depending on elastic strain and chemical composition and we obtain lower semicontinuity results, existence theorems and relaxation in the spacesH ^1,p(; ⁿ)×L ^q (; ^d) with respect to weak convergence. Our proofs use parametrized measures associated with weakly converging sequences.The research was partially supported by the National Science Foundation under Grants No. DMS-9000133 and DMS-9201215 and also by the Army Research Office and the National Science Foundation through the Center for Nonlinear Analysis.The research was partially supported by the National Science Foundation uncer Grants No. DMs 911572, the AFOSR 91 0301, the ARO DAAL03 92 G 003 and also by the ARO and the NSF through the Center for Nonlinear Analysis.The research was supported by DGICYT (Spain) through Programa de Perfeccionamiento y Movilidad del Personal Investigador and through grant PB90-0245, by the Army Research Office and the National Science Foundation through the Center for Nonlinear Analysis and also by the project EurHomogenization SC1-CT91-0732 of the European Comunity.