A Posteriori Detection of a Quasiperiodically Recurring Fragment in Numerical Sequences in the Presence of Noise and Data Loss

摘要

The problem of a posteriori detection of a recurring pattern (fragment) in a numerical sequence is solved. The case where the repetitions are quasiperiodic is analyzed. It is assumed that (i) the number of occurrences of the fragment in the sequence is unknown and the serial number of the term of the sequence that corresponds to the beginning of the fragment is a deterministic (nonrandom) variable; (ii) the recurring fragment is subject to distortions, such as setting to zero of the first and/or last terms; the number of terms setting to zero is a deterministic but unknown value, which depends on the fragment; and vanishing of terms is interpreted as a loss of data on the pattern; and (iii) the distorted sequence is corrupted by additive Gaussian uncorrelated noise. The problem under consideration is essentially reduced to testing a set of hypotheses on the mean of a Gaussian random vector; the cardinality of the set of hypotheses grows exponentially with increasing dimension of the vector, i.e., sequence length. A polynomial algorithm ensuring the likelihood detection is substantiated; the time and space complexities of the algorithm depend on the parameters of the problem. Results of numerical modeling are given.