О количестве перекрытий слов в паттернах

Изучалась задача оценки количества перекрытий в паттерне — наборе слов в некотором алфавите $A$, имеющих одну и ту же длину $m$. Получены теоретические и экспериментальные оценки количества перекрытий для паттернов двух видов. Первый из них — это случайные паттерны, для которых верна равномерная вероятностная модель: все буквы в алфавите $A$ и, соответственно, все слова длины $m$ равновероятны. Доказано, что среднее количество перекрытий $P$ для случайных паттернов, состоящих из $n$ слов длины $m$, линейно зависит от размера паттерна $n$ и не зависит от длины слов в паттерне. В проведенных компьютерных экспериментах отношение $P/n$ менялось в пределах от $0.33$ до $1.06$; теоретические оценки этого отношения для тех же паттернов не превосходят $1.67$. Вторым видом паттернов, изученных в статье, являются паттерны, заданные матрицами позиционных весов из базы данных HOCOMOCO и пороговыми весами. Для этих паттернов отношение количества перекрытий к количеству слов в экспериментах менялось от $0.004$ до $1$, для более половины паттернов это отношение меньше $0.1$.