Weak convergence to fractional Brownian motion in Brownian scenery

 Kesten and Spitzer have shown that certain random walks in random sceneries converge to stable processes in random sceneries. In this paper, we consider certain random walks in sceneries defined using stationary Gaussian sequence, and show their convergence towards a certain self-similar process that we call fractional Brownian motion in Brownian scenery. Received: 17 April 2002 / Revised version: 11 October 2002 / Published online: 15 April 2003 Research supported by NSFC (10131040). Mathematics Subject Classification (2002): 60J55, 60J15, 60J65 Key words or phrases: Weak convergence – Random walk in random scenery – Local time – Fractional Brownian motion in Brownian scenery     

A linear integer programming bound for maximum-entropy sampling

 We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the results of some computational experiments. Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002 Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral bound – Fischer's inequality – branch-and-bound – dynamic programming Mathematics Subject Classification (2000): 52B12, 90C10 Send offprint requests to: Jon Lee Correspondence to: Jon Lee     

Renormalization and homogenization of fractional diffusion equations with random data

 This paper presents a renormalization and homogenization theory for fractional-in-space or in-time diffusion equations with singular random initial conditions. The spectral representations for the solutions of these equations are provided. Gaussian and non-Gaussian limiting distributions of the renormalized solutions of these equations are then described in terms of multiple stochastic integral representations. Received: 30 May 2000 / Revised version: 9 November 2001 / Published online: 10 September 2002 Mathematics Subject Classification (2000): Primary 62M40, 62M15; Secondary 60H05, 60G60 Key words or phrases: Fractional diffusion equation – Scaling laws – Renormalised solution – Long-range dependence – Non-Gaussian scenario – Mittag-Leffler function – Stable distributions – Bessel potential – Riesz potential     

On the infinite divisibility of squared Gaussian processes

 We show that fractional Brownian motions with index in (0,1] satisfy a remarkable property: their squares are infinitely divisible. We also prove that a large class of Gaussian processes are sharing this property. This property then allows the construction of two-parameters families of processes having the additivity property of the squared Bessel processes. Received: 1 April 2002 / Revised version: 7 September 2002 / Published online: 19 December 2002 Mathematics Subject Classification (2000): 60E07, 60G15, 60J25, 60J55 Key words or phrases: Gaussian processes – Infinite divisibility – Markov processes     

Enhanced interface repulsion from quenched hard–wall randomness

 We consider the harmonic crystal, or massless free field, , , that is the centered Gaussian field with covariance given by the Green function of the simple random walk on ℤ ^d . Our main aim is to obtain quantitative information on the repulsion phenomenon that arises when we condition to be larger than , is an IID field (which is also independent of ϕ), for every x in a large region , with N a positive integer and D a bounded subset of ℝ ^d . We are mostly motivated by results for given typical realizations of σ (quenched set–up), since the conditioned harmonic crystal may be seen as a model for an equilibrium interface, living in a (d+1)–dimensional space, constrained not to go below an inhomogeneous substrate that acts as a hard wall. We consider various types of substrate and we observe that the interface is pushed away from the wall much more than in the case of a flat wall as soon as the upward tail of σ ₀ is heavier than Gaussian, while essentially no effect is observed if the tail is sub–Gaussian. In the critical case, that is the one of approximately Gaussian tail, the interplay of the two sources of randomness, ϕ and σ, leads to an enhanced repulsion effect of additive type. This generalizes work done in the case of a flat wall and also in our case the crucial estimates are optimal Large Deviation type asymptotics as of the probability that ϕ lies above σ in D _N . Received: 6 February 2002 / Revised version: 23 May 2002 / Published online: 30 September 2002 Mathematics Subject Classification (2000): 82B24, 60K35, 60G15 Keywords or phrases: Harmonic Crystal – Rough Substrate – Quenched and Annealed Models – Entropic Repulsion – Gaussian fields – Extrema of Random Fields – Large Deviations – Random Walks     

Hydrodynamic limit for ∇φ interface model on a wall

 We consider random evolution of an interface on a hard wall under periodic boundary conditions. The dynamics are governed by a system of stochastic differential equations of Skorohod type, which is Langevin equation associated with massless Hamiltonian added a strong repelling force for the interface to stay over the wall. We study its macroscopic behavior under a suitable large scale space-time limit and derive a nonlinear partial differential equation, which describes the mean curvature motion except for some anisotropy effects, with reflection at the wall. Such equation is characterized by an evolutionary variational inequality. Received: 10 January 2002 / Revised version: 18 August 2002 / Published online: 15 April 2003 Mathematics Subject Classification (2000): 60K35, 82C24, 35K55, 35K85 Key words or phrases: Hydrodynamic limit – Effective interfaces – Hard wall – Skorohod's stochastic differential equation – Evolutionary variational inequality     

Multifractal products of cylindrical pulses

 New multiplicative and statistically self-similar measures μ are defined on ℝ as limits of measure-valued martingales. Those martingales are constructed by multiplying random functions attached to the points of a statistically self-similar Poisson point process defined in a strip of the plane. Several fundamental problems are solved, including the non-degeneracy and the multifractal analysis of μ. On a bounded interval, the positive and negative moments of diverge under broad conditions. First received: 14 September 1999 / Resubmited: 27 June 2001 / Revised version: 30 May 2002 / Published online: 30 September 2002 Mathematics Subject Classification (2002): 28A80, 60G18, 60G44, 60G55, 60G57 Key words or phrases: Random measures – Multifractal analysis – Continuous time martingales – Statistically self-similar Poisson point processes     

Some dichotomy results for central Gaussian convolution semigroups on compact groups

 Consider a central Gaussian convolution semigroup (μ _t ) _{t > 0} on a connected compact semisimple group. Then either the measure μ _t is singular with respect to Haar measure for all t > 0, or there exists a time t such that μ _t is absolutely continuous with respect to Haar measure and admits a continuous density. Received: 6 November 2001 / Revised version: 13 June 2002 / Published online: 30 September 2002 Research partially supported by NSF grant DMS 0102126 Mathematics Subject Classification (2000): 28C10, 28C20, 60B15, 60G30 Keywords or phrases: Gaussian convolution semigroups – Dichotomy – Absolute continuity     

The modal logic of the countable random frame

 We study the modal logic M L ^r of the countable random frame, which is contained in and `approximates' the modal logic of almost sure frame validity, i.e. the logic of those modal principles which are valid with asymptotic probability 1 in a randomly chosen finite frame. We give a sound and complete axiomatization of M L ^r and show that it is not finitely axiomatizable. Then we describe the finite frames of that logic and show that it has the finite frame property and its satisfiability problem is in EXPTIME. All these results easily extend to temporal and other multi-modal logics. Finally, we show that there are modal formulas which are almost surely valid in the finite, yet fail in the countable random frame, and hence do not follow from the extension axioms. Therefore the analog of Fagin's transfer theorem for almost sure validity in first-order logic fails for modal logic. Received: 1 May 2000 / Revised version: 29 July 2001 / Published online: 2 September 2002 Mathematics Subject Classification (2000): 03B45, 03B70, 03C99 Key words or phrases: Modal logic – Random frames – Almost sure frame validity – Countable random frame – Axiomatization – Completeness     

Conditioning of convex piecewise linear stochastic programs

 In this paper we consider stochastic programming problems where the objective function is given as an expected value of a convex piecewise linear random function. With an optimal solution of such a problem we associate a condition number which characterizes well or ill conditioning of the problem. Using theory of Large Deviations we show that the sample size needed to calculate the optimal solution of such problem with a given probability is approximately proportional to the condition number. Received: May 2000 / Accepted: May 2002-07-16 Published online: September 5, 2002 RID="★" The research of this author was supported, in part, by grant DMS-0073770 from the National Science Foundation Key Words. stochastic programming – Monte Carlo simulation – large deviations theory – ill-conditioned problems     

On the long time behavior of the stochastic heat equation

We consider the stochastic heat equation in one space dimension and compute – for a particular choice of the initial datum – the exact long time asymptotic. In the Carmona-Molchanov approach to intermittence in non stationary random media this corresponds to the identification of the sample Lyapunov exponent. Equivalently, by interpreting the solution as the partition function of a directed polymer in a random environment, we obtain a weak law of large numbers for the quenched free energy. The result agrees with the one obtained in the physical literature via the replica method. The proof is based on a representation of the solution in terms of the weakly asymmetric exclusion process. Received: 11 November 1997 / Revised version: 31 July 1998     

Reconstructing a random scenery observed with random errors along a random walk path

 We show that an i.i.d. uniformly colored scenery on ℤ observed along a random walk path with bounded jumps can still be reconstructed if there are some errors in the observations. We assume the random walk is recurrent and can reach every point with positive probability. At time k, the random walker observes the color at her present location with probability 1−δ and an error Y _k with probability δ. The errors Y _k , k≥0, are assumed to be stationary and ergodic and independent of scenery and random walk. If the number of colors is strictly larger than the number of possible jumps for the random walk and δ is sufficiently small, then almost all sceneries can be almost surely reconstructed up to translations and reflections. Received: 3 February 2002 / Revised version: 15 January 2003 Published online: 28 March 2003 Mathematics Subject Classification (2000): 60K37, 60G50 Key words or phrases:Scenery reconstruction – Random walk – Coin tossing problems     

Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra

 We consider stochastic programming problems with probabilistic constraints involving random variables with discrete distributions. They can be reformulated as large scale mixed integer programming problems with knapsack constraints. Using specific properties of stochastic programming problems and bounds on the probability of the union of events we develop new valid inequalities for these mixed integer programming problems. We also develop methods for lifting these inequalities. These procedures are used in a general iterative algorithm for solving probabilistically constrained problems. The results are illustrated with a numerical example. Received: October 8, 2000 / Accepted: August 13, 2002 Published online: September 27, 2002 Key words. stochastic programming – integer programming – valid inequalities     

A notion of rank in set theory without choice

 Starting from the definition of `amorphous set' in set theory without the axiom of choice, we propose a notion of rank (which will only make sense for, at most, the class of Dedekind finite sets), which is intended to be an analogue in this situation of Morley rank in model theory. Received: 22 September 2000 / Revised version: 14 May 2002 Published online: 19 December 2002 The research of the first author was supported by the SERC. Mathematics Subject Classification (2000): 03E25 Key words or phrases: Rank – Degree – Amorphous     

The speed of biased random walk on percolation clusters

 We consider biased random walk on supercritical percolation clusters in ℤ². We show that the random walk is transient and that there are two speed regimes: If the bias is large enough, the random walk has speed zero, while if the bias is small enough, the speed of the random walk is positive. Received: 20 November 2002 / Revised version: 17 January 2003 Published online: 15 April 2003 Research supported by Microsoft Research graduate fellowship. Research partially supported by the DFG under grant SPP 1033. Research partially supported by NSF grant #DMS-0104073 and by a Miller Professorship at UC Berkeley. Mathematics Subject Classification (2000): 60K37; 60K35; 60G50 Key words or phrases: Percolation – Random walk     

Karush-Kuhn-Tucker systems: regularity conditions,error bounds and a class of Newton-type methods

 We consider optimality systems of Karush-Kuhn-Tucker (KKT) type, which arise, for example, as primal-dual conditions characterizing solutions of optimization problems or variational inequalities. In particular, we discuss error bounds and Newton-type methods for such systems. An exhaustive comparison of various regularity conditions which arise in this context is given. We obtain a new error bound under an assumption which we show to be strictly weaker than assumptions previously used for KKT systems, such as quasi-regularity or semistability (equivalently, the R ₀-property). Error bounds are useful, among other things, for identifying active constraints and developing efficient local algorithms. We propose a family of local Newton-type algorithms. This family contains some known active-set Newton methods, as well as some new methods. Regularity conditions required for local superlinear convergence compare favorably with convergence conditions of nonsmooth Newton methods and sequential quadratic programming methods. Received: December 10, 2001 / Accepted: July 28, 2002 Published online: February 14, 2003 Key words. KKT system – regularity – error bound – active constraints – Newton method Mathematics Subject Classification (1991): 90C30, 65K05     

Non-monotone trust region methods for nonlinear equality constrained optimization without a penalty function

 We propose and analyze a class of penalty-function-free nonmonotone trust-region methods for nonlinear equality constrained optimization problems. The algorithmic framework yields global convergence without using a merit function and allows nonmonotonicity independently for both, the constraint violation and the value of the Lagrangian function. Similar to the Byrd–Omojokun class of algorithms, each step is composed of a quasi-normal and a tangential step. Both steps are required to satisfy a decrease condition for their respective trust-region subproblems. The proposed mechanism for accepting steps combines nonmonotone decrease conditions on the constraint violation and/or the Lagrangian function, which leads to a flexibility and acceptance behavior comparable to filter-based methods. We establish the global convergence of the method. Furthermore, transition to quadratic local convergence is proved. Numerical tests are presented that confirm the robustness and efficiency of the approach. Received: December 14, 2000 / Accepted: August 30, 2001 Published online: September 27, 2002 Key words. nonmonotone trust-region methods – sequential quadratic programming – penalty function – global convergence – equality constraints – local convergence – large-scale optimization Mathematics Subject Classification (2000): 65K05, 90C30     

Green function estimate for censored stable processes

 Sharp two-sided estimates for Green functions of censored α-stable process Y in a bounded C ^1,1 open set D are obtained, where α  (1, 2). It is shown that the Martin boundary and minimal Martin boundary of Y can all be identified with the Euclidean boundary of D. Sharp two-sided estimates for the Martin kernel of Y are also derived. Received: 27 January 2002 / Revised version: 10 June 2002 / Published online: 24 October 2002 This research is supported in part by NSF Grant DMS-0071486. Mathematics Subject Classification (2002): Primary: 60J45, 31C35; Secondary: 60G52, 31C15 Keywords or phrases: Censored stable process – Green function – Capacity – Martin boundary – Martin kernel – Harmonic function