Large deviations for constrained pattern matching

In the constrained pattern matching one searches for a given pattern in a constrained sequence, which finds applications in communication, magnetic recording, and biology. We concentrate on the so-called (d, k) constrained binary sequences in which any run of zeros must be of length at least d and at most k, where 0 les d Lt k. In our previous paper [2] we established the central limit theorem (CLT) for the number of occurrences of a given pattern in such sequences. Here, we present precise large deviations results, often used in diverse applications. In particular, we apply our results to detect under- and over-represented patterns in neuronal data (spike trains), which satisfy structural constraints that match the framework of (d, k) binary sequences. Among others, we obtain justifiably accurate statistical inferences about their biological properties and functions. Throughout, we use techniques of analytic information theory such as combinatorial calculus, generating functions, and complex asymptotics.