Империя – II - Фоменко Анатолий Тимофеевич (мир бесплатных книг .TXT) 📗
Простейший отрезок колоды – это две последовательно расположенные в ней карты. (Такие карты мы в дальнейшем будем называть картами-соседями.) Если имеющаяся в нашем распоряжении большая колода действительно была получена с помощью описанного выше механизма «блочного тасования» из нескольких одинаковых малых колод, то многие из карт-соседей в ней были соседями и в исходных малых колодах.
Конечно, в ходе тасования появятся и новые «ложные» пары карт-соседей. Но все же доля «истинных» (исходных) соседей среди всех пар карт-соседей большой колоды будет значительной.
Для нас важно, что эта доля будет оказывать существенное влияние на статистический характер распределения подобных пар в большой колоде. При этом, «ложные» соседи создадут, естественно, некоторый «случайный шум», смазывающий картину распределения в колоде «истинных» соседей. Однако систематическую часть этого шума удается скомпенсировать, а случайная оказывается невелика в реальных примерах (см. ниже).
Используя описанную модельную задачу, перейдем к неформальному описанию методик статистического анализа хронологических списков.
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 экземпляров этой пары были разъединены при тасовании.
Вероятность этого события мала.
С другой стороны, для «ложной» пары карт-соседей условием попадания в указанную совокупность является случайная встреча этих карт при тасовании, что при неполном «блочном» тасовании также маловероятно.
Таким образом, большинство «истинных» пар карт-соседей попадут в нашу совокупность, а большинство «ложных» – не попадут в нее. В итоге, существенную часть этой совокупности составят «истинные» пары карт-соседей.
Рассмотрев все пары карт, которые где-либо в К оказались соседями, и вычислив для каждой такой пары значение разнесения (то есть количество карт, разделяющих эту пару в колоде К), мы получим набор целых чисел – значений разнесения между соседями в К.
По этому набору построим график – гистограмму частот разнесений карт-соседей следующим образом. Отложим по горизонтальной оси все возможные значения разнесений между картами в колоде К (ясно, что разнесения не могут превосходить длины К), а по вертикальной оси – частоту, с которой данное значение встречается в наборе разнесений.
По такой гистограмме легко выделяются «необычно» частые значения разнесений: на местах таких значений гистограмма имеет ярко выраженный локальный максимум (всплеск). Например, если гистограмма частот разнесений карт-соседей имеет вид как на рис. 18, то существует два «необычно частых» значения разнесений: р1 и р2. Если «необычно» частых значений разнесения между картами-соседями в колоде К нет, то соответствующая гистограмма вообще не будет содержать всплесков (доказательство см. в главе 2). В этом случае следует предположить, что дубликатов описанного выше типа в колоде К нет.
В противном случае, дубликаты по-видимому имеется и их следует проанализировать. Сдвиги между дубликатами (исходными колодами) в этой структуре определяются как значения, на которых гистограмма делает всплески.
4. 7. Метод построения матриц связей.
Предназначен для поиска дубликатов в хронологических списках
Здесь мы на приведенном выше модельном примере изложим лишь общую идею методики. Метод был предложен авторами в [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 колоды К на два множества: множество пар-дубликатов (в статистическом смысле) и множество «независимых» пар.
