The problem of transmitting information in a specified direction over a communication channel with three terminals is considered. Examples are given of the various ways of sending information. Basic inequalities for average mutual information rates are obtained. A coding theorem and weak converse are proved and a necessary and sufficient condition for a positive capacity is derived. Upper and lower bounds on the capacity are obtained, which coincide for channels with symmetric structure.

The intrinsic random functions (IRF) are a particular case of the Guelfand generalized processes with stationary increments. They constitute a much wider class than the stationary RF, and are used in practical applications for representing non-stationary phenomena. The most important topics are: existence of a generalized covariance (GC) for which statistical inference is possible from a unique realization; theory of the best linear intrinsic estimator (BLIE) used for contouring and estimating problems; the turning bands method for simulating IRF; and the models with polynomial GC, for which statistical inference may be performed by automatic procedures.

In Part I we developed stability concepts for discrete chains, together with Foster–Lyapunov criteria for them to hold. Part II was devoted to developing related stability concepts for continuous-time processes. In this paper we develop criteria for these forms of stability for continuous-parameter Markovian processes on general state spaces, based on Foster-Lyapunov inequalities for the extended generator.

Such test function criteria are found for non-explosivity, non-evanescence, Harris recurrence, and positive Harris recurrence. These results are proved by systematic application of Dynkin's formula.

We also strengthen known ergodic theorems, and especially exponential ergodic results, for continuous-time processes. In particular we are able to show that the test function approach provides a criterion for f-norm convergence, and bounding constants for such convergence in the exponential ergodic case.

We apply the criteria to several specific processes, including linear stochastic systems under non-linear feedback, work-modulated queues, general release storage processes and risk processes.

In the present paper a uniform asymptotic series is derived for the probability distribution of the sum of a large number of independent random variables. In contrast to the usual Edgeworth-type series, the uniform series gives good accuracy throughout its entire domain. Our derivation uses the fact that the major components of the distribution are determined by a saddle point and a singularity at the origin. The analogous series for the probability density, due to Daniels, depends only on the saddle point. Two illustrative examples are presented that show excellent agreement with the exact distributions.

This paper is concerned with blocking and loss probabilities in circuit-switched networks. We show that when the capacity of links and the offered traffic are increased together, a limiting regime emerges in which loss probabilities are as if links block independently, with blocking probabilities given by the solution of a simple convex programming problem. We then show that an approximate procedure, based on solving Erlang&s formula under the assumption of independent blocking, produces a unique solution when routes are fixed, and that under the limiting regime the estimates of loss probabilities obtained from the procedure converge to the correct values.

The present paper considers the stochastic difference equation Yn = AnYn-1 + Bn with i.i.d. random pairs (An, Bn) and obtains conditions under which Yn converges in distribution. This convergence is related to the existence of solutions of and (A, B) independent, and the convergence w.p. 1 of ∑ A1A2 ··· An-1Bn. A second subject is the series ∑ Cnf(Tn) with (Cn) a sequence of i.i.d. random variables, (Tn) the sequence of points of a Poisson process and f a Borel function on (0, ∞). The resulting random variable turns out to be infinitely divisible, and its Lévy–Hinčin representation is obtained. The two subjects coincide in case An and Cn are independent, Bn = AnCn, An = U1/αn with Un a uniform random variable, f(x) = e−x/α.

We study a single-server queue in which the server takes a vacation whenever the system becomes empty. The service and vacation times and the arrival process are all assumed to be mutually independent. The successive service times and the vacation times each form independent, identically distributed sequences with general distributions. A new class of non-renewal arrival processes is introduced. As special cases, it includes the Markov-modulated Poisson process and the superposition of phase-type renewal processes.

Algorithmically tractable equations for the distributions of the waiting times at an arbitrary time and at arrivals, as well as for the queue length at an arbitrary time, at arrivals, and at departures are established. Some factorizations, which are known for the case of renewal input, are generalized to this new framework and new factorizations are obtained. The algorithmic implementation of these results is discussed.

The conventional linear/quadratic/Gaussian assumptions are modified in that minimisation of the expectation of cost G defined by (2) is replaced by minimisation of the criterion function (5). The scalar –θ is a measure of risk-aversion. It is shown that modified versions of certainty equivalence and the separation theorem still hold, that optimal control is still linear Markov, and state estimate generated by a version of the Kalman filter. There are also various new features, remarked upon in Sections 5 and 7. The paper generalises earlier work of Jacobson.

This paper analyzes, derives efficient computational procedures and numerically investigates the following fluid model which is of interest in manufacturing and communications: m producing machines supply a buffer, n consuming machines feed off it. Each machine independently alternates between exponentially distributed random periods in the ‘in service' and ‘failed' states. Producers/consumers have their own failure/repair rates and working capacities. When the buffer is either full or empty some of the machines in service are not utilized to capacity; otherwise they are fully utilized. Our main result is for the state distribution of the Markovian system in equilibrium which is the solution of a system of differential equations. The spectral expansion for its solution is obtained. Two important decompositions are obtained: the eigenvectors have the Kronecker-product form in lower-dimensional vectors; the characteristic polynomial is factored with each factor an explicitly given polynomial of degree at most 4. All eigenvalues are real. For each of various cases of the model, a system of linear equations is derived from the boundary conditions; their solution complete the spectral expansion. The count in operations of the entire procedure is O(m3n3): independence from buffer size exemplifies an important attraction of fluid models. Computations have revealed several interesting features, such as the benefit of small machines and the inelasticity of production rate to inventory. We also give results on the eigenvalues of a more general fluid model, reversible Markov drift processes.

We consider a non-Bayesian infinite horizon version of the multi-armed bandit problem with the objective of designing simple policies whose regret increases slowly with time. In their seminal work on this problem, Lai and Robbins had obtained a O(log n) lower bound on the regret with a constant that depends on the Kullback–Leibler number. They also constructed policies for some specific families of probability distributions (including exponential families) that achieved the lower bound. In this paper we construct index policies that depend on the rewards from each arm only through their sample mean. These policies are computationally much simpler and are also applicable much more generally. They achieve a O(log n) regret with a constant that is also based on the Kullback–Leibler number. This constant turns out to be optimal for one-parameter exponential families; however, in general it is derived from the optimal one via a ‘contraction' principle. Our results rely entirely on a few key lemmas from the theory of large deviations.

The maximum of a Gaussian random field was used by Worsley et al. (1992) to test for activation at an unknown point in positron emission tomography images of blood flow in the human brain. The Euler characteristic of excursion sets was used as an estimator of the number of regions of activation. The expected Euler characteristic of excursion sets of stationary Gaussian random fields has been derived by Adler and Hasofer (1976) and Adler (1981). In this paper we extend the results of Adler (1981) to χ2, F and t fields. The theory is applied to some three-dimensional images of cerebral blood flow from a study on pain perception.

This paper studies the first passage times to flat boundaries for a double exponential jump diffusion process, which consists of a continuous part driven by a Brownian motion and a jump part with jump sizes having a double exponential distribution. Explicit solutions of the Laplace transforms, of both the distribution of the first passage times and the joint distribution of the process and its running maxima, are obtained. Because of the overshoot problems associated with general jump diffusion processes, the double exponential jump diffusion process offers a rare case in which analytical solutions for the first passage times are feasible. In addition, it leads to several interesting probabilistic results. Numerical examples are also given. The finance applications include pricing barrier and lookback options.

Consider a stochastic process X(t) (t ≧ 0) taking values in a countable state space, say, {1, 2,3, …}. To be picturesque we think of X(t) as the state which a particle is in at epoch t. Suppose the particle moves from state to state in such a way that the successive states visited form a Markov chain, and that the particle stays in a given state a random amount of time depending on the state it is in as well as on the state to be visited next. Below is a possible realization of such a process.

Bounds of exponential type are derived for the first-hitting time and occupation times of a real-valued random sequence which has a uniform negative drift whenever the sequence is above a fixed level. The only other assumption on the random sequence is that the increments satisfy a uniform exponential decay condition. The bounds provide a flexible technique for proving stability of processes frequently encountered in the control of queues.

Two applications are given. First, exponential-type bounds are derived for a GI/G/1 queue when the service distribution is exponential type. Secondly, geometric ergodicity is established for a certain Markov chain in which arises in the decentralized control of a multi-access, packet-switched broadcast channel.

The queueing systems considered in this paper consist of r independent arrival channels and s independent service channels, where as usual the arrival and service channels are independent. Arriving customers form a single queue and are served in the order of their arrival without defections. We shall treat two distinct modes of operation for the service channels. In the standard system a waiting customer is assigned to the first available service channel and the servers (servers ≡ service channels) are shut off when they are idle. Thus the classical GI/G/s system is a special case of our standard system. In the modified system a waiting customer is assigned to the service channel that can complete his service first and the servers are not shut off when they are idle. While the modified system is of some interest in its own right, we introduce it primarily as an analytical tool. Let λi denote the arrival rate (reciprocal of the mean interarrival time) in the ith arrival channel and μj the service rate (reciprocal of the mean service time) in the jth service channel. Then is the total arrival rate to the system and is the maximum service rate of the system. As a measure of congestion we define the traffic intensity ρ = λ/μ.

In this note, we study a new repair replacement model for a deteriorating system, in which the successive survival times of the system form a geometric process and are stochastically non-increasing, whereas the consecutive repair times after failure also constitute a geometric process but are stochastically non-decreasing. Two kinds of replacement policy are considered, one based on the working age of the system and the other one determined by the number of failures. The explicit expressions of the long-run average costs per unit time under these two kinds of policy are calculated.

The calculation of probabilities on pedigrees of arbitrary complexity is discussed for a basic model of transmission and penetrance (encompassing Mendelian inheritance, and certain environmental influences).

The structure of pedigrees, and the types of loops occurring, is discussed. Some results in graph theory are obtained and, using these, a recurrence relation derived for certain probabilities. The recursive procedure enables the successive peeling off of certain members of the pedigree, and the condensation of the information on those individuals into a function on a subset of those remaining. The underlying theory is set out, and examples given of the utilization of the resulting algorithm.

In this paper we extend the results of Meyn and Tweedie (1992b) from discrete-time parameter to continuous-parameter Markovian processes Φ evolving on a topological space.

We consider a number of stability concepts for such processes in terms of the topology of the space, and prove connections between these and standard probabilistic recurrence concepts. We show that these structural results hold for a major class of processes (processes with continuous components) in a manner analogous to discrete-time results, and that complex operations research models such as storage models with state-dependent release rules, or diffusion models such as those with hypoelliptic generators, have this property. Also analogous to discrete time, ‘petite sets', which are known to provide test sets for stability, are here also shown to provide conditions for continuous components to exist.

New ergodic theorems for processes with irreducible and countably reducible skeleton chains are derived, and we show that when these conditions do not hold, then the process may be decomposed into an uncountable orbit of skeleton chains.

The structure of the probability space associated with a general point process, when regarded as a counting process, is reviewed using the coincidence formalism. The rest of the paper is devoted to the class of regular point processes for which all coincidence probabilities admit densities. It is shown that their distribution is completely specified by the system of coincidence densities. The specification formalism is stressed for ‘completely’ regular point processes. A construction theorem gives a characterization of the system of coincidence densities of such a process. It permits the study of most models of point processes. New results on the photon process, a particular type of conditioned Poisson process, are derived. New examples are exhibited, including the Gauss-Poisson process and the ‘fermion’ process that is suitable whenever the points are repulsive.