On the distributions of the lengths of the longest monotone subsequences in random words

We consider the distributions of the lengths of the longest weakly increasing and strongly decreasing subsequences in words of length N from an alphabet of k letters. (In the limit as k→∞ these become the corresponding distributions for permutations on N letters.) We find Toeplitz determinant representations for the exponential generating functions (on N) of these distribution functions and show that they are expressible in terms of solutions of Painlevé V equations. We show further that in the weakly increasing case the generating unction gives the distribution of the smallest eigenvalue in the k×k Laguerre random matrix ensemble and that the distribution itself has, after centering and normalizing, an N→∞ limit which is equal to the distribution function for the largest eigenvalue in the Gaussian Unitary Ensemble of k×k hermitian matrices of trace zero. Received: 9 September 1999 / Revised version: 24 May 2000 / Published online: 24 January 2001     

On the second derivative of the spherical contact distribution function of smooth grain models

We consider a stationary grain model Ξ in ℝ ^d with convex, compact and smoothly bounded grains. We study the spherical contact distribution function F of Ξ and derive (under suitable assumptions) an explicit formula for its second derivative F″. The value F″(0) is of a simple form and admits a clear geometric interpretation.For the Boolean model we obtain an interesting new formula for the(d− 1)-st quermass density. Received: 22 November 1999 / Revised version: 2 November 2000 /?Published online: 14 June 2001     

Random walk on upper triangular matrices mixes rapidly

We present an upper bound O(n ² ) for the mixing time of a simple random walk on upper triangular matrices. We show that this bound is sharp up to a constant, and find tight bounds on the eigenvalue gap. We conclude by applying our results to indicate that the asymmetric exclusion process on a circle indeed mixes more rapidly than the corresponding symmetric process. Received: 25 January 1999 / Revised version: 17 September 1999 / Published online: 14 June 2000     

Increment sizes of the principal value of Brownian local time

Let W be a standard Brownian motion, and define Y(t)= ∫₀ ^t ds/W(s) as Cauchy's principal value related to local time. We determine: (a) the modulus of continuity of Y in the sense of P. Lévy; (b) the large increments of Y. Received: 1 April 1999 / Revised version: 27 September 1999 / Published online: 14 June 2000     

Locally Closed Semirings

 We call a semiring S locally closed if for all a ∈ S there is some integer k such that 1 + a + ⋯ + a ^k  =1 + a + ⋯ + a ^k + 1 . In any locally closed semiring we may define a star operation a ↦ a ^*, where a ^* is the above finite sum. We prove that when S is locally closed and commutative, then S is an iteration semiring. Partially supported by grant no. T30511 from the National Foundation of Hungary for Scientific Research and the Austrian–Hungarian Bilateral Research and Development Fund, no. A-4/1999, and by the Austrian–Hungarian Action Foundation. Partially supported by the Austrian–Hungarian Bilateral Research and Development Fund, no. A-4/1999, and by the Austrian–Hungarian Action Foundation. Received March 16, 2001     

Ordered overlaps in disordered mean-field models

Let M(N) be a sequence of integers with M→∞ as N→∞ and M=o(N). For bounded i.i.d. r.v. ξ _i ^k and bounded i.i.d. r.v. σ _i , we study the large deviation of the family of (ordered) scalar products X ^k =N ⁻¹∑ _{i =1} ^N σ _i ξ _i ^k ,k≤M, under the distribution conditioned on the ξ _i ^k 's. To get a full large deviation principle, it is necessary to specify also the total norm(∑ _{k ≤ M} (X ^k )²)^1/2, which turns to be associated with some extra Gaussian distribution. Our results apply to disordered, mean-field systems, including generalized Hopfield models in the regime of a sublinear number of patterns. We build also a class of examples where this norm is the crucial order parameter. Received: 6 April 1999 / Revised version: 29 May 2000 /?Published online: 24 July 2001     

Random coin tossing

Summary. A sequence of heads and tails is produced by repeatedly selecting a coin from two possible coins, and tossing it. The second coin is tossed at renewal times in a renewal process, and the first coin is tossed at all other times. The first coin is fair (Prob(heads)=1/2), and the second coin is known either to be fair, or to have known biasθ∈(0,1] (Prob(heads) ). Letting u _k := Prob (There is a renewal at time k), we show that if ∑ _{k =0} ^∞ u _k ²=∞, we can determine, using only the sequence of heads and tails produced, if the second coin had bias θ or 0. If , we show that this is not possible. Received: 20 November 1996 / In revised form: 20 February 1997     

On Itô s formula for multidimensional Brownian motion

Consider a d-dimensional Brownian motion X = (X ¹,…,X ^d ) and a function F which belongs locally to the Sobolev space W ^1,2. We prove an extension of It? s formula where the usual second order terms are replaced by the quadratic covariations [f _k (X), X ^k ] involving the weak first partial derivatives f _k of F. In particular we show that for any locally square-integrable function f the quadratic covariations [f(X), X ^k ] exist as limits in probability for any starting point, except for some polar set. The proof is based on new approximation results for forward and backward stochastic integrals. Received: 16 March 1998 / Revised version: 4 April 1999     

Dependent percolation in two dimensions

For a natural number k, define an oriented site percolation on ℤ² as follows. Let x _i , y _j be independent random variables with values uniformly distributed in {1, …, k}. Declare a site (i, j) ∈ℤ² closed if x _i = y _j , and open otherwise. Peter Winkler conjectured some years ago that if k≥ 4 then with positive probability there is an infinite oriented path starting at the origin, all of whose sites are open. I.e., there is an infinite path P = (i ₀, j ₀)(i ₁, j ₁) · · · such that 0 = i ₀≤i ₁≤· · ·, 0 = j ₀≤j ₁≤· · ·, and each site (i _n , j _n ) is open. Rather surprisingly, this conjecture is still open: in fact, it is not known whether the conjecture holds for any value of k. In this note, we shall prove the weaker result that the corresponding assertion holds in the unoriented case: if k≤ 4 then the probability that there is an infinite path that starts at the origin and consists only of open sites is positive. Furthermore, we shall show that our method can be applied to a wide variety of distributions of (x _i ) and (y _j ). Independently, Peter Winkler [14] has recently proved a variety of similar assertions by different methods. Received: 4 March 1999 / Revised version: 27 September 1999 / Published online: 21 June 2000     

Anomalous behaviour for the random corrections to the cumulants of random walks in fluctuating random media

The Central Limit Theorem for a model of discrete-time random walks on the lattice ℤ^ν in a fluctuating random environment was proved for almost-all realizations of the space-time nvironment, for all ν > 1 in [BMP1] and for all ν≥ 1 in [BBMP]. In [BMP1] it was proved that the random correction to the average of the random walk for ν≥ 3 is finite. In the present paper we consider the cases ν = 1,2 and prove the Central Limit Theorem as T→∞ for the random correction to the first two cumulants. The rescaling factor for theaverage is for ν = 1 and (ln T), for ν=2; for the covariance it is , ν = 1,2. Received: 25 November 1999 / Revised version: 7 June 2000 / Published online: 15 February 2001     

Pathwise uniqueness for reflecting Brownian motion in Euclidean domains

For a bounded C ^1,α domain in ℝ ^d we show that there exists a strong solution to the multidimensional Skorokhod equation and that weak uniqueness holds for this equation. These results imply that pathwise uniqueness and strong uniqueness hold for the Skorokhod equation. Received: 3 February 1999 / Revised version: 2 September 1999 /?Published online: 11 April 2000     

A family of diffusion processes on Sierpinski carpets

We construct a family of diffusions P ^α = {P ^x} on the d-dimensional Sierpinski carpet F^. The parameter α ranges over d _H < α < ∞, where d _H = log(3 ^d − 1)/log 3 is the Hausdorff dimension of the d-dimensional Sierpinski carpet F^. These diffusions P ^α are reversible with invariant measures μ = μ^[α]. Here, μ are Radon measures whose topological supports are equal to F^ and satisfy self-similarity in the sense that μ(3A) = 3^α·μ(A) for all A∈ℬ(F^). In addition, the diffusion is self-similar and invariant under local weak translations (cell translations) of the Sierpinski carpet. The transition density p = p(t, x, y) is locally uniformly positive and satisfies a global Gaussian upper bound. In spite of these well-behaved properties, the diffusions are different from Barlow-Bass' Brownian motions on the Sierpinski carpet. Received: 30 September 1999 / Revised version: 15 June 2000 / Published online: 24 January 2000     

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

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     

Invariant manifolds for weak solutions to stochastic equations

Viability and invariance problems related to a stochastic equation in a Hilbert space H are studied. Finite dimensional invariant C ² submanifolds of H are characterized. We derive Nagumo type conditions and prove a regularity result: any weak solution, which is viable in a finite dimensional C ² submanifold, is a strong solution. These results are related to finding finite dimensional realizations for stochastic equations. There has recently been increased interest in connection with a model for the stochastic evolution of forward rate curves. Received: 15 April 1999 / Revised version: 4 February 2000 / Published online: 18 September 2000     

Stable windings on hyperbolic surfaces

Let ℳ be a geometrically finite hyperbolic surface with infinite volume, having at least one cusp. We obtain the limit law under the Patterson-Sullivan measure on T ¹ℳ of the windings of the geodesics of ℳ around the cusps. This limit law is stable with parameter 2δ− 1, where δ is the Hausdorff dimension of the limit set of the subgroup Γ of M?bius isometries associated with ℳ. The normalization is t ^{−1/(2δ−1)}, for geodesics of length t. Our method relies on a precise comparison between geodesics and diffusion paths, for which we need to approach the Patterson-Sullivan measure mentioned above by measures that are regular along the stable leaves. Received: 8 October 1999 / Revised version: 2 June 2000 / Published online: 21 December 2000     

Asymptotic separation for independent trajectories of Markov processes

We say that n independent trajectories ξ₁(t),…,ξ _n (t) of a stochastic process ξ(t)on a metric space are asymptotically separated if, for some ɛ > 0, the distance between ξ _i (t _i ) and ξ _j (t _j ) is at least ɛ, for some indices i, j and for all large enough t ₁,…,t _n , with probability 1. We prove sufficient conitions for asymptotic separationin terms of the Green function and the transition function, for a wide class of Markov processes. In particular,if ξ is the diffusion on a Riemannian manifold generated by the Laplace operator Δ, and the heat kernel p(t, x, y) satisfies the inequality p(t, x, x) ≤ Ct ^−ν/2 then n trajectories of ξ are asymptotically separated provided . Moreover, if for some α∈(0, 2)then n trajectories of ξ^(α) are asymptotically separated, where ξ^(α) is the α-process generated by −(−Δ)^α/2. Received: 10 June 1999 / Revised version: 20 April 2000 / Published online: 14 December 2000 RID="*" ID="*" Supported by the EPSRC Research Fellowship B/94/AF/1782 RID="**" ID="**" Partially supported by the EPSRC Visiting Fellowship GR/M61573     

Accelerated hybrid conjugate gradient algorithm with modified secant condition for unconstrained optimization

An accelerated hybrid conjugate gradient algorithm represents the subject of this paper. The parameter β _k is computed as a convex combination of b_k^HS\beta_k^{HS} (Hestenes and Stiefel, J Res Nat Bur Stand 49:409–436, 1952) and b_k^DY\beta_k^{DY} (Dai and Yuan, SIAM J Optim 10:177–182, 1999), i.e. b_k^C = (1-q_k)b_k^HS + q_k b_k^DY\beta_k^C =\left({1-\theta_k}\right)\beta_k^{HS} + \theta_k \beta_k^{DY}. The parameter θ _k in the convex combinaztion is computed in such a way the direction corresponding to the conjugate gradient algorithm is the best direction we know, i.e. the Newton direction, while the pair (s _k , y _k ) satisfies the modified secant condition given by Li et al. (J Comput Appl Math 202:523–539, 2007) B _k + 1 s _k  = z _k , where z_k = y_k +(h_k / || s_k ||² )s_kz_k =y_k +\left({{\eta_k} / {\left\| {s_k} \right\|^2}} \right)s_k, h_k = 2( f_k -f_k+1 )+( g_k +g_k+1 )^Ts_k\eta_k =2\left( {f_k -f_{k+1}} \right)+\left( {g_k +g_{k+1}} \right)^Ts_k, s _k  = x _k + 1 − x _k and y _k  = g _k + 1 − g _k . It is shown that both for uniformly convex functions and for general nonlinear functions the algorithm with strong Wolfe line search is globally convergent. The algorithm uses an acceleration scheme modifying the steplength α _k for improving the reduction of the function values along the iterations. Numerical comparisons with conjugate gradient algorithms show that this hybrid computational scheme outperforms a variant of the hybrid conjugate gradient algorithm given by Andrei (Numer Algorithms 47:143–156, 2008), in which the pair (s _k , y _k ) satisfies the classical secant condition B _k + 1 s _k  = y _k , as well as some other conjugate gradient algorithms including Hestenes-Stiefel, Dai-Yuan, Polack-Ribière-Polyak, Liu-Storey, hybrid Dai-Yuan, Gilbert-Nocedal etc. A set of 75 unconstrained optimization problems with 10 different dimensions is being used (Andrei, Adv Model Optim 10:147–161, 2008).     

<Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> Bounds for the Commutator of Parabolic Singular Integral with Rough Kernels

In this paper, the authors give the L ^p (1 < p < ∞ ) boundedness of the k-th order commutator of parabolic singular integral with the kernel function Ω ∈ L(log⁺ L) ^k + 1(S ^n − 1). The result in this paper is an extension of some known results. The research was supported by NSF of China (Grant: 10571015) and SRFDP of China (Grant: 20050027025).