Estimates of the probability of a regenerative process reaching a high level
Kateryna Akbash, Ivan Matsak, Oleg Zakusylo · 2025
Read Estimates of the probability of a regenerative process reaching a high level by Kateryna Akbash, Ivan Matsak, Oleg Zakusylo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-24600.txt.
Introduction
Kateryna Akbash, Ivan Matsak, and Oleg Zakusylo study a random process that renews itself in cycles. Their math work asks how likely such a process is to climb to a high level. They give bounds from both sides for that chance, not just one rough guess.
Two side results on sums with a delay play a key role in their proof. The authors then show how the bounds can be used in queue work. Such queues model lines of jobs or calls that wait for help, so the bounds help judge how long or how full a line may get.
Catalog record
| CREATOR | Kateryna Akbash, Ivan Matsak, Oleg Zakusylo |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-24600
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Estimates of the probability of a regenerative process reaching a high level Kateryna Akbash, Ivan Matsak, Oleg Zakusylo Abstract The problem of estimating the probability of a random process reaching a certain level is well known. In this article, two-sided estimates are established for the probability that a regenerative process reaches a high level. Two auxiliary results for geometric sums with delay will play an important role. Examples of application to random processes describing queue lengths in queueing theory are also given. a Volodymyr Vynnychenko Central Ukrainian State University, 1 , Shevchenko street, Kropyvnytskyi 25006, Ukraine b Taras Shevchenko National University of Kyiv, 2/6 , Academician Glushkov avenue, Kyiv 03127, Ukraine [email protected] (K.S.Akbash), [email protected] (O.K. Zakusylo), [email protected] (I.K.Matsak), MSC: Primary 60K25, 60F05 Keywords: probabilities of reaching a high level, regenerative processes, geometric sums, queue-length processes 1 Introduction. Main results The problem of estimating the probability of a random process (r.p.) reaching a certain level arises naturally in applications. For example, in mathematical reliability theory, the problem of estimating the distribution of the time to failure of a redundant system with recovery is well known [ 12 ] . Similar problems also exist in queueing theory, inventory management, etc. Such problems have been intensively studied in ( [ 1 ] , [ 4 ] , [ 11 ] , [ 12 ] , [ 15 ] , [ 22 ] , [ 23 ] ). Clearly, this topic is closely related to the study of extreme values of random processes. Moreover, the extreme values of processes that describe queue lengths or queue wait times for queueing systems have also been studied in many studies [ 4 ] , [ 7 ] , [ 14 ] , [ 23 ] . It should be noted that in many cases, the corresponding mathematical models can be adequately described by regenerative random processes. In this article, we restrict our attention to regenerative processes. The solution to our problem will be based on limit theorems and corresponding estimates for geometric sums (see, for example, [ 1 ] , [ 5 ] , [ 15 ] , [ 19 ] ). Let us recall the definition of a regenerative r.p. Let T be a non-negative random variable (r.v.) such that \mathbf{P}(T>0)>0 , \mathbf{P}(T<\infty)=1 , and let a r.p. \xi(t) , be given on the interval [0,T),\xi(t)\in\mathbb{R}^{1} . Such a pair \pounds=(T,\xi(t)) , t\in[0,T) is called a cycle. Note that the r.v. T and the r.p. \xi(t) may be dependent. Let \pounds_{k}=(T_{k},\xi_{k}(t)) , k\geq 1 , be an infinite sequence of independent cycles, identically distributed with the cycle \pounds=(T,\xi(t)) . Then the process X(t),t\geq 0, is regenerative if it can be represented as follows: X(t)=\xi_{k}(t-S_{k-1}),\quad\mbox{for}\quad t\in[S_{k-1},S_{k}), where S_{k}=T_{1}+\ldots+T_{k},k\geq 1 , S_{0}=0 , (see, for example, [ 21 ] , part II, ch.2, [ 10 ] , ch.11, §8). Points S_{k} are called moments of regeneration, and the interval [S_{k-1},S_{k}) is called the k th period of regeneration. Assume that X(S_{k})=\xi_{k}(0)=0,k\geq 0 , that is, the process X(t) at the beginning of the regeneration cycle starts from state 0 . We impose a separability condition on the r.p. \xi_{i}(t) . Then we can introduce the r.p. \bar{X}(t)=\sup_{0\leq s<t}X(s),\quad t\geq 0 and consider a sequence of independent identically distributed random variables (i.i.d.r.v) \bar{X}_{k}=\sup_{S_{k-1}\leq s<S_{k}}X(s),\quad k=1,2,\ldots, i.e., \bar{X}_{k} is the maximum value of process {X}(t) at the k th regeneration cycle. Let’s introduce some necessary notations. We divide the regeneration cycles into two types. The first type includes cycles in which some event does not occur, and the second type includes cycles in which event A occurs. Event A is interpreted as a failure of some system, which is described by process {X}(t) . In applied problems, {X}(t) often denotes the number of faulty elements of a system at time t . Then event A occurs on the k th cycle if at some point t\in[S_{k-1},S_{k}) all u working elements of the system fail, i.e. \displaystyle A=A_{u}=\{\bar{X}_{k}\geq u\}. (1) In this article, by A_{u} we will mean an event that is defined by the formula ( 1 ), where u>0 is a fixed positive constant, \bar{A_{u}}=\{\bar{X}_{k}<u\} denotes the complementary event. Let \quad q=q(u)=\mathbf{P}(A_{u})=\mathbf{P}(\bar{X}_{k}\geq u)>0. Set q^{*}=-\ln(1-q) . It will be more convenient for us to normalize the corresponding amounts by the value q^{*} , which is equivalent to q . More precisely, q\leq q^{*}\leq q+q^{2}\quad\mbox{for}\quad 0<q<1/2. It will be shown later that our estimates are meaningful only for small values of q . Therefore, we will assume that throughout 0<q<1/2 . Let us denote by \mathbb{F}(x)=\mathbf{P}(T<x) the distribution function of the r.v. T , and by T_{k}^{-} the lengths of the cycles on which event \bar{A_{u}} occurred (cycle type 1 ), \mathbb{F}^{-}(x)=\mathbf{P}(T_{k}^{-}<x)=\mathbf{P}(T_{k}<x/\bar{A_{u}}), m_{1}^{-}=\int_{0}^{\infty}xd\mathbb{F}^{-}(x),\quad m_{r}^{-}=\int_{0}^{\infty}x^{r}d\mathbb{F}^{-}(x). Define analogously T_{k}^{+},\quad\mathbb{F}^{+}(x),\quad m_{1}^{+},\quad m_{r}^{+} to type- 2 cycles, in which event A_{u} occurred. In addition, for cycles of the 2 nd type, we will consider the value \hat{m}_{1}^{+} as the mean time for the process \xi(t) to reach the level u in the corresponding cycle. Finally, we introduce the r.v. \mathfrak{T}_{X}(u) - the first moment when process X(t) reaches level u , that is, \mathfrak{T}_{X}(u)=\inf(t\geq 0:\quad X(t)\geq u), and also \quad\Delta_{X}(x)=1-\exp(-{x})-G_{X}\left(\frac{xm_{1}^{-}}{q^{*}}\right),\quad G_{X}(x)=\mathbf{P}(\mathfrak{T}_{X}(u)\leq x). We impose the following condition on the process X(t) : for some {\gamma>2} \displaystyle m_{\gamma}=\mathbf{E}T^{\gamma}<\infty, (2) and thus m_{1}=\mathbf{E}T<\infty and m_{2}=\mathbf{E}T^{2}<\infty . The main result of this article is formulated in the following theorem. Theorem 1 . Let condition ( 2 ) be satisfied, 0<x<1 is a fixed number and q>0 . Then \displaystyle\exp(-x){q^{*}}\left(\frac{\hat{m}_{1}^{+}}{m_{1}^{-}}-\mathbb{C}_{0}(\mathbb{F},x)\right)\leq\Delta_{X}(x)\leq\exp(-x){q^{*}}\times (3) \displaystyle\times \displaystyle\left(\frac{\hat{m}_{1}^{+}}{m_{1}^{-}}(1+2x(e-2))+\mathbb{C}_{1}(\mathbb{F},x)+\mathbb{C}_{2}(\mathbb{F},x)\right). where \mathbb{C}_{0}(\mathbb{F},x)=\frac{m_{2}^{-}}{(m_{1}^{-})^{2}}+\frac{\gamma m_{\gamma}(q^{*})^{\gamma-2}(1+q)}{(\gamma-1)x^{\gamma-1}(m_{1}^{-})^{\gamma}}, \mathbb{C}_{1}(\mathbb{F},x)=\left(2x(e-2)+1\right)\frac{m_{\gamma}(q^{*})^{\gamma-1}(1+q)}{(m_{1}^{-})^{\gamma}x^{\gamma-1}}, \mathbb{C}_{2}(\mathbb{F},x)=(e-2)\left(\left(\frac{2m_{2}^{-}}{(m^{-}_{1})^{2}}+1\right)\left(x+\left(\frac{m^{-}_{2}}{(m^{-}_{1})^{2}}-1\right)q^{*}\right)+\frac{2m^{-}_{2}x}{(m^{-}_{1})^{2}}-2x+q^{*}\right). Remark 1 . It can be assumed that in many practical problems the probability of event A (the probability of system failure) is quite small, and therefore the estimate ( 3 ) is most interesting for small x . Therefore, we restrict ourselves to the case when 0<x<1 . It should be noted that the left-hand side inequality in ( 3 ) will remain true for all x>0 . Corollary 1 . If, under the conditions and notations of Theorem 1 the distribution function \mathbb{F}(x) is fixed and does not depend on the parameter u , q(u)\rightarrow 0 when u\rightarrow\infty , then \displaystyle\exp(-x){q^{*}}\left(\frac{\hat{m}_{1}^{+}}{m^{-}_{1}}-\frac{m_{2}}{m^{2}_{1}}+o(1)\right)\leq\Delta_{X}(x)\leq\exp(-x){q^{*}}\times (4) \displaystyle\times \displaystyle\left(\frac{\hat{m}_{1}^{+}}{m_{1}^{-}}(1+2x(e-2))+(e-2)\left(\frac{4m_{2}x}{m_{1}^{2}}-x+o(1)\right)\right). Remark 2 . Under the conditions of Corollary 1 the lower bound for function 1-G_{X}(\frac{xm_{1}^{-}}{q^{*}}) can be written as follows: for u\rightarrow\infty \displaystyle 1-G_{X}\left(\frac{xm_{1}^{-}}{q^{*}}\right)\geq\exp(-x)+\exp(-x){q^{*}}\left(\frac{\hat{m}_{1}^{+}}{m^{-}_{1}}-\frac{m_{2}}{m^{2}_{1}}+o(1)\right). (5) This is a pessimistic estimate. In practice, it is often the pessimistic assessments that are often of primary importance (see [ 12 ] ). It is clear that the estimate ( 5 ) is asymptotically more accurate than the estimate obtained in [ 1 ] : 1-G_{X}\left(\frac{xm_{1}^{-}}{q^{*}}\right)\geq\exp(-x)-\exp(-{x})q^{*}\times \times\left((2x(e-2)+1)\frac{{m}^{+}_{1}}{m^{-}_{1}}+\\ (e-2)\left(\frac{4m_{2}}{(m^{-}_{1})^{2}}-1\right)+o(1)\right). The same applies to some uniform estimates (see, for example, Theorem 4 of [ 22 ] and the simple and rather sharp estimate for geometric sums with delay in Theorem 2.2 of [ 5 ] ). Note also that under the conditions of Corollary 1 for \frac{\hat{m}_{1}^{+}}{m^{-}_{1}}>\frac{m_{2}}{m^{2}_{1}} , for instance, if \frac{\hat{m}_{1}^{+}}{m^{-}_{1}}\rightarrow\infty (see example 2 in section 4), the approximation 1-G_{X}\left(\frac{xm_{1}^{-}}{q^{*}}\right)\sim 1-\exp(-x)+\exp(-x){q^{*}}\frac{\hat{m}_{1}^{+}}{m^{-}_{1}} is asymptotically more accurate than the traditional approximation: 1-G_{X}\left(\frac{xm_{1}^{-}}{q^{*}}\right)\sim\exp(-x). It should be noted, however, that in the general case the problem of finding the value of \hat{m}_{1}^{+} is rather involved. Remark 3 . Consider a regenerative process of