Читать онлайн «Империя – II». Страница 115

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Здесь мы на приведенном выше модельном примере изложим лишь общую идею методики. Метод был предложен авторами в [10], [12]. Подробно он изложена в главе 3.

Анализ дубликатов (исходных малых колод) в колоде К можно осуществить на основе следующих простых соображений.

Предположим, что имеющаяся в нашем распоряжении колода К была действительно получена описанным выше способом из нескольких экземпляров более короткой (исходной) колоды. Рассмотрим два отрезка А1 и А2 колоды К. Будем называть отрезки А1 и А2 дубликатами, если они соотвественно содержат карты, которые в экземплярах исходной колоды находились рядом (рис. 19).

Заметим, что при этом может случиться, что отрезки А1 и А2 вовсе не содержат одинаковых карт и тем не менее, являются дубликатами. Такая ситуация возникает, когда в отрезок А при тасовании попали одни карты из некоторого малого отрезка А исходной колоды, а в отрезок А – другие карты из того же «прообраза» А (рис. 19).

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

Однако в любом случае, если А1 и А2 – действительно дубликаты, то есть содержат части, восходящие к общему прообразу А в исходной короткой колоде, то среди множества экземпляров их прообраза А, разбросанных при тасовании по колоде К и как-то искаженных при этом, должны встретиться и такие экземпляры, которые содержат как карты, попавшие из А1 в А2, так и карты, попавшие в А (на рис. 19 такой экземпляр А обведен кружком).

Следовательно, в том случае, когда А1 и А2 – дубликаты, вероятность встреч карт из А1 и А2 где-нибудь в колоде К, больше, чем аналогичная вероятность в случае, когда А1 и А2 дубликатами не являются (естественно, имеются в виду не сами экземпляры карт из А1 и А2, а такие же карты).

В самом деле, в первом случае действует описанный механизм, объединяющий карты из А1 и А2 в колоде К, а во втором – это объединение может произойти лишь чисто случайным образом.

Приведенные соображения позволяют предложить методику, разделяющую всевозможные пары отрезков А1 и А2 колоды К на два множества: множество пар-дубликатов (в статистическом смысле) и множество «независимых» пар.