Bounds for the probability of a dense embedding of one discrete sequence into another

We obtain upper and lower bounds for the probability that a given sequence $X$ of finite length of symbols of a finite alphabet occurs inside a random equiprobable sequence $Y$ of symbols of the same alphabet as a subsequence whose terms are separated in $Y$ by at most one symbol. We give sequences $X$ at which the bounds are attained.
This research was supported by the Russian Foundation for Basic Research, grants 02–01–00266 and 05.01.00035, and by the Program of the President of the Russian Federation for support of leading scientific schools, grant 1758.2003.1.