Improvements on the distribution of maximal segmental scores in a Markovian sequence

Abstract

Let $(A_i{)}_{i\ge 0}$ be a finite state irreducible aperiodic Markov chain and $f$ a lattice score function such that the average score is negative and positive scores are possible. Define $S_0:=0$ and $S_k:={\sum }_{i=1}^{k}f(A_i)$ the successive partial sums, $S^{+}$ the maximal non-negative partial sum, $Q_1$ the maximal segmental score of the first non-negative excursion and $M_n:={\max }_{0\le k\le \ell \le n}(S_{\ell }-S_k)$ the local score first defined by Karlin and Altschul (1990). We establish recursive formulae for the exact distribution of $S^{+}$ and derive new approximations for the distributions of $Q_1$ and $M_n$. Computational methods are presented in a simple application case and comparison is performed between these new approximations and the ones proposed by Karlin and Dembo (1992) in order to evaluate improvements.