Waiting Time Distribution for the Emergence of Superpatterns

Consider a sequence ({X_{n}}_{n=1}^{infty }) of i.i.d. uniform random variables taking values in the alphabet set {1, 2,…, d}. A k-superpattern is a realization of ({X_{n}}_{n=1}^{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 =inf {tge 1:{X_{n}}_{n=1}^{t} text {is a superpattern}}). Our restricted set-up leads to proofs that are very combinatorial in nature, since we are essentially conducting a string analysis.