Основные определения

Большая колода карт и составляющие ее малые колоды

Вернемся к модельной задаче о колодах карт (уже описанной в предыдущем параграфе), в терминах которой будут сформулированы необходимые определения.

Предположим, что в нашем распоряжении имеется некоторая последовательность карт К (колода карт), которая может содержать повторяющиеся карты. Будем говорить, что колода к содержит дубликаты, если она получена из нескольких одинаковых по составу и порядку более коротких колод карт Х (также содержащих, возможно, повторяющиеся карты), которые были сложены подряд в одну общую колоду ХХ… Х, а затем получившаяся таким образом большая колода была перетасована.

Мы допускаем, что перед тасованием каждый экземпляр исходной колоды Х был как-то искажен. Под искажениями будем понимать случайное исключение, дублирование или замену отдельной карты или же последовательности подряд стоящих карт. Предположим однако, что локальные искажения в различных частях каждой из исходных колод независимы друг от друга.

Если же исследуемая колода дубликатов не содержит (то есть порядок карт в ней не порожден описанным выше механизмом), будем называть порядок карт в колоде правильным.

Формулировка проблемы

Задача состоит в том, чтобы по известной последовательности карт в колоде К проверить гипотезу Н0 о том, что порядок карт в К – правильный, то есть К не содержит дубликатов. Если гипотеза Н0 отвергается, то требуется определить величины сдвигов между экземплярами исходной колоды Х, расположенными в колоде К (и не до конца разрушенными при тасовании – см. рис. 17).

Для решения этой задачи сформулируем следствие гипотезы Н0, допускающее проверку методами математической статистики.

Разбиение большой колоды

Пусть общее число карт в колоде К равно n и из них m различных. Разобъем колоду К на отрезки одинаковой длины:

К = (К1, К2,…, КN),

где через N обозначено общее количество отрезков разбиения. Пусть каждый из этих отрезков содержит p карт. Разбиение выберем так, чтобы число карт в отрезке разбиения было существенно меньше общего числа карт в колоде К:

p «е