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

2018/03/07 by Grusea, Simona, Mercier, Sabine
#60F05 #60F10 #60G70 #60J10 #60K15 #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1803.02769

Abstract

Let (A_i)_{i ≥ 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 and S_k:=∑_i=1^k f(A_i) the successive partial sums, S⁺ the maximal non-negative partial sum, Q₁ the maximal segmental score of the first non-negative excursion and M_n:=max_{0≤ k≤ℓ≤ n} (S_ℓ-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₁ 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.

Related

• Asymptotic independence of three statistics of maximal segmental scores
• Lower bounds for moments of global scores of pairwise Markov chains
• Optimal Chernoff and Hoeffding Bounds for Finite State Markov Chains
• Ergodic Theorems for discrete Markov chains
• A Short Proof of a Convex Representation for Stationary Distributions of Markov Chains with an Application to State Space Truncation