A Computationally Motivated Definition Of Parametric Estimation And Its Applications To The Gaussian Distribution

We introduce a treatment of parametric estimation in which optimality of an estimator is measured in probability rather than in variance (the measure for which the strongest general results are known in statistics). Our motivation is that the quality of an approximation algorithm is measured by the probability that it fails to approximate the desired quantity within a set tolerance. We concentrate on the Gaussian distribution and show that the sample mean is the unique “best” estimator, in probability, for the mean of a Gaussian distribution. We also extend this method to general penalty functions and to multidimensional spherically symmetric Gaussians. The algorithmic significance of studying the Gaussian distribution is established by showing that determining the average matching size in a graph is #P-hard, and moreover approximating it reduces to estimating the mean of a random variable that (under some mild conditions) has a distribution closely approximating a Gaussian. This random variable is (essentially) polynomial time samplable, thereby yielding an FPRAS for the problem.     

An analysis of a Monte Carlo algorithm for estimating the permanent

Karmarkar, Karp, Lipton, Lovász, and Luby proposed a Monte Carlo algorithm for approximating the permanent of a non-negativen×n matrix, which is based on an easily computed, unbiased estimator. It is not difficult to construct 0,1-matrices for which the variance of this estimator is very large, so that an exponential number of trials is necessary to obtain a reliable approximation that is within a constant factor of the correct value. Nevertheless, the same authors conjectured that for a random 0,1-matrix the variance of the estimator is typically small. The conjecture is shown to be true; indeed, for almost every 0,1-matrixA, just O(nw(n)e ^-2) trials suffice to obtain a reliable approximation to the permanent ofA within a factor 1±ɛ of the correct value. Here ω(n) is any function tending to infinity asn→∞. This result extends to random 0,1-matrices with density at leastn ^−1/2ω(n). It is also shown that polynomially many trials suffice to approximate the permanent of any dense 0,1-matrix, i.e., one in which every row- and column-sum is at least (1/2+α)n, for some constant α>0. The degree of the polynomial bounding the number of trials is a function of α, and increases as α→0. Supported by NSF grant CCR-9225008. The work described here was partly carried out while the author was visiting Princeton University as a guest of DIMACS (Center for Discrete Mathematics and Computer Science).     

Computable de Finetti measures

We prove a computable version of the de Finetti theorem on exchangeable sequences of real random variables. As a consequence, exchangeable stochastic processes expressed in probabilistic functional programming languages can be automatically rewritten as procedures that do not modify non-local state. Along the way, we prove that a distribution on the unit interval is computable if and only if its moments are uniformly computable.     

Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard

Given an m×n integer matrix A of full row rank, we consider the problem of computing the maximum of ∥B ^-1 A∥₂ where B varies over all bases of A. This quantity appears in various places in the mathematical programming literature. More recently, logarithm of this number was the determining factor in the complexity bound of Vavasis and Ye’s primal-dual interior-point algorithm. We prove that the problem of approximating this maximum norm, even within an exponential (in the dimension of A) factor, is NP-hard. Our proof is based on a closely related result of L. Khachiyan [1]. Received November 13, 1998 / Revised version received January 20, 1999? Published online May 12, 1999     

Analysis of a three node queueing network

The three node Jackson queueing network is the simplest acyclic network in which in equilibrium the sojourn times of a customer at each of the nodes are dependent. We show that assuming the individual sojourn times are independent provides a good approximation to the total sojourn time. This is done by simulating the network and showing that the sojourn times generally pass a Kolmogorov-Smirnov test as having come from the approximating distribution. Since the sum of dependent random variables may have the same distribution as the sum of independent random variables with the same marginal distributions, it is conceivable that our approximation is exact. However, we numerically compute upper and lower bounds for the distribution of the total sojourn time; these bounds are so close that the approximating distribution lies outside of the bounds. Thus, the bounds are accurate enough to distinguish between the two distributions even though the Kolmogorov-Smirnov test generally cannot.     

The Selfconsistent Pauli Equation

 We deal with consistent first order non-relativistic corrections (i.e. in the small parameter , where c is the speed of light) of the Dirac–Maxwell system. We discuss a selfconsistent modeling of the Pauli equation as the O(ɛ) approximation of the Dirac equation. We suggest a coupling to the “magnetostatic”O(ɛ) approximation of the Maxwell equations consisting of Poisson equations for the four components of the potential. We sketch the semiclassical/nonrelativistic limits of this model. (Received 22 May 2000)     

Asymptotic independence of maximum waiting times for increasing alphabet

For everyk≥1 consider the waiting time until each pattern of lengthk over a fixed alphabet of sizen appears at least once in an infinite sequence of independent, uniformly distributed random letters. Lettingn→∞ we determine the limiting finite dimensional joint distributions of these waiting times after suitable normalization and provide an estimate for the rate of convergence. It will turn out that these waiting times are getting independent. Research supported by the Hungarian National Foundation for Scientific Research, Grant No. 1905.     

Translated Poisson Approximation for Markov Chains

The paper is concerned with approximating the distribution of a sum W of integer valued random variables Y _i , 1 ≤ i ≤ n, whose distributions depend on the state of an underlying Markov chain X. The approximation is in terms of a translated Poisson distribution, with mean and variance chosen to be close to those of W, and the error is measured with respect to the total variation norm. Error bounds comparable to those found for normal approximation with respect to the weaker Kolmogorov distance are established, provided that the distribution of the sum of the Y _i ’s between the successive visits of X to a reference state is aperiodic. Without this assumption, approximation in total variation cannot be expected to be good.     

On mixed finite element methods for linear elastodynamics

Summary We construct and analyze finite element methods for approximating the equations of linear elastodynamics, using mixed elements for the discretization of the spatial variables. We consider two different mixed formulations for the problem and analyze semidiscrete and up to fourth-order in time fully discrete approximations.L ² optimal-order error estimates are proved for the approximations of displacement and stress.Work supported in part by the Hellenic State Scholarship Foundation     

Transient flows in queueing systems via closure approximations

We present a method for obtaining approximations to the distribution of flow times of customers in arbitrary queueing systems. We first propose approximations for uni-variate and multi-variate distributions of non-negative random variables. Then using a closure approximation, we show that the distribution of flow time can be calculated recursively. Computational results for the single server, multi-server and tandem queues are encouraging, with less than 5%average error in the mean flow time in most cases. The average error in the variance of flow times is found to be less than 10% for the more regular distributions.     

Quick Approximation to Matrices and Applications

m ×n matrix A with entries between say −1 and 1, and an error parameter ε between 0 and 1, we find a matrix D (implicitly) which is the sum of simple rank 1 matrices so that the sum of entries of any submatrix (among the ) of (A−D) is at most εmn in absolute value. Our algorithm takes time dependent only on ε and the allowed probability of failure (not on m, n). We draw on two lines of research to develop the algorithms: one is built around the fundamental Regularity Lemma of Szemerédi in Graph Theory and the constructive version of Alon, Duke, Leffman, R?dl and Yuster. The second one is from the papers of Arora, Karger and Karpinski, Fernandez de la Vega and most directly Goldwasser, Goldreich and Ron who develop approximation algorithms for a set of graph problems, typical of which is the maximum cut problem. From our matrix approximation, the above graph algorithms and the Regularity Lemma and several other results follow in a simple way. We generalize our approximations to multi-dimensional arrays and from that derive approximation algorithms for all dense Max-SNP problems. Received: July 25, 1997     

Packing random rectangles

A random rectangle is the product of two independent random intervals, each being the interval between two random points drawn independently and uniformly from [0,1]. We prove that te number C _n of items in a maximum cardinality disjoint subset of n random rectangles satisfies

Generalized Cornish-Fisher expansions

Cornish-Fisher expansions about the normal distribution provide accurate approximations for distributions of estimates and also for the level in the nominal error of confidence intervals. However, there is an advantage is expanding about a skew distribution like the chi-square, since the first order approximations become second order if the skewness is matched. Higher order approximations are also simplified. We demonstrate the method by approximating the distribution of standardized and Studentized linear combinations of means.     

Vector valued Riesz distributions on Euclidian Jordan algebras

Let V be a Euclidean Jordan algebra, Гthe associated symmetric cone and G be the identity component of the linear automorphism group of Г.In this paper we associate to a certain class of spherical representations (ρ, ɛ) of G certain ɛ-valued Riesz distributions generalizing the classical scalar valued Riesz distributions on V. Our construction is motivated by the analytic theory of unitary highest weight representations where it permits to study certain holomorphic families of operator valued Riesz distributions whose positive definiteness corresponds to the unitarity of a representation of the automorphism group of the associated tube domain Г +iV.     

Equivalence in Finite-Variable Logics is Complete for Polynomial Time

of first-order logic whose formulas contain at most k variables (for some ). We show that for each , equivalence in the logic is complete for polynomial time. Moreover, we show that the same completeness result holds for the powerful extension of with counting quantifiers (for every ). The k-dimensional Weisfeiler–Lehman algorithm is a combinatorial approach to graph isomorphism that generalizes the naive color-refinement method (for ). Cai, Fürer and Immerman [6] proved that two finite graphs are equivalent in the logic if, and only if, they can be distinguished by the k-dimensional Weisfeiler-Lehman algorithm. Thus a corollary of our main result is that the question of whether two finite graphs can be distinguished by the k-dimensional Weisfeiler–Lehman algorithm is P-complete for each . Received: March 23, 1998     

Efficient Algorithms for Approximating Polygonal Chains

We consider the problem of approximating a polygonal chain C by another polygonal chain C' whose vertices are constrained to be a subset of the set of vertices of C . The goal is to minimize the number of vertices needed in the approximation C' . Based on a framework introduced by Imai and Iri [25], we define an error criterion for measuring the quality of an approximation. We consider two problems. (1) Given a polygonal chain C and a parameter ɛ \geq 0 , compute an approximation of C , among all approximations whose error is at most ɛ , that has the smallest number of vertices. We present an O(n ^{4/3 + δ} ) -time algorithm to solve this problem, for any δ > 0; the constant of proportionality in the running time depends on δ . (2) Given a polygonal chain C and an integer k , compute an approximation of C with at most k vertices whose error is the smallest among all approximations with at most k vertices. We present a simple randomized algorithm, with expected running time O(n ^{4/3 + δ} ) , to solve this problem. Received September 17, 1998, and in revised form July 8, 1999.     

Deriving hydrodynamic equations for lattice systems

We study the dynamics of lattice systems in ℤ^d, d ≥ 1. We assume that the initial data are random functions. We introduce the family of initial measures {μ₀^ɛ, ɛ > 0}. The measures μ₀^ɛ are assumed to be locally homogeneous or “slowly changing” under spatial shifts of the order o(ɛ⁻¹ ) and inhomogeneous under shifts of the order ɛ⁻¹ . Moreover, correlations of the measures μ₀^ɛ decrease uniformly in ɛ at large distances. For all τ ∈ ℝ \ 0, r ∈ ℝ^d, and κ > 0, we consider distributions of a random solution at the instants t = τ/ɛ^κ at points close to [r/ɛ] ∈ ℤ^d. Our main goal is to study the asymptotic behavior of these distributions as ɛ → 0 and to derive the limit hydrodynamic equations of the Euler and Navier-Stokes type.     

Coupling and Poisson approximation

We give an overview of the Stein-Chen method for establishing Poisson approximations of various random variables. Couplings of certain variables are used to gives explicit bounds for the total variation distance between the distribution of a random variable and a Poisson variable. Some applications are given. In some cases, explicit couplings may be used to obtain good estimates; in other applications it suffices to show the existence of couplings with certain monotonicity properties.Supported by the Göran Gustafsson Foundation for Research in Natural Sciences and Medicine.     

Moments of first passage times in general birth–death processes

We consider ordinary and conditional first passage times in a general birth–death process. Under existence conditions, we derive closed-form expressions for the kth order moment of the defined random variables, k ≥ 1. We also give an explicit condition for a birth–death process to be ergodic degree 3. Based on the obtained results, we analyze some applications for Markovian queueing systems. In particular, we compute for some non-standard Markovian queues, the moments of the busy period duration, the busy cycle duration, and the state-dependent waiting time in queue.