Exact Distribution for the Local Score of One i.i.d. Random Sequence

Abstract

Let X₁…X_n be a sequence of i.i.d. positive or negative integer-valued random variables and H_n = max_{0 ≤ i ≤ j ≤ n}(X_i + ··· + X_j) be the local score of the sequence. The exact distribution of H_n is obtained using a simple Markov chain. This result is applied to the scoring of DNA and protein sequences in molecular biology.