Density dichotomy in random words

Abstract: Word

W

is said to encounter word

V

provided there is a homomorphism

p h i

mapping letters to nonempty words so that

p h i (V)

is a substring of

W

. For example, taking

p h i

such that

p h i (h) = c

and

p h i (u) = i e n

, we see that "science" encounters "huh" since

c i e n c = p h i (h u h)

. The density of

V

in

W

,

d e l t a (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 c h o o s e 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,

S i g m a

a finite alphabet with at least 2 letters, and

W_{n} i n S i g m a^{n}

chosen uniformly at random. Word

V

is doubled if and only if

m a t h b b E (d e l t a (V, W_{n})) i g h t a r r o w 0

as

n i g h t a r r o w i n f t y

. We further explore convergence for nondoubled words and concentration of the limit distribution for doubled words around its mean.

Recommendations

Cites work

Cited in

(1)

Describes a project that uses

Uses Software

This page was built for publication: Density dichotomy in random words