On some relations between stationary time and customer state probabilities for qneueing systems G/GI/s/r

By means of a general formula for stochastic processes with imbedded marked point processes (PMP) some necessary and sufficient condition is given for the validity of a relationship, which is well-known in the case of exponentially distributed service times, between stationary time and customer state probabilities for loss systems G/GI/s/O (Theorem 3). A result of Miyazawa for the GI/GI/l/∞ queue is generalized to the case of non-recurrent interarrival times (Theorem 4)-. Furthermore, bounds are derived for the mean increment of the waiting time process at arrival epochs and for the mean actual waiting time in multi-server queues.     

Local times of stochastic processes with positive definite bivariate densities

A new class of stochastic processes, called processes of positive bivariate type, is defined. Such a process is typically one whose bivariate density functions are positive definite, at least for pairs of time points which are sufficiently mutually close. The class includes stationary Gaussian processes and stationary reversible Markov processes, and is closed under the operations of composition and convolution. The purpose of this work is to show that the local times of such processes can be investigated in a natural way. One of the main contributions is an orthogonal expansion of the local time which is new even in the well-studied stationary Gaussian case. The basic tool in its construction is the Lancaster-Sarmanov expansion of a bivariate density in a series of canonical correlations and canonical variables.     

MEXIT: Maximal un-coupling times for stochastic processes

Classical coupling constructions arrange for copies of the same Markov process started at two different initial states to become equal as soon as possible. In this paper, we consider an alternative coupling framework in which one seeks to arrange for two different Markov (or other stochastic) processes to remain equal for as long as possible, when started in the same state. We refer to this “un-coupling” or “maximal agreement” construction as MEXIT, standing for “maximal exit”. After highlighting the importance of un-coupling arguments in a few key statistical and probabilistic settings, we develop an explicit MEXIT construction for stochastic processes in discrete time with countable state-space. This construction is generalized to random processes on general state-space running in continuous time, and then exemplified by discussion of MEXIT for Brownian motions with two different constant drifts.     

Sample-path analysis of processes with imbedded point processes

The purpose of this paper is to review, unify, and extend previous work on sample-path analysis of queues. Our main interest is in the asymptotic behavior of a discrete-state, continuous-time process with an imbedded point process. We present a sample-path analogue of the renewal-reward theorem, which we callY=X. We then applyY=X to derive several relations involving the transition rates and the asymptotic (long-run) state frequencies at an arbitrary point in time and at the points of the imbedded point process. Included are sample-path versions of the rate-conservation principle, the global-balance conditions, and the insensitivity of the asymptotic frequency distribution to the distribution of processing time in a LCFS-PR service facility. We also provide a natural sample-path characterization of the PASTA property.The research of this author was partially supported by the U.S. Army Research Office, Contract DAAG29-82-K-0151 at N.C. State University, and by the National Science Foundation, Grant No. ECS-8719825, at the University of North Carolina, Chapel Hill.The research of this author was partially supported by the U.S. Army Research Office, Contract DAAG29-82-K-0151 at N.C. State University.     

On the dynamic programming principle for uniformly nondegenerate stochastic differential games in domains and the Isaacs equations

We prove the dynamic programming principle for uniformly nondegenerate stochastic differential games in the framework of time-homogeneous diffusion processes considered up to the first exit time from a domain. In contrast with previous results established for constant stopping times we allow arbitrary stopping times and randomized ones as well. There is no assumption about solvability of the the Isaacs equation in any sense (classical or viscosity). The zeroth-order “coefficient” and the “free” term are only assumed to be measurable in the space variable. We also prove that value functions are uniquely determined by the functions defining the corresponding Isaacs equations and thus stochastic games with the same Isaacs equation have the same value functions.     

Imbedded construction of stationary sequences and point processes with a random memory

We show convergence in variation to a unique stationary state for a class of point processes (respectively, stochastic sequences) with stochastic intensity kernels (respectively, transition probabilities) including the (A,m)-processes of Lindvall [12]. This is done under two basic conditions: first, the random memory of the processes considered is consistent or non-reusable (that is, past information not used at a given time cannot be recalled at a later time) and secondly, the kernels have a deterministic fixed component for which the memory is almost surely finite.     

Stochastic partial differential equations and filtering of diffusion processes

We establish basic results on existence and uniqueness for the solution of stochastic PDE's. We express the solution of a backward linear stochastic PDE in terms of the conditional law of a partially observed Markov diffusion process. It then follows that the adjoint forward stochastic PDE governs the evolution of the “unnormalized conditional density”     

Computing a Stationary Base-Stock Policy for a Finite Horizon Stochastic Inventory Problem with Non-linear Shortage Costs

Abstract

We consider a periodic-review stochastic inventory problem in which demands for a single product in each of a finite number of periods are independent and identically distributed random variables. We analyze the case where shortages (stockouts) are penalized via fixed and proportional costs simultaneously. For this problem, due to the finiteness of the planning horizon and non-linearity of the shortage costs, computing the optimal inventory policy requires a substantial effort as noted in the previous literature. Hence, our paper is aimed at reducing this computational burden. As a resolution, we propose to compute “the best stationary policy.” To this end, we restrict our attention to the class of stationary base-stock policies, and show that the multi-period, stochastic, dynamic problem at hand can be reduced to a deterministic, static equivalent. Using this important result, we introduce a model for computing an optimal stationary base-stock policy for the finite horizon problem under consideration. Fundamental analytic conclusions, some numerical examples, and related research findings are also discussed.     

On max-stable processes and the functional D-norm

We introduce some mathematical framework for extreme value theory in the space of continuous functions on compact intervals and provide basic definitions and tools. Continuous max-stable processes on [0, 1] are characterized by their “distribution functions” G which can be represented via a norm on function space, called D-norm. The high conformity of this setup with the multivariate case leads to the introduction of a functional domain of attraction approach for stochastic processes, which is more general than the usual one based on weak convergence. We also introduce the concept of “sojourn time transformation” and compare several types of convergence on function space. Again in complete accordance with the uni- or multivariate case it is now possible to get functional generalized Pareto distributions (GPD) W via W?=?1?+?log(G) in the upper tail. In particular, this enables us to derive characterizations of the functional domain of attraction condition for copula processes.     

Spectral tail processes and max-stable approximations of multivariate regularly varying time series

A regularly varying time series as introduced in Basrak and Segers (2009) is a (multivariate) time series such that all finite dimensional distributions are multivariate regularly varying. The extremal behavior of such a process can then be described by the index of regular variation and the so-called spectral tail process, which is the limiting distribution of the rescaled process, given an extreme event at time 0. As shown in Basrak and Segers (2009), the stationarity of the underlying time series implies a certain structure of the spectral tail process, informally known as the “time change formula”. In this article, we show that on the other hand, every process which satisfies this property is in fact the spectral tail process of an underlying stationary max-stable process. The spectral tail process and the corresponding max-stable process then provide two complementary views on the extremal behavior of a multivariate regularly varying stationary time series.     

On the complexity of convex hull algorithms if rotational minima can be found very fast

For a large class of time functionsT, we show the following: Assuming that there is some parallel processor which requiresθ(T(j)) time units when searching the minimum amongj arbitrary points with respect to an arbitrary rotational ordering. Then the planar Convex Hull Problem forn points is of the complexityθ(nT(n)). Also our auxiliar results are significant: We shall deal with a graph theoretical lemma, and we shall prove a result which is similar to those of [Frie 72] and [Schm 83]: The worst-case complexity of the sorting problem is Ω(n log (n)) even if the operations “+”, “-”, “×”, “/” and queries ‘p(x) ∈ A?’ are possible where the rational functionp and the setA ?IR are arbitrary. At last, we describe the architecture of a network which actually searches polar minima inθ(T(j)) time units.     

On the Hamiltonicity Gap and doubly stochastic matrices

We consider the Hamiltonian cycle problem embedded in singularly perturbed (controlled) Markov chains. We also consider a functional on the space of stationary policies of the process that consists of the (1,1)‐entry of the fundamental matrices of the Markov chains induced by these policies. We focus on the subset of these policies that induce doubly stochastic probability transition matrices which we refer to as the “doubly stochastic policies.” We show that when the perturbation parameter, ε, is sufficiently small, the minimum of this functional over the space of the doubly stochastic policies is attained at a Hamiltonian cycle, provided that the graph is Hamiltonian. We also show that when the graph is non‐Hamiltonian, the above minimum is strictly greater than that in a Hamiltonian case. We call the size of this difference the “Hamiltonicity Gap” and derive a conservative lower bound for this gap. Our results imply that the Hamiltonian cycle problem is equivalent to the problem of minimizing the variance of the first hitting time of the home node, over doubly stochastic policies. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Representation of stochastic processes of second order and linear operations

Series representations are obtained for the entire class of measurable, second order stochastic processes defined on any interval of the real line. They include as particular cases all earlier representations; they suggest a notion of “smoothness” that generalizes well-known continuity notions; and they decompose the stochastic process into two orthogonal parts, the smooth part and a strongly discontinuous part. Also linear operations on measurable, second order processes are studied; it is shown that all “smooth” linear operations on a process, and, in particular, all linear operations on a “smooth” process, can be approximated arbitrarily closely by linear operations on the sample paths of the process.     

Stochastic processes determined by a general success-breeds-success principle

The general “success-breeds-success” (SBS) principle as introduced in a previous paper extends the classical SBS principle in that the allocation of items over sources is determined by a more general rule than in the classical case. In this article we study the time evolution of the total number of sources, the average number of items per source and the number of sources with n items at time t, in the general SBS framework. Conditional as well as absolute expectations are calculated. Moreover, we investigate if and when these processes are martingales, supermartingales or submartingales. Stability results for the stochastic processes are obtained in the sense that we are able to determine when these processes converge. The article also studies the evolution of the expected average number of items per source.     

On stochastic boundedness and stationary measures for Markov processes

In this report we relate the property of stochastic boundedness to the existence of stationary measures for arbitrary Markov processes on the positive real line. We further develop a sufficiency criterion for the independence of such measures from initial conditions. The results are then applied to the question of approximating the fixed point vector of an irreducible infinite stochastic matrix by the solutions of finite ones.     

On the differentiability of a class of stationary gaussian processes

For a stationary Gaussian process either almost all sample paths are almost everywhere differentiable or almost all sample paths are almost nowhere differentiable. In this paper it is shown by means of an example involving a random lacunary trigonometric series that “almost everywhere differentiable” and “almost nowhere differentiable” cannot in general be replaced by “everywhere differentiable” and “nowhere differentiable”, respectively.     

The tightness in the ergodic analysis of regenerative queueing processes

The tightness of some queueing stochastic processes is proved and its role in an ergodic analysis is considered. It is proved that the residual service time process in an open Jackson-type network is tight. The same problem is solved for a closed network, where the basic discrete time process is embedded at the service completion epochs. An extention of Kiefer and Wolfowitz's “key” lemma to a nonhomogeneous multiserver queue with an arbitrary initial state is obtained. These results are applied to get the ergodic theorems for the basic regenerative network processes. This revised version was published online in June 2006 with corrections to the Cover Date.     

Cognitive processes of the brain: An ultrametric model of information dynamics in unconsciousness

We discuss differences in mathematical representations of the physical and mental worlds. Following Aristotle, we present the mental space as discrete, hierarchic, and totally disconnected topological space. One of the basic models of such spaces is given by ultrametric spaces and more specially by m-adic trees. We use dynamical systems in such spaces to model flows of unconscious information at different level of mental representation hierarchy, for “mental points”, categories, and ideas. Our model can be interpreted as an unconventional computational model: non-algorithmic hierarchic “computations” (identified with the process of thinking at the unconscious level).     

Monotone matrices and monotone Markov processes

A stochastic matrix is “monotone” [4] if its row-vectors are stochastically increasing. Closure properties, characterizations and the availability of a second maximal eigenvalue are developed. Such monotonicity is present in a variety of processes in discrete and continous time. In particular, birth-death processes are monotone. Conditions for the sequential monotonicity of a process are given and related inequalities presented.     

Sequential games as stochastic processes

This paper examines the stochastic processes generated by sequential games that involve repeated play of a specific game. Such sequential games are viewed as adaptive decision-making processes over time wherein each player updates his “state” after every play. This revision may involve one's strategy or one's prior distribution on the competitor's strategies. It is shown that results from the theory of discrete time Markov processes can be applied to gain insight into the asymptotic behavior of the game. This is illustrated with a duopoly game in economics.