Extremal first passage times for trees

For random walks associated with trees with probability zero of staying at any vertex, we develop explicit graph theoretic formulas for the mean first passage times between states, we give lower and upper bounds for the entries of the mean first passage matrix E, and we characterize the cases of equality in these bounds. We also consider the variance of the first return time to a state and we find those trees which maximize the variance and those trees which minimize the variance. As may be expected, the trees which provide extremal behavior are given by paths and stars.     

Entropy Maximization for Markov and Semi-Markov Processes

The literature about maximum of entropy for Markov processes deals mainly with discrete-time Markov chains. Very few papers dealing with continuous-time jump Markov processes exist and none dealing with semi-Markov processes. It is the aim of this paper to contribute to fill this lack. We recall the basics concerning entropy for Markov and semi-Markov processes and we study several problems to give an overview of the possible directions of use of maximum entropy in connection with these processes. Numeric illustrations are presented, in particular in application to reliability.     

Reduced systems in Markov chains and their applications in queueing theory

A reduced system is a smaller system derived in the process of analyzing a larger system. While solving for steady-state probabilities of a Markov chain, generally the solution can be found by first solving a reduced system of equations which is obtained by appropriately partitioning the transition probability matrix. In this paper, we catagorize reduced systems as standard and nonstandard and explore the existence of reduced systems and their properties relative to the original system. We also discuss first passage probabilities and means for the standard reduced system relative to the original system. These properties are illustrated while determining the steady-state probabilities and first passage time characteristics of a queueing system.     

A divide and conquer approach to computing the mean first passage matrix for Markov chains via Perron complement reductions

Let M_T be the mean first passage matrix for an n‐state ergodic Markov chain with a transition matrix T. We partition T as a 2×2 block matrix and show how to reconstruct M_T efficiently by using the blocks of T and the mean first passage matrices associated with the non‐overlapping Perron complements of T. We present a schematic diagram showing how this method for computing M_T can be implemented in parallel. We analyse the asymptotic number of multiplication operations necessary to compute M_T by our method and show that, for large size problems, the number of multiplications is reduced by about 1/8, even if the algorithm is implemented in serial. We present five examples of moderate sizes (of orders 20–200) and give the reduction in the total number of flops (as opposed to multiplications) in the computation of M_T. The examples show that when the diagonal blocks in the partitioning of T are of equal size, the reduction in the number of flops can be much better than 1/8. Copyright © 2001 John Wiley & Sons, Ltd.     

On the first passage times of reflected O-U processes with two-sided barriers

In this article, we give the Laplace transform of the first passage times of reflected Ornstein-Uhlenbeck process with two-sided barriers. AMS Subject Classifications 60H10 · 60G40 · 90B05 Supported by NSF of China.     

Tail probabilities of low-priority waiting times and queue lengths in MAP/GI/1 queues

We consider the problem of estimating tail probabilities of waiting times in statistical multiplexing systems with two classes of sources – one with high priority and the other with low priority. The priority discipline is assumed to be nonpreemptive. Exact expressions for the transforms of these quantities are derived assuming that packet or cell streams are generated by Markovian Arrival Processes (MAPs). Then a numerical investigation of the large-buffer asymptotic behavior of the the waiting-time distribution for low-priority sources shows that these asymptotics are often non-exponential.     

The steady‐state probabilities for regenerative semi‐Markov processes with application to prevention and screening

There is a growing interest in planning and implementing broad‐scale clinical trials with a focus on prevention and screening. Often, the data‐generating mechanism for such experiments can be viewed as a semi‐Markov process. In this communication, we develop general expressions for the steady‐state probabilities for regenerative semi‐Markov processes. Hence, the probability of being in a certain state at the time of recruitment to a clinical trial can be calculated. An application to breast cancer prevention is demonstrated. Copyright © 1999 John Wiley & Sons, Ltd.     

First passage times for Markov renewal processes and applications

This paper proposes a uniformly convergent algorithm for the joint transform of the first passage time and the first passage number of steps for general Markov renewal processes with any initial state probability vector. The uniformly convergent algorithm with arbitrarily prescribed error can be efficiently applied to compute busy periods, busy cycles, waiting times, sojourn times, and relevant indices of various generic queueing systems and queueing networks. This paper also conducts a numerical experiment to implement the proposed algorithm.     

Optimal risk probability for first passage models in semi-Markov decision processes

This paper studies the risk minimization problem in semi-Markov decision processes with denumerable states. The criterion to be optimized is the risk probability (or risk function) that a first passage time to some target set doesn't exceed a threshold value. We first characterize such risk functions and the corresponding optimal value function, and prove that the optimal value function satisfies the optimality equation by using a successive approximation technique. Then, we present some properties of optimal policies, and further give conditions for the existence of optimal policies. In addition, a value iteration algorithm and a policy improvement method for obtaining respectively the optimal value function and optimal policies are developed. Finally, two examples are given to illustrate the value iteration procedure and essential characterization of the risk function.     

Moduli of continuity of local times of strongly symmetric Markov processes via Gaussian processes

LetX be a strongly symmetric standard Markov process on a locally compact metric spaceS with 1-potential densityu ¹(x, y). Let {L _t ^y , (t, y)R ⁺×S} denote the local times ofX and letG={G(y), yS} be a mean zero Gaussian process with covarianceu ¹(x, y). In this paper results about the moduli of continuity ofG are carried over to give similar moduli of continuity results aboutL _t ^y considered as a function ofy. Several examples are given with particular attention paid to symmetric Lévy processes.The research of both authors was supported in part by a grant from the National Science Foundation. In addition the research of Professor Rosen was also supported in part by a PSC-CUNY research grant. Professor Rosen would like to thank the Israel Institute of Technology, where he spent the academic year 1989–90 and was supported, in part, by the United States-Israel Binational Science Foundation. Professor Marcus was a faculty member at Texas A&M University while some of this research was carried out.     

First passage of time-reversible spectrally negative Markov additive processes

We study the first passage process of a spectrally negative Markov additive process (MAP). The focus is on the background Markov chain at the times of the first passage. This process is a Markov chain itself with a transition rate matrix Λ. Assuming time reversibility, we show that all the eigenvalues of Λ are real, with algebraic and geometric multiplicities being the same, which allows us to identify the Jordan normal form of Λ. Furthermore, this fact simplifies the analysis of fluctuations of a MAP. We provide an illustrative example and show that our findings greatly reduce the computational efforts required to obtain Λ in the time-reversible case.     

A characterization for mixtures of semi-Markov processes

Mixtures of recurrent semi-Markov processes are characterized through a partial exchangeability condition of the array of successor states and holding times. A stronger invariance condition on the joint law of successor states and holding times leads to mixtures of Markov laws.     

On first passage time structure of random walks

For continuous time birth-death processes on {0,1,2,…}, the first passage time T⁺_n from n to n + 1 is always a mixture of (n + 1) independent exponential random variables. Furthermore, the first passage time T_0,n+1 from 0 to (n + 1) is always a sum of (n + 1) independent exponential random variables. The discrete time analogue, however, does not necessarily hold in spite of structural similarities. In this paper, some necessary and sufficient conditions are established under which T⁺_n and T_0,n+1 for discrete time birth-death chains become a mixture and a sum, respectively, of (n + 1) independent geometric random variables on {1,2,…};. The results are further extended to conditional first passage times.     

Rainflow analysis in Coastal Engineering using switching second order Markov models

The paper deals with the use of Markov and switching Markov chain models of turning points to reproduce random sets of sea states. The advantages of these models are emphasized and compared with existing models based on wave height records, indicating that long and short range and period cycles are included, while the wave height records ignore this important information from the point of view of damage accumulation. Existing models for first order Markov processes are extended to the case of second order processes and closed formulas are given to derive the rainflow matrices of these processes. Finally, one illustrative example of application is given.     

On the moments of some first passage times and the associated processes

First passage problems for exponenetial class of random processes are discussed     

Pointwise estimates for first passage times of perpetuity sequences

We consider first passage times ${\tau }_u=inf\{n:Y_n>u\}$ for the perpetuity sequence

$Y_n=B_1+A_1{B}_2+?+(A_1\dots A_{n?1})B_n,$

where $(A_n,B_n)$ are i.i.d. random variables with values in ${\mathbb{R}}^{+}\times \mathbb{R}$. Recently, a number of limit theorems related to ${\tau }_u$ were proved including the law of large numbers, the central limit theorem and large deviations theorems (see Buraczewski et al., in press). We obtain a precise asymptotics of the sequence $\mathbb{P}[{\tau }_u=logu∕\rho ]$, $\rho >0$, $u\to \infty$ which considerably improves the previous results of Buraczewski et al. (in press). There, probabilities $\mathbb{P}[{\tau }_u\in I_u]$ were identified, for some large intervals $I_u$ around $k_u$, with lengths growing at least as $loglogu$. Remarkable analogies and differences to random walks (Buraczewski and Ma?lanka, in press; Lalley, 1984) are discussed.     

Numerical Solution of non-Homogeneous Semi-Markov Processes in Transient Case*

In this article a numerical solution for the evolution equation of a continuous time non-homogeneous semi-Markov process (NHSMP) is obtained using a quadrature method. The paper, after a short introduction to continuous time NHSMP, presents the numerical solution of the process evolution equation with a general quadrature method. Furthermore, the paper gives results that justify this approach, proving that the numerical solution tends to the evolution equation of the continuous time NHSMP. Moreover, the formulae related to some specific quadrature methods are given and a method for obtaining the discrete time NHSMP by applying a very particular quadrature formula for the discretization is shown. In this way the relation between the continuous and discrete time NHSMP is proved. Then, the problem of obtaining the continuous time NHSMP from the discrete one is considered. This problem is solved showing that the discrete process converges in law to the continuous one if the discretized time interval tends to zero. In addition, the discrete time NHSMP in matrix form is presented, and the fact that the solution to this process always exists is proved. Finally, an algorithm for solving the discrete time NHSMP is given. To illustrate the use of this algorithm for a discrete NHSMP, an example in the area of finance is presented.     

On some functionals of the first passage times in jump models of stochastic volatility

Abstract

We compute some functionals related to the generalized joint Laplace transforms of the first times at which two-dimensional jump processes exit half strips. It is assumed that the state space components are driven by Cox processes with both independent and common (positive) exponential jump components. The method of proof is based on the solutions of the equivalent partial integro-differential boundary-value problems for the associated value functions. The results are illustrated on several two-dimensional jump models of stochastic volatility which are based on non-affine analogs of certain mean-reverting or diverting diffusion processes representing closed-form solutions of the appropriate stochastic differential equations.     

A central limit theorem for the sojourn times of strongly ergodic Markov chains

Let X_n be an irreducible aperiodic recurrent Markov chain with countable state space I and with the mean recurrence times having second moments. There is proved a global central limit theorem for the properly normalized sojourn times. More precisely, if $\text{t}{}^{\mathrm{(n}}\text{)}{}_{\mathrm{i}}\text{=Σ}{}^{\mathrm{n}}{}_{\mathrm{k=1}}\text{i}\text{?}{}_{\mathrm{i}}\text{(X}{}_{\mathrm{k}}\text{)}$, then the probability measures induced by {t⁽ⁿ⁾_i/√n?√nπ_i}_i?I(π_i being the ergotic distribution) on the Hilbert-space of square summable I-sequences converge weakly in this space to a Gaussian measure determined by a certain weak potential operator.     

On the computation of the optimal cost function for discrete time Markov models with partial observations

We consider several applications of two state, finite action, infinite horizon, discrete-time Markov decision processes with partial observations, for two special cases of observation quality, and show that in each of these cases the optimal cost function is piecewise linear. This in turn allows us to obtain either explicit formulas or simplified algorithms to compute the optimal cost function and the associated optimal control policy. Several examples are presented.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-86-0029, in part by the National Science Foundation under Grant ECS-8617860, in part by the Advanced Technology Program of the State of Texas, and in part by the DoD Joint Services Electronics Program through the Air Force Office of Scientific Research (AFSC) Contract F49620-86-C-0045.