2026-07-24T21:21:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12047 2024-03-06T10:49:16Z ddc:004 open_access

Hidden Words Statistics for Large Patterns Janson, Svante Szpankowski, Wojciech Hidden pattern matching subsequences probability U-statistics projection method We study here the so called subsequence pattern matching also known as hidden pattern matching in which one searches for a given pattern w of length m as a subsequence in a random text of length n. The quantity of interest is the number of occurrences of w as a subsequence (i.e., occurring in not necessarily consecutive text locations). This problem finds many applications from intrusion detection, to trace reconstruction, to deletion channel, and to DNA-based storage systems. In all of these applications, the pattern w is of variable length. To the best of our knowledge this problem was only tackled for a fixed length m=O(1) [P. Flajolet et al., 2006]. In our main result Theorem 5 we prove that for m=o(n^{1/3}) the number of subsequence occurrences is normally distributed. In addition, in Theorem 6 we show that under some constraints on the structure of w the asymptotic normality can be extended to m=o(√n). For a special pattern w consisting of the same symbol, we indicate that for m=o(n) the distribution of number of subsequences is either asymptotically normal or asymptotically log normal. We conjecture that this dichotomy is true for all patterns. We use Hoeffding’s projection method for U-statistics to prove our findings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Svante Janson and Wojciech Szpankowski 2020 Is Part Of LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2020.17 urn:nbn:de:0030-drops-120476 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.17 eng https://creativecommons.org/licenses/by/3.0/legalcode