2015/04/17 by Joshua Cooper, Cooper, Joshua, Danny Rorabaugh +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #05A05 #68R15 #Authorship Attribution and Profiling #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05A05 #msc:68R15 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1504.04424
12 pages
openalex publication_date 2015/04/17 · arxiv created 2016/10/17 · arxiv updated 2016/10/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Word W is said to encounter word V provided there is a homomorphism ϕ mapping letters to nonempty words so that ϕ(V) is a substring of W. For example, taking ϕ such that ϕ(h)=c and ϕ(u)=ien, we see that "science" encounters "huh" since cienc=ϕ(huh). The density of V in W, δ(V,W), is the proportion of substrings of W that are homomorphic images of V. So the density of "huh" in "science" is 2/8 \choose 2. A word is doubled if every letter that appears in the word appears at least twice. The dichotomy: Let V be a word over any alphabet, Σ a finite alphabet with at least 2 letters, and Wn ∈ Σn chosen uniformly at random. Word V is doubled if and only if 𝔼(δ(V,Wn)) → 0 as n → ∞. We further explore convergence for nondoubled words and concentration of the limit distribution for doubled words around its mean.