Refined Approximations for the Ewens Sampling Formula

The Ewens sampling formula is a family of probability distributions over the space of cycle types of permutations of n objects, indexed by a real parameter θ. In the case θ = 1, where the distribution reduces to that induced by the uniform distribution on all permutations, the joint distributions of the numbers of cycles of lengths less than b = o(n) is extremely well approximated by a product of Poisson distributions, having mean 1/j for cycle length j: the error is super-exponentially small with nb^?1. For θ ≠ 1. the analogous approximation, with means adjusted to θ/j, is good, but with error only linear in n^?1b. In this article, it is shown that, by choosing the means of the Poisson distributions more carefully, an error quadratic in n^?1b can be achieved, and that essentially nothing better is possible.     

Approximation of monomials by lower degree polynomials

Our topic is the uniform approximation ofx ^k by polynomials of degreen (n on the interval [–1, 1]. Our major result indicates that good approximation is possible whenk is much smaller thann ² and not possible otherwise. Indeed, we show that the approximation error is of the exact order of magnitude of a quantity,p _k,n , which can be identified with a certain probability. The numberp _k,n is in fact the probability that when a (fair) coin is tossedk times the magnitude of the difference between the number of heads and the number of tails exceedsn.     

Approximation power of RBFs and their associated SBFs: a connection

Error estimates for scattered data interpolation by “shifts” of a conditionally positive definite function (CPD) for target functions in its native space, which is its associated reproducing kernel Hilbert space (RKHS), have been known for a long time. Regardless of the underlying manifold, for example ℝⁿ or S ⁿ, these error estimates are determined by the rate of decay of the Fourier transform (or Fourier series) of the CPD. This paper deals with the restriction of radial basis functions (RBFs), which are radial CPD functions on ℝⁿ⁺¹, to the unit sphere S ⁿ. In the paper, we first strengthen a result derived by two of us concerning an explicit representation of the Fourier–Legendre coefficients of the restriction in terms of the Fourier transform of the RBF. In addition, for RBFs that are related to completely monotonic functions, we derive a new integral representation for these coefficients in terms of the measure generating the completely monotonic function. These representations are then utilized to show that if an RBF has a native space equivalent to a Sobolev space H _s(ℝⁿ⁺¹), then the restriction to S ⁿ has a native space equivalent to H _s−1/2(S ⁿ). In addition, they are used to recover the asymptotic behavior of such coefficients for a wide variety of RBFs. Some of these were known earlier. Joseph D. Ward: Francis J. Narcowich: Research supported by grant DMS-0204449 from the National Science Foundation.     

Multivariate approximation in the worst case setting over reproducing kernel Hilbert spaces

We study the worst case setting for approximation of d variate functions from a general reproducing kernel Hilbert space with the error measured in the L_∞ norm. We mainly consider algorithms that use n arbitrary continuous linear functionals. We look for algorithms with the minimal worst case errors and for their rates of convergence as n goes to infinity. Algorithms using n function values will be analyzed in a forthcoming paper.We show that the L_∞ approximation problem in the worst case setting is related to the weighted L₂ approximation problem in the average case setting with respect to a zero-mean Gaussian stochastic process whose covariance function is the same as the reproducing kernel of the Hilbert space. This relation enables us to find optimal algorithms and their rates of convergence for the weighted Korobov space with an arbitrary smoothness parameter α>1, and for the weighted Sobolev space whose reproducing kernel corresponds to the Wiener sheet measure. The optimal convergence rates are n^-(α-1)/2 and n^-1/2, respectively.We also study tractability of L_∞ approximation for the absolute and normalized error criteria, i.e., how the minimal worst case errors depend on the number of variables, d, especially when d is arbitrarily large. We provide necessary and sufficient conditions on tractability of L_∞ approximation in terms of tractability conditions of the weighted L₂ approximation in the average case setting. In particular, tractability holds in weighted Korobov and Sobolev spaces only for weights tending sufficiently fast to zero and does not hold for the classical unweighted spaces.     

On exponential ergodicity of multiclass queueing networks

One of the key performance measures in queueing systems is the decay rate of the steady-state tail probabilities of the queue lengths. It is known that if a corresponding fluid model is stable and the stochastic primitives have finite moments, then the queue lengths also have finite moments, so that the tail probability ℙ(⋅>s) decays faster than s ⁻ⁿ for any n. It is natural to conjecture that the decay rate is in fact exponential.     

Average‐case complexity of shortest‐paths problems in the vertex‐potential model

We study the average‐case complexity of shortest‐paths problems in the vertex‐potential model. The vertex‐potential model is a family of probability distributions on complete directed graphs with arbitrary real edge lengths, but without negative cycles. We show that on a graph with n vertices and with respect to this model, the single‐source shortest‐paths problem can be solved in O(n²) expected time, and the all‐pairs shortest‐paths problem can be solved in O(n² log n) expected time. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 33–46, 2000     

A new rounding procedure for the assignment problem with applications to dense graph arrangement problems

We present a randomized procedure for rounding fractional perfect matchings to (integral) matchings. If the original fractional matching satisfies any linear inequality, then with high probability, the new matching satisfies that linear inequality in an approximate sense. This extends the well-known LP rounding procedure of Raghavan and Thompson, which is usually used to round fractional solutions of linear programs.?We use our rounding procedure to design an additive approximation algorithm to the Quadratic Assignment Problem. The approximation error of the algorithm is εn ² and it runs in n ^{O (log n /ε2)} time.?We also describe Polynomial Time Approximation Schemes (PTASs) for dense subcases of many well-known NP-hard arrangement problems, including MINIMUM LINEAR ARRANGEMENT, MINIMUM CUT LINEAR ARRANGEMENT, MAXIMUM ACYCLIC SUBGRAPH, and BETWEENNESS. Received: December 12, 1999 / Accepted: October 25, 2001?Published online February 14, 2002     

Functional Quantization and Small Ball Probabilities for Gaussian Processes

Quantization consists in studying the L ^r -error induced by the approximation of a random vector X by a vector (quantized version) taking a finite number n of values. We investigate this problem for Gaussian random vectors in an infinite dimensional Banach space and in particular, for Gaussian processes. A precise link proved by Fehringer⁽⁴⁾ and Dereich et al. ⁽³⁾ relates lower and upper bounds for small ball probabilities with upper and lower bounds for the quantization error, respectively. We establish a complete relationship by showing that the same holds for the direction from the quantization error to small ball probabilities. This allows us to compute the exact rate of convergence to zero of the minimal L ^r -quantization error from logarithmic small ball asymptotics and vice versa.     

A One-Dimensional Optimization Algorithm and Its Convergence Rate under the Wiener Measure

In this paper we describe an adaptive algorithm for approximating the global minimum of a continuous function on the unit interval, motivated by viewing the function as a sample path of a Wiener process. It operates by choosing the next observation point to maximize the probability that the objective function has a value at that point lower than an adaptively chosen threshold. The error converges to zero for any continuous function. Under the Wiener measure, the error converges to zero at rate e^−nδ_n, where {δ_n} (a parameter of the algorithm) is a positive sequence converging to zero at an arbitrarily slow rate.     

On real and complex-valued bivariate Chebyshev polynomials

In the real uniform approximation of the function x^myⁿ by the space of bivariate polynomials of total degree m + n − 1 on the unit square, the product of monic univariate Chebyshev polynomials yields an optimal error. We exploit the fundamental Noether's theorem of algebraic curves theory to give necessary and sufficient conditions for unicity and to describe the set of optimal errors in case of nonuniqueness. Then, we extend these results to the complex approximation on biellipses. It turns out that the product of Chebyshev polynomials also provides an optimal error and that the same kind of uniqueness conditions prevail in the complex case. Yet, when nonuniqueness occurs, the characterization of the set of optimal errors presents peculiarities, compared to the real problem.     

Asymptotic analysis of the nonsteady viscous flow with a given flow rate in a thin pipe

The nonsteady Navier–Stokes equations are considered in a thin infinite pipe with the small diameter ? in the case of the Reynolds number of order ?. The time-dependent flow rate is a given function. The complete asymptotic expansion is constructed and justified. The error estimate of order O(? ^J ) for the difference of the exact solution and the J-th asymptotic approximation is proved for any real J.     

Parabolic Type Decay Rates for 1-D-Thermoelastic Systems with Time-Dependent Coefficients

 The purpose of this paper is to derive L ^p − L ^q decay estimates for linear thermoelastic systems with time-dependent coefficient in one space variable. When all coefficients in the system have the same growth speed with small oscillations, we obtain a parabolic type decay estimate. For the system with time-dependent coefficients, we need to investigate the delicate asymptotic behaviour of characteristic roots and the remainder of diagonalization, which will be treated by dividing the phase space into three regions. Received September 15, 2001; in revised form April 20, 2002     

Non-uniform bounds for short asymptotic expansions in the CLT for balls in a Hilbert space

We consider short asymptotic expansions for the probability of a sum of i.i.d. random elements to hit a ball in a Hilbert space H. The error bound for the expansion is of order O(n^-1). It depends on the first 12 eigenvalues of the covariance operator only. Moreover, the bound is non-uniform, i.e. the accuracy of the approximation becomes better as the distance between a boundary of the ball and the origin in H grows.     

Near-circularity of the error curve in complex Chebyshev approximation

Let f(z) be analytic on the unit disk, and let p^*(z) be the best (Chebyshev) polynomial approximation to f(z) on the disk of degree at most n. It is observed that in typical problems the “error curve,” the image of the unit circle under (f − p^*)(z), often approximates to a startling degree a perfect circle with winding number n + 1. This phenomenon is approached by consideration of related problems whose error curves are exactly circular, making use of a classical theorem of Carathéodory and Fejér. This leads to a technique for calculating approximations in one step that are roughly as close to best as the best approximation error curve is close to circular, and hence to strong theorems on near-circularity as the radius of the domain shrinks to 0 or as n increases to ∞. As a computational example, very tight bounds are given for approximation of e^z on the unit disk. The generality of the near-circularity phenomenon (more general domains, rational approximation) is discussed.     

Entropy,Approximation Quantities and the Asymptotics of the Modulus of Continuity

The paper deals with the approximation of bounded real functions f on a compact metric space (X, d) by so-called controllable step functions in continuation of [Ri/Ste]. These step functions are connected with controllable coverings, that are finite coverings of compact metric spaces by subsets whose sizes fulfil a uniformity condition depending on the entropy numbers ε_n(X) of the space X. We show that a strong form of local finiteness holds for these coverings on compact metric subspaces of IR^m and S^m. This leads to a Bernstein type theorem if the space is of finite convex information. In this case the corresponding approximation numbers ε_n(f) have the same asymptotics its ω(f, ε_n(X)) for f ε C(X). Finally, the results concerning functions f ε M(X) and f ε C(X) are transferred to operators with values in M(X) and C(X), respectively.     

The Median of the Number of Simple Paths on Three Vertices in the Random Graph

We study the asymptotic behavior of the random variable equal to the number of simple paths on three vertices in the binomial random graph in which the edge probability equals the threshold probability of the appearance of such paths. We prove that, for any fixed nonnegative integer b and a sufficiently large number n of vertices of the graph, the probability that the number of simple paths on three vertices in the given random graph is b decreases with n. As a consequence of this result, we obtain the median of the number of simple paths on three vertices for sufficiently large n.

     

Approximation with polynomial kernels and SVM classifiers

This paper presents an error analysis for classification algorithms generated by regularization schemes with polynomial kernels. Explicit convergence rates are provided for support vector machine (SVM) soft margin classifiers. The misclassification error can be estimated by the sum of sample error and regularization error. The main difficulty for studying algorithms with polynomial kernels is the regularization error which involves deeply the degrees of the kernel polynomials. Here we overcome this difficulty by bounding the reproducing kernel Hilbert space norm of Durrmeyer operators, and estimating the rate of approximation by Durrmeyer operators in a weighted L¹ space (the weight is a probability distribution). Our study shows that the regularization parameter should decrease exponentially fast with the sample size, which is a special feature of polynomial kernels. Dedicated to Charlie Micchelli on the occasion of his 60th birthday Mathematics subject classifications (2000) 68T05, 62J02. Ding-Xuan Zhou: The first author is supported partially by the Research Grants Council of Hong Kong (Project No. CityU 103704).     

Schwarz Iterative Methods: Infinite Space Splittings

We prove the convergence of greedy and randomized versions of Schwarz iterative methods for solving linear elliptic variational problems based on infinite space splittings of a Hilbert space. For the greedy case, we show a squared error decay rate of \(O((m+1)^{-1})\) for elements of an approximation space \(\mathscr {A}_1\) related to the underlying splitting. For the randomized case, we show an expected squared error decay rate of \(O((m+1)^{-1})\) on a class \(\mathscr {A}_{\infty }^{\pi }\subset \mathscr {A}_1\) depending on the probability distribution.     

Finding shortest paths in the plane in the presence of barriers to travel (for any lp - norm)

This paper develops an efficient algorithm for the computation of the shortest paths between given sets of points (origins and destinations) in the plane, when these paths are constrained not to cross any of a finite set of polygonal (open or closed) barriers. It is proved that when distances are measured by an 1_p - norm with 1 < p < ∞, these paths are formed by sequences straight line segments whose intermediate (e.g. apart from origin and destination) end points are barrier vertices. Moreover, only segments that locally support the barriers to which their end points belong are elligible for inclusion in a shortest path. The special case of one origin and one destination is considered, as well as the more general case of many origins and destinations. If n is the number of nodes (origins, destinations and barrier vertices), an algorithm is presented that builds that network of all shortest paths in O(n² log n) time. If the total number of edges in this network is e (bounded by n²), the application of Dijkstra's algorithm enables this computation of the shortest paths from any origin to all destinations in O(e log n) time. If the origins, shortest paths from all origins to all destinations can thus be found in O(ne log n) ≤ O(n^{3 log n}) time.It is also shown that optimal solutions when distances are measured according to the rectilinear or max-norm (i.e. l_p-norm with p = 1 or p = ∞) can be deduced from the results of the algorithm.     

Analysis of infeasible-interior-point paths arising with semidefinite linear complementarity problems

We consider semidefinite monotone linear complementarity problems (SDLCP) in the space ⁿ of real symmetric n×n-matrices equipped with the cone ⁿ₊ of all symmetric positive semidefinite matrices. One may define weighted (using any Mⁿ₊₊ as weight) infeasible interior point paths by replacing the standard condition XY=rI, r>0, (that defines the usual central path) by (XY+YX)/2=rM. Under some mild assumptions (the most stringent is the existence of some strictly complementary solution of (SDLCP)), these paths have a limit as r0, and they depend analytically on all path parameters (such as r and M), even at the limit point r=0.Mathematics Subject Classification (1991): 90C33, 65K05