Waiting Time Problems for Patterns in a Sequence of Multi-State Trials

Abstract

In this paper, we investigate waiting time problems for a finite collection of patterns in a sequence of independent multi-state trials. By constructing a finite GI/M/1-type Markov chain with a disaster and then using the matrix analytic method, we can obtain the probability generating function of the waiting time. From this, we can obtain the stopping probabilities and the mean waiting time, but it also enables us to compute the waiting time distribution by a numerical inversion.

1. Introduction

Waiting time problems for runs and patterns in a random sequence of trials are considered important, as they are of theoretical interest and have practical applications in various areas of statistics and applied probability such as reliability, sampling inspection, quality control, DNA/RNA sequence analysis, and hypothesis testing ([1]). For comprehensive surveys and applications of related waiting time problems, refer to the books of Balakrishnan and Koutras [2] and Fu and Lou [3].

Let $\{X_t,t\ge 1\}$ be a sequence of random variables taking values in a finite set A. A finite sequence of elements of A is called a pattern. We consider a finite collection $\mathcal{C}=\{C_1,C_2,\dots ,C_K\}$ of patterns, possibly of different lengths. For $i=1,\dots ,K$, let ${\tau }_{C_i}$ be the waiting time until the first occurrence of pattern $C_i$ as a run in the series $X_1,X_2,\dots$. Let W be the waiting time until one of the K patterns appears, i.e.,

$$\begin{array}{c}\hfill W=min\{{\tau }_{C_1},\dots ,{\tau }_{C_K}\}.\end{array}$$

Many researchers have studied waiting time problems for general and specific choices of $\mathcal{C}$ in a random sequence of trials. When $\{X_t,t\ge 1\}$ is a sequence of independent and identically distributed (i.i.d.) Bernoulli trials, Fu and Koutras [4] developed a finite Markov chain embedding method, which was first employed by Fu [5], to study the exact distributions for the numbers of specified runs and patterns. Fu [6] extended the finite Markov chain embedding method to study the exact distributions for the numbers of runs and patterns in a sequence of i.i.d. multi-state trials. In addition, he obtained the waiting time distribution of a specified pattern.

In this paper, we are mainly interested in computing the waiting time distribution, as well as the stopping probabilities $\mathbb{P}(W={\tau }_{C_j})$, $j=1,\dots ,K$. Li [7], Gerber and Li [8], Guibas and Odlyzko [9], Blom and Thorburn [10] and Antzoulakos [11] considered the case when $\{X_t,t\ge 1\}$ is a sequence of i.i.d. multi-state trials. Li [7] and Gerber and Li [8] used the martingale approach to obtain the mean waiting time $\mathbb{E}\left[W\right]$ and the stopping probabilities $\mathbb{P}(W={\tau }_{C_i})$, $i=1,\dots ,K$ for a finite collection $\mathcal{C}$ of patterns. Guibas and Odlyzko [9] used the combinatorial method to obtain the probability generating function of the waiting time. Blom and Thorburn [10] also used the combinatorial method to obtain the mean waiting time $\mathbb{E}\left[W\right]$ and the stopping probabilities $\mathbb{P}(W={\tau }_{C_i})$, $i=1,\dots ,K$ for a finite collection $\mathcal{C}$ of patterns with the same length. Antzoulakos [11] used the finite Markov chain embedding method to study waiting time problems for a single pattern as well as a finite collection $\mathcal{C}$ of patterns.

Han and Hirano [12], Fu and Chang [13], Glaz et al. [14], Pozdnyakov [15], Gava and Salotti [16], Zhao et al. [17] and Kerimov and Öner [18] considered the case when $\{X_t,t\ge 1\}$ is a discrete time homogenous Markov chain with a finite state space, i.e., $\{X_t,t\ge 1\}$ is a sequence of Markov dependent multi-state trials. Han and Hirano [12] studied waiting time problems for two different patterns. Fu and Chang [13] studied waiting time problems for a finite collection of patterns by using the finite Markov chain embedding method. Glaz et al. [14] obtained the mean waiting time $\mathbb{E}\left[W\right]$ and the probability generating function of the waiting time for a finite collection of patterns in a two-state Markov chain by using the method of gambling teams and martingale approach. Pozdnyakov [15] investigated the same problems as in Glaz et al. [14] for multi-state Markovian trials. Gava and Salotti [16] obtained the system of linear equations of stopping probabilities $\mathbb{P}(W={\tau }_{C_i})$, $i=1,\dots ,K$, by using the methods developed for gambling teams in [14,15]. Recently, Zhao et al. [17] found a method, which is based on the method of [9], to calculate $\mathbb{E}\left[W\right]$ and $\mathbb{P}(W={\tau }_{C_i})$, $i=1,\dots ,K$. Even more recently, Kerimov and Öner [18] found oscillation properties of the expected stopping times and stopping probabilities for patterns consisting of two consecutive states. For useful reviews of different approaches to solve waiting time problems of patterns for both i.i.d. and Markov dependent trials, refer to Fu and Lou [3].

Antzoulakos [11] and Fu and Chang [13] obtained the probability generating function of the waiting time for a finite collection of patterns in a sequence of i.i.d. and Markov dependent multi-state trials, respectively. They used a Markov chain with absorbing states corresponding to the patterns and considered the waiting time as the first entrance time into the absorbing state. The Markov chain has the transition probability matrix P of the form:

$$\begin{array}{c}\hfill P=\left[\begin{array}{cc}{P}_{TT}& P_{TA}\\ O& I\end{array}\right],\end{array}$$

(1)

where $P_{TT}$ is the submatrix of P whose entries are transition probabilities from a transient state to a transient state, $P_{TA}$ is the submatrix of P whose entries are transition probabilities from a transient state to an absorbing state, O is the zero matrix and I is the identity matrix. By using the general formula that represents the probability generating function of the first entrance time into the absorbing state, they obtained the probability generating function of the waiting time. Their results are expressed in terms of the submatrices $P_{TT}$ and $P_{TA}$, as well as variants of them. Chang [19] also studied waiting time problems for a finite collection of patterns. He investigated the distribution of the waiting time until the rth occurrence of any pattern in the collection of patterns. He also used the expression (1) for the analysis.

In this paper, we consider a sequence of i.i.d. multi-state trials. We also use a Markov chain with transition probability matrix of the form (1). However, we heavily investigate the structure of the submatrices $P_{TT}$ and $P_{TA}$. This enables us to construct a finite GI/M/1-type Markov chain with a disaster and consider the waiting time as the time until the occurrence of the disaster. Based on this and the matrix analytic method, we obtain the probability generating function of the waiting time W on $\{W={\tau }_{C_j}\}$, ${\Psi }_j\left(z\right)=\mathbb{E}\left[z^W{\mathbb{1}}_{\{W={\tau }_{C_j}\}}\right]$, $j=1,\dots ,K$. From this, we can obtain the stopping probabilities $\mathbb{P}(W={\tau }_{C_i})$, $i=1,\dots ,K$ as well as the conditional/unconditional mean waiting times, $\mathbb{E}\left[W\right|W={\tau }_{C_j}]$ and $\mathbb{E}\left[W\right]$, but it also enables us to compute the waiting time distribution by a numerical inversion. The benefit of our method is that it is useful and efficient even when the length of the pattern is large. Our method can also be extended to Markov dependent multi-state trials.

The paper is organized as follows. In Section 2, we formulate our waiting time problems. In Section 3, we construct a GI/M/1-type Markov chain with a disaster. From this we can obtain our results, which are given in Section 4. In Section 5, numerical examples are presented to illustrate our results. Conclusions are given in Section 6.

2. Problem Formulation

Let $\{X_t,t\ge 1\}$ be a sequence of i.i.d. trials taking values in a finite set A. Assume that for $t=1,2,\dots$,

$$\begin{array}{c}\hfill \mathbb{P}(X_t=x)=p_x,x\in A,\end{array}$$

where ${\sum }_{x\in A}{p}_x=1$. For a finite collection $\mathcal{C}=\{C_1,C_2,\dots ,C_K\}$ of patterns, suppose that pattern $C_i$ is of the form

$$\begin{array}{c}\hfill C_i=s_1^i\cdots s_{l_i}^i,i=1,\dots ,K,\end{array}$$

where $s_j^i\in A,j=1,\dots ,l_i$, i.e., $C_i$ is any pattern of length $l_i$. Here, $l_i$, $i=1,\dots ,K$ are fixed positive integers with $l_1\ge l_2\ge \cdots \ge l_K$. Recall that W is the waiting time until one of the K patterns appears, i.e.,

$$\begin{array}{c}\hfill W=min\{{\tau }_{C_1},\dots ,{\tau }_{C_K}\}.\end{array}$$

We will call W the sooner waiting time.

Our main interest is to derive the probability generating function of the sooner waiting time W on $\{W={\tau }_{C_j}\}$, $j=1,\dots ,K$, i.e.,

$$\begin{array}{c}\hfill {\Psi }_j\left(z\right)=\mathbb{E}\left[z^W{\mathbb{1}}_{\{W={\tau }_{C_j}\}}\right],j=1,\dots ,K.\end{array}$$

(2)

From this, we can obtain the stopping probabilities, the conditional/unconditional probability mass functions of W, and the conditional/unconditional means of W as follows:

• The stopping probabilities $\mathbb{P}(W={\tau }_{C_j}),j=1,\dots ,K$, are given by $\mathbb{P}(W={\tau }_{C_j})={\Psi }_j\left(1\right)$.
• The conditional probability mass function of W, given $W={\tau }_{C_j}$, i.e., $\mathbb{P}(W=n|W={\tau }_{C_j})$, $j=1,\dots ,K$, can be computed from the conditional probability generating function of W given $W={\tau }_{C_j}$, $\frac{{\Psi }_j\left(z\right)}{{\Psi }_j\left(1\right)}$, by a numerical inversion.
• The probability mass function of W, $\mathbb{P}(W=n)$, can be computed from ${\sum }_{j=1}^K{\Psi }_j\left(z\right)$ by a numerical inversion.
• The conditional mean of W, $\mathbb{E}\left[W\right|W={\tau }_{C_j}]$, $j=1,\dots ,K$, can be obtained from $\mathbb{E}\left[W\right|W={\tau }_{C_j}]=\frac{{\mathcal{W}}_j^{\left(1\right)}}{{\Psi }_j\left(1\right)}$, where ${\mathcal{W}}_j^{\left(1\right)}=\frac{d}{dz}{\Psi }_j\left(z\right){|}_{z=1}$. In addition, the unconditional mean of W, $\mathbb{E}\left[W\right]$, can be obtained from $\mathbb{E}\left[W\right]={\sum }_{j=1}^K{\mathcal{W}}_j^{\left(1\right)}$.

3. GI/M/1-Type Markov Chain with a Disaster

In this section, we construct a GI/M/1-type Markov chain with a disaster to obtain an expression for (2). We define the following three terms:

• $s_1\cdots s_j$ is a subpattern of pattern $C_i$ if $s_1\cdots s_j=s_k^i{s}_{k+1}^i\cdots s_{k+j}^i$ for some k with $1\le k\le l_i-j$; when $j=0$, $s_1\cdots s_j$ means the null pattern (i.e., the pattern with length 0).
• A subpattern $s_1\cdots s_j$ of pattern $C_i$ is proper if $j<l_i$ (i.e., $s_1\cdots s_j\ne C_i$).
• A subpattern $s_1\cdots s_j$ of pattern $C_i$ is a leading subpattern of $C_i$ if $s_1\cdots s_j=s_1^i\cdots s_j^i$ for some j with $0\le j\le l_i$.

Assume that for $i\ne j$, $C_i$ is not a proper subpattern of $C_j$.

We now introduce a two-dimensional process $({\tilde{N}}_t,{\tilde{J}}_t)$, $t=0,1,2,\dots$, where ${\tilde{N}}_t$ and ${\tilde{J}}_t$ are defined as follows:

(i) ${\tilde{N}}_0=0$, and for $t=1,2,\dots$,

• ${\tilde{N}}_t$ is the largest $n\in \{0,1,\dots ,min\{l_1-1,t\}\}$ such that $(X_{t-n+1},\dots ,X_t)$ is a proper leading subpattern of a pattern in $\mathcal{C}$, if $t<W$.
• ${\tilde{N}}_t=\Delta$, where $\Delta$ is an extra point, if $t\ge W$.

(ii) ${\tilde{J}}_0=1,$ and for $t=1,2,\dots$,

• ${\tilde{J}}_t$ is the smallest $i\in \{1,\dots ,K\}$ such that $(X_{t-{\tilde{N}}_t+1},\dots ,X_t)$ is a proper leading subpattern of pattern $C_i$, if ${\tilde{N}}_t\in \{1,\dots ,l_1-1\}$.
• ${\tilde{J}}_t=1$, if ${\tilde{N}}_t=0$.
• ${\tilde{J}}_t=j$, if ${\tilde{N}}_t=\Delta$ and $W={\tau }_{C_j}$.

To clarify the definitions of ${\tilde{N}}_t$ and ${\tilde{J}}_t$, we provide the following example: Let $\{X_t,t\ge 1\}$ be a sequence of i.i.d. trials taking values in a finite set $A=\{a,b,c\}$. Suppose $\mathcal{C}=\{C_1,C_2,C_3\}$, where $C_1=aaabbb,C_2=aaba$ and $C_3=abc$. For example, if we consider the sequence of trials

$$\begin{array}{c}\hfill bcaababbaaabbbbc\cdots ,\end{array}$$

then $({\tilde{N}}_t,{\tilde{J}}_t)$, $t=0,1,2,\dots$ are given in

Table 1. Sample paths of ${\tilde{N}}_t$ and ${\tilde{J}}_t$ corresponding to the sample path of $X_t$, $bcaababbaaabbbbc\cdots$.

t	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	⋯
$X_t$		b	c	a	a	b	b	b	a	a	a	b	b	b	b	c	⋯
${\tilde{N}}_t$	0	0	0	1	2	3	0	0	1	2	3	4	5	$\Delta$	$\Delta$	$\Delta$	⋯
${\tilde{J}}_t$	1	1	1	1	1	2	1	1	1	1	1	1	1	1	1	1	⋯

. As another example, if we consider the sequence of trials

$$\begin{array}{c}\hfill ababaccaacaabaa\cdots ,\end{array}$$

then $({\tilde{N}}_t,{\tilde{J}}_t)$, $t=0,1,2,\dots$ are given in

Table 2. Sample paths of ${\tilde{N}}_t$ and ${\tilde{J}}_t$ corresponding to the sample path of $X_t$, $ababaccaacaabaa\cdots$.

t	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	⋯
$X_t$		a	b	a	b	a	c	c	a	a	c	a	a	b	b	a	⋯
${\tilde{N}}_t$	0	1	2	1	2	1	0	0	1	2	0	1	2	3	$\Delta$	$\Delta$	⋯
${\tilde{J}}_t$	1	1	3	1	3	1	1	1	1	1	1	1	1	2	2	2	⋯

. Note that $\{({\tilde{N}}_t,{\tilde{J}}_t),t=0,1,\dots \}$ is a discrete time Markov chain.

Define $m_0=1$ and for $k=1,2,\dots ,l_1-1$, let $m_k$ be the number of patterns in $\mathcal{C}$ whose lengths are larger than k, i.e.,

$$\begin{array}{cc}\hfill m_k& =max\{j\in \{1,\dots ,K\}:k<l_j\},k=1,\dots ,l_1-1.\hfill \end{array}$$

We also define $m_{\Delta }=K$. Note that ${\tilde{N}}_t\in \{0,1,\dots ,l_1-1,\Delta \}$. If ${\tilde{N}}_t=k$, then ${\tilde{J}}_t\in \{1,2,\dots ,m_k\}$. Furthermore, the set of all possible values of ${\tilde{J}}_t$ when ${\tilde{N}}_t=k\in \{0,1,\dots ,l_1-1,\Delta \}$ is given by

$${\mathcal{I}}_k=\left\{\begin{array}{cc}\left\{1\right\}\hfill & \mathrm{if}k=0,\hfill \\ \{i:1\le i\le m_k,s_1^i\cdots s_k^i\mathrm{is}\mathrm{not}a\mathrm{leading}\mathrm{subpattern}\mathrm{of}{C}_j\mathrm{for}j<i\}\hfill & \mathrm{if}1\le k\le l_1-1,\hfill \\ \{1,\dots ,K\}\hfill & \mathrm{if}k=\Delta .\hfill \end{array}\right.$$

Therefore, the state space of the discrete time Markov chain $\{({\tilde{N}}_t,{\tilde{J}}_t),t=0,1,\dots \}$ is

$$\begin{array}{cc}\hfill \mathcal{E}& =\{(k,i):k=0,1,\dots ,l_1-1,\Delta ;i\in {\mathcal{I}}_k\}.\hfill \end{array}$$

(3)

For each state $(k,i)$, the first component k is called level. The one-step transition probability matrix P of $\{({\tilde{N}}_t,{\tilde{J}}_t),t=0,1,\dots \}$ is given, in lexicographic order with $\Delta$ being the last element in the set of levels, as follows:

$$P=\begin{array}{c}0\\ 1\\ 2\\ ⋮\\ l_1-2\\ l_1-1\\ \Delta \end{array}\left[\begin{array}{cccccccc}{P}_{00}& P_{01}& O& O& \cdots & \cdots & O& P_{0\Delta }\\ P_{10}& P_{11}& P_{12}& O& \cdots & \cdots & O& P_{1\Delta }\\ P_{20}& P_{21}& P_{22}& P_{23}& O& \cdots & O& P_{2\Delta }\\ ⋮& ⋮& ⋮& \ddots & \ddots & ⋮& ⋮& ⋮\\ P_{l_1-2,0}& P_{l_1-2,1}& P_{l_1-2,2}& \cdots & \cdots & \cdots & P_{l_1-2,l_1-1}& P_{l_1-2,\Delta }\\ P_{l_1-1,0}& P_{l_1-1,1}& P_{l_1-1,2}& \cdots & \cdots & \cdots & P_{l_1-1,l_1-1}& P_{l_1-1,\Delta }\\ O& O& O& \cdots & \cdots & \cdots & O& I_{\Delta }\end{array}\right],$$

(4)

where the submatrices are described below. A matrix consisting of $(i,j)$ components with $i\in \mathcal{I}$ and $j\in \mathcal{J}$ will be called an $\mathcal{I}\times \mathcal{J}$ matrix.

• For $k=0,1,\dots ,l_1-1$, $P_{k0}$ is the ${\mathcal{I}}_k\times {\mathcal{I}}_0$ matrix whose $(i,1)$-component is

  $$\begin{array}{c}\hfill {\left(P_{k0}\right)}_{i1}=\sum _{x\in A_{k0}^i}{p}_x,\end{array}$$

  where $A_{k0}^i$ is the subset of A consisting of x such that $s_{k^{\prime }}^i{s}_{k^{\prime }+1}^i\cdots s_k^{i}x$ is not a leading subpattern of a pattern in $\mathcal{C}$ for any $k^{\prime }\in \{1,\dots ,k+1\}$.
• For $k=0,1,\dots ,l_1-1$, $P_{k\Delta }$ is an ${\mathcal{I}}_k\times {\mathcal{I}}_{\Delta }$ matrix. The $(i,j)$-component of $P_{k\Delta }$ is

  $$\begin{array}{c}\hfill {\left(P_{k\Delta }\right)}_{ij}=p_{s_{l_j}^j}\end{array}$$

  if $s_1^i{s}_2^i\cdots s_k^i=s_1^j{s}_2^j\cdots s_{l_j-1}^j$. Otherwise, ${\left(P_{k\Delta }\right)}_{ij}=0$.
• For $k=0,1,\dots ,l_1-1$, and $k^{\prime }=1,\dots ,min\{k+1,l_1-1\}$, $P_{k{k}^{\prime }}$ is an ${\mathcal{I}}_k\times {\mathcal{I}}_{k^{\prime }}$ matrix. The $(i,j)$-component of $P_{k{k}^{\prime }}$ is

  $$\begin{array}{c}\hfill {\left(P_{k{k}^{\prime }}\right)}_{ij}=p_{s_{k^{\prime }}^j}\end{array}$$

  if the following three conditions hold:

  (i)

  $s_{k-k^{\prime }+2}^i{s}_{k-k^{\prime }+3}^i\cdots s_k^i{s}_{k^{\prime }}^j$ is a proper leading subpattern of pattern $C_j$;

  (ii)

  $s_1^j\cdots s_{k^{\prime }}^j$ is not a proper leading subpattern of pattern $C_{j^{\prime }}$ for $j^{\prime }\in \{1,\dots ,j-1\}$;

  (iii)

  $s_n^i{s}_{n+1}^i\cdots s_k^i{s}_{k^{\prime }}^j$ is not a leading subpattern of a pattern in $\mathcal{C}$ for $n\in \{1,2,\dots ,k-k^{\prime }+1\}$.

  Otherwise, ${\left(P_{k{k}^{\prime }}\right)}_{ij}=0$.
• O’s are zero matrices (possibly of different sizes).
• $I_{\Delta }$ is the ${\mathcal{I}}_{\Delta }\times {\mathcal{I}}_{\Delta }$ identity matrix.

To make it easier to understand how the matrix P in (4) is constructed, we explain with an example. For the previously described example with $A=\{a,b,c\}$, $C_1=aaabbb,C_2=aaba$ and $C_3=abc$, we have

$$\begin{array}{c}\hfill {\mathcal{I}}_0=\left\{1\right\},{\mathcal{I}}_1=\left\{1\right\},{\mathcal{I}}_2=\{1,3\},{\mathcal{I}}_3=\{1,2\},{\mathcal{I}}_4=\left\{1\right\},{\mathcal{I}}_5=\left\{1\right\},{\mathcal{I}}_{\Delta }=\{1,2,3\}.\end{array}$$

The matrix P is

$$\begin{array}{c}\hfill P=\left[\begin{array}{ccccccc}{P}_{00}& P_{01}& O& O& O& O& P_{0\Delta }\\ P_{10}& P_{11}& P_{12}& O& O& O& P_{1\Delta }\\ P_{20}& P_{21}& P_{22}& P_{23}& O& O& P_{1\Delta }\\ P_{30}& P_{31}& P_{32}& P_{33}& P_{34}& O& P_{1\Delta }\\ P_{40}& P_{41}& P_{42}& P_{43}& P_{44}& P_{45}& P_{1\Delta }\\ P_{50}& P_{51}& P_{52}& P_{53}& P_{54}& P_{55}& P_{1\Delta }\\ O& O& O& O& O& O& I_{\Delta }\end{array}\right],\end{array}$$

where

$$\begin{array}{c}\hfill \begin{array}{cc}{P}_{00}=p_b+p_c,\hfill & P_{01}=p_a,\hfill \\ P_{10}=p_c,\hfill & P_{11}=0,\hfill & P_{12}=\left[p_a{p}_b\right],\hfill \\ P_{20}=\left[\begin{array}{c}{p}_c\\ p_b\end{array}\right],\hfill & P_{21}=\left[\begin{array}{c}0\\ p_a\end{array}\right],\hfill & P_{22}=\left[\begin{array}{cc}0& 0\\ 0& 0\end{array}\right],\hfill & P_{23}=\left[\begin{array}{cc}{p}_a& p_b\\ 0& 0\end{array}\right],\hfill \\ P_{30}=\left[\begin{array}{c}{p}_c\\ p_b\end{array}\right],\hfill & P_{31}=\left[\begin{array}{c}0\\ 0\end{array}\right],\hfill & P_{32}=\left[\begin{array}{cc}0& 0\\ 0& 0\end{array}\right],\hfill & P_{33}=\left[\begin{array}{cc}{p}_a& 0\\ 0& 0\end{array}\right],\hfill & P_{34}=\left[\begin{array}{c}{p}_b\\ 0\end{array}\right],\hfill \\ P_{40}=0,\hfill & P_{41}=0,\hfill & P_{42}=\left[00\right],\hfill & P_{43}=\left[00\right],\hfill & P_{44}=0,\hfill & P_{45}=p_b,\hfill \\ P_{50}=p_c,\hfill & P_{51}=p_a,\hfill & P_{52}=\left[00\right],\hfill & P_{53}=\left[00\right],\hfill & P_{54}=0,\hfill & P_{55}=0,\hfill \\ P_{0\Delta }=\left[000\right],\hfill & P_{1\Delta }=\left[000\right],\hfill & P_{2\Delta }=\left[\begin{array}{ccc}0& 0& 0\\ 0& 0& p_c\end{array}\right],\hfill & P_{3\Delta }=\left[\begin{array}{ccc}0& 0& 0\\ 0& p_a& p_c\end{array}\right],\hfill \\ P_{4\Delta }=\left[0p_a{p}_c\right],\hfill & P_{5\Delta }=\left[p_{b}00\right],\hfill & I_{\Delta }=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right].\hfill \end{array}\end{array}$$

That is, P is given by

$$\begin{array}{c}\hfill P=\left[\begin{array}{ccccccccccc}{p}_b+p_c& p_a& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ p_c& 0& p_a& p_b& 0& 0& 0& 0& 0& 0& 0\\ p_c& 0& 0& 0& p_a& p_b& 0& 0& 0& 0& 0\\ p_b& p_a& 0& 0& 0& 0& 0& 0& 0& 0& p_c\\ p_c& 0& 0& 0& p_a& 0& p_b& 0& 0& 0& 0\\ p_b& 0& 0& 0& 0& 0& 0& 0& 0& p_a& p_c\\ 0& 0& 0& 0& 0& 0& 0& p_b& 0& p_a& p_c\\ p_c& p_a& 0& 0& 0& 0& 0& 0& p_b& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1\end{array}\right].\end{array}$$

Let $\{(N_t,J_t),t=0,1,\dots \}$ be a two-dimensional discrete time Markov chain with the same state space $\mathcal{E}$ as that given in (3) and the same transition probability matrix P as that given in (4), but with an arbitrary initial state. Note that $\{(N_t,J_t),t=0,1,\dots \}$ is a finite $GI/M/1$-type Markov chain with a disaster. This disaster occurs when $N_t$ reaches $\Delta$.

4. Probability Generating Function of the Waiting Time

In this section, we derive an expression for (2). The analysis is based on the matrix analytic method. For more details, refer to Neuts [20,21] and Latouche and Ramaswami [22]. Let

$$\begin{array}{cc}\hfill {\tau }_n& =inf\{t\ge 1:N_t=n\},n=0,1,\dots ,l_1-1,\hfill \\ \hfill {\tau }_{\Delta }& =inf\{t\ge 1:N_t=\Delta \}.\hfill \end{array}$$

For $n=0,1,\dots ,l_1-2$, we define

$$\begin{array}{cc}\hfill {\left(G_n\left(z\right)\right)}_{ij}& =\mathbb{E}\left[z^{{\tau }_{n+1}}{\mathbb{1}}_{\{{\tau }_{n+1}<{\tau }_{\Delta },J_{{\tau }_{n+1}}=j\}}\mid (N_0,J_0)=(n,i)\right],\hfill \end{array}$$

which means the probability generating functions for the time of the first visit to state $(n+1,j)$, starting from state $(n,i)$ at time 0, before the first visit to level $\Delta$. Let $G_n\left(z\right)$ be the matrix of the probability generating functions whose $(i,j)$-component is ${\left(G_n\left(z\right)\right)}_{ij}$. Conditioning on the first transition, we have

$$\begin{array}{c}\hfill G_n\left(z\right)=z\left[P_{n,n+1}+\sum _{k=0}^n{P}_{nk}{G}_{k:n+1}\left(z\right)\right],0\le n\le l_1-2,\end{array}$$

(5)

where the $(i,j)$-component of $G_{k:n+1}\left(z\right)$ is

$$\begin{array}{c}\hfill {\left(G_{k:n+1}\left(z\right)\right)}_{ij}=\mathbb{E}\left[z^{{\tau }_{n+1}}{\mathbb{1}}_{\{{\tau }_{n+1}<{\tau }_{\Delta },J_{{\tau }_{n+1}}=j\}}\mid (N_0,J_0)=(k,i)\right],0\le k\le n\le l_1-2.\end{array}$$

Since

$$\begin{array}{cc}\hfill G_{n:n+1}\left(z\right)& =G_n\left(z\right),0\le n\le l_1-2,\hfill \\ \hfill G_{k:n+1}\left(z\right)& =G_k\left(z\right)G_{k+1:n+1}\left(z\right),0\le k<n\le l_1-2,\hfill \end{array}$$

we have

$$\begin{array}{c}\hfill G_{k:n+1}\left(z\right)=G_k\left(z\right)G_{k+1}\left(z\right)\cdots G_n\left(z\right),0\le k\le n\le l_1-2.\end{array}$$

(6)

Substituting (6) into (5), we obtain

$$G_n\left(z\right)=z\left[P_{n,n+1}+\sum _{k=0}^n{P}_{nk}{G}_k\left(z\right)G_{k+1}\left(z\right)\cdots G_n\left(z\right)\right],0\le n\le l_1-2.$$

(7)

Equation (7) can be interpreted as follows: Starting from level n, the Markov chain may visit level $n+1$ (while avoiding level $\Delta$) in two ways: it may move up to level $n+1$ at the very next transition (contributing the factor $z{P}_{n,n+1}$), or it may move to level k ($0\le k\le n$) at the first transition, move up from level k to level $k+1$, then from level $k+1$ to level $k+2$, and so on, until finally moving from level n to level $n+1$ (contributing the factor $z{\sum }_{k=0}^n{P}_{nk}{G}_k\left(z\right)G_{k+1}\left(z\right)\cdots G_n\left(z\right)$). From (7), we obtain

$$G_n\left(z\right)=z{\left[I_n-z\sum _{k=0}^n{P}_{nk}{G}_k\left(z\right)G_{k+1}\left(z\right)\cdots G_{n-1}\left(z\right)\right]}^{-1}{P}_{n,n+1},0\le n\le l_1-2,$$

(8)

where $I_n$ is the ${\mathcal{I}}_n\times {\mathcal{I}}_n$ identity matrix.

For $n=0,1,\dots ,l_1-1$, we define

$$\begin{array}{c}\hfill {\left(H_n\left(z\right)\right)}_{ij}=\left\{\begin{array}{cc}\mathbb{E}\left[z^{{\tau }_{\Delta }}{\mathbb{1}}_{\{{\tau }_{n+1}>{\tau }_{\Delta },J_{{\tau }_{\Delta }}=j\}}\mid (N_0,J_0)=(n,i)\right]\hfill & \mathrm{if}n=0,1,\dots ,l_1-2,\hfill \\ \mathbb{E}\left[z^{{\tau }_{\Delta }}{\mathbb{1}}_{\{J_{{\tau }_{\Delta }}=j\}}\mid (N_0,J_0)=(l_1-1,i)\right]\hfill & \mathrm{if}n=l_1-1,\hfill \end{array}\right.\end{array}$$

which means that ${\left(H_n\left(z\right)\right)}_{ij}$ ($n=0,1,\dots ,l_1-2$) is the probability generating function for the time of the first visit to state $(\Delta ,j)$, starting from state $(n,i)$, before the first visit to level $n+1$, and that ${\left(H_{l_1-1}\left(z\right)\right)}_{ij}$ is the probability generating function for the time of the first visit to state $(\Delta ,j)$, starting from state $(l_1-1,i)$. Let $H_n\left(z\right)$ be the matrix of the probability generating functions whose $(i,j)$-component is ${\left(H_n\left(z\right)\right)}_{ij}$. Conditioning on the first transition, we have

$$\begin{array}{c}\hfill H_n\left(z\right)=z\left[P_{n\Delta }+\sum _{k=0}^n{P}_{nk}{H}_{k:n+1}\left(z\right)\right],0\le n\le l_1-1,\end{array}$$

(9)

where the $(i,j)$-component of $H_{k:n+1}\left(z\right)$ ($0\le k\le n\le l_1-1$) is

$$\begin{array}{c}\hfill {\left(H_{k:n+1}\left(z\right)\right)}_{ij}=\left\{\begin{array}{cc}\mathbb{E}\left[z^{{\tau }_{\Delta }}{\mathbb{1}}_{\{{\tau }_{n+1}>{\tau }_{\Delta },J_{{\tau }_{\Delta }}=j\}}\mid (N_0,J_0)=(k,i)\right]\hfill & \mathrm{if}n=0,1,\dots ,l_1-2,\hfill \\ \mathbb{E}\left[z^{{\tau }_{\Delta }}{\mathbb{1}}_{\{J_{{\tau }_{\Delta }}=j\}}\mid (N_0,J_0)=(k,i)\right]\hfill & \mathrm{if}n=l_1-1.\hfill \end{array}\right.\end{array}$$

(10)

Since

$$\begin{array}{cc}\hfill H_{n:n+1}\left(z\right)& =H_n\left(z\right),0\le n\le l_1-1,\hfill \\ \hfill H_{k:n+1}\left(z\right)& =H_k\left(z\right)+G_k\left(z\right)H_{k+1}\left(z\right),0\le k<n\le l_1-1,\hfill \end{array}$$

we have

$$\begin{array}{c}\hfill H_{k:n+1}\left(z\right)=\sum _{k^{\prime }=k}^n{G}_k\left(z\right)\cdots G_{k^{\prime }-1}\left(z\right)H_{k^{\prime }}\left(z\right),0\le k\le n\le l_1-1.\end{array}$$

(11)

Substituting (11) into (9), we obtain

$$\begin{array}{c}\hfill H_n\left(z\right)=z\left[P_{n\Delta }+\sum _{k=0}^n{P}_{nk}\sum _{k^{\prime }=k}^n{G}_k\left(z\right)G_{k+1}\left(z\right)\cdots G_{k^{\prime }-1}\left(z\right)H_{k^{\prime }}\left(z\right)\right],0\le k\le n\le l_1-1,\end{array}$$

which can be written as

$$\begin{array}{cc}\hfill H_n\left(z\right)=& z\left[P_{n\Delta }+\sum _{k=0}^{n-1}{P}_{nk}\sum _{k^{\prime }=k}^{n-1}{G}_k\left(z\right)G_{k+1}\left(z\right)\cdots G_{k^{\prime }-1}\left(z\right)H_{k^{\prime }}\left(z\right)\right]\hfill \\ \hfill & +z\sum _{k=0}^n{P}_{nk}{G}_k\left(z\right)G_{k+1}\left(z\right)\cdots G_{n-1}\left(z\right)H_n\left(z\right),0\le k\le n\le l_1-1.\hfill \end{array}$$

From this equation, we obtain

$$\begin{array}{cc}\hfill H_n\left(z\right)=& z{\left[I_n-z\sum _{k=0}^n{P}_{nk}{G}_k\left(z\right)G_{k+1}\left(z\right)\cdots G_{n-1}\left(z\right)\right]}^{-1}\hfill \\ \hfill & \times \left[P_{n\Delta }+\sum _{k=0}^{n-1}{P}_{nk}\sum _{k^{\prime }=k}^{n-1}{G}_k\left(z\right)G_{k+1}\left(z\right)\cdots G_{k^{\prime }-1}\left(z\right)H_{k^{\prime }}\left(z\right)\right],0\le n\le l_1-1.\hfill \end{array}$$

(12)

Recall that ${\Psi }_j\left(z\right)=\mathbb{E}\left[z^W{\mathbb{1}}_{\{W={\tau }_{C_j}\}}\right]$, $j=1,\dots ,K$. Since

$$\begin{array}{c}\hfill \mathbb{P}(W=n,W={\tau }_{C_j})=\mathbb{P}(({\tau }_{\Delta },J_{{\tau }_{\Delta }})=(n,j)\mid (N_0,J_0)=(0,1)),\end{array}$$

we have

$$\begin{array}{c}\hfill {\Psi }_j\left(z\right)=\mathbb{E}\left[z^W{\mathbb{1}}_{\{W={\tau }_{C_j}\}}\right]=\mathbb{E}[z^{{\tau }_{\Delta }}{\mathbb{1}}_{\{J_{{\tau }_{\Delta }}=j\}}\mid (N_0,J_0)=(0,1)],j=1,\dots ,K,\end{array}$$

which means, by (10),

$$\begin{array}{c}\hfill {\Psi }_j\left(z\right)={\left(H_{0:l_1}\left(z\right)\right)}_{1j}.\end{array}$$

Therefore, by (11),

$$\begin{array}{c}\hfill ({\Psi }_1\left(z\right),\dots ,{\Psi }_K\left(z\right))=\sum _{k=0}^{l_1-1}{G}_0\left(z\right)G_1\left(z\right)\cdots G_{k-1}\left(z\right)H_k\left(z\right).\end{array}$$

In summary, we obtain the following theorem.

Theorem 1.

The probability generating functions of the sooner waiting time W on $\{W={\tau }_{C_j}\}$, ${\Psi }_j\left(z\right)=\mathbb{E}\left[z^W{\mathbb{1}}_{\{W={\tau }_{C_j}\}}\right]$, $j=1,\dots ,K$, are given by

$$\begin{array}{c}\hfill ({\Psi }_1\left(z\right),\dots ,{\Psi }_K\left(z\right))=\sum _{k=0}^{l_1-1}{G}_0\left(z\right)G_1\left(z\right)\cdots G_{k-1}\left(z\right)H_k\left(z\right),\end{array}$$

(13)

where $G_k\left(z\right)$, $k=0,1,\dots ,l_1-2$ and $H_k\left(z\right)$, $k=0,1,\dots ,l_1-1$ are given by (8) and (12), respectively.

From Theorem 1, we can obtain the following results.

Corollary 1.

(i) 

The stopping probabilities $\mathbb{P}(W={\tau }_{C_j}),j=1,\dots ,K$, are given by

$$\begin{array}{c}\hfill \mathbb{P}(W={\tau }_{C_j})={\Psi }_j\left(1\right).\end{array}$$

(ii) 

The conditional probability generating functions of W, given $W={\tau }_{C_j},j=1,\dots ,K$, are given by

$$\begin{array}{c}\hfill \mathbb{E}\left[z^W\right|W={\tau }_{C_j}]=\frac{{\Psi }_j\left(z\right)}{{\Psi }_j\left(1\right)}.\end{array}$$

(14)

(iii) 

The marginal probability generating function of W is given by

$$\begin{array}{c}\hfill \mathbb{E}\left[z^W\right]=\sum _{j=1}^K{\Psi }_j\left(z\right).\end{array}$$

(15)

Remark. As mentioned in Section 2, the conditional probability mass function $\mathbb{P}(W=n|W={\tau }_{C_j})$, $j=1,\dots ,K$ can be computed from (14) by a numerical inversion. In addition, the probability mass function $\mathbb{P}(W=n)$ can be computed from (15) by a numerical inversion. For the numerical inversion of probability generating functions, refer to Abate and Whitt [23].

By Theorem 1, we can also obtain the conditional/unconditional means of the sooner waiting time. To get this, we introduce

$$\begin{array}{cc}\hfill & {\mathcal{G}}_k=G_k\left(1\right),{\mathcal{G}}_k^{\left(1\right)}=\frac{d}{dz}{G}_k\left(z\right){|}_{z=1},k=0,1,\dots ,l_1-2,\hfill \\ \hfill & {\mathcal{H}}_k=H_k\left(1\right),{\mathcal{H}}_k^{\left(1\right)}=\frac{d}{dz}{H}_k\left(z\right){|}_{z=1},k=0,1,\dots ,l_1-1.\hfill \end{array}$$

Recall that ${\mathcal{W}}_j^{\left(1\right)}=\frac{d}{dz}{\Psi }_j\left(z\right){|}_{z=1}$, $j=1,\dots ,K$. By differentiating (13) with respect to z and evaluating at $z=1$, we have

$$({\mathcal{W}}_1^{\left(1\right)},\dots ,{\mathcal{W}}_K^{\left(1\right)})=\sum _{k=0}^{l_1-1}\left(\sum _{i=0}^{k-1}{\mathcal{G}}_0{\mathcal{G}}_1\cdots {\mathcal{G}}_{i-1}{\mathcal{G}}_i^{\left(1\right)}{\mathcal{G}}_{i+1}\cdots {\mathcal{G}}_{k-1}{\mathcal{H}}_k+{\mathcal{G}}_0{\mathcal{G}}_1\cdots {\mathcal{G}}_{k-1}{\mathcal{H}}_k^{\left(1\right)}\right).$$

(16)

Therefore, to obtain an expression for ${\mathcal{W}}_j^{\left(1\right)}$, $j=1,\dots ,K$, we need to determine ${\mathcal{G}}_k^{\left(1\right)}$, $k=0,1,\dots ,l_1-2$, and ${\mathcal{H}}_k^{\left(1\right)}$, $k=0,1,\dots ,l_1-1$. Equation (8) may be written as

$$\left[I_n-z\sum _{k=0}^n{P}_{nk}{G}_k\left(z\right)G_{k+1}\left(z\right)\cdots G_{n-1}\left(z\right)\right]G_n\left(z\right)=z{P}_{n,n+1},0\le n\le l_1-2,$$

from which

$$\begin{array}{cc}\hfill & \left[I_n-\sum _{k=0}^n{P}_{nk}{\mathcal{G}}_k\cdots {\mathcal{G}}_{n-1}\right]{\mathcal{G}}_n^{\left(1\right)}-\left[\sum _{k=0}^n{P}_{nk}{\mathcal{G}}_k\cdots {\mathcal{G}}_{n-1}+\sum _{k=0}^{n-1}{P}_{nk}\sum _{i=k}^{n-1}{\mathcal{G}}_k\cdots {\mathcal{G}}_i^{\left(1\right)}\cdots {\mathcal{G}}_{n-1}\right]{\mathcal{G}}_n\hfill \\ \hfill & =P_{n,n+1},0\le n\le l_1-2.\hfill \end{array}$$

Therefore, ${\mathcal{G}}_n^{\left(1\right)}$, $n=0,1,\dots ,l_1-2$ are obtained as follows:

$$\begin{array}{cc}\hfill {\mathcal{G}}_n^{\left(1\right)}=& {\left[I_n-\sum _{k=0}^n{P}_{nk}{\mathcal{G}}_k\cdots {\mathcal{G}}_{n-1}\right]}^{-1}\left[\sum _{k=0}^n{P}_{nk}{\mathcal{G}}_k\cdots {\mathcal{G}}_{n-1}+\sum _{k=0}^{n-1}{P}_{nk}\sum _{i=k}^{n-1}{\mathcal{G}}_k\cdots {\mathcal{G}}_i^{\left(1\right)}\cdots {\mathcal{G}}_{n-1}\right]{\mathcal{G}}_n\hfill \\ \hfill & +{\left[I_n-\sum _{k=0}^n{P}_{nk}{\mathcal{G}}_k\cdots {\mathcal{G}}_{n-1}\right]}^{-1}{P}_{n,n+1}.\hfill \end{array}$$

(17)

Similarly, we can obtain ${\mathcal{H}}_n^{\left(1\right)}$, $n=0,1,\dots ,l_1-1$, by using equation (12). Equation (12) may be written as

$$\begin{array}{cc}\hfill & \left[I_n-z\sum _{k=0}^n{P}_{nk}{G}_k\left(z\right)G_{k+1}\left(z\right)\cdots G_{n-1}\left(z\right)\right]H_n\left(z\right)\hfill \\ \hfill & =z\left[P_{n\Delta }+\sum _{k=0}^{n-1}{P}_{nk}\sum _{k^{\prime }=k}^{n-1}{G}_k\left(z\right)G_{k+1}\left(z\right)\cdots G_{k^{\prime }-1}\left(z\right)H_{k^{\prime }}\left(z\right)\right],0\le n\le l_1-1,\hfill \end{array}$$

from which

$$\begin{array}{cc}\hfill & \left[I_n-\sum _{k=0}^n{P}_{nk}{\mathcal{G}}_k\cdots {\mathcal{G}}_{n-1}\right]{\mathcal{H}}_n^{\left(1\right)}-\left[\sum _{k=0}^n{P}_{nk}{\mathcal{G}}_k\cdots {\mathcal{G}}_{n-1}+\sum _{k=0}^{n-1}{P}_{nk}\sum _{i=k}^{n-1}{\mathcal{G}}_k\cdots {\mathcal{G}}_i^{\left(1\right)}\cdots {\mathcal{G}}_{n-1}\right]{\mathcal{H}}_n\hfill \\ \hfill =& P_{n\Delta }+\sum _{k=0}^{n-1}{P}_{nk}\sum _{k^{\prime }=k}^{n-1}{\mathcal{G}}_k{\mathcal{G}}_{k+1}\cdots {\mathcal{G}}_{k^{\prime }-1}{\mathcal{H}}_{k^{\prime }}\hfill \\ \hfill & +\sum _{k=0}^{n-1}{P}_{nk}\sum _{k^{\prime }=k}^{n-1}\left(\sum _{i=k}^{k^{\prime }-1}{\mathcal{G}}_k\cdots {\mathcal{G}}_i^{\left(1\right)}\cdots {\mathcal{G}}_{k^{\prime }-1}{\mathcal{H}}_{k^{\prime }}+{\mathcal{G}}_k\cdots {\mathcal{G}}_{k^{\prime }-1}{\mathcal{H}}_{k^{\prime }}^{\left(1\right)}\right),0\le n\le l_1-1.\hfill \end{array}$$

Therefore, ${\mathcal{H}}_n^{\left(1\right)}$, $n=0,1,\dots ,l_1-1$ are obtained as follows:

$$\begin{array}{cc}\hfill {\mathcal{H}}_n^{\left(1\right)}=& {\left[I_n-\sum _{k=0}^n{P}_{nk}{\mathcal{G}}_k\cdots {\mathcal{G}}_{n-1}\right]}^{-1}\left[\sum _{k=0}^n{P}_{nk}{\mathcal{G}}_k\cdots {\mathcal{G}}_{n-1}+\sum _{k=0}^{n-1}{P}_{nk}\sum _{i=k}^{n-1}{\mathcal{G}}_k\cdots {\mathcal{G}}_i^{\left(1\right)}\cdots {\mathcal{G}}_{n-1}\right]{\mathcal{H}}_n\hfill \\ \hfill & +{\left[I_n-\sum _{k=0}^n{P}_{nk}{\mathcal{G}}_k\cdots {\mathcal{G}}_{n-1}\right]}^{-1}\{P_{n\Delta }+\sum _{k=0}^{n-1}{P}_{nk}\sum _{k^{\prime }=k}^{n-1}{\mathcal{G}}_k{\mathcal{G}}_{k+1}\cdots {\mathcal{G}}_{k^{\prime }-1}{\mathcal{H}}_{k^{\prime }}\hfill \\ \hfill & +\sum _{k=0}^{n-1}{P}_{nk}\sum _{k^{\prime }=k}^{n-1}\left(\sum _{i=k}^{k^{\prime }-1}{\mathcal{G}}_k\cdots {\mathcal{G}}_i^{\left(1\right)}\cdots {\mathcal{G}}_{k^{\prime }-1}{\mathcal{H}}_{k^{\prime }}+{\mathcal{G}}_k\cdots {\mathcal{G}}_{k^{\prime }-1}{\mathcal{H}}_{k^{\prime }}^{\left(1\right)}\right)\},0\le n\le l_1-1.\hfill \end{array}$$

(18)

Since ${\mathcal{W}}_j^{\left(1\right)}=\mathbb{E}\left[W{\mathbb{1}}_{\{W={\tau }_{C_j}\}}\right]$, $j=1,\dots ,K$, we can obtain the conditional mean waiting times $\mathbb{E}\left[W\right|W={\tau }_{C_j}]$, $j=1,\dots ,K$ from $\mathbb{E}\left[W\right|W={\tau }_{C_j}]=\frac{{\mathcal{W}}_j^{\left(1\right)}}{\mathbb{P}(W={\tau }_{C_j})}$. We can also obtain the unconditional mean waiting time $\mathbb{E}\left[W\right]$ from $\mathbb{E}\left[W\right]={\sum }_{j=1}^K{\mathcal{W}}_j^{\left(1\right)}$. From these two formulas and (16), we obtain the following theorem.

Theorem 2.

The conditional and unconditional means of the sooner waiting time W are given by, respectively,

$$\begin{array}{cc}\hfill & (\mathbb{E}\left[W\right|W={\tau }_{C_1}],\dots ,\mathbb{E}\left[W\right|W={\tau }_{C_K}])=\left(\frac{{\mathcal{W}}_1^{\left(1\right)}}{\mathbb{P}(W={\tau }_{C_1})},\dots ,\frac{{\mathcal{W}}_K^{\left(1\right)}}{\mathbb{P}(W={\tau }_{C_K})}\right),\hfill \\ \hfill & \mathbb{E}\left[W\right]=\sum _{j=1}^K{\mathcal{W}}_j^{\left(1\right)},\hfill \end{array}$$

where

$$\begin{array}{c}\hfill ({\mathcal{W}}_1^{\left(1\right)},\dots ,{\mathcal{W}}_K^{\left(1\right)})=\sum _{k=0}^{l_1-1}\left(\sum _{i=0}^{k-1}{\mathcal{G}}_0{\mathcal{G}}_1\cdots {\mathcal{G}}_{i-1}{\mathcal{G}}_i^{\left(1\right)}{\mathcal{G}}_{i+1}\cdots {\mathcal{G}}_{k-1}{\mathcal{H}}_k+{\mathcal{G}}_0{\mathcal{G}}_1\cdots {\mathcal{G}}_{k-1}{\mathcal{H}}_k^{\left(1\right)}\right),\end{array}$$

with ${\mathcal{G}}_k^{\left(1\right)}$, $k=0,1,\dots ,l_1-2$ and ${\mathcal{H}}_k^{\left(1\right)}$, $k=0,1,\dots ,l_1-1$ given by (17) and (18), respectively.

5. Numerical Examples

In this section, we present numerical results for the computations of the stopping probabilities, the probability mass functions (along with the tail probabilities) of the sooner waiting time, and the conditional/unconditional means of the sooner waiting time. To illustrate our results, we provide two examples.

Example 1.

Let $\{X_n,n\ge 1\}$ be a sequence of i.i.d. trials taking values in a finite set $A=\{a,b,c\}$. Assume that for $n=1,2,\dots$,

$$\begin{array}{c}\hfill p_a=\mathbb{P}(X_n=a)=\frac{1}{3},p_b=\mathbb{P}(X_n=b)=\frac{1}{3},p_c=\mathbb{P}(X_n=c)=\frac{1}{3}.\end{array}$$

Suppose that $K=10$, i.e., the collection $\mathcal{C}$ consists of 10 patterns, $\mathcal{C}=\{C_1,\dots ,C_{10}\}$. We select the collection of patterns $\{C_1,\dots ,C_{10}\}$ as shown in

Table 3. The patterns used in Example 1.

$C_1$	bbcabbccbacc
$C_2$	cbcbccbbb
$C_3$	cbbaacbcc
$C_4$	abaccba
$C_5$	bacabb
$C_6$	cbcab
$C_7$	acaab
$C_8$	caaca
$C_9$	aaca
$C_{10}$	aaac

, where the lengths of the patterns, $l_1,\dots ,l_{10}$, are chosen from the order statistics of i.i.d. random variables with mean 5. The set of patterns given in Table 3 is an example of a randomly selected pattern set such that one pattern is not a subpattern of another. The procedure of randomly selecting a one pattern set is omitted here.

By Theorem 1, we can compute $({\Psi }_1\left(z\right),\dots ,{\Psi }_K\left(z\right))$.

Table 4. The stopping probabilities $\mathbb{P}(W={\tau }_{C_j})$, $j=1,\dots ,10$ for Example 1.

j	$\mathbb{P}(\mathit{W}={\mathit{\tau }}_{{\mathit{C}}_{\mathit{j}}})$
1	$6.3509\times {10}^{-5}$
2	$1.7152\times {10}^{-3}$
3	$1.7152\times {10}^{-3}$
4	$1.4655\times {10}^{-2}$
5	$4.6715\times {10}^{-2}$
6	$1.3893\times {10}^{-1}$
7	$9.3671\times {10}^{-2}$
8	$1.2852\times {10}^{-1}$
9	$1.5249\times {10}^{-1}$
10	$4.2152\times {10}^{-1}$

shows the stopping probabilities

$$\mathbb{P}(W={\tau }_{C_j})={\Psi }_j\left(1\right),j=1,\dots ,10.$$

In Figure 1, we plot the joint probabilities $\mathbb{P}(W\ge n,W={\tau }_{C_j})$, $j=1,4,7,10$, with n varying. This can be computed by the numerical inversion of its generating function:

$$\begin{array}{cc}\hfill \sum _{n=1}^{\infty }\mathbb{P}(W\ge n,W={\tau }_{C_j})z^n& =\frac{z}{1-z}({\Psi }_j\left(1\right)-{\Psi }_j\left(z\right)).\hfill \end{array}$$

In

Table 5. The probability mass function $\mathbb{P}(W=n)$ and tail probability $\mathbb{P}(W\ge n)$ for Example 1.

n	$\mathbb{P}(\mathit{W}=\mathit{n})$	$\mathbb{P}(\mathit{W}\ge \mathit{n})$
5	$2.8807\times {10}^{-2}$	$9.7531\times {10}^{-1}$
10	$2.6300\times {10}^{-2}$	$8.3422\times {10}^{-1}$
15	$2.2424\times {10}^{-2}$	$7.1069\times {10}^{-1}$
20	$1.9103\times {10}^{-2}$	$6.0542\times {10}^{-1}$
30	$1.3863\times {10}^{-2}$	$4.3936\times {10}^{-1}$
40	$1.0060\times {10}^{-2}$	$3.1884\times {10}^{-1}$
50	$7.3009\times {10}^{-3}$	$2.3138\times {10}^{-1}$
60	$5.2983\times {10}^{-3}$	$1.6792\times {10}^{-1}$
70	$3.8450\times {10}^{-3}$	$1.2186\times {10}^{-1}$
80	$2.7903\times {10}^{-3}$	$8.8432\times {10}^{-2}$
90	$2.0249\times {10}^{-3}$	$6.4175\times {10}^{-2}$
100	$1.4695\times {10}^{-3}$	$4.6572\times {10}^{-2}$
200	$5.9533\times {10}^{-5}$	$1.8867\times {10}^{-3}$

, we present the probability mass function of W

$$\mathbb{P}(W=n)=\sum _{j=1}^{10}\mathbb{P}(W=n,W={\tau }_{C_j}),$$

and the tail probability of W

$$\mathbb{P}(W\ge n)=\sum _{j=1}^{10}\mathbb{P}(W\ge n,W={\tau }_{C_j}),$$

with n varying. Here, $\mathbb{P}(W=n,W={\tau }_{C_j})$ can be computed by the numerical inversion of its generating function:

$$\begin{array}{cc}\hfill \sum _{n=1}^{\infty }\mathbb{P}(W=n,W={\tau }_{C_j})z^n& ={\Psi }_j\left(z\right).\hfill \end{array}$$

By Theorem 2, we can compute the conditional mean of the sooner waiting time W, $\mathbb{E}\left[W\right|W={\tau }_{C_j}]$, $j=1,\dots ,K$, and the unconditional mean of W, $\mathbb{E}\left[W\right]$.

Table 6. The conditional mean $\mathbb{E}\left[W\right|W={\tau }_{C_j}]$, $j=1,\dots ,10$ and unconditional mean $\mathbb{E}\left[W\right]$ for Example 1.

(a) $\mathbb{E}\left[\mathit{W}\right|\mathit{W}={\mathit{\tau }}_{{\mathit{C}}_{\mathit{j}}}]$
j	$\mathbb{E}\left[W\right|W={\tau }_{C_j}]$
1	41.7543
2	40.0476
3	40.0476
4	40.6783
5	41.0372
6	36.3888
7	35.0704
8	35.6263
9	29.7715
10	31.4236
(b)$\mathbb{E}\left[\mathbf{W}\right]$
$\mathbb{E}\left[W\right]$	33.3582

shows the conditional and unconditional mean waiting times for Example 1.

The next example will be for the Bernoulli trials.

Example 2.

Let $\{X_n,n\ge 1\}$ be a sequence of i.i.d. Bernoulli trials, i.e., $\{X_n,n\ge 1\}$ takes values in a finite set $A=\{0,1\}$. Assume that for $n=1,2,\dots$,

$$\begin{array}{c}\hfill p_0=\mathbb{P}(X_n=0)=\frac{1}{2},p_1=\mathbb{P}(X_n=1)=\frac{1}{2}.\end{array}$$

Suppose that the collection $\mathcal{C}$ consists of 5 patterns, $\mathcal{C}=\{C_1,\dots ,C_5\}$, where

$$\begin{array}{cc}\hfill C_1& =1111111111111111,\hfill \\ \hfill C_2& =0101010101010101,\hfill \\ \hfill C_3& =001001001001,\hfill \\ \hfill C_4& =00010001,\hfill \\ \hfill C_5& =0000.\hfill \end{array}$$

For Example 2, the joint probabilities $\mathbb{P}(W\ge n,W={\tau }_{C_j})$, $j=1,\dots ,5$ are shown in Figure 2. Also, the stopping probabilities $\mathbb{P}(W={\tau }_{C_j})$, $j=1,\dots ,5$, the probability mass function of W (along with the tail probability) and the conditional/unconditional means of W are shown in

Table 7. The stopping probabilities $\mathbb{P}(W={\tau }_{C_j})$, $j=1,\dots ,5$ for Example 2.

j	$\mathbb{P}(\mathit{W}={\mathit{\tau }}_{{\mathit{C}}_{\mathit{j}}})$
1	$2.1412\times {10}^{-4}$
2	$2.9831\times {10}^{-4}$
3	$4.7235\times {10}^{-3}$
4	$5.5265\times {10}^{-2}$
5	$9.3950\times {10}^{-1}$

,

Table 8. The probability mass function $\mathbb{P}(W=n)$ and tail probability $\mathbb{P}(W\ge n)$ for Example 2.

n	$\mathbb{P}(\mathit{W}=\mathit{n})$	$\mathbb{P}(\mathit{W}\ge \mathit{n})$
5	$3.1250\times {10}^{-2}$	$9.3750\times {10}^{-1}$
10	$3.0273\times {10}^{-2}$	$7.7734\times {10}^{-1}$
15	$2.4963\times {10}^{-2}$	$6.3660\times {10}^{-1}$
20	$2.0452\times {10}^{-2}$	$5.2110\times {10}^{-1}$
30	$1.3705\times {10}^{-2}$	$3.4916\times {10}^{-1}$
40	$9.1827\times {10}^{-3}$	$2.3396\times {10}^{-1}$
60	$6.1528\times {10}^{-3}$	$1.5676\times {10}^{-1}$
70	$4.1227\times {10}^{-3}$	$1.0504\times {10}^{-1}$
80	$2.7624\times {10}^{-3}$	$7.0380\times {10}^{-2}$
90	$1.8509\times {10}^{-3}$	$4.7158\times {10}^{-2}$
50	$1.2402\times {10}^{-3}$	$3.1598\times {10}^{-2}$
100	$8.3100\times {10}^{-4}$	$2.1172\times {10}^{-2}$
200	$1.5158\times {10}^{-5}$	$3.8620\times {10}^{-4}$

and

Table 9. The conditional mean $\mathbb{E}\left[W\right|W={\tau }_{C_j}]$, $j=1,\dots ,5$ and unconditional mean $\mathbb{E}\left[W\right]$ for Example 2.

(a) $\mathbb{E}\left[\mathit{W}\right|\mathit{W}={\mathit{\tau }}_{{\mathit{C}}_{\mathit{j}}}]$
j	$\mathbb{E}\left[W\right|W={\tau }_{C_j}]$
1	38.6231
2	38.7707
3	36.8873
4	37.4396
5	26.7334
(b)$\mathbb{E}\left[\mathbf{W}\right]$
$\mathbb{E}\left[W\right]$	27.3792

, respectively.

6. Conclusions

We have derived the probability generating function of the sooner waiting time for a finite collection of patterns in a sequence of i.i.d. multi-state trials. From this probability generating function we have obtained the stopping probabilities and the mean waiting time, but it also has enabled us to compute the waiting time distribution by a numerical inversion. As mentioned in the introduction, our method can be extended to Markov dependent multi-state trials.

For further research, we will investigate the tail asymptotics for the sooner waiting time W. From Figure 1 and Figure 2, we can expect that the distribution of W has a geometric tail behavior. This is true under certain aperiodic condition because W is the first passage time to a subset of the state space, in a discrete time Markov chain with a finite state space. Under some assumptions about periodicity, the distribution of W exhibits a geometric tail behavior, i.e.,

$$\begin{array}{c}\hfill \mathbb{P}(W\ge n)\sim c{\sigma }^{n}asn\to \infty \end{array}$$

for some $c>0$ and $\sigma \in (0,1)$. Here “∼" means that the limit of the ratio is 1. It would be of interest to find explicit expressions for c and $\sigma$. We also have the following geometric tail behavior:

$$\begin{array}{c}\hfill \mathbb{P}(W\ge n,W={\tau }_{C_i})\sim c_i{\sigma }^{n}asn\to \infty \end{array}$$

for some $c_i>0$ and $\sigma \in (0,1)$. Here $\sigma$ is independent of i and is the same as that described above. It would also be of interest to find explicit expressions for $c_i$, $i=1,\dots ,K$.