Waiting Time Random Variables: Upper Bounds

#### U. Paun

2013, v.19, №4, 791-818

ABSTRACT

Using the Markov chain method and certain results from the Markov chain theory, we give (to illustrate our method) upper bounds for $P(X=n)$ and $P (X>n)$ when $X=$ the waiting time of $k$th occurrence of $s$ in an $s$-$f$ sequence of trials ($k\geq 1$; $s$ - "success", $f$ - "failure") and when $X$ is the waiting time of a pattern $\theta =a_{i_{1}}a_{i_{2}} \dots a_{i_{k}}$ with $a_{i_{1}}=a_{i_{2}}= \dots = a_{i_{k}}$ or $a_{i_{2}},a_{i_{3}}, \dots, a_{i_{k}} \neq a_{i_{1}}$ in an $a_{1}$-$a_{2}$-$\dots$-$a_{m}$ sequence of trials ($m\geq 2$, $k\geq 1,i_{1},i_{2}, \dots,i_{k} \in \langle m \rangle$). Moreover, a more general case than the latter one, namely, $X$ is the waiting time of a pattern $\theta =a_{i_{1}}a_{i_{2}} \dots a_{i_{k}}$ in an $a_{1}$-$a_{2}$-$\dots$-$a_{m}$ sequence of trials ($m\geq 2,k\geq 1,i_{1},i_{2},\dots,i_{k}\in \langle m \rangle$) is considered -- our method works in each special case of this one. In this article, the trials are only independent -- they are or not identically distributed. On the other hand, we give two upper bounds for the expectation of a discrete waiting time random variable and, further, two applications of one of them.

Keywords: Markov chain,upper bound,ergodicity coefficient,Markov chainmethod,waiting time random variable,lower Hessenberg matrix,expectation