Let $(A_i)_{i \geq 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\coloneqq 0$ and $S_k\coloneqq \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 excursion above 0, and $M_n\coloneqq \max_{0\leq k\leq\ell\leq 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 a new approximation for the tail behaviour of $Q_1$ , together with an asymptotic equivalence for the distribution of $M_n$ . Computational methods are explicitly presented in a simple application case. The new approximations are compared with those proposed by Karlin and Dembo (1992) in order to evaluate improvements, both in the simple application case and on the real data examples considered by Karlin and Altschul (1990).

Using random walk theory, we first establish explicitly the exact distribution of the maximal partial sum of a sequence of independent and identically distributed random variables. This result allows us to obtain a new approximation of the distribution of the local score of one sequence. This approximation improves the one given by Karlin et al., which can be deduced from this new formula. We obtain a more accurate asymptotic expression with additional terms. Examples of application are given.