DMTCS Proceedings, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)

Font Size:  Small  Medium  Large

Toward the asymptotic count of bi-modular hidden patterns under probabilistic dynamical sources: a case study

Loïck Lhote, Manuel E. Lladser

Abstract


Consider a countable alphabet &A;. A multi-modular hidden pattern is an r-tuple (w1,…,wr), where each wi is a word over &A; called a module. The hidden pattern is said to occur in a text t when the later admits the decomposition t=v0w1v1⋯ vr-1wrvr, for arbitrary words vi over &A;. Flajolet, Szpankowski and Vallée (2006) proved via the method of moments that the number of matches (or occurrences) with a multi-modular hidden pattern in a random text X1⋯Xn is asymptotically Normal, when (Xn)n≥1 are independent and identically distributed &A;-valued random variables. Bourdon and Vallée (2002) had conjectured however that asymptotic Normality holds more generally when (Xn)n≥1 is produced by an expansive dynamical source. Whereas memoryless and Markovian sequences are instances of dynamical sources with finite memory length, general dynamical sources may be non-Markovian i.e. convey an infinite memory length. The technical difficulty to count hidden patterns under sources with memory is the context-free nature of these patterns as well as the lack of logarithm- and exponential-type transformations to rewrite the product of non-commuting transfer operators. In this paper, we address a case study in which we have successfully overpassed the aforementioned difficulties and which may illuminate how to address more general cases via auto-correlation operators. Our main result shows that the number of matches with a bi-modular pattern (w1,w2) normalized by the number of matches with the pattern w1, where w1 and w2 are different alphabet characters, is indeed asymptotically Normal when (Xn)n≥1 is produced by a holomorphic probabilistic dynamical source.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional