Identifying a word (pattern) in a long sequence of letters is not an easy task. To achieve this objective, several models have been proposed under the assumption that the sequence of letters is described by a Markov chain. The Markovian hypothesis imposes restrictions on the distribution of the sojourn time in a state, which has geometric distribution in a discrete process. This is the main drawback when applying Markov chains to real problems. By contrast, semi-Markov processes are generalized. In semi-Markov processes, the sojourn time in a state can be governed by any distribution function. The goal of this article is to compute the first hitting time (position) of a word (pattern) in a semi-Markov sequence. To achieve this objective, we use the auxiliary prefix and backward chain. To give an example of the applications of the proposed model, the model is tested in a bacteriophage DNA sequence that is lacking the enzyme SmaI. We compute the probability that a word occurs for the first time after n nucleotides in a DNA sequence. The corresponding probability distribution, the mean waiting position, the variance, and rate of the occurrence of the word are obtained.
1. Introduction
Genome sequencing is often compared with a code ruled by four nitrogenous bases: adenine (A), cytosine (C), thymine (T), and guanine (G). Given a genome sequence, it is interesting to recognize a word (pattern), counting the number of or determining the first position that this appears (Hebert et al., 2003; Robin et al., 2007; Abadi and Vergene, 2008; Li et al., 2016, 2018; Sigwart and Garbett, 2018). This word could be, for example, responsible for the production of a particular protein, a genetic disorder, a specific malformation, or could be useful to detect similar (or dissimilar) genes in different organisms.
Looking for a word by simple inspection, over a sequence of millions of letters, is a very cumbersome job. There are a number of models and algorithms that propose an automatic treatment (Aboluion, 2011; Stefanov et al., 2011; Picard et al., 2011; Den Hollander, 2013; Montemanni, 2015; Srivastava and Baptista, 2016; Codish et al., 2017). Nevertheless, model DNA sequences with mathematical tools are challenged questions for mathematicians and biologists.
The efficiency and precision of such automatic treatments depend mostly on the kind of dependency between nucleotides, for example, identically distributed random variables, Markov or semi-Markov chains (SMCs), etc. In the literature, a variety of methods have been suggested for treating this problem under the hypothesis that the sequence is described by independently and identically distributed random variables (Stefanov and Pakes, 1997; Robin and Daudin, 1999; Chadjiconstantinidis et al., 2000). Nevertheless, more complex models have been proposed considering that the sequence is described by a Markov chain (Fu and Koutras, 1994; Antzoulakos, 2001; Fu and Chang, 2002; Crochemore and Stefanov, 2003; Glaz et al., 2006; Nuel, 2008; Touyar et al., 2008). Even if Markov processes model better DNA sequences than Bernoulli trials, they have some issues. The main drawback of models based on the Markov hypothesis is that they cannot take into account general distributions in the sojourn time in a state. Discrete-time semi-Markov processes generalize discrete-time Markov chains. In semi-Markov processes, the distribution function of the sojourn time in a state can be any one; see, e.g., Limnios and Oprişan (2001) and Mode and Pickens (1998).
Chryssaphinou et al. (2008) proposed a model to find a pattern in a semi-Markov sequence by using as state space all the words of the same size as the searched word and the backward times for each word. Using Chryssaphinou's model, if we consider that DNA sequences are taken from the set of nucleics \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A} = \{ A , T , G , C \} $$
\end{document} and they are formed at least by thousands of them, let us denote by M this number; therefore, to find a word of size h we need \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\vert { \cal A}{ \vert ^h} \times { \rm{ }} ( M - h )$$
\end{document} elements in the state space. This method requires a very large memory and except small examples it cannot be used in real problems. To prove the model proposed here can be implemented in real DNA sequences, in the last part of the article, it is tested in a bacteriophage DNA sequence.
Finding a specific pattern in a sequence of symbols is useful in many areas. For instance, in databases it could be the keyword for certain research; in biology, it can make reference to a particular illness, enzyme, or protein; in communication, it could be a precise word during a conversation, etc. The model and algorithm proposed here can be applied in all these areas due to them holding true in any irreducible SMC with finite state space. In this article, we focus on determining the probability law of the random variable that counts the number of nucleotides we need to pass before finding for the first time a specific word in the genomic sequence considering that the DNA is modeled by a irreducible SMC.
To obtain a more efficient algorithm under the semi-Markovian hypothesis, we use the prefixes chain. Suppose we search the word (pattern) w = ACCT in a DNA sequence. We construct the word step by step from its first symbol to its last one. The elements of this construction are called prefixes, that is, consider the following DNA sequence from a bacteriophage: GGGCGGCGACCTCGCGGGTTTTCGCTATTTATGAAAATTTTCCGGTTTAAGGCGTTTCCTTCTTCTTCGTCATAACTTAATGTTTTTATTTAAAATACCCTCTGAAAAGAAAGGAAAG… and suppose we want to compute the first position of w = ACCT, that is, we want to compute how many nucleotides have to appear in the DNA before w. To do this, we use the prefixes of w, which is the set {A, AC, ACC, ACCT}, (more details about prefixes will be given in Section 2). For this example, it is clear that the first appearance of w occurs at position (starting from 0) 11. Using the chain of the longest prefix of the word and all possible backward times for each prefix, the distribution for the (first) hitting position of the word in a sequence of letters is computed. To show the applicability of our proposed model, we test it in a bacteriophage DNA sequence. We present the distribution function, the expected value, the variance, and the standard deviation of the random variable that represents the (first) hitting position of the word. The word occurrence rate is also presented.
The article is organized as follows: In Section 2, we introduce the prefixes chain. In Section 3, we present the semi-Markov setting. In Section 4, we introduce the (first) hitting position of the word. In Section 5, we present a genomic application. In Section 6, we present some concluding remarks.
2. The Prefix Chain
Let us consider a finite alphabet, say \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A} = \{ {a_1} , \; \ldots , \;{a_l} \} $$
\end{document}, 2 ≤ l < ∞. A word of length \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$h \in { \mathbb{N}^*}: = \{ 1 , \;2 , \; \ldots \} $$
\end{document} is an element of the Cartesian product \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${{ \cal A}^h}$$
\end{document}, that is, (w1, …, wh). Following the notation of Lothaire (1983), this word will be denoted as w : = w1w2⋯wh whereas its length will be expressed by |w| and represents the number of symbols of the word, in this case |w| = h. We will consider the set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\mathbb{N} = \{ 0 , \;1 , \; \ldots \} $$
\end{document} as the set of natural numbers.
Based on the structure of w, we shall define its prefix set. The prefix set is denoted by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\tilde E$$
\end{document} and is the set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\tilde E = \{ \varepsilon , \;{w_1} , \;{w_1}{w_2} , \; \ldots , \;{w_1}{w_2} \cdots {w_{h - 1}} , \;w \} $$
\end{document}, where symbol ɛ denotes the empty prefix that is used in case none of the symbols \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\{ {w_1} , \;{w_1}{w_2} , \; \ldots , \;{w_1}{w_2} \cdots {w_{h - 1}} , \;w \} $$
\end{document} appears in the sequence. Observe that |ɛ| = 0.
Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\delta : \tilde E \times { \cal A} \to \tilde E$$
\end{document} be a mapping such that for a prefix q∈\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\tilde E$$
\end{document} and a letter \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$a \; \in \;{ \cal A}$$
\end{document}, δ(q, a) is defined as the longest suffix of qa (concatenation of q and a) in the prefix set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\tilde E$$
\end{document}. To clarify this definition, observe the follow examples.
Example 1.If\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A} = \{ a , \;b \} $$
\end{document}, w = ba, the prefix set is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\tilde E$$
\end{document} = {ɛ, b, ba}, then\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\begin{matrix}{ \delta ( \varepsilon , \;a ) = \varepsilon , } \hfill & { \delta ( \varepsilon , \;b ) = b , } \hfill \\ { \delta ( b , \;a ) = ba , } \hfill & { \delta ( b , \;b ) = b , } \hfill \\ { \delta ( ba , \;a ) = \varepsilon , } \hfill & { \delta ( ba , \;b ) = b , } \hfill \\\end{matrix}
\end{align*}
\end{document}
Example 2.Suppose we add one letter to the alphabet and we search the same word as in Example 1, that is, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A} = \{ a , \;b , \;c \} $$
\end{document}and w = ba. The prefix set does not change \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\tilde E$$
\end{document} = {ɛ, b, ba} due to w being the same; nevertheless, the results for δ are different due to the alphabet having one letter more. The results for δ are:\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\begin{matrix}{ \delta ( \varepsilon , \;a ) = \varepsilon , } \hfill & { \delta ( \varepsilon , \;b ) = b , } \hfill & { \delta ( \varepsilon , \;c ) = \varepsilon , } \hfill \\ { \delta ( b , \;a ) = ba , } \hfill & { \delta ( b , \;b ) = b , } \hfill & { \delta ( b , \;c ) = \varepsilon , } \hfill \\ { \delta ( ba , \;a ) = \varepsilon , } \hfill & { \delta ( ba , \;b ) = b , } \hfill & { \delta ( ba , \;c ) = \varepsilon .} \hfill \\ \end{matrix}
\end{align*}
\end{document}
Observe that, for p ∈\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\tilde E$$
\end{document} the set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\{ i \; \in \;{ \cal A}: \delta ( p , \;i ) = \varepsilon \} $$
\end{document} has more than one element if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\vert { \cal A} \vert > 2$$
\end{document}. Therefore, δ(p, i) is not a one-to-one mapping in general. According to Nicodeme et al. (2002), new elements can be added to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\tilde E$$
\end{document} such that δ(p, i) becomes a one-to-one mapping for p fixed. If p and q are two prefixes such that q is different from prefix ɛ, that is, q = w1w2, …, wl for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${w_1} , \;{w_2} , \; \cdots , \;{w_l} \; \in \;{ \cal A}$$
\end{document} where 1 ≤ l ≤ h and, if there is some \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i \in { \cal A}$$
\end{document} such that δ(p, i) = q, therefore i is the last letter of q, that is, i = wl for this reason for p fixed only when δ results in ɛ, that is, δ(p, i) = ɛ, the function δ is not one to one. The empty prefix ɛ will be labeled according to the letter that is added to p to obtain ɛ, which means, instead of writing
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\delta ( p , \;i ) = \varepsilon ,
\end{align*}
\end{document}
it will be written
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\delta ( p , \;i ) = { \varepsilon _i}.
\end{align*}
\end{document}
be the extended state space of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\tilde E$$
\end{document} in which for p∈E and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i \in { \cal A}$$
\end{document}, δ(p, i) is now a one-to-one mapping. The previous definition of δ can be extended as follows, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\delta :E \times { \cal A} \to E$$
\end{document}. Henceforth, this last definition will be considered.
The partial inverse of δ is defined by the function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \delta ^{ - 1}}:E \to { \cal A}$$
\end{document} in the following way:
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{ \delta ^{ - 1}} ( q ) = i \in { \cal A} \ { \rm{where}} \;{ \rm{there}} \;{ \rm{exist}} \;{ \rm{a }}p \in E \;{ \rm{such}} \;{ \rm{that}} \; \delta ( p , \;i ) = q. \tag{2}
\end{align*}
\end{document}
Note that over E the partial inverse is one-to-one mapping. Roughly speaking, the partial inverse of prefix q gives the last letter of q, that is, if q = ba, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \delta ^{ - 1}} ( q ) = a$$
\end{document}.
The general idea of the model is to compute the first position of the word by using the prefix process. The transition probability between prefixes depends on the semi-Markov kernel of letters. In the next section, we shall give the semi-Markov setting and its relation between prefixes and the sequence of letters.
3. The Semi-Markov Setting
Let us consider a complete probability space \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( \Omega , \; \mathcal{F} , \; \mathbb{P} )$$
\end{document}, on which we define all processes and random variables. Let (Zk) be an irreducible SMC with state space \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A}$$
\end{document}, and (Jn, Sn) its embedded Markov renewal chain (Barbu et al., 2004), where S0 : = 0, and
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{S_{n + 1}}: = { \rm{inf}} \{ k > {S_n}:{Z_k} \ne {Z_{{S_n}}} \} , \;n \ge 0 ,
\end{align*}
\end{document}
with the convention \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \rm{inf }}\ \O { \rm{ = + }} \infty$$
\end{document}, that is, process (Sn) are the successive points when a state changes in (Zk), called renewal points or jump points of process (Zk). Process \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ ( {J_n} ) _{n \in \mathbb{N}}}$$
\end{document} is the embedded Markov chain, the chain that records (Zk) at points (Sn), that is, Jn = ZSn. Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ ( {X_n} ) _{n \in \mathbb{N}}}$$
\end{document} be the successive sojourn times in the visited states. By convention, X0 : = S0 : = 0 and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${X_{n + 1}}: = {S_{n + 1}} - {S_n}$$
\end{document}, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$n \in \mathbb{N}$$
\end{document}. Let i, j be two elements of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A}$$
\end{document}; then, the semi-Markov kernel of (Zk) is defined as follows:
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{q_{ij}} ( k ) : = \mathbb{P} ( {J_{n + 1}} = j , \;{S_{n + 1}} - {S_n} = k \mid {J_n} = i ) , \quad n \ge 0 , \;k \in \mathbb{N}. \tag{3}
\end{align*}
\end{document}
The cumulative semi-Markov kernel is defined by
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{Q_{ij}} ( k ) : = \mathbb{P} ( {J_{n + 1}} , \;{X_{n + 1}} \le k \mid {J_n} = i ) = \sum \limits_{l = 0}^k {{q_{ij}}} ( l ) , \quad i , \;j \in { \cal A} , \;k \in \mathbb{N}.
\end{align*}
\end{document}
It is worth noticing that the semi-Markov kernel considered here is independent of n, which means that the SMC is homogeneous in time. Also observe that we use index \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$k \in \mathbb{N}$$
\end{document} for the calendar points, and index \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$n \in \mathbb{N}$$
\end{document} for the number of jumps of (Zk). If semi-Markov kernel is time homogeneous, then (Jn) is a homogeneous Markov chain. We denote by pij, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i , \;j \in { \cal A}$$
\end{document} its transition probability
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{p_{ij}}: = \mathbb{P} ( {J_{n + 1}} = j \mid {J_n} = i ) , \quad i , j \in { \cal A} , \quad n \in \mathbb{N}.
\end{align*}
\end{document}
Note that pij can be expressed in terms of the semi-Markov kernel by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${p_{ij}} = \sum \nolimits_{k = 0}^ \infty {{q_{ij}}} ( k )$$
\end{document}.
The cumulative distribution function of sojourn time in state \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i \in { \cal A}$$
\end{document} is
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{H_i} ( k ) : = \sum \limits_{l = 0}^k { \sum \limits_{j \in { \cal A}} {{q_{ij}}} } ( l ) .
\end{align*}
\end{document}
The conditional cumulative distribution of the waiting time Xn+ 1, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$n \in \mathbb{N}$$
\end{document}, is
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{F_{ij}} ( k ) : = \mathbb{P} ( {X_{n + 1}} \le k \mid {J_n} = i , \;{J_{n + 1}} = j ) = \left\{ { \begin{matrix}{{{{Q_{ij}} ( k ) } \over {{p_{ij}}}} , } \hfill & {{ \rm{if}} \;{{ \rm{p}}_{{ \rm{ij}}}} \ne { \rm{0}} , } \hfill \\ {1 , } \hfill & {{ \rm{if}} \;{{ \rm{p}}_{{ \rm{ij}}}}{ \rm{ = 0}}.} \hfill \\\end{matrix} } \right. \tag{4}
\end{align*}
\end{document}
The main difference between Markov and semi-Markov discrete-time processes is the distribution function Fij(k). In a Markov chain, this function has to be geometric with parameter \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$1 - P ( i , \;i )$$
\end{document}, where P is the transition probability matrix; on the other hand, in the semi-Markov process, the distribution function Fij(k) can be any type.
For \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i \in { \cal A}$$
\end{document}, we shall denote the maximum sojourn time in state \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i \in { \cal A}$$
\end{document} as
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{r_i}: = { \rm{sup}} \{ k \ge 0: \sum \limits_{j \in { \cal A}} {{q_{ij}}} ( k ) \ne 0 \} . \tag{5}
\end{align*}
\end{document}
Now, let (Uk) be the backward recurrence times for the SMC (Zk), defined by
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{U_k}: = k - { \rm{max}} \{ {S_m}:{S_m} \le k \} \quad and \quad {U_k}: = k \quad if \quad {S_1} > k. \tag{6}
\end{align*}
\end{document}
Example 3.If Z: aaabba… is a sample of (Zk), its backward recurrence time (Uk) is:
U0 = 0, U1 = 1, U2 = 2, U3 = 0, U4 = 1, U5 = 0, …
In essence, the backward time at position k is the number of steps spent in state Zk since the last jump. Notice that if k coincides with a renewal point, the value of Uk is 0. After a renewal point, Uk grows one by one until another renewal point, and so on.
If ri is the maximum sojourn time in state i, Equation (5), then the maximum value for the backward time in state \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i \in { \cal A}$$
\end{document}, is
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{l_i}: = {r_i} - 1. \tag{7}
\end{align*}
\end{document}
While considering the problem: Compute the first hitting position of a word (pattern) in a biological sequence. The sequence represents the semi-Markov process (Zk); the state space \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A}$$
\end{document} is the genomic alphabet: adenine (A), cytosine (C), thymine (T), and guanine (G); and the maximum sojourn time in a state \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i \in { \cal A}$$
\end{document} represents the maximal number of nucleotides that can be found together through the DNA sequence. The general idea is computing the first hitting position of the word by using the prefix process. In the sequel of this section, we shall define the embedded prefix chain in the semi-Markov process.
Let us consider a stochastic process \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ ( {Z_k} ) _{k \in \mathbb{N}}}$$
\end{document} that models a sequence of letters taken from a finite alphabet \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A}$$
\end{document}. If w is a word from \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A}$$
\end{document}, the embedded prefix chain is defined as follows (Crochemore and Stefanov, 2003).
Definition 1.The prefix chain of w = w1, …, wh defined in E, where E is the extended prefix set, Equation (1), is denoted by\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$Y: = { ( {Y_k} ) _{k \in \mathbb{N}}}$$
\end{document}where\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{Y_0}: = \{ \begin{matrix}{{w_1}} \hfill & {{ \rm{if}} \;{Z_0} = {w_1} , } \hfill \\ {{ \varepsilon _a}} \hfill & {{ \rm{if}} \;{Z_0} = a \;{ \rm{with}} \;a \ne {w_1} , } \hfill \\ \end{matrix}
\end{align*}
\end{document}
Example 4.If the alphabet is\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A} = \{ a , \;b , \;c \} $$
\end{document}and the word is w = ba then, if the elements of the prefix set E are listed as follows E = {ɛa = 0, ɛc = 1, b = 2, ba = 3}. For the following sample\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
Z:aaaccba \ldots
\end{align*}
\end{document}
we have as result
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
Y:0001123 \ldots
\end{align*}
\end{document}
The number of positions we have to wait for an occurrence of w in (Zk) corresponds to the number of positions that we have to wait for an occurrence of w in (Yk) (Nuel, 2008).
Let (Yk, Uk) be the process of prefixes and backward time. To define the state space of (Yk, Uk), let us introduce the blocks of the word. If \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w = \underbrace {i \cdots i}_h$$
\end{document}, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i \in { \cal A}$$
\end{document} and, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$h \in { \mathbb{N}^*}$$
\end{document}, we shall say that w is a block of i′s of length h and it will be denoted by
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
w = {i^{ ( h ) }} , { \rm{ }}i \in { \cal A} , \quad h \in \mathbb{N} , { \rm{ }}1 \le h < \infty .
\end{align*}
\end{document}
If w is not a block, it can be obtained by concatenating words that are blocks (Karaliopoulou, 2009). That is, w can be expressed as
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
w = w ( 1 ) w ( 2 ) \cdots w ( \eta ) , \tag{8}
\end{align*}
\end{document}
where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( 1 ) = {i_1}^{ ( {n_1} ) } , \;w ( 2 ) = {i_2}^{ ( {n_2} ) }$$
\end{document}, …,\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( \eta ) = {i_ \eta }^{ ( {n_ \eta } ) }$$
\end{document}, for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${i_1} , \;{i_2} , \; \ldots , \;{i_ \eta } \in { \cal A}$$
\end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${n_1} , \;{n_2} , \; \ldots , \;{n_ \eta } \in { \mathbb{N}^*}$$
\end{document}, such that n1 + n2 + … + nη = |w|. Noticing that a prefix is also a word, therefore it can be represented by the concatenation of blocks.
We shall define the backward position time of a prefix \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$p = {w_1}{w_2} \cdots {w_{l - 1}}{w_l}$$
\end{document} for 1 ≤ l ≤ h, as the size of its last block −1. This definition comes from the time (the number of positions) we have stayed in the last letter of the prefix since the last jump (renewal point). Notice that, in general the backward time of a prefix is different from the backward time Uk of the letters. The backward time of a prefix will be denoted by U(p).
Example 5.Let w = bbaab be a word from the alphabet\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A} = \{ a , \;b \} $$
\end{document}, and let p = bba be a prefix of w. Then, it is clear that the backward time of p is U(p) = 0.
Now, we are ready to introduce the backward times for each prefix through the semi-Markov process. Let lp, be the set of backward times that correspond to prefix p. If \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i \in { \cal A}$$
\end{document} is the partial inverse of p, that is, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i = { \delta ^{ - 1}} ( p )$$
\end{document}, Equation (2), and n1 is the size of the first block of w, Equation (8), then
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{l_p} = \left\{ { \begin{matrix}{ \left[ \kern- 0.15em \left[ {0 , \;{l_i}} \right] \kern- 0.15em \right] , } \hfill & {{ \rm{if}} \; \vert p \vert = 0 , } \hfill \\ { \{ U \; ( p ) \} , } \hfill & {{ \rm{if}} \; \vert p \vert \ne {n_1} \ { \rm{ and}} \ \vert p \vert \ne 0 , } \hfill \\ { \left[ \kern- 0.15em \left[ {U \; \left( p \right) , \;{l_i}} \right] \kern- 0.15em \right] , } \hfill & {{ \rm{if}} \; \vert p \vert = {n_1}.} \hfill \\ \end{matrix} } \right. \tag{9}
\end{align*}
\end{document}
be the set that represents the prefix p and its backward times, by consequence the set
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
K: = \bigcup \limits_{p \in E} {{K_p}} \tag{11}
\end{align*}
\end{document}
represents all prefixes and their corresponding backward times. Clearly we have: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${K_p} \; \cap \;{K_q} = \O$$
\end{document}, if p ≠ q. The set K is the state space of process (Yk, Uk). Algorithm 1 proposed here (Section 7) provides the state space K.
Proposition 1.The process\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ ( {Y_k} , \;{U_k} ) _{k \in \mathbb{N}}}$$
\end{document}is a Markov chain with state space K. Let us consider p ∈E,\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i = { \delta ^{ - 1}} ( p )$$
\end{document}and\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\alpha ( i ) = \mathbb{P} ( {Z_0} = i )$$
\end{document}, where\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i \in { \cal A}$$
\end{document}and 1{A}is the indicator function of A. Then, the initial distribution of the process (Yk, Uk) is\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\mathbb{P} ( {Y_0} = p , \;{U_0} = u ) = \left\{ { \begin{matrix}{ \alpha ( {w_1} ) { \rm{ }}{1_{ \{ u = 0 \} }}} \hfill & {if \;p { \rm{ = }}{w_{ \rm{1}}} , } \hfill \\ { \alpha ( i ) { \rm{ }}{1_{ \{ u = 0 \} }}} \hfill & {if \;p { \rm{ = }}{ \varepsilon _i} , \;i \in { \cal A} \setminus \{ {w_{ \rm{1}}} \} , } \hfill \\ 0 \hfill & {otherwise , } \hfill \\ \end{matrix} } \right.
\end{align*}
\end{document}
and its transition probabilities are\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\mathbb{P} ( {Y_{k + 1}} = q , \;{U_{k + 1}} = v \mid {Y_k} = p , \;{U_k} = u ) = \left\{ { \begin{matrix}{{{{q_{ia}} ( u + 1 ) } \over {1 - {H_i} ( u ) }}{ \rm{ }}{1_{ \{ \delta ( p , a ) = q \} }}} \hfill & {{ \rm{if}} \; \quad i \ne a , \quad v = 0 , } \hfill \\ {{{1 - {H_i} ( u + 1 ) } \over {1 - {H_i} ( u ) }}{1_{ \{ \delta ( p , a ) = q \} }}} \hfill & {{ \rm{if}} \quad \;i = a , \quad v = u + 1 , } \hfill \\ 0 \hfill & {{ \rm{otherwise}}.} \hfill \\ \end{matrix} } \right. \tag{12}
\end{align*}
\end{document}
Proof. The initial distribution comes from the definition of Y0, Definition 1, and the backward position time at starting time, Equation (6). We shall use here the fact that (Zk, Uk) is a Markov chain with known transition probability (Barbu and Limnios, 2008). Let p ∈E be a prefix and suppose that there exists \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$a \in { \cal A}$$
\end{document} such that δ(p, a) = q, for some q∈E. If \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$p = {w_1}{w_2} \cdots {w_{l - 1}}{w_l}$$
\end{document} for 1 ≤ l ≤ h, then
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\mathbb{P} ( {Y_{k + 1}} & = q , \;{U_{k + 1}} = v \mid {Y_k} = p
, \;{U_k} = u ) \\ & = \mathbb{P} ( {Z_{k + 1}} = a , \;{U_{k +
1}} = v \mid {Z_k} = {w_l} , \;{U_k} = u , \;{Z_{k - 1}} = {w_{l -
1}} , \;{U_{k - 1}} = \cdot , \; \ldots , \;{Z_{k - l + 1}} =
{w_1} , \;{U_{k - l + 1}} = \cdot ) , \\ & = \mathbb{P} ( {Z_{k +
1}} = a , \;{U_{k + 1}} = v \mid {Z_k} = {w_l} , \;{U_k} = u ) .
\tag{13}
\end{align*}
\end{document}
If p = ɛj for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$j \in { \cal A} \setminus \{ {w_1} \} $$
\end{document}, then
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
& \mathbb{P} ( {Y_{k + 1}} = q , \;{U_{k + 1}} = v \mid {Y_k} = p
, \;{U_k} = u ) \\ & = \mathbb{P} ( {Z_{k + 1}} = a , \;{U_{k +
1}} = v \mid {Z_k} = j , \;{U_k} = u , \;{Z_{k - 1}} = \cdot ,
\;{U_{k - 1}} = \cdot , \; \ldots , \;{Z_{k - i + 1}} = \cdot ,
\;{U_{k - i + 1}} = \cdot ) , \\ & = \mathbb{P} ( {Z_{k + 1}} = a
, \;{U_{k + 1}} = v \mid {Z_k} = j , \;{U_k} = u ) .
\tag{14}
\end{align*}
\end{document}
To denote in general the transition probability, let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i = { \delta ^{ - 1}} ( p )$$
\end{document} be the partial inverse of p. Therefore, in Equations (13) and (14), Zk = i; thus,
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\mathbb{P} ( {Y_{k + 1}} = q , \;{U_{k + 1}} = v \mid {Y_k} = p , \;{U_k} = u ) = \mathbb{P} ( {Z_{k + 1}} = a , \;{U_{k + 1}} = v \mid {Z_k} = i , \;{U_k} = u ) . \tag{15}
\end{align*}
\end{document}
If k + 1 is a renewal time for (Zk), then v = 0 and i ≠ a yields
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\mathbb { P } ( { Z_ { k + 1 } } = a , \; { U_ { k + 1 } } = v \mid { Z_k } = i , \; { U_k } = u ) = { \frac { { q_ { ia } } ( u + 1 ) } { 1 - { H_i } ( u ) } } , \tag { 16 }
\end{align*}
\end{document}
if k + 1 is not a renewal time for (Zk), then v = u + 1 and a = i yields
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\mathbb { P } ( { Z_ { k + 1 } } = a , \; { U_ { k + 1 } } = v \mid { Z_k } = i , \; { U_k } = u ) = { \frac { 1 - { H_i } ( u + 1 ) } { 1 - { H_i } ( u ) } } , \tag { 17 }
\end{align*}
\end{document}
(Barbu and Limnios, 2008); so, the proposition is proved.
To simplify the notation, let P be the transition probability matrix and β the initial distribution of process (Yk, Uk), respectively, such that
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
P ( ( p , \;u ) , \; ( q , \;v ) ) : = \mathbb{P} ( {Y_{k + 1}} = q , \;{U_{k + 1}} = v \mid {Y_k} = p , \;{U_k} = u ) \tag{18}
\end{align*}
\end{document}
and
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\beta ( p , \;u ) : = \mathbb{P} ( {Y_0} = p , \;{U_0} = u ) . \tag{19}
\end{align*}
\end{document}
Algorithm 2 proposed here (Section 7) computes the transition probability matrix P.
If \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ ( {J_n} , \;{S_n} ) _{n \in \mathbb{N}}}$$
\end{document} is irreducible, then Markov chain (Zk, Uk) is irreducible too (Chryssaphinou et al., 2008). We shall prove, in the next proposition, the same properties for (Yk, Uk), that is, the irreducibility and aperiodicity.
Proposition 2.Let\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A}$$
\end{document}be an alphabet, such that\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\vert { \cal A} \vert \; \ge \;2$$
\end{document}. If the Markov renewal process (Jn, Sn) with state space\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A} \times \mathbb{N}$$
\end{document}is irreducible, then process (Yk, Uk) with state space K is also irreducible and aperiodic.
Proof. Let it be that (p, u), (q, v)∈K, and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i = { \delta ^{ - 1}} ( p )$$
\end{document}. If q = w1 or q = ɛa with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$a \in { \cal A} \setminus \{ {w_1} \} $$
\end{document} the proof is a direct consequence of the irreducibility of (Zk, Uk). If q = w1w2, …, w\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\ell$$
\end{document}, with 1 < \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\ell$$
\end{document} ≤ h. Let q1 = w1, q2 = w1w2, …, q = w1w2⋯w\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\ell$$
\end{document}, be the consecutive prefixes from w1 to q = w1w2, …, w\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\ell$$
\end{document} and (q1, u1), (q2, u2), …, (q, v) the consecutive couples in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$E \times \mathbb{N}$$
\end{document}, such that for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$1 \le i \le \ell - 1$$
\end{document}\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{u_{i + 1}} = \left\{ { \begin{matrix}0 \hfill & {{ \rm{if}} \;{w_{ \rm{i}}} \ne {w_{{ \rm{i + 1}}}}} \hfill \\ {{u_i} + 1} \hfill & {{ \rm{elsewhere}}} \hfill \\ \end{matrix} } \right.
\end{align*}
\end{document}
due to the irreducibility of (Zk, Uk), for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( i , u ) \in { \cal A} \times \mathbb{N}$$
\end{document} there exist \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$n \in { \mathbb{N}^*}$$
\end{document} such that, for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$m \in \mathbb{N}$$
\end{document}\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\mathbb{P} ( {Z_{m + n}} = {w_1} , \;{U_{m + n}} = {u_1} \mid {Z_m} = i , \;{U_m} = u ) \; > \;0 ,
\end{align*}
\end{document}
Therefore, there exist \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${n_1} = n + \ell - 1$$
\end{document} such that
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\mathbb{P} ( {Y_{m + {n_1}}} = q , \;{U_{m + {n_1}}} = v \mid {Y_m} = p , \;{U_m} = u ) > 0.
\end{align*}
\end{document}
Now, to prove that (Yk, Uk) is aperiodic, let p and q be elements of E, such that |p| = l and |q| = l + 1, for 1 ≤ l < h,
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
n: = { \rm{min}} \{ k:{P^k} ( ( p , \;u ) , \; ( p , \;u ) ) > 0 \}
\end{align*}
\end{document}
be the minimum numbers of steps to pass from (p, u) to (p, u) and from (q, v) to (q, v), respectively. From Equation (12), it is clear that m = n + 1. Let d be the period of (p, i) and (q, j), hence d|n and d|(n + 1); thus, d = 1.
4. The Hitting Time of the Word
Let Nw be the number of elements in the sequence of letters before the first hitting position of w; to define the random variable Nw, we use the prefix chain and its backward time, that is,
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{N_w}: = { \rm{min}} \{ k \ge 0: ( {Y_k} , \;{U_k} ) = ( w , \; \cdot p ) \in K \} . \tag{20}
\end{align*}
\end{document}
As has been noted in Section 2, an occurrence of w in (Zk) corresponds to an occurrence of w in (Yk). The following proposition gives the probability law of Nw.
Proposition 3.Let {Wc, W} be a partition of the state space K such that W : = {(w,\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\cdot$$
\end{document})∈K} and Wc : = K \ W. Let\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \bf{1}}$$
\end{document}be a column vector of ones with size |Wc|. Let Pw = P|Wc×Wc and βw be the restrictions, respectively, on Wc × Wc and Wc of the transition matrix P and the initial distribution β. Then,\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\mathbb{P} ( {N_w} = n ) = \left\{ { \begin{matrix}0 \hfill & {if \;n < h - { \rm{1}} , } \hfill \\ {{ \beta _w}{{ ( {P_w} ) }^{h - 1}}{ \bf{1}}} \hfill & {if \;n { \rm{ = }}h - { \rm{1}} , } \hfill \\ {{ \beta _w}P_w^{n - 1} [ I - {P_w} ] { \bf{1}}} \hfill & {if \;n \ge h.} \hfill \\ \end{matrix} } \right.
\end{align*}
\end{document}
Proof. For \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$n < h - 1$$
\end{document}, it is obvious. For \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$n = h - 1$$
\end{document}, let p1 = w1, p2 = w1w2, …, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${p_{h - 1}} = {w_1}{w_1} \cdots {w_{h - 1}}$$
\end{document}, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w = {w_1}{w_1} \cdots {w_{h - 1}}{w_h}$$
\end{document} be the consecutive prefixes from w1 to w, then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\mathbb{P} ( {N_w} = h - 1 ) & = \sum \limits_{{u_h} \in {l_w}} {
\sum \limits_{{u_{h - 1}} \in {l_{{p_{h - 1}}}}} \cdots } \sum
\limits_{{u_2} \in {l_{{p_2}}}} { \sum \limits_{{u_1} \in
{l_{{p_1}}}} P } ( ( {p_{h - 1}} , \;{u_{h - 1}} ) , \; ( w ,
\;{u_h} ) ) \\ & \cdots P ( ( {p_1} , \;{u_1} ) , \; ( {p_2} ,
\;{u_2} ) ) \mathbb{P} ( {Y_0} = {p_1} , \;{U_0} = {u_1} ) ,
\end{align*}
\end{document}
Proposition 4.Under the same hypothesis, as in Proposition 3, where\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$f ( h - 1 ) = \mathbb{P} ( {N_w} = h - 1 )$$
\end{document}. The generating function of Nw, that is, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ( s ) : = \mathbb{E} [ {s^{{N_w}}} ]$$
\end{document}, for |s| ≤ 1 is\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
G ( s ) = {s^{h - 1}}f ( h - 1 ) {1_{ \{ h \ge 1 \} }} + s{ \beta _w}{ ( s{P_w} ) ^{h - 1}}{ ( I - s{P_w} ) ^{ - 1}} ( I - {P_w} ) {1_{ \{ h \ge 1 \} }}{ \bf{1}}.
\end{align*}
\end{document}
Proof. By definition of the generating function and Proposition 3, we write:
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
G ( s ) & = \sum \limits_{k \ge h - 1} \mathbb{P} ( {N_w} = k )
{s^k} \\ & = {s^{h - 1}}f ( h - 1 ) {1_{ \{ h \ge 1 \} }} + \sum
\limits_{k \ge h} {{s^k}} { \beta _w}P_w^{k - 1} [ I - {P_w} ] {
\bf{1}}.
\tag{21}
\end{align*}
\end{document}
Due to the fact that Wc is a proper subset of the state space K of an irreducible and aperiodic Markov chain, we write
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\sum \limits_{k \ge 0} {{{ ( s{P_w} ) }^k}} = { ( I - s{P_w} ) ^{ - 1}} \tag{22}
\end{align*}
\end{document}
Hence,
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
G ( s ) = {s^{h - 1}}f ( h - 1 ) {1_{ \{ h \ge 1 \} }} + s{
\beta _w}{ ( s{P_w} ) ^{h - 1}}{ ( I - s{P_w} ) ^{ - 1}} ( I -
{P_w} ) {1_{ \{ h \ge 1 \} }}{ \bf{1}}. \;
\end{align*}
\end{document}
Lemma 1.The n derivate of\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( I - s{P_w} )$$
\end{document}holds the following property:\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\frac { d } { { ds } } { ( I - s { P_w } ) ^ { - n } } = n { ( I - s { P_w } ) ^ { - ( n + 1 ) } } { P_w } = n { P_w } { ( I - s { P_w } ) ^ { - ( n + 1 ) } } .
\end{align*}
\end{document}
Proposition 5.The mean and variance of Nw are, respectively,\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\mathbb{E} [ {N_w} ] = ( h - 1 ) f ( h - 1 ) {1_{ \{ h \ge 2 \} }} + { \beta _w} [ Q + hP_w^{h - 2} ] {P_w}{ \bf{1}} \tag{23}
\end{align*}
\end{document}
and for h ≥ 3\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\mathbb{V}{ \rm{ar}} [ {N_w} ] = 2 ( h - 1 ) f ( h - 1 ) + a + b + c + d - { ( \mathbb{E} [ {N_w} ] ) ^2} , \tag{24}
\end{align*}
\end{document}
Proof. Using the generating function of Nw, G(s), and Lemma 1, we get
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{ \frac { dG ( s ) } { ds } } & = ( h - 1 ) { s^ { h - 2 } } f (
h - 1 ) { 1_ { \ { h \ge 2 \ } } } \\ & \,\;+ { \beta _w } [ { ( I
- s { P_w } ) ^ { - 1 } } + h { ( s { P_w } ) ^ { h - 2 } } ] ( sP
) {
( I - s { P_w } ) ^ { - 1 } } ( I - { P_w } ) { \bf { 1 } } , \\
\tag { 25 }
\end{align*}
\end{document}
which yields
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{ \frac { dG ( s ) } { ds } } { \vert _ { s = 1 } } = \mathbb { E } [ { N_w } ] = ( h - 1 ) f ( h - 1 ) { 1_ { \ { h \ge 2 \ } } } + { \beta _w } [ { ( I - { P_w } ) ^ { - 1 } } + h { ( { P_w } ) ^ { h - 2 } } ] P { \bf { 1 } } .
\end{align*}
\end{document}
For the variance of Nw, the derivate of Equation (25) will be computed as follows:
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{d \over {ds}} ( h - 1 ) {s^{h - 2}}f ( h - 1 ) = ( h - 1 ) ( h -
2 ) {s^{h - 3}}f ( h - 1 ) {1_{ \{ h \ge 3 \} }} , \tag{26}
\end{align*}
\end{document}\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\frac { d } { { ds } } [ { ( I - s { P_w } ) ^ { - 1 } } + h { ( s { P_w } ) ^ { h - 2 } } ] = { ( I - s { P_w } ) ^ { - 2 } } { P_w } + h ( h - 2 ) { ( s { P_w } ) ^ { h - 3 } } { P_w } { 1_ { \ { h \ge 3 \ } } } , \tag { 27 }
\end{align*}
\end{document}
and
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\frac { d } { { ds } } ( s { P_w } ) { ( I - s { P_w } ) ^ { - 1 } } = ( s { P_w } ) { ( I - s { P_w } ) ^ { - 2 } } { P_w } + { P_w } { ( I - s { P_w } ) ^ { - 1 } } . \tag { 28 }
\end{align*}
\end{document}
Then, using Equations (27) and (28) and simplifying terms, it yields for h ≥ 3
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\frac { d } { { ds } } [ { ( I - s { P_w } ) ^ { - 1 } } + h { (
s { P_w } ) ^ { h - 2 } } ] ( s { P_w } ) { ( I - s { P_w } ) ^ {
- 1 } } & = \ { 2 ( s { P_w } ) { ( I - s { P_w } ) ^ { - 2 } }} \\
& \,\;+ [ 1 + h { ( s { P_w } ) ^ { h - 1 } } ] { ( I - s { P_w }
) ^ { - 1 } } \\ & \,\;+ ( h - 1 ) h { ( s { P_w } ) ^ { h - 2 } }
\ { ( I - s { P_w } ) ^ { - 1 } } { P_w } . \tag { 29 }
\end{align*}
\end{document}
Therefore, using Equations (26) and (29) for h ≥ 3:
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\frac { { d^2 } {G ( s )} } { d { s^2 } } & = ( h - 1 ) ( h - 2
) { s^ { h - 3 } } f ( h - 1 ) + { \beta _w } \ { 2 ( s { P_w } )
{ ( I - s { P_w } ) ^ { - 2 } } }\\ & \,\;+ [ 1 + h { ( s { P_w }
) ^ { h - 1 } } ] { ( I - s { P_w } ) ^ { - 1 } } \\ & \,\;+ ( h -
1 ) h { ( sP ) ^ { h - 2 } } \ { ( I - s { P_w } ) ^ { - 1 } } P (
I - P ) { \bf { 1 } }. \tag { 30 }
\end{align*}
\end{document}
Therefore for h ≥ 3,
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
{ \frac { { d^2 } G ( s ) } { d { s^2 } } } { \vert _ { s = 1 } } = ( h - 1 ) ( h - 2 ) f ( h - 1 ) + { \beta _w } \ { 2P_w^2 { ( I - { P_w } ) ^ { - 2 } } + [ { P_w } + hP_w^h ] { ( I - { P_w } ) ^ { - 1 } } + ( h - 1 ) hP_w^ { h - 1 } \ } { \bf { 1 } } .
\end{align*}
\end{document}
Using the expression
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\mathbb { V } { \rm { ar } } [ { N_w } ] = { \frac { { d^2 } G ( s ) } { d { s^2 } } } { \vert _ { s = 1 } } + { \frac { dG ( s ) } { ds } } { \vert _ { s = 1 } } - { ( { \frac { dG ( s ) } { ds } } { \vert _ { s = 1 } } ) ^2 } ,
\end{align*}
\end{document}
we get for h ≥ 3,
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
\mathbb{V}{ \rm{ar}} [ {N_w} ] = { ( h - 1 ) ^2}f ( h - 1 ) + a + b + c + d - { ( \mathbb{E} [ {N_w} ] ) ^2} ,
\end{align*}
\end{document}
The mathematical model proposed in this article can be implemented in any irreducible semi-Markov chain with finite state space; to show one of its applications, in this section we present a genomic example.
Let us consider the DNA sequence of bacteriophage. This DNA includes 48,502 nucleotides. In this case, the genomic alphabet is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A} = \{ A , T , G , C \} $$
\end{document} and let us consider the pattern w = CCCGGG, which is the enzyme SmaI. The SmaI enzyme is a DNA cutter. That is, when it finds the “CCCGGG” fragment it applies and cuts the DNA in the middle of this fragment, that is, into “…CCC” and “GGG….”
The probability that the SmaI enzyme appears after k nucleotides is observed in Figure 1. The random variable Nw counts the numbers of nucleotides before the apparition of the enzyme and it is defined according to Equation (20). The probability function of Nw is denoted \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${f_w} ( k ) : = \mathbb{P} ( {N_w} = k )$$
\end{document}, and this probability is computed by using Preposition 3.
Probability law of Nw, that is, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${f_w} ( k ) : = \mathbb{P} ( {N_w} = k )$$
\end{document}.
In Figure 2, we can observe that the SmaI enzyme does not appear frequently in the DNA. The word occurrence rate for k ≥ 1 is given by the rate function
Rate of occurrence of the word w in the DNA sequence.
where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \bar F_w} ( k ) = 1 - {F_w} ( k )$$
\end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${F_w} ( k ) : = \sum \nolimits_{l = 0}^k {{f_w}} ( l )$$
\end{document}. Figure 3 gives the values for the distribution function Fw(k). In continuous time, the rate function takes values also >1; in the discrete-time case, it takes values only in the interval [0,1]. For this reason, in another context, Roy and Gupta (1992) proposed another rate function as follows:
Cumulative distribution function of Nw, that is, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${F_w} ( k ) : = \mathbb{P} ( {N_w} \le k )$$
\end{document}.
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
r ( k ) = - { \rm{ln}} ( 1 - \lambda ( k ) ) . \tag{31}
\end{align*}
\end{document}
Nevertheless, when λ(k) is close to 0, we have obviously
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
r ( k ) \,\cong\, \lambda ( k ) .
\end{align*}
\end{document}
In the case of the present example, the values λ(k) are very small; so, Figure 2 represents also the function r(k).
Considering that DNA sequence has 48,502 nucleotides, that is, it has size M = 48,502 and using the expressions:
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
& \mathbb{E} [ {N_w} \cdot {1_{ \{ {N_w} \le M \} }} ] = \sum \limits_{k = h - 1}^M k {f_w} ( k ) , \\ & \mathbb{E} [ T_w^2 \cdot { \rm{ }}{1_{ \{ {N_w} \le M \} }} ] = \sum \limits_{k = h - 1}^M {{k^2}} {f_w} ( k ) , \\
\end{align*}
\end{document}
where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${f_w} ( k ) : = \mathbb{P} ( {N_w} = k )$$
\end{document} is obtaining according to Proposition 3, the expected value
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\mathbb{E} [ {N_w} \cdot { \rm{ }}{1_{ \{ {N_w} \le M \} }} ]$$
\end{document} and the standard deviation σ[Nw\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\cdot$$
\end{document}1{Nw≤M}] are computed.
Considering different lengths for the DNA sequence, that is, considering different values for M, the mean values of Nw for each M are observed in Figure 4. If we take into account that DNA sequence has infinity length, the mean value of Nw is computed according to Equation (23). The variance is computed by using Equation (24); therefore, for the bacteriophage DNA sequence we have the values:
Expected value of Nw for different values of M in the DNA.
Notice that in Figure 4 the value \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\mathbb{E} [ {N_w} \cdot { \rm{ }}{1_{ \{ {N_w} \le M \} }} ]$$
\end{document} reaches \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\mathbb{E} [ {N_w} ]$$
\end{document} as M becomes large enough, as it was expected by the dominated converge theorem. It is worth noticing that the standard deviation here is high. This is due to the fact that the evolution of the rate of occurrence of the word is small. After position 9, it becomes geometric, as can be seen in Figure 2. According to geometric distribution with success probability p, the variance is given by formula
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
\begin{align*}
Var ( X ) = { \frac { 1 - p } { { p^2 } } } .
\end{align*}
\end{document}
Let us observe that variance grows if p decreases. In our model, the rate of occurrence of the word is tiny; we can see in the same Figure 2 that after position 9, we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$p = \lambda ( 9 ) = 1.6 \times {10^{ - 4}}$$
\end{document}, which means that the probability to have success is small, and this gives the big value for the standard deviation.
6. Concluding Remarks
In this article, we proposed, for the first time in our knowledge, a new model and algorithm that can be implemented in real applications to compute the first hitting position (time) of a word (pattern) in a semi-Markov sequence. Although Chryssaphinou et al. (2008) proposed the only theoretical model before this work, for the occurrence of words in discrete-time SMCs, the method proposed by Chryssaphinou et al. cannot be implemented because the cardinality of the state space of the model they have proposed is huge. It has \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\vert { \cal A}{ \vert ^h} \times ( M - h )$$
\end{document} elements, where M represents the length of the SMC (Zk), \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A}$$
\end{document} the alphabet, and h the length of the pattern. Notice that, if the values of h and/or M grow, the cardinality of the state space becomes enormous, and this makes the implementation difficult. By contrast, the model proposed here needs less memory space than the one proposed by Chryssaphinou et al. (2008). This model is based on prefixes and its extended state space; with these assumptions, process (Yk, Uk) becomes a Markov chain where its transition matrix P is easily written. For a word w with length |w| = h and maximum value for the backward time of a prefix: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\gamma = { \rm{max}} \{ {l_p}:p \in E \} $$
\end{document}, we need a state space of cardinality \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( h + \vert { \cal A} \vert - 1 ) \times \gamma$$
\end{document} at most.
Moreover, we proposed results for the (first) position time to w, its law, its mean and variance, and its generating function. As can be seen in Figure 4, the value \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\mathbb{E} [ {N_w} \cdot { \rm{ }}{1_{ \{ {N_w} \le M \} }} ]$$
\end{document} reaches \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\mathbb{E} [ {N_w} ]$$
\end{document}, as M becomes large enough, as was expected by the dominated converge theorem.
It is worth noting that for words of length 1, that is, a letter, our algorithm recovers the Markov process (Zk, Uk). Of course, this work (algorithm) could be used for any irreducible semi-Markov sequence with finite state space and any finite word (pattern).
7. Appendix
We present here two algorithms that are needed to work with our model in practical problems, where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A}$$
\end{document} is the alphabet, w is the word, q is the semi-Markov kernel of the SMC (Zk), E is the extended state space of prefixes, n1 is the size of the first block of w, and K is the state space of process (Yk, Uk).
. add state \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( p , i - 1 )$$
\end{document} to K
end for
end if
if |p| ≠ 0 and |p| ≠ n1, that is, p = w1w2⋯wl, l ≠ n1 and 1 ≤ l ≤ hthen
. add state \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( p , { \rm{backward - time}} )$$
\end{document} to K
end if
if |p| = n1then
fori = n1 until i = rδ-1(p)do
. add the state (p, i) to K
end for
end if
end for
Algorithm 2. Transition probability matrix P
. Require: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal A} , \;{ \bf{q}}$$
\end{document}, E, K
. Initialization
for every (p, u), (q, v) ∈Kdo
for every \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$a \in { \cal A}$$
\end{document}do
ifδ(p, a) = = qthen
if\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \delta ^{ - 1}} ( p ) = = a$$
\end{document} and u + 1 = vthen
else if\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \delta ^{ - 1}} ( p ) \ne a$$
\end{document} and v = = 0 then
P((p, u), (q, v)) = Equation (16)
end if
else
P((p, u), (q, v)) = 0
end if
end for
end for
Footnotes
Author Disclosure Statement
The authors declare they have no competing financial interests.
Funding Information
This work was supported by a PhD scholarship funding, granted by the Mexican Consejo Nacional de Ciencia y Tecnologia (CONACYT).
References
1.
AbadiM., and VergeneN.2008. Poisson approximations for search of rare words in DNA sequences. Am. J. Prob. Math. Stat. 4, 223–224.
2.
AboluionN.A.2011. The construction of DNA codes using a computer algebra system [Ph.D. thesis]. University of Glamorgan, UK.
3.
AntzoulakosD.L.2001. Waiting times for patterns in a sequence of multistate trials. J. Appl. Probab. 38, 508–518.
4.
BarbuV., BoussemartM., and LimniosN.2004. Discrete time semi-Markov processes for reability and survival analysis. Commun. Stat. Theory Methods. 33, 2833–2868.
5.
BarbuV., and LimniosN.2008. Semi-Markov Chains and Hidden Semi-Markov Models Toward Applications: Their Use in Reliability and DNA Analysis, 1st ed. Springer, New York.
6.
ChadjiconstantinidisS., AntzoulakosD.L., and KoutrasM.V.2000. Joint distribution of successes, failures and patterns in enumeration problems. Adv. Appl. Probab. 32, 866–884.
7.
ChryssaphinouO., KaraliopoulouM., and LimniosN.2008. On discrete time Semi-Markov chains and applications in words occurrences. Commun. Stat. Theory Methods. 37, 1306–1322.
8.
CodishM., FrankM., and LagoonV.2017. The DNA word design problem: A new constraint model and new results. IJCAI-17. Conference in Australia, 2017.
9.
CrochemoreM., and StefanovV.T.2003. Waiting time and complexity for matching patterns with automata. Inform. Process. Lett. 87, 119–125.
10.
Den HollanderF.2013. Stochastic models for genetic evolution. Lecture notes. Mathematical Institue, Leiden University.
11.
FuJ., and KoutrasM.1994. Distribution theory of runs: A Markov chain approach. J. Am. Stat. Assoc. 89, 1050–1558.
12.
FuJ.C., and ChangY.M.2002. On probability generating functions for waiting time distributions of compound patterns in a sequence of multistate trials. J. Appl. Probab. 39, 70–80.
13.
GlazJ., KulldorffM., PozdnyakovV., et al.2006. Gambling teams and waiting times for patterns in two-state Markov chains. J. Appl. Probab. 43, 127–140.
14.
HebertP.D., CywinskaA., BallS.L., et al.2003. Biological identifications through DNA barcodes. Proc. R. Soc. London Series B Biol. Sci. 270, 313–321.
15.
KaraliopoulouM.2009. On the number of word occurrences in a semi-Markov sequence of letters. ESAIM Probab. Stat. 13, 328–342.
16.
LiF., ZhangM., TianB., et al.2018. Recognizing irregular entities in biomedical text via deep neural networks. Pattern Recogn. Lett. 105, 105–113.
17.
LiZ., CaoH., CuiY., et al.2016. Extracting DNA words based on the sequence features: Non-uniform distribution and integrity. Theor. Biol. Med. Model. 13, 2.
18.
LimniosN., and OprişanG.2001. Semi-Markov Processes and Reliability. Springer Science and Business Media, Boston, MA.
19.
LothaireM.1983. Combinatorics on Words. Addison-Wesley, Cambridge, MA.
20.
ModeC.J., and PickensG.T.1988. Computational methods for renewal theory and semi-Markov processes with illustrative examples. Am. Stat. 42, 143–152.
21.
MontemanniR.2015. Combinatorial optimization algorithms for the design of codes: A survey. J. Appl. Oper. Res. 7, 36–41.
22.
NeutsM.1981. Matrix-Geometric Solutions an Algorithmic Approach. The Johns Hopkins University Press, Baltimore and London.
NuelG.2008. Pattern Markov chains embedding through deterministic finite automata. J. Appl. Probab. 45, 226–243.
25.
PicardF., SchbathS., LebarbierE., et al.2011. Statistiques et génome. la Gazette des mathématiciens. 130, 51–82.
26.
RobinS., and DaudinJ.1999. Exact distribution of word occurrences in a random sequence of letters. J. Appl. Probab. 36, 179–193.
27.
RobinS., SchbathS., and VandewalleV.2007. Statistical tests to compare motif count exceptionalities. BMC Bioinform. 8, 84.
28.
RoyD., and GuptaR.P.1992. Classifications of discrete lives. Microelectron Reliab. 32, 1459–1473.
29.
SigwartJ., and GarbettA.2018. Biodiversity assessment, DNA barcoding, and the minority majority. Integr. Comp. Biol. 58, 1146–1156.
30.
SrivastavaS., and BaptistaM.S.2016. Markovian language model of the DNA and its information content. Royal Soc. Open Sci. 3, 150527.
31.
StefanovV., and PakesA.1997. Explicit distributional results in pattern formation. Ann. Appl. Probab. 7, 666–678.
32.
StefanovV., RobinS. and SchbathS.2011. Occurrence of structured motifs in random sequences: Arbitrary number of boxes. Discrete Appl. Math. 159, 826–831.
33.
TouyarN., SchbathS., CellierD., et al.2008. Poisson approximation for the number of repeats in a Markov chain model. J. Appl. Probab. 45, 440–455.
