Империя – II

17).

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

Ясно, что поскольку тасование – это случайная процедура, то поставленная задача не может иметь однозначного (детерминированного) ответа. Оказывается, что ее можно все же попытаться решить вероятностными методами. Естественный путь к такому решению состоит в исследовании похожих друг на друга кусков (отрезков) перетасованной большой колоды.

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

Но отрезок большой колоды, не изменившийся при тасовании, является, очевидно, также отрезком одного из экземпляров исходной малой колоды. Накопив информацию о большом количестве таких неискаженных кусков, мы сможем восстановить структуру исходных колод «по частям». Это – общая идея, которая лежит в основе методов, излагаемых ниже, в главах 2 и 3.

4. 5. Как найти величины хронологических сдвигов

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

Предположим, что два экземпляра исходной малой колоды сдвинуты в большой колоде на величину Д (то есть между соответствующими картами этих колод расположено приблизительно Д карт в большой колоде). Это означает, что в большой колоде имеется очень много одинаковых (или похожих друг на друга, если допустить возможность искажений) кусков, «разнесенных» в ней на величину Д (карт).

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

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

Простейший отрезок колоды – это две последовательно расположенные в ней карты. (Такие карты мы в дальнейшем будем называть картами-соседями.) Если имеющаяся в нашем распоряжении большая колода действительно была получена с помощью описанного выше механизма «блочного тасования» из нескольких одинаковых малых колод, то многие из карт-соседей в ней были соседями и в исходных малых колодах.

Конечно, в ходе тасования появятся и новые «ложные» пары карт-соседей. Но все же доля «истинных» (исходных) соседей среди всех пар карт-соседей большой колоды будет значительной.

Для нас важно, что эта доля будет оказывать существенное влияние на статистический характер распределения подобных пар в большой колоде. При этом, «ложные» соседи создадут, естественно, некоторый «случайный шум», смазывающий картину распределения в колоде «истинных» соседей. Однако систематическую часть этого шума удается скомпенсировать, а случайная оказывается невелика в реальных примерах (см. ниже).

Используя описанную модельную задачу, перейдем к неформальному описанию методик статистического анализа хронологических списков.

4. 6. Метод гистограмм частот разнесения связанных имен. Определяет величины сдвигов между дубликатами в хронологических списках

Здесь мы на модельном примере изложим идею и основные шаги методики. На формальном уровне она изложена в главе 2.

Обозначим буквой К большую перетасованную колоду карт, описанную выше. Наша задача – определить величины сдвигов между экземплярами малых исходных колод в к.

Пусть k1 k2 – некая пара последовательных карт в К (то есть k1 и k2 – соседи). Предположим, что k1 и k2 – «истинные» соседи, то есть они были соседями также и в исходных малых колодах, до тасования. Тогда пары вида k1 k2, разбросанные по колоде К, будут отмечать в ней положения своих малых колод (откуда они пришли).

Сдедовательно, расстояния (разнесения) между такими парами будут равны сдвигам (разнесениям) между экземплярами малых колод в К. Это – идеальная ситуация. В реальности, конечно, по экземплярам одной только пары k1 k2 в колоде К судить о сдвигах между дубликатами (малыми колодами) в К нельзя, даже если сама пара k1 k2 – «истинная». В самом деле некоторые экземпляры этой пары могут случайным образом быть разбиты при тасовании и информация о соответствущем сдвиге в этом случае потеряется.

С другой стороны, среди экземпляров пары k1 k2 могут встретиться и «ложные», случайно возникшие при тасовании, и в этом случае мы зарегистрируем ложный сдвиг. Кроме того, мы заранее не знаем – «истиная» ли данная пара карт-соседей в К или нет.

Поэтому поступим следующим образом. Чтобы исключить потерю информации при случайном разбиении пар k1 k2 в ходе тасования, будем рассматривать карты k1 и k2 в колоде К по отдельности.

Итак, подсчитаем расстояния между всеми парами карт в К, при условии однако, что хотя бы в одном месте колоды К эти (такие же) карты все же стоят рядом (являются соседями). В чем смысл этого условия? Оно позволяет выделить такую совокупность пар карт, в которой «истинные» карты-соседи составляют заметную долю. В самом деле, пусть k1 k2 – «истинная» пара карт-соседей. Поскольку все исходные малые колоды были до тасования одинаковы, то эта пара существовала перед тасованием в N экземплярах (где N – число исходных малых колод).

Чтобы данная пара карт не попала в нашу совокупность, необходимо, чтобы все N экземпляров этой пары были разъединены при тасовании.

Вероятность этого события мала.

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

Таким образом, большинство «истинных» пар карт-соседей попадут в нашу совокупность, а большинство «ложных» – не попадут в нее. В итоге, существенную часть этой совокупности составят «истинные» пары карт-соседей.

Рассмотрев все пары карт, которые где-либо в К оказались соседями, и вычислив для каждой такой пары значение разнесения (то есть количество карт, разделяющих эту пару в колоде К), мы получим набор целых чисел – значений разнесения между соседями в К.

По этому набору построим график – гистограмму частот разнесений карт-