Waiting Time Distribution for the Emergence of Superpatterns

2013/02/19 by Anant P. Godbole, Anant Godbole, Godbole, Anant +2
Computer Science · Mathematics · #60C05 #Algorithms and Data Compression #Cellular Automata and Applications #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR) #math.PR #msc:60C05

paper · pdf · doi:10.48550/arxiv.1302.4668

17 pages

arxiv created 2013/02/19 · openalex publication_date 2013/02/19 · arxiv updated 2013/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Consider a sequence X₁, X₂,... of i.i.d. uniform random variables taking values in the alphabet set 1,2,...,d. A k-superpattern is a realization of X₁,...,X_t that contains, as an embedded subsequence, each of the non-order-isomorphic subpatterns of length k. We focus on the non-trivial case of d=k=3 and study the waiting time distribution of tau=inft>=7: X₁,...,X_t is a superpattern

Related

• An asymptotically tight lower bound for superpatterns with small alphabets
• On the waiting time till some patterns occur in i.i.d. sequences
• Some Results on Superpatterns for Preferential Arrangements
• Lower bounds for superpatterns and universal sequences
• Fluctuations of the Longest Common Subsequence for Sequences of Independent Blocks