\documentstyle[aofa00]{article}
\newtheorem{theorem}{Theorem}
\newenvironment{pic}[1]%
{\input{#1}\begin{figure}\centerline{\box\graph}\vspace*{\bigskipamount}}%
{\end{figure}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\renewcommand{\baselinestretch}{1.0}
\newenvironment{comment}{\setbox0=\vbox\bgroup}{\egroup}
\newcommand{\con}{\rightarrow}
\newcommand{\cd}{\mbox{$\stackrel{d}{\rightarrow}$}}
\newcommand{\cp}{\mbox{$\stackrel{p}{\rightarrow}$}}
\newcommand{\ed}{\mbox{$ \ \stackrel{d}{=}$ \ }}
\newcommand{\Fracstrut}{\vrule height 10pt depth 3pt width 0pt}
\newcommand{\myfrac}[2]{\frac{\displaystyle\Fracstrut#1}{\displaystyle\Fracstrut
#2}}
\newenvironment{singlespace}{\def\baselinestretch{1.0}\large\normalsize}{\par}
\def\noi{\noindent}
\def\lf{\lfloor}
\def\rf{\rfloor}
\def\eod{\vrule height 6pt width 5pt depth 0pt}
\def\parsec{\par\noindent}
\def\big{\bigskip\parsec}
\def\med{\medskip\parsec}
\def\pr{{\rm Pr}}
\def\eps{\varepsilon}
\def\lef{\preceq}
\def\lefs{\prec}
\def\nlef{\not\preceq}
\def\rig{\subseteq}
\def\H{{\rm H}}
\def\h{{\rm  h}}
\def\rigs{\subset}
\def\nrig{\not\subseteq}
\def\aa{\Lambda}
\def\CH{{\cal H}}
\def\semb{\Leftrightarrow}
\def\impl{\Rightarrow}
\def\bb{\beta}
\def\ee{\epsilon}
\def\GG{\Gamma}
\def\mm{\mu}
\def\oo{\omega}
\def\ss{\sigma}

\def\roh{\rho _{H}}

\def\alph{{\cal S}}
\def\te{{\bf t}}
\def\pat{{\bf p}}
\def\ahz{A_\H(z)}

\def\phb{P(H)}
\def\pht{P_H(H)}

\def\lgh{{\cal R}_\H}
\def\lrh{{\cal R}_\H}
\def\llh{{\cal L}_\H}
\def\luh{{\cal U}_\H}
\def\lah{{\cal A}_\H}
\def\lmh{{\cal M}_\H}

\def\lbar{\bar{L} (z)}
%\def\ltilde{\widetilde{L} (z)}
%\def\dht{\widetilde{D}_{H}(z)}
%\def\mht{\widetilde{M}_{H}(z)}
%\def\uht{\widetilde{U}_{H}(z)}
%\def\uhit{\widetilde{U}_{H}^i(z)}
%\def\aht{\tilde{A}(z)}
%\def\bht{\tilde{B}(z)}

\def\ltilde{L_{\H} (z)}
\def\dht{D_{\H}(z)}
\def\mht{M_{\H}(z)}
\def\uht{U_{\H}(z)}
\def\uhit{U_{\H}^i(z)}
\def\aht{A_{\H}(z)}
\def\bht{B_{\H}(z)}


\def\rhi{R_{i}(z)}
\def\rhb{R_{H}(z)}
\def\fgh{R_\H(z)}

\def\fah{A_\H(z)}
\def\fuh{L_\H(z)}
\def\dh{D_\H}
\def\nh{N_\H}
\def\ah{A_{\H}}
\def\dhz{{P(H)z^m+(1-z)A_H(z)}}
\def\nhz{{P(H)z^m+(1-z)(A_H(z)-1)}}
\def\ltr{{{\cal T} _r}}
\def\ltt{{{\cal T} }}
\def\lt0{{{\cal T}_0}}
\def\T{{\tt T}}

\def\t{{\rm t}}
\def\s{{\rm s}}
\def\a{{\tt a}}
\def\b{{\tt b}}
\def\c{{\tt c}}
\def\trn{t_{r,n}}
\def\Var{{\rm Var ~}}
\def\L{{\cal L}}
\def\R{{\cal R}}
\def\U{{\cal U}}
\def\M{{\cal M}}
\def\TM{M_{\H}}
\def\TU{U_{\H}}

\def\T{{\cal T}}
\def\A{{\cal A}}
\def\S{{\cal S}}
\def\P{{\bf P}}
\def\VP{{\bf P}}
\def\VT{{\bf T}}
\def\F{{\Bbb F}}
\def\l{\ell}
\def\V{{\cal V}}
\def\W{{\cal W}}
\def\vpi{\mbox{\boldmath $\pi$}}


%
\begin{document}

\isittopoffset   {0mm}  % for 8.5 x 11 inch paper: use \isittopoffset{-9mm}

\isitleftoffset  {0mm}  % for 8.5 x 11 inch paper: use \isitleftoffset{3mm}

\isittitle{On Pattern Frequency Occurrences in a Markovian Sequence}
\med
\isitauthor      {Mireille R\'{e}gnier\footnotemark ~and~ Wojciech Szpankowski\footnotemark}

\isitaffiliation {INRIA, Rocquencourt, 78153 Le Chesnay Cedex, France\\
Department Computer Science, Purdue University,
W. Lafayette, IN 47907, U.S.A.}

\footnotetext[1]{Supported by the ESPRIT LTR
Project No. 20244 (ALCOM IT), and NATO Collaborative 
Grant CRG.950060.}
\footnotetext[2]{Supported by NSF Grants NCR-9206315 and NCR-9415491, and
NATO Collaborative Grant CRG.950060.}


\begin{isitpaper}

Consider a {\it given} pattern and a random text generated by
a Markovian source of any order.
We study the frequency of pattern occurrences in a random text when
overlapping copies of the pattern are counted separately
(cf. \cite{go3,li,prt}).
More precisely: let us consider two strings, a {\it given} 
pattern string $H=h_1h_2\ldots h_m$ and
a random text string $T=t_1t_2\ldots t_n$ of respective lengths equal to $m$
and $n$ over an alphabet $\alph$ of size $V$. 
We shall write $P(H_i^j)=\pr\{T_{i+k}^{j+k}=H_i^j\}$ for the probability of
the substring $H_i^j=h_i\ldots h_j$ occurrence in the random text
$T_{i+k}^{j+k}$ between symbols $i+k$ and $j+k$ for any $k$.
We define also the $\H$-conditional generating function  of a language
$\L$ (i.e., a set of words satisfying certain properties) as
$
\ltilde =\sum_{w\in \L} P(w| w_{-m}=h_1 \cdots w_{-1} =h_m )z^{|w|}
%\enspace
$,
where $w_{-i}$ stands for a
symbol preceding the first character of $w$ at distance $i$.
Finally, we define the so called {\it autocorrelation polynomial} $A(z)$ as:
{\it Given a string $H$, let
$
\aht =\sum_{k \epsilon HH} P(H_{k+1}^m|H_1^k) z^{m-k}
$
where $HH$ is the set of
positions of $H$ for which a prefix of $H$ is equal to a suffix of $H$,
e.g., $k\in HH$ means that the last $k$ symbols of $H$ are equal to
the first $k$ symbols of $H$.}

In the sequel, we denote by $O_n(\H)$
a random variable representing the number
of occurrences of $\H$ in a random text $T$ of size $n$.
We introduce the  generating function of the language $\T_r$ of words that
contains exactly $r$ occurrences of $\H$:
$T^{(r)}(z)=\sum_{n\geq 0} \pr\{O_n(\H)=r\} z^{n}$
for $|z|\leq 1$. We also define a bivariate generating function as follows:
$T(z,u)=\sum_{r=1}^\infty T^{(r)}(z)u^r=\sum_{r=1}^\infty \sum_{n=0}^\infty
\pr\{O_n(\H)=r\} z^{n}u^r$. 
Our main results for the Markovian model are summarized in the following two
theorems proved in \cite{rs} (see \cite{rs1} for extensions of these findings to
approximate pattern occurrences):

\begin{theorem}
Let $H$ be a given pattern of size $m$, and $T$ be a random
text of length $n$ generated according to a stationary Markov
chain (of any order) over a $V$-ary alphabet $\S$.\\
The generating functions $T^{(r)}(z)$ and $T(z,u)$ can
be computed as follows:
\begin{eqnarray*}
T^{(r)}(z) &=& R(z) \TM^{r-1}(z) \uht ~,  \\
T(z,u)&=& R(z) {u \over 1-u \mht} \uht ~,
\end{eqnarray*}
where, after defining
$$
D_H(z)=(1-z)(\aht +(\pht -P(H))z^m)
+z^m P(H) ~,
$$
we have
\begin{eqnarray*}
\mht&=& 1+{z-1 \over D_H(z)} ~,  \\
\uht&=&{1-\mht \over 1-z}={1\over D_H(z)} ~, 
\end{eqnarray*}
and $R(z)= z^m P(H) \uht$.
In the above,
$P(H)= P(w=H)$ and
$\pht =P(w=H|w_{-1}^{-m}= H)$.
\label{gft}
\end{theorem}

The above theorem is a key to the next asymptotic results.
These results are derived using analytical tools.

\begin{theorem}
Let the hypotheses of Theorem \ref{gft} be fulfilled, and in addition
$nP(H)\to \infty$. The following
results hold.
\med
{\rm (i)} {\sc Moments}.  For all $n\ge m$
\begin{eqnarray*}
EO_n(H)&=&P(H)(n-m+1) ~,  \\
\Var O_n(H)&=& nP(H)c_1 +P(H)c_2  ~,
\end{eqnarray*}
where $c_1$ and $c_2$ are explicitly computable constants (cf.
\cite{rs}).
\med
{\rm (ii)} {\sc Case $r=O(1)$}. Let $\rho_H$ be the smallest root
of $D_H(z)=0$ outside the unit circle $|z|<1$, and let $\rho>\rho_H$. Then:
$$
\pr\{O_n(\H)=r\}\sim \sum_{j=1}^{r+1} (-1)^j a_{j} {n \choose j-1}
\rho_\H^{-(n+j)} 
%&=& {1\over r!} a'_{r+1}n^r\rho_\H^{-(n+m-r-1)} +O(n^{r-1}\rho_\H^{-n})
%\label{e7}
$$
where $a_j$ are explicitly computable constants (cf. \cite{rs}).
\med
{\rm (iii)} {\sc Case $r=EO_n+x\sqrt{\Var O_n}$}. Let $x=O(1)$.
Then:
$$
\pr\{O_n(H)=r\}={1\over \sqrt{2\pi c_1 n}}  e^{-\frac{1}{2} x^2}
\left(1+O\left({1\over \sqrt{n}}\right)\right) ~,
$$
\parsec
{\rm (iv)} {\sc Case $r=(1+\delta)EO_n$}. Let $a=1+\delta$ and
$\delta \neq 0$.
Define $\rho(t)$ to be the root of
$1-e^t\TM(e^{\rho})=0$ ,
and $\omega_a$ to be the root of
$\rho'(\omega_a)  =a$ 
Then:
$$
\pr\{O_n(H)=r\}= {1\over \omega_a\sqrt{2\pi c_1 n} }
%\exp\left(-(n-m+1)(a\omega_a+\log \rho(\omega_a)\right)
e^{-((n-m+1) I(a)}
\left(1+O\left({1\over n}\right)\right)
$$
where $I(a)=a\omega_a- \rho(\omega_a)$.
\label{asymp}
\end{theorem}



\begin{isitreferences}
\bibitem{go3}
L. Guibas and A. W. Odlyzko, String Overlaps, Pattern Matching, and
Nontransitive Games,
{\it J. Combin.Theory Ser. A}, 30, 183-208, 1981.
\bibitem{li}
S. R. Li,
A Martingale Approach to the Study of Occurrences of
Sequence Patterns in Repeated Experiments,
{\it Ann. Probab.}, 8, 1171-1176, 1980.
\bibitem{prt}
B. Prum, F. Rodolphe, and E. Turckheim,
Finding Words with Unexpected Frequencies in Deoxyribonucleic Acid Sequence,
{\it J.R. Stat. Soc. B}, 57, 205-220, 1995.
\bibitem{rs}
M. Regnier and W. Szpankowski,
A Last Word on Pattern Frequency Occurrence in a Markovian Sequence?,
Purdue University, CSD-TR-96-043, 1996.
\bibitem{rs1}
M. Regnier and W. Szpankowski,
On the Approximate Pattern Occurrence in a Text,
Purdue University, CSD-TR-96-083, 1996.


\end{isitreferences}

\end{isitpaper}


\end{document}

