A linear list is a collection of items that can be accessed sequentially. The cost of a request is the number of items that need to be examined before the desired item is located, i.e. the distance of the requested item from the beginning of the list. The transposition rule is one of the algorithms designed to reduce the search cost by organizing the list. In particular, upon a request for a given item, the item is transposed with the preceding one. We develop a new approach for analyzing the algorithm, based on a coupling to a certain constrained asymmetric exclusion process. This allows us to establish an asymptotic optimality of the rule for two families of request distributions.

We introduce and motivate the study of (n + 1) × r arrays X with Bernoulli entries Xk,j and independently distributed rows. We study the distribution of which denotes the number of consecutive pairs of successes (or runs of length 2) when reading the array down the columns and across the rows. With the case r = 1 having been studied by several authors, and permitting some initial inferences for the general case r > 1, we examine various distributional properties and representations of Sn for the case r = 2, and, using a more explicit analysis, the case of multinomial and identically distributed rows. Applications are also given in cases where the array X arises from a Pólya sampling scheme.

The Itô formula is the fundamental theorem of stochastic calculus. This short note presents a new proof of Itô's formula for the case of continuous semimartingales. The new proof is more geometric than previous approaches, and has the particular advantage of generalizing immediately to the multivariate case without extra notational complexity.

The assumption of linear costs of observation usually leads to optimal stopping boundaries which are straight lines. For non-linear costs of observation, the question arises of how the shape of cost functions influences the shape of optimal stopping boundaries. In Irle (1987), (1988) it was shown that, under suitable assumptions on c, for the problem of optimal stopping (Wt + x)+ - c(s + t), t ∊ [0,∞), the optimal stopping boundary h(t) can be enscribed between k1/c'(t) and k2/c'(t) for some constants k1, k2. In this paper we find the exact asymptotic expansion h(t) = 1/(4c'(t))(1 + o(1)).

We consider a multiarmed bandit problem, where each arm when pulled generates independent and identically distributed nonnegative rewards according to some unknown distribution. The goal is to maximize the long-run average reward per pull with the restriction that any previously learned information is forgotten whenever a switch between arms is made. We present several policies and a peculiarity surrounding them.

Let ℰ be an event governed by a homogeneous second-order two-state Markov chain. Assume the steady state has been achieved. Consider Nm the number of times that ℰ occurs in m successive trials. The limiting distribution of P(Nm = k) is obtained under the condition that mP(ℰ)=λ.

In [3] Heyde proposed an extended version of the well-known Hájek-Rényi inequality to include random variables without finite moments. The purpose of this note is to point out that the theorem in [3] is in error, and to prove the following theorem in its stead:

Theorem. Let X1, X2, ··· be any sequence of random variables, and define be independent random variables, each with mean zero and finite variance, and define Zk = Xk - Yk for k ≧ 1. Let c1, c2, ··· be a non-increasing sequence of positive numbers.

We consider a two-sided exit problem for a Lévy process with no positive jumps. The Laplace transform of the time when the process first exits an interval from above is obtained. It is expressed in terms of another Laplace transform for the one-sided exit problem. Applications of this result are discussed. In particular, a new expression for the solution to the two-sided exit problem is obtained. The joint distribution of the minimum and the maximum values of such a Lévy process is also studied.

The stochastic model for breaking of molecular segments proposed by Bithell is analysed and some results relating to the distribution of the number of fragments are obtained by using a slightly more general model which allows multiple ruptures. The product density technique is employed to derive the mean and mean square number of segments at any time t and the number of segments with length greater than y at time of production.

A new structure with the special property that an instantaneous reflection barrier is imposed on the ordinary birth—death processes is considered. An easy-checking criterion for the existence of such Markov processes is first obtained. The uniqueness criterion is then established. In the nonunique case, all the honest processes are explicitly constructed. Ergodicity properties for these processes are investigated. It is proved that honest processes are always ergodic without necessarily imposing any extra conditions. Equilibrium distributions for all these ergodic processes are established. Several examples are provided to illustrate our results.

In this paper we study the conditional limiting behaviour for the virtual waiting time process for the queue M/D/1. We describe the family of conditional invariant distributions which are continuous and parametrized by the eigenvalues λ ∊ (0, λc], as it happens for diffusions. In this case, there is a periodic dependence of the limiting conditional distributions on the initial point and the minimal conditional invariant distribution is a mixture, according to an exponential law, of the limiting conditional distributions.

Let {Zt, t ≧ 0} be an irreducible regular semi-Markov process with transition probabilities Pij (t). Let f(t) be non-negative and non-decreasing to infinity, and let λ ≧ 0. This paper identifies a large set of functions f(t) with the solidarity property that convergence of the integral ≧ eλtf(t)Pij(t) dt for a specific pair of states i and j implies convergence of the integral for all pairs of states. Similar results are derived for the Markov renewal functions Mij (t). Among others it is shown that f(t) can be taken regularly varying.

We study the closure properties of the family ℒ(α) of classes of life distributions introduced by Lin (1998) under general compounding. We define a discrete analogue of this family and study some properties.

A method is presented for constructing a continuous, stationary process with a given rate of upcrossings at all levels and for which it is possible to find the exact distribution of the number of upcrossings, in an interval, at all levels.

The paper presents sufficient conditions for certain functions to be convex. Functions of this type often appear in Markov decision processes, where their maximum is the solution of the problem. Since a convex function takes its maximum at an extreme point, the conditions may greatly simplify a problem. In some cases a full solution may be obtained after the reduction is made. Some illustrative examples are discussed.

This paper arises from the observation by Dirac [1] that an exact measurement of the velocity of an electron should give one of the instantaneous values ± c. The velocity v < c with which the electron moves bodily is in some statistical sense an average. This aspect of the quantum states of motion of a relativistic particle has frequently been mentioned [2], [3] and, as is wellknown, is connected with the self energy problem. Such deductions from quantum mechanics have led the author to consider the possibility of constructing from purely statistical ideas an entity having the physical properties of a relativistic elementary particle. One might reasonably hope to build up characteristics such as rest mass and spin in such a scheme. Properties such as energy and momentum will arise as averages over fluctuating random quantities. In this paper we shall concentrate on rest mass, energy and momentum. We shall show that a zero rest mass object which is regarded as being imbedded in a statistical structure emulates the characteristic of rest mass. The average energy and momentum of this statistical system are then shown to satisfy the usual classical relativistic relation between energy and momentum. The statistical structure chosen is that of an object with a randomly orientated velocity vector, c, which has a fixed magnitude c … |c| where c is the velocity of light.

The results obtained by Lehoczky on the first emptiness of a dam subject to random outputs are extended to a more general model.

A sequential stochastic decision process with independent random variables is considered in which the decision maker selects a chance with a certain probability at each time period or at random times. If the decision maker has selected m chances, the process has to be stopped. The expectation and the variance of the stopping variable are determined for a finite and an infinite decision horizon.

We consider a supercritical, p-dimensional Markov branching process (MBP). Based on the finite and the infinite lines of descent of particles of this p-dimensional MBP, we construct an associated 2p-dimensional process. We show that such a process is a 2p-dimensional, supercritical MBP. This 2p-dimensional process retains the branching property when conditioned on the sets of extinction and non-extinction. Asymptotic results and central limit theorems for the associated process and the original process are established by using the results of Gadag and Rajarshi (1987).