Brownian motion and random walk perturbed at extrema

Let b _t be Brownian motion. We show there is a unique adapted process x _t which satisfies dx _t = db _t except when x _t is at a maximum or a minimum, when it receives a push, the magnitudes and directions of the pushes being the parameters of the process. For some ranges of the parameters this is already known. We show that if a random walk close to b _t is perturbed properly, its paths are close to those of x _t . Received: 15 October 1997 / Revised version: 18 May 1998     

Fluctuations of empirical means at low temperature for finite Markov chains with rare transitions in the general case

Summary. The integrated autocovariance and autocorrelation time are essential tools to understand the dynamical behavior of a Markov chain. We study here these two objects for Markov chains with rare transitions with no reversibility assumption. We give upper bounds for the autocovariance and the integrated autocorrelation time, as well as exponential equivalents at low temperature. We also link their slowest modes with the underline energy landscape under mild assumptions. Our proofs will be based on large deviation estimates coming from the theory of Wentzell and Freidlin and others [4, 3, 12], and on coupling arguments (see [6] for a review on the coupling method). Received 5 August 1996 / In revised form: 6 August 1997     

Splitting for rare event simulation: A large deviation approach to design and analysis

Particle splitting methods are considered for the estimation of rare events. The probability of interest is that a Markov process first enters a set B$B$ before another set A$A$, and it is assumed that this probability satisfies a large deviation scaling. A notion of subsolution is defined for the related calculus of variations problem, and two main results are proved under mild conditions. The first is that the number of particles generated by the algorithm grows subexponentially if and only if a certain scalar multiple of the importance function is a subsolution. The second is that, under the same condition, the variance of the algorithm is characterized (asymptotically) in terms of the subsolution. The design of asymptotically optimal schemes is discussed, and numerical examples are presented.     

Mixed and Isoperimetric Estimates on the Log-Sobolev Constants of Graphs and Markov Chains

Two types of lower bounds are obtained on the log-Sobolev constants of graphs and Markov chains. The first is a mixture of spectral gap and logarithmic isoperimetric constant, the second involves the Gaussian isoperimetric constant. The sharpness of both types of bounds is tested on some examples. Product generalizations of some of these results are also briefly given. Received March 1, 1999/Revised July 17, 2000 RID="*" ID="*" Research supported in part by the NSF Grant No. DMS–9803239. The author greatly enjoyed the hospitality of CIMAT, Gto, Mexico, where part of this work was done.     

The Cheeger Constant, the Heat Kernel, and the Green Kernel of an Infinite Graph

 This paper gives a new approach to estimate the Cheeger constant, the heat kernel, and the Green kernel of the combinatorial Laplacian for an infinite graph. Received March 12, 2001; in final form July 11, 2002     

Brownian motion, harmonic functions and hyperbolicity for Euclidean complexes

A Euclidean complex X is a simplicial complex whose simplices are (flat) Euclidean simplices. We construct a natural Brownian motion on X and show that if X has nonpositive curvature and satisfies Gromov's hyperbolicity condition, then, with probability one, Brownian motion tends to a random limit on the Gromov boundary. Applying a combination of geometric and probabilistic techniques we describe spaces of harmonic functions on X. Received November 18, 1999; in final form January 18, 2000 / Published online April 12, 2001     

A Normal Law for Matchings

Dedicated to the memory of Paul Erdős, both for his pioneering discovery of normality in unexpected places, and for his questions, some of which led (eventually) to the present work.   For a simple graph G, let be the size of a matching drawn uniformly at random from the set of all matchings of G. Motivated by work of C. Godsil [11], we give, for a sequence and , several necessary and sufficient conditions for asymptotic normality of the distribution of , for instance

Large deviation principles for Euclidean functionals and other nearly additive processes

We prove a large deviation principle for a process indexed by cubes of the multidimensional integer lattice or Euclidean space, under approximate additivity and regularity hypotheses. The rate function is the convex dual of the limiting logarithmic moment generating function. In some applications the rate function can be expressed in terms of relative entropy. The general result applies to processes in Euclidean combinatorial optimization, statistical mechanics, and computational geometry. Examples include the length of the minimal tour (the traveling salesman problem), the length of the minimal matching graph, the length of the minimal spanning tree, the length of the k-nearest neighbors graph, and the free energy of a short-range spin glass model. Received: 3 April 1999 / Revised version: 23 June 1999 / Published online: 8 May 2001     

Commutator bounds for eigenvalues,with applications to spectralgeometry

We prove a purely algebraic version of an eigenvalue inequality of Hile and Protter, and derive corollaries bounding differences of eigenvalues of Laplace– Beltrami operators on manifolds. We significantly improve earlier bounds of Yang and Yau, Li, and Harrell.     

Parameter selection rules for path-following with singular embedding

Summary. Singular embedding methods require appropriately adjusted parameters to guarantee the contraction of locally quadratically convergent iterative methods. Firstly some general rule for the parameter selection is proposed and its rate of convergence is analyzed. Secondly, some modifications in the case of polynomial error and contraction bounds are studied. Finally, these results are applied to the embedding of an elliptic boundary value problem with discontinuous nonlinearities into a family of smooth problems. Here the regularization is done in such a way that the solutions of the resulting auxiliary problems require only one step of Newton's method. Received December 2, 1996 / Revised version reveived April 7, 1998     

List Homomorphisms and Circular Arc Graphs

G , H, and lists , a list homomorphism of G to H with respect to the lists L is a mapping , such that for all , and for all . The list homomorphism problem for a fixed graph H asks whether or not an input graph G together with lists , , admits a list homomorphism with respect to L. We have introduced the list homomorphism problem in an earlier paper, and proved there that for reflexive graphs H (that is, for graphs H in which every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP-complete otherwise. Here we consider graphs H without loops, and find that the problem is closely related to circular arc graphs. We show that the list homomorphism problem is polynomial time solvable if the complement of H is a circular arc graph of clique covering number two, and is NP-complete otherwise. For the purposes of the proof we give a new characterization of circular arc graphs of clique covering number two, by the absence of a structure analogous to Gallai's asteroids. Both results point to a surprising similarity between interval graphs and the complements of circular arc graphs of clique covering number two. Received: July 22, 1996/Revised: Revised June 10, 1998     

Approximating Probability Distributions Using Small Sample Spaces

We formulate the notion of a "good approximation" to a probability distribution over a finite abelian group ?. The quality of the approximating distribution is characterized by a parameter ɛ which is a bound on the difference between corresponding Fourier coefficients of the two distributions. It is also required that the sample space of the approximating distribution be of size polynomial in and 1/ɛ. Such approximations are useful in reducing or eliminating the use of randomness in certain randomized algorithms. We demonstrate the existence of such good approximations to arbitrary distributions. In the case of n random variables distributed uniformly and independently over the range , we provide an efficient construction of a good approximation. The approximation constructed has the property that any linear combination of the random variables (modulo d) has essentially the same behavior under the approximating distribution as it does under the uniform distribution over . Our analysis is based on Weil's character sum estimates. We apply this result to the construction of a non-binary linear code where the alphabet symbols appear almost uniformly in each non-zero code-word. Received: September 22, 1990/Revised: First revision November 11, 1990; last revision November 10, 1997     

, Vertex Isoperimetry and Concentration

. This approach refines results relating the spectral gap of a graph to the so-called magnification of a graph. A concentration result involving is also derived. Received July 22, 1998     

Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules

O (c+d) steps using constant-size queues, where c is the congestion of the paths in the network, and d is the length of the longest path. The proof, however, used the Lovász Local Lemma and was not constructive. In this paper, we show how to find such a schedule in time, with probability , for any positive constant β, where is the sum of the lengths of the paths taken by the packets in the network, and m is the number of edges used by some packet in the network. We also show how to parallelize the algorithm so that it runs in NC. The method that we use to construct the schedules is based on the algorithmic form of the Lovász Local Lemma discovered by Beck. Received: July 8, 1996     

Procedures for kernel approximation and solution of fredholm integral equations of the second kind

Summary The purpose of this paper is to present explicit ALGOL procedures for (1) the approximation of a kernel (surface) by tensor products of splines, and (2) the computation of approximate eigenvalues and eigenfunctions for Fredholm integral equations of the second kind. Editor's Note. In this fascile, prepublication of algorithms from the Approximations series of the Handbook for Automatic Computation is continued. Algorithms are published in ALGOL 60 reference language as approved by the IFIP. Contributions in this series should be styled after the most recently published ones     

The fast Fourier transform and the numerical solution of one-dimensional boundary integral equations

Summary Here we present a fully discretized projection method with Fourier series which is based on a modification of the fast Fourier transform. The method is applied to systems of integro-differential equations with the Cauchy kernel, boundary integral equations from the boundary element method and, more generally, to certain elliptic pseudodifferential equations on closed smooth curves. We use Gaussian quadratures on families of equidistant partitions combined with the fast Fourier transform. This yields an extremely accurate and fast numerical scheme. We present complete asymptotic error estimates including the quadrature errors. These are quasioptimal and of exponential order for analytic data. Numerical experiments for a scattering problem, the clamped plate and plane estatostatics confirm the theoretical convergence rates and show high accuracy.     

Integration over a simplex,truncated cubes,and Eulerian numbers

Summary A method of integrating a function over a simplex is described in which (i) the simplex is first transformed into a right-angled isosceles simplex; (ii) this simplex is dissected into small cubes and truncated cubes; (iii) the integration over the truncated cubes is performed by the centroid method or by Stroud's method, and this requires the use of formulae for the moments of a truncated cube. These formulae are developed and are expressed in terms of Eulerian numbers. In the special case when the truncated cube is itself a right-angled isoceles simplex a new algorithm is given, depending on the discrete Fourier transform, for calculating the moments as polynomials inn wheren is the dimensionality.     

Index transforms for multidimensional DFT's and convolutions

Summary Index transforms ofm-dimensional arrays inton-dimensional arrays play a significant role in many fast algorithms of multivariate discrete Fourier transforms (DFT's) and cyclic convolutions. The computation ofm-dimensional long DFT's or convolutions can be transfered to the parallel computation ofn-dimensional short DFT's or convolutions (n>m). In this paper, the nature of index transforms is explored using group-theoretical ideas. We solve the open problems concerning index transforms posed recently by Hekrdla [5, 6].     

Diffusions on path and loop spaces: existence, finite dimensional approximation and Hölder continuity

Summary. We construct Ornstein–Uhlenbeck processes and more general diffusion processes on path and loop spaces of Riemannian manifolds by finite dimensional approximation. We also show H?lder continuity of the sample paths w.r.t. the supremum norm. The proofs are based on the Lyons–Zheng decomposition. Received: 6 September 1996 / In revised form: 1 April 1997     

On the convergence of the Galerkin method for nonsmooth solutions of integral equations

Summary It is shown that the stability region of the Galerkin method includes solutions not lying in the conventional energy space. Optimal order error estimates for these nonsmooth solutions are derived. The new result is compared with the classical statement by means of the basic potential problem.