Bounds for the probability of a constrained embedding of one discrete sequence into another
Владимир Гаврилович Михайлов, Natalia Mikhailovna Mezhennaya · Discrete Mathematics and Applications · 2005
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.