When analyzing the equilibrium behavior of M/G/1 type Markov chains by transform methods, restrictive hypotheses are often made to avoid technical problems that arise in applying results from complex analysis and linear algebra. It is shown that such restrictive assumptions are unnecessary, and an analysis of these chains using generating functions is given under only the natural hypotheses that first moments (or second moments in the null recurrent case) exist. The key to the analysis is the identification of an important subspace of the space of bounded solutions of the system of homogeneous vector-valued Wiener–Hopf equations associated with the chain. In particular, the linear equations in the boundary probabilities obtained from the transform method are shown to correspond to a spectral basis of the shift operator on this subspace. Necessary and sufficient conditions under which the chain is ergodic, null recurrent or transient are derived in terms of properties of the matrix-valued generating functions determined by transitions of the Markov chain. In the transient case, the Martin exit boundary is identified and shown to be associated with certain eigenvalues and vectors of one of these generating functions. An equilibrium analysis of the class of G/M/1 type Markov chains by similar methods is also presented.

In phylogenetic analysis it is useful to study the distribution of the parsimony length of a tree under the null model, by which the leaves are independently assigned letters according to prescribed probabilities. Except in one special case, this distribution is difficult to describe exactly. Here we analyze this distribution by providing a recursive and readily computable description, establishing large deviation bounds for the parsimony length of a fixed tree on a single site and for the minimum length (maximum parsimony) tree over several sites. We also show that, under very general conditions, the former distribution converges asymptotically to the normal, thereby settling a recent conjecture. Furthermore, we show how the mean and variance of this distribution can be efficiently calculated. The proof of normality requires a number of new and recent results, as the parsimony length is not directly expressible as a sum of independent random variables, and so normality does not follow immediately from a standard central limit theorem.

A threshold AR(1) process with boundary width 2δ > 0 was defined by Brockwell and Hyndman [5] in terms of the unique strong solution of a stochastic differential equation whose coefficients are piecewise linear and Lipschitz. The positive boundary-width is a convenient mathematical device to smooth out the coefficient changes at the boundary and hence to ensure the existence and uniqueness of the strong solution of the stochastic differential equation from which the process is derived. In this paper we give a direct definition of a threshold AR(1) process with δ = 0 in terms of the weak solution of a certain stochastic differential equation. Two characterizations of the distributions of the process are investigated. Both express the characteristic function of the transition probability distribution as an explicit functional of standard Brownian motion. It is shown that the joint distributions of this solution with δ = 0 are the weak limits as δ ↓ 0 of the distributions of the solution with δ > 0. The sense in which an approximating sequence of processes used by Brockwell and Hyndman [5] converges to this weak solution is also investigated. Some numerical examples illustrate the value of the latter approximation in comparison with the more direct representation of the process obtained from the Cameron–Martin–Girsanov formula and results of Engelbert and Schmidt [9]. We also derive the stationary distribution (under appropriate assumptions) and investigate stability of these processes.

The shape of a rectangular prism in (d + 1) dimensions can be described by d quantities. In this talk, using a definition of shape which involves the ratios of edge lengths, we investigate shape distributions which are invariant when the prism is cut into two, also rectangular, prisms, with one prism retained for measurement and the other discarded. Interesting new distributions on [0, l]d arise.

We consider the application of importance sampling in steady-state simulations of finite Markov chains. We show that, for a large class of performance measures, there is a choice of the alternative transition matrix for which the ratio of the variance of the importance sampling estimator to the variance of the naive simulation estimator converges to zero as the sample path length goes to infinity. Obtaining this ‘optimal’ transition matrix involves computing the performance measure of interest, so the optimal matrix cannot be computed in precisely those situations where simulation is required to estimate steady-state performance. However, our results show that alternative transition matrices of the form Q = P + E/T, where P is the original transition matrix and T is the sample path length, can be expected to provide good results. Moreover, we provide an iterative algorithm for obtaining alternative transition matrices of this form that converge to the optimal matrix as the number of iterations increases, and present an example that shows that spending some computer time iterating this algorithm and then conducting the simulation with the resulting alternative transition matrix may provide considerable variance reduction when compared to naive simulation.

We give criteria for the finiteness or infiniteness of the passage-time moments for continuous non-negative stochastic processes in terms of sub/supermartingale inequalities for powers of these processes. We apply these results to one-dimensional diffusions and also reflected Brownian motion in a wedge. The discrete-time analogue of this problem was studied previously by Lamperti and more recently by Aspandiiarov, Iasnogorodski and Menshikov [2]. Our results are continuous analogues of those in [2], but our proofs are direct and do not rely on approximation by discrete-time processes.

In the first part of this paper a global Kushner–Clark theorem about the convergence of stochastic algorithms is proved: we show that, under some natural assumptions, one can ‘read' from the trajectories of its ODE whether or not an algorithm converges. The classical stochastic optimization results are included in this theorem. In the second part, the above smoothness assumption on the mean vector field of the algorithm is relaxed using a new approach based on a path-dependent Lyapounov functional. Several applications, for non-smooth mean vector fields and/or bounded Lyapounov function settings, are derived. Examples and simulations are provided that illustrate and enlighten the field of application of the theoretical results.

Consider a connected planar graph. A bounded face is said to be of type k, or is called a k-face, if the boundary of that face contains k edges. Under various natural rules for randomly dividing bounded faces by the addition of new edges, we investigate the limiting distribution of face type as the number of divisions increases.

This paper considers a structure, named a ‘random partition process’, which is a generalisation of a random tessellation. The cells, possibly multi-part and with holes, have a general topology summarised by the Euler characteristic. Vertices of all orders are allowed. Using the tools of ergodic theory, all of the formulae, from the traditional theory of random tessellations with convex cells, are generalised. Some motivating examples are given.

A homogeneous Gaussian Markov lattice-process model has a regression coefficient that determines the extent to which a random variable of a vertex is dependent on those of the neighbors. In many studies, the absolute value of this parameter has been assumed to be less than the reciprocal of the number of neighbors. This condition is shown to be necessary and sufficient for the existence of the Gaussian process satisfying the model equations under some assumptions on lattices using the notion of dual processes. We also give examples of models that neither satisfy the condition imposed on the region for the parameter nor the assumptions on lattices. A formula for autocovariance functions of Gaussian Markov processes on general lattices is derived, and numerical procedures to calculate the autocovariance functions are proposed.

The ‘Mabinogion sheep’ problem, originally due to D. Williams, is a nice illustration in discrete time of the martingale optimality principle and the use of local time in stochastic control. The use of singular controls involving local time is even more strikingly highlighted in the context of continuous time. This paper considers a class of diffusion versions of the discrete-time Mabinogion sheep problem. The stochastic version of the Bellman dynamic programming approach leads to a free boundary problem in each case. The most surprising feature in the continuous-time context is the existence of diffusion versions of the original discrete-time problem for which the optimal boundary is different from that in the discrete-time case; even when the optimal boundary is the same, the value functions can be very different.

We study a classical stochastic control problem arising in financial economics: to maximize expected logarithmic utility from terminal wealth and/or consumption. The novel feature of our work is that the portfolio is allowed to anticipate the future, i.e. the terminal values of the prices, or of the driving Brownian motion, are known to the investor, either exactly or with some uncertainty. Results on the finiteness of the value of the control problem are obtained in various setups, using techniques from the so-called enlargement of filtrations. When the value of the problem is finite, we compute it explicitly and exhibit an optimal portfolio in closed form.

We consider stochastic approximation algorithms on a general Hilbert space, and study four conditions on noise sequences for their analysis: Kushner and Clark's condition, Chen's condition, a decomposition condition, and Kulkarni and Horn's condition. We discuss various properties of these conditions. In our main result we show that the four conditions are all equivalent, and are both necessary and sufficient for convergence of stochastic approximation algorithms under appropriate assumptions.

We consider a real-valued random walk S which drifts to –∞ and is such that E(exp θS1) < ∞ for some θ > 0, but for which Cramér's condition fails. We investigate the asymptotic tail behaviour of the distributions of the all time maximum, the upwards and downwards first passage times and the last passage times. As an application, we obtain new limit theorems for certain conditional laws.

Consider A Stationary Line Segment Process In The Plane, Observed Through A Window W. Line Segments Which Cross The Boundary Of The Window Are Only Partially Observed. One Might Say That The Observed Lengths Of The Line Segments Are Then Censored. However, Classical Methods From The Theory Of Censored Survival Data (Kaplan-Meier Estimator) Can Be Seen To Be Inappropriate.

A single machine is available to process a collection of jobs J, each of which evolves stochastically under processing. Jobs incur costs while awaiting the machine at a rate which is state dependent and processing must respect a set of precedence constraints Γ. Index policies are optimal in a variety of scenarios. The indices concerned are characterised as values of restart problems with the average reward criterion. This characterisation yields a range of efficient approaches to their computation. Index-based suboptimality bounds are derived for general processing policies. These bounds enable us to develop sensitivity analyses and to evaluate scheduling heuristics.

Let ?(u) be the probability of eventual ruin in the classical Sparre Andersen model of risk theory if the initial risk reserve is u. For a large class of such models ?(u) behaves asymptotically like a multiple of exp (–Ru) where R is the adjustment coefficient; R depends on the premium income rate, the claim size distribution and the distribution of the time between claim arrivals. Estimation of R has been considered by many authors. In the present paper we deal with confidence bounds for R. A variety of methods is used, including jackknife estimation of asymptotic variances and the bootstrap. We show that, under certain assumptions, these procedures result in interval estimates that have asymptotically the correct coverage probabilities. We also give the results of a simulation study that compares the different techniques in some particular cases.

We derive optimal gambling and investment policies for cases in which the underlying stochastic process has parameter values that are unobserved random variables. For the objective of maximizing logarithmic utility when the underlying stochastic process is a simple random walk in a random environment, we show that a state-dependent control is optimal, which is a generalization of the celebrated Kelly strategy: the optimal strategy is to bet a fraction of current wealth equal to a linear function of the posterior mean increment. To approximate more general stochastic processes, we consider a continuous-time analog involving Brownian motion. To analyze the continuous-time problem, we study the diffusion limit of random walks in a random environment. We prove that they converge weakly to a Kiefer process, or tied-down Brownian sheet. We then find conditions under which the discrete-time process converges to a diffusion, and analyze the resulting process. We analyze in detail the case of the natural conjugate prior, where the success probability has a beta distribution, and show that the resulting limit diffusion can be viewed as a rescaled Brownian motion. These results allow explicit computation of the optimal control policies for the continuous-time gambling and investment problems without resorting to continuous-time stochastic-control procedures. Moreover they also allow an explicit quantitative evaluation of the financial value of randomness, the financial gain of perfect information and the financial cost of learning in the Bayesian problem.

A general model for the evolution of the frequency distribution of types in a population under mutation and selection is derived and investigated. The approach is sufficiently general to subsume classical models with a finite number of alleles, as well as models with a continuum of possible alleles as used in quantitative genetics. The dynamics of the corresponding probability distributions is governed by an integro-differential equation in the Banach space of Borel measures on a locally compact space. Existence and uniqueness of the solutions of the initial value problem is proved using basic semigroup theory. A complete characterization of the structure of stationary distributions is presented. Then, existence and uniqueness of stationary distributions is proved under mild conditions by applying operator theoretic generalizations of Perron–Frobenius theory. For an extension of Kingman's original house-of-cards model, a classification of possible stationary distributions is obtained.

For a stationary particle process X with convex particles in ℝdd ≧ 2, a mean body M(X) can be defined by where h(M,·) denotes the support function of the convex body M, γ the intensity of X, and P0 is the distribution of the typical particle of X (a probability measure on the set of convex bodies with Steiner point at the origin). Replacing the support function h(M,·) by the surface area measure S(M,·) (see Schneider (1993), for the basic notions from convex geometry), we get the Blaschke body B(X) of X, After normalization, the left-hand side represents the mean normal distribution of X. The main problem discussed here is whether B(X) (respectively S(B(X), ·)) is uniquely determined by the mean bodies M(X ∩ E) in random planar sections X ∩ E of X. From more general results in Weil (1995), it follows that the expectation ES(M(X ∩ E), ·) (taken w.r.t. the uniform distribution of two-dimensional subspaces E in ℝd) equals the surface area measure of a section mean B2(B(X)) of B(X). Thus, the formulated stereological question can be reduced to the injectivity of the transform B2 : K ↦ B2(K).