Régnier, Mireille and Denise, Alain - Rare Events and Conditional Events on Random Strings

dmtcs:310 - Discrete Mathematics & Theoretical Computer Science, January 1, 2004, Vol. 6 no. 2
Rare Events and Conditional Events on Random Strings

Authors: Régnier, Mireille and Denise, Alain

Some strings -the texts- are assumed to be randomly generated, according to a probability model that is either a Bernoulli model or a Markov model. A rare event is the over or under-representation of a word or a set of words. The aim of this paper is twofold. First, a single word is given. One studies the tail distribution of the number of its occurrences. Sharp large deviation estimates are derived. Second, one assumes that a given word is overrepresented. The distribution of a second word is studied; formulae for the expectation and the variance are derived. In both cases, the formulae are accurate and actually computable. These results have applications in computational biology, where a genome is viewed as a text.


Source : oai:HAL:hal-00959004v1
Volume: Vol. 6 no. 2
Published on: January 1, 2004
Submitted on: March 26, 2015
Keywords: computable closed formulae,large deviations,combinatorics,generating fumctions,words,genome,computable closed formulae.,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Consultation statistics

This page has been seen 80 times.
This article's PDF has been downloaded 43 times.