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.     

Mean and variance of first passage time of non-homogeneous random walk

The prime concern of this paper is the first passage time of a non-homogeneous random walk, which is nearest neighbor but able to stay at its position. It is revealed that the branching structure of the walk corresponds to a 2-type non-homogeneous branching process and the first passage time of the walk can be expressed by that branching process. Therefore, one can calculate the mean and variance of the first passage time, though its exact distribution is unknown.     

On the first passage time of a simple random walk on a tree

We consider a simple random walk on a tree. Exact expressions are obtained for the expectation and the variance of the first passage time, thereby recovering the known result that these are integers. A relationship of the mean first passage matrix with the distance matrix is established and used to derive a formula for the inverse of the mean first passage matrix.     

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.     

Delayed random walks

A delayed random walk $\text{{S}{}^1{}_{\mathrm{n}}\text{, n ≥ 0}}$ is defined here as a partial sum process of independent random variables in which the first N summands (N optional) are distributed F¹,…,F_N, respectively, while all remaining summands are distributed F₀, where {F_k, _k ≥ 0} is a sequence of proper distribution functions on the real line. Delayed random walks arise naturally in the study of certain generalized single server queues. This paper examines optional times of the process such as $\text{π = inf {n: n ≥ 1 and S}{}^1{}_{\mathrm{n}}\text{≥ 0}}$. Conditions insuring the finiteness of E {π} and E {π²} are obtained, generating functions calculated, and illustrative examples given. The bivariate functions $\text{E{r}{}^{\mathrm{\pi }}\text{explsqbitS}{}^1{}_{\mathrm{\pi }}\text{rsqb}}$ and $\text{E {}\text{∑}\text{n=0}\text{π?1}\text{explsqbitS}{}^1{}_{\mathrm{n}}\text{rsqb}}$ are studied for the case where N ≡ 1.     

First passage time for some stationary processes

For a 1-dependent stationary sequence {X_n} we first show that if u satisfies p₁=p₁(u)=P(X₁>u)0.025 and n>3 is such that 88np₁³1, then

P{max(X₁,…,X_n)u}=ν·μⁿ+O{p₁³(88n(1+124np₁³)+561)}, n>3,

where

ν=1−p₂+2p₃−3p₄+p₁²+6p₂²−6p₁p₂,μ=(1+p₁−p₂+p₃−p₄+2p₁²+3p₂²−5p₁p₂)⁻¹

with

p_k=p_k(u)=P{min(X₁,…,X_k)>u}, k1

and

|O(x)||x|.

From this result we deduce, for a stationary T-dependent process with a.s. continuous path {Y_s}, a similar, in terms of P{max_0skTY_s<u}, k=1,2 formula for P{max_0stY_su}, t>3T and apply this formula to the process Y_s=W(s+1)−W(s), s0, where {W(s)} is the Wiener process. We then obtain numerical estimations of the above probabilities.     

Sojourn time problems in feedback queues

A brief survey of the literature on sojourn time problems in single node feedback queueing systems is presented. The derivation of the distribution and moments of the sojourn time of a typical customer in a Markov renewal queue with state dependent feedback is considered in depth. The techniques used relate to the derivation of a first passage time distribution in a particular Markov renewal process. These results are applied to birth-death queues with state dependent feedback. For such models an alternative approach using the theory of Markov chains in continuous time is also examined.     

随机单调的离散时间马氏链强遍历速度的估计I

研究了离散时间马氏链的强遍历性,对随机单调的离散时间马氏链,给出了最大强遍历收敛速度的下界估计。     

Competing first passage percolation on random graphs with finite variance degrees

We study the growth of two competing infection types on graphs generated by the configuration model with a given degree sequence. Starting from two vertices chosen uniformly at random, the infection types spread via the edges in the graph in that an uninfected vertex becomes type 1 (2) infected at rate λ₁ (λ₂) times the number of nearest neighbors of type 1 (2). Assuming (essentially) that the degree of a randomly chosen vertex has finite second moment, we show that if λ₁ = λ₂, then the fraction of vertices that are ultimately infected by type 1 converges to a continuous random variable V ∈ (0,1), as the number of vertices tends to infinity. Both infection types hence occupy a positive (random) fraction of the vertices. If λ₁ ≠ λ₂, on the other hand, then the type with the larger intensity occupies all but a vanishing fraction of the vertices. Our results apply also to a uniformly chosen simple graph with the given degree sequence.     

Large deviations of the first passage time for a random walk with semiexponentially distributed jumps

Suppose that ξ, ξ(1), ξ(2), ... are independent identically distributed random variables such that ?ξ is semiexponential; i.e., $P( - \xi \geqslant t) = e^{ - t^\beta L(t)} $ is a slowly varying function as t → ∞ possessing some smoothness properties. Let E ξ = 0, D ξ = 1, and S(k) = ξ(1) + ? + ξ(k). Given d > 0, define the first upcrossing time η ₊(u) = inf{k ≥ 1: S(k) + kd > u} at nonnegative level u ≥ 0 of the walk S(k) + kd with positive drift d > 0. We prove that, under general conditions, the following relation is valid for $u = (n) \in \left[ {0, dn - N_n \sqrt n } \right]$ : 0.1 $P(\eta + (u) > n) \sim \frac{{E\eta + (u)}}{n}P(S(n) \leqslant x) as n \to \infty $ , where x = u ? nd < 0 and an arbitrary fixed sequence N _n not exceeding $d\sqrt n $ tends to ∞. The conditions under which we prove (0.1) coincide exactly with the conditions under which the asymptotic behavior of the probability P(S(n) ≤ x) for $x \leqslant - \sqrt n $ was found in [1] (for $x \in \left[ { - \sqrt n ,0} \right]$ it follows from the central limit theorem).     

On first passage times of a hyper-exponential jump diffusion process

We investigate some important probabilistic properties relating to the first passage time of a hyper-exponential jump diffusion process, including its finiteness, expectation, conditional memorylessness, and conditional independence. Moreover, the joint distribution of the first passage time and the overshoot is studied from a primal-dual perspective.     

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

First passage problems for exponenetial class of random processes are discussed     

On the cover time of random walks on graphs

This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n ²) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271.     

Some first passage time problems for the shortest queue model

We consider the symmetric shortest queue (SQ) problem. Here we have a Poisson arrival stream of rate λ feeding two parallel queues, each having an exponential server that works at rate μ. An arrival joins the shorter of the two queues; if both are of equal length the arrival joins either with probability 1/2. We consider the first passage time until one of the queues reaches the value m ₀, and also the time until both reach this level. We give explicit expressions for the first two first passage moments, conditioned on the initial queue lengths, and also the full first passage distribution. We also give some asymptotic results for m ₀→∞ and various values of ρ=λ/μ. H. Yao work was partially supported by PSC-CUNY Research Award 68751-0037. C. Knessl work was supported in part by NSF grants DMS 02-02815 and DMS 05-03745.     

Numerical computation of mean passage times and absorption probabilities in Markov and Semi-Markov models

This paper discusses an efficient method to compute mean passage times and absorption probabilities in Markov and Semi-Markov models. It uses the state reduction approach introduced by Winfried Grassmann for the computation of the stationary distribution of a Markov model. The method is numerically stable and has a simple probabilistic interpretation. It is especially stressed, that the natural frame for the state reduction method is rather Semi-Markov theory than Markov theory.

---

Zusammenfassung Es wird ein wirkungsvolles Rechenverfahren zur Bestimmung von mittleren Zeiten bis zur Absorption und von Absorptions-Wahrscheinlichkeiten in Markoff- und Semi-Markoff-Modellen dargestellt. Die Methode beruht auf dem Zustands-Reduktions-Ansatz, der von Grassmann für die Berechnung stationärer Verteilungen von Markoff-Ketten eingeführt wurde. Das Verfahren ist numerisch stabil und hat eine einfache wahrscheinlichkeitstheoretische Interpretation. Es wird hervorgehoben, da\ der natürliche Rahmen der Methode eher die Semi-Markoff-Theorie als die Markoff-Theorie ist.

     

Nonparametric evaluation of the first passage time of degradation processes

This paper discusses a nonparametric method to approximate the first passage time (FPT) distribution of the degradation processes incorporating random effects if the process type is unknown. The FPT of a degradation process is unnecessarily observed since its density function can be approximated by inverting the empirical Laplace transform using the empirical saddlepoint method. The empirical Laplace transform is composed of the measured increments of the degradation processes. To evaluate the performance of the proposed method, the approximated FPT is compared with the theoretical FPT assuming a true underlying process. The nonparametric method discussed in this paper is shown to possess the comparatively small relative errors in the simulation study and performs well to capture the heterogeneity in the practical data analysis. To justify the fitting results, the goodness‐of‐fit tests including Kolmogorov‐Smirnov test and Cramér‐von Mises test are conducted, and subsequently, a bootstrap confidence interval is constructed in terms of the 90th percentile of the FPT distribution.     

Discrete-time zero-sum Markov games with first passage criteria

In this paper, we deal with two-person zero-sum stochastic games for discrete-time Markov processes. The optimality criterion to be studied is the discounted payoff criterion during a first passage time to some target set, where the discount factor is state-dependent. The state and action spaces are all Borel spaces, and the payoff functions are allowed to be unbounded. Under the suitable conditions, we first establish the optimality equation. Then, using dynamic programming techniques, we obtain the existence of the value of the game and a pair of optimal stationary policies. Moreover, we present the exponential convergence of the value iteration and a ‘martingale characterization’ of a pair of optimal policies. Finally, we illustrate the applications of our main results with an inventory system.     

具有不良影响的一类存贮过程的首中时

考虑一类具有正负跳(正负跳大小服从Erlang分布)的存贮过程的首中时,利用马氏无穷小算子的方法来刻画首中时的拉普拉斯变换.     

A class of infinitely divisible distributions connected to branching processes and random walks

A class of infinitely divisible distributions on {0,1,2,…} is defined by requiring the (discrete) Lévy function to be equal to the probability function except for a very simple factor. These distributions turn out to be special cases of the total offspring distributions in (sub)critical branching processes and can also be interpreted as first passage times in certain random walks. There are connections with Lambert's W function and generalized negative binomial convolutions.