Stochastic algorithms with armijo stepsizes for minimization of functions

Stochastic algorithms for optimization problems, where function evaluations are done by Monte Carlo simulations, are presented. At each iteratex _i, they draw a predetermined numbern(i) of sample points from an underlying probability space; based on these sample points, they compute a feasible-descent direction, an Armijo stepsize, and the next iteratex _i+1. For an appropriate optimality function , corresponding to an optimality condition, it is shown that, ifn(i) , then (x _i) 0, whereJ is a set of integers whose upper density is zero. First, convergence is shown for a general algorithm prototype: then, a steepest-descent algorithm for unconstrained problems and a feasible-direction algorithm for problems with inequality constraints are developed. A numerical example is supplied.     

Service stage Petri net models with product form solution

A class of service stage Petri net models whose equilibrium probabilities satisfy local balance equations is presented. Examples of their applicability include bus oriented multiprocessor interconnections, the classical dining philosophers problem and the alternating bit protocol. The natural topological space for embedding the state transition lattice for this class of SSPN is shown to be a multidimensional toroidal manifold.     

Deterministic equivalent for a continuous-time linear-convex stochastic control problem

We consider a finite-horizon control model with additive input. There are two convex functions which describe the running cost and the terminal cost within the system. The cost of input is proportional to the input and can take both positive and negative values. It is shown that there exists a deterministic control problem whose optimal cost is the same as the one in the stochastic control problem. The optimal policy for the stochastic problem consists of keeping the process as close to the optimal deterministic trajectory as possible.This research is supported by NSERC Grant A4619, MRCO, NSF Grant DMS-86-01510, and AFOSR Grant 87-0278.     

Prophet inequalities for cost of observation stopping problems

Comparisons are made between the expected gain of a prophet (an observer with complete foresight) and the maximal expected gain of a gambler (using only non-anticipating stopping times) observing a sequence of independent, uniformly bounded random variables where a non-negative fixed cost is charged for each observation. Sharp universal bounds are obtained under various restrictions on the cost and the length of the sequence. For example, it is shown for X₁, X₂, … independent, [0, 1]-valued random variables that for all c ≥ 0 and all n ≥ 1 that E(max_{1 ≤ j ≤ n}(X_j − jc)) − sup_{t Tn} E(X_t − tc) ≤ 1/e, where T_n is the collection of all stopping times t which are less than or equal to n almost surely.     

Invariance Principle Under Self-Normalization for Nonidentically Distributed Random Variables

Let V _n ^–1 _n be the adaptive process of self-normalized partial sums S _k of independent random variables X _i , defined by linear interpolation between the points (V _k ²/V _n ²,S _k /V _n ), kn, where V _k ²= _ik X _i ². We prove that if the X _k 's are symmetric, V _n ^–1 _n converges weakly to the Brownian motion W in each Hölder space supporting W if and only if V _n ^–1 max _kn |X _k |=o _P (1). We give some partial extension to the non symmetric case.     

One-armed bandit models with continuous and delayed responses

One-armed bandit processes with continuous delayed responses are formulated as controlled stochastic processes following the Bayesian approach. It is shown that under some regularity conditions, a Gittins-like index exists which is the limit of a monotonic sequence of break-even values characterizing optimal initial selections of arms for finite horizon bandit processes. Furthermore, there is an optimal stopping solution when all observations on the unknown arm are complete. Results are illustrated with a bandit model having exponentially distributed responses, in which case the controlled stochastic process becomes a Markov decision process, the Gittins-like index is the Gittins index and the Gittins index strategy is optimal. Acknowledgement.We thank an anonymous referee for constructive and insightful comments, especially those related to the notion of the Gittins index.Both authors are funded by the Natural Sciences and Engineering Research Council (NSERC) of Canada.     

Approximate solution for some stochastic differential equations involving both Gaussian and Poissonian white noises

By combining the Kramers-Moyal expansion with fractional Brownian motion of order n, in a formal symbolic calculus, one can obtain an approximation for the solution of some stochastic differential equations involving both Gaussian and Poissonian white noises, in terms of rotating Gaussian white noises on the grid defined by the complex roots of the unity. Illustrative examples are outlined.     

Asymptotic stability, ergodicity and other asymptotic properties of the nonlinear filter

In this work we study connections between various asymptotic properties of the nonlinear filter. It is assumed that the signal has a unique invariant probability measure. The key property of interest is expressed in terms of a relationship between the observation σ field and the tail σ field of the signal, in the stationary filtering problem. This property can be viewed as the permissibility of the interchange of the order of the operations of maximum and countable intersection for certain σ-fields. Under suitable conditions, it is shown that the above property is equivalent to various desirable properties of the filter such as

(a) uniqueness of invariant measure for the signal,

(b) uniqueness of invariant measure for the pair (signal, filter),

(c) a finite memory property of the filter,

(d) a property of finite time dependence between the signal and observation σ fields and

(e) asymptotic stability of the filter.

Previous works on the asymptotic stability of the filter for a variety of filtering models then identify a rich class of filtering problems for which the above equivalent properties hold.     

On the spectral function of the Poisson–Voronoi cells

Denote by (t)=∑_n1e^−λ_nt, t>0, the spectral function related to the Dirichlet Laplacian for the typical cell of a standard Poisson–Voronoi tessellation in . We show that the expectation E(t), t>0, is a functional of the convex hull of a standard d-dimensional Brownian bridge. This enables us to study the asymptotic behaviour of E(t), when t→0⁺,+∞. In particular, we prove that the law of the first eigenvalue λ₁ of satisfies the asymptotic relation lnP{λ₁t}−2^dω_dj_(d−2)/2^d·t^−d/2 when t→0⁺, where ω_d and j_(d−2)/2 are respectively the Lebesgue measure of the unit ball in and the first zero of the Bessel function J_(d−2)/2.     

Local polynomial fitting under association

We consider the estimation of multivariate regression functions r(x₁,…,x_d) and their partial derivatives up to a total order p1 using high-order local polynomial fitting. The processes {Y_i,X_i} are assumed to be (jointly) associated. Joint asymptotic normality is established for the estimates of the regression function r and all its partial derivatives up to the total order p. Expressions for the bias and variance/covariance matrix (of the asymptotic distribution) are given.