хронологических списков.

     4. 6. МЕТОД ГИСТОГРАММ ЧАСТОТ РАЗНЕСЕНИЯ СВЯЗАННЫХ ИМЕН.

         ОПРЕДЕЛЯЕТ ВЕЛИЧИНЫ СДВИГОВ МЕЖДУ ДУБЛИКАТАМИ В
                     ХРОНОЛОГИЧЕСКИХ СПИСКАХ
     Здесь мы на модельном примере изложим идею и  основные  шаги
методики. На формальном уровне она изложена в главе 2.

     Обозначим  буквой  К  большую  перетасованную  колоду  карт,
описанную выше. Наша задача -- ОПРЕДЕЛИТЬ ВЕЛИЧИНЫ  СДВИГОВ  МЕЖДУ
ЭКЗЕМПЛЯРАМИ МАЛЫХ ИСХОДНЫХ КОЛОД В К.

     Пусть к к -- некая пара последовательных карт в К (то есть к  и
            1 2                                               1
к -- соседи). Предположим, что к  и к -- ``истинные'' соседи, то есть

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

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

     Это -- идеальная  ситуация. В  реальности, конечно, по
экземплярам одной только пары к к  в колоде К  судить  о  сдвигах
                               1 2
между дубликатами (малыми колодами) в К нельзя, даже  если  сама
пара к к -- ``истинная''. В самом деле  некоторые  экземпляры  этой
      1 2
пары  могут  случайным  образом  быть  разбиты  при  тасовании  и
информация о соответствущем сдвиге в этом  случае  потеряется.

     С  другой  стороны, среди  экземпляров  пары   к к    могут
                                                      1 2
встретиться и ``ложные'', случайно возникшие  при  тасовании, и  в
этом случае  мы  зарегистрируем  ложный  сдвиг. Кроме  того, мы
заранее не знаем -- ``истиная'' ли данная пара карт-соседей в К  или
нет.

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

                           1    2
Итак, ПОДСЧИТАЕМ РАССТОЯНИЯ МЕЖДУ ВСЕМИ  ПАРАМИ  КАРТ  В  К, ПРИ
УСЛОВИИ ОДНАКО, ЧТО ХОТЯ БЫ В ОДНОМ МЕСТЕ КОЛОДЫ К ЭТИ (ТАКИЕ ЖЕ)
КАРТЫ ВСЕ ЖЕ СТОЯТ РЯДОМ (ЯВЛЯЮТСЯ СОСЕДЯМИ).

     В чем смысл этого  условия? Оно  позволяет  выделить  такую
совокупность  пар  карт, в   которой  ``истинные'' карты-соседи
составляют заметную долю. В самом деле, пусть к к  -- ``истинная''
                                               1 2
пара карт-соседей. Поскольку все исходные малые  колоды  были  до
тасования одинаковы, то эта пара существовала перед тасованием  в
N экземплярах (где N -- число исходных  малых  колод).

     Чтобы данная  пара  карт  НЕ  ПОПАЛА  в  нашу  совокупность,
необходимо, чтобы ВСЕ N экземпляров этой  пары  были  разъединены
при тасовании.

     Вероятность  этого  события  МАЛА.

     С другой стороны, для ``ложной'' пары  карт-соседей  условием
ПОПАДАНИЯ в указанную  совокупность  является  случайная  встреча
этих карт при тасовании, что  при  неполном ``блочном'' тасовании
ТАКЖЕ МАЛОВЕРОЯТНО.

     Таким  образом, большинство ``ИСТИННЫХ'' пар   карт-соседей
ПОПАДУТ в нашу совокупность, а большинство ``ЛОЖНЫХ'' -- НЕ  ПОПАДУТ
в нее. В итоге, существенную  часть  этой  совокупности  составят
``истинные'' пары карт-соседей.

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

     По  этому  набору  построим  график -- ГИСТОГРАММУ   ЧАСТОТ
РАЗНЕСЕНИЙ   КАРТ-СОСЕДЕЙ   следующим   образом. Отложим    по
горизонтальной  оси  все  возможные  значения  разнесений   между
картами в колоде К (ясно, что разнесения  не  могут  превосходить
длины К), а по вертикальной  оси -- частоту, с  которой  данное
значение встречается в наборе разнесений.

     По такой  гистограмме  легко  выделяются ``необычно'' частые
значения разнесений: на местах таких значений  гистограмма  имеет
ярко выраженный  локальный  максимум  (всплеск). Например, если
гистограмма частот  разнесений  карт-соседей  имеет  вид  как  на
рис. 18, то существует два ``необычно частых'' значения  разнесений:
р  и р.

 1    2
     Если  ``необычно'' частых   значений    разнесения    между
картами-соседями в колоде К нет, то  соответствующая  гистограмма