(Это несколько упрощает
терминологию.)
В дальнейшем, для распределений f_1, f_2, f_3 мы будем
употреблять термин "гистограмма частот". Распределения f_2 и f_3 и
вообще, условные распределения случайной величины \Вз\А при условии
наступления некоторого локального события (напомним, что
локальными мы называем события, наступления которых можно
добиться подбором имен ЛИШЬ В ОДНОЙ главе списка, как, например,
для введенных выше событий A и B), -- мы будем называть
"гистограммами частот разнесений связанных имен".
Оказывается, что распределение \Вз\А (то есть функция f_1) не
зависит от конкретного вида списка Х и его легко посчитать для
широкого класса списков.
2. 3. МАТЕМАТИЧЕСКАЯ ЛЕММА О РАЗНЕСЕНИИ СВЯЗАННЫХ ИМЕН
ЛЕММА. В том случае, когда во всех главах списка Х
содержится одно и то же количество имен, распределение
случайной величины \Вз\А задается формулой:
З 1
| -
если x=0,
P{\Вз\А = x} =| N
{ (1)
2(N -- x)
| --------Д
если 1\Д<\Аx\Д<\АN.
Ю 2
N
Здесь x -- целое. Для остальных целых x соответствующая
вероятность равна нулю.
Таким образом, для всех списков Х с главами постоянного
объема функция f одна и та же -- это линейно убывающая в
1
промежутке от 1 до N-1 функция.
ДОКАЗАТЕЛЬСТВО. Поскольку случайная величина \Вз\А определяется
по номерам глав, содержащих выбранные имена, то можно считать,
что выбираются не сами имена, а главы. Так как объем глав по
предположению постоянен, то выбор любой главы на первом шаге
осуществляется с одинаковой вероятностью равной 1/N. То же верно
и для второго шага выбора.
Рассмотрим сначала случай 1 \Д<\А x \Д<\А N. В этом случае
существует ровно N -- x возможностей фиксировать главу с меньшим
номером в паре глав, разнесенных на расстояние x в списке. Вторая
глава в этой паре имеет номер на x больший, чем первая и этим
определяется (по первой) однозначно. Учитывая, что глава с
меньшим номером может появиться как на первом, так и на втором
шаге выбора, получаем, что общее количество возможностей выбрать
пару глав, разнесенных на расстояние x( с учетом порядка выбора),
равно 2(N -- x). Вероятность выбрать наперед заданную пару глав с
2
учетом порядка выбора равна 1/N. Следовательно, по формуле
2
полной вероятности, P{\Вз\А = x} = 2(N-x)/N.
Пусть теперь x = 0. Тогда на обоих шагах выбора появляется
одна и та же глава. Всего глав N и каждая из них может быть
2
выбрана дважды подряд с вероятностью 1/N. Следовательно, P{\Вз\А=0}
= 1/N. Лемма доказана.
2. 4. НОРМИРОВКА СПИСКА ИМЕН
Как показывают расчеты для РЕАЛЬНЫХ хронологических списков,
распределение \Вз\А имеет вид (1) даже в том случае, когда объемы
глав списка равны друг другу ЛИШЬ ПРИБЛИЗИТЕЛЬНО. Это означает,
что распределение \Вз\А УСТОЙЧИВО К ВАРИАЦИЯМ в объемах глав. Однако
бывают случаи, когда хронологический список имен разбит на главы
разко РАЗЛИЧНЫЕ по объему. В этом случае список необходимо
НОРМИРОВАТЬ, разделив кратности вхождения имен в каждую главу на
объем этой главы (чтобы не рассматривать дробных кратностей можно
предварительно умножить все кратности на произведение объемов
всех глав).
После такой нормировки ОБЪЕМЫ ГЛАВ СТАНУТ ОДИНАКОВЫМИ.
Поэтому мы без ограничения общности будем считать, что
распределение вероятностей P{\Вз\А = x} является линейно убывающей
функцией на множестве целых чисел от 1 до N (причем при x=N она
равно нулю).
2. 5. МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ СПИСКОВ ИМЕН С ПРАВИЛЬНОЙ
ХРОНОЛОГИЕЙ
Исследуем структуру хронологического списка Х, сравнивая
распределение \Вз\А с распределениями \Вз\А и \Вз\А. Естественные
2 3
представления о том, как должен быть устроен правильный
хронологический список имен приводят к следующему интуитивно
очевидному утверждению:
(А) В случае ПРАВИЛЬНОЙ ХРОНОЛОГИИ списка Х, условие и \В=\А и
r s
(или и \Д:\А и ), наложенное на пару имен списка, НЕ ДОЛЖНО ВЛИЯТЬ
r s
на глобальные особенности взаимного расположения всего множества
таких же имен в списке Х.
Ясно, что УТВЕРЖДЕНИЕ (А) ТЕСНО СВЯЗАНО С ПРИНЦИПОМ
ЗАТУХАНИЯ ЧАСТОТ. В самом деле, оно означает, что локальные связи
имен в списке не должны приводить к их глобальным связям.
Так будет, если в списке нет глобальных зависимостей, а
локальные зависимости затухают. Но именно этого требует от
правильных списков принцип затухания частот.
Утверждение (А) можно формализовать с помощью введенных выше
случайных величин \Вз\А, \Вз\А и \Вз\А следующим образом.
2 3
(Б) Распределения случайных величин \Вз\А и \Вз\А, построенные по
2 3
списку с ПРАВИЛЬНОЙ ХРОНОЛОГИЕЙ, в котором отсутствует
зависимость между различными главами, ДОЛЖНЫ СОВПАДАТЬ С
РАСПРЕДЕЛЕНИЕМ \Вз\А. Графики функций f и f, построенные по такому
2 3
списку, разбитому на главы одинакового объема, должны совпадать
на промежутке от 1 до N с графиком ЛИНЕЙНО УБЫВАЮЩЕЙ функции.
Если же между близкими главами списка есть взаимная зависимость,
постепенно затухающая для все более отдаленных пар глав, то
графики функций f и f должны совпадать с графиком линейно
2 3
убывающей функции ЛИШЬ на промежутке от \Ве\А до N, где \Ве\А -- радиус
затухания зависимости в списке.
ЗАМЕЧАНИЕ. Строго говоря, это утверждение верно для
БЕСКОНЕЧНЫХ списков, так как некоторые расхождения между
распределениями \Вз\А и \Вз\А, \Вз\А могут возникать из-за КОНЕЧНОСТИ ДЛИНЫ
2 3
списка Х. Поэтому методика применима лишь к спискам достаточно
большого объема (не менее 150-200 имен).
Ясно, что утверждение (Б) является следствием утверждения
(А).
'
В самом деле, значения \Вз\А, большие, чем \Ве\А, определяются лишь
теми парами имен, которые разнесены в списке не менее, чем на \Ве
глав. Составы карт в главах, удаленных друг от друга не менее,
чем на \Ве\А номеров, по предположению, независимы друг от друга.
Утверждение (А) означает, что такая зависимость не может
возникнуть и в том случае, если мы ограничимся рассмотрением лишь
локально связанных пар имен (сопряженных, ровесников).
Таким образом, из (А) следует, что это ограничение не влияет
(в правильных списках) на вероятность появления того или иного
значения расстояний между именами в выбранной паре имен, при
условии, однако, что это расстояние не меньше, чем \Ве\А. Другими
словами, соответствующие условные распределения \Вз\А совпадают с
безусловными -- что и утверждается в (Б).
ВЫВОД
Итак, для ПРАВИЛЬНЫХ списков имен Х распределения случайных
величин \Вз\А и \Вз\А должны совпадать на отрезке [\Ве\А, N] с ЛИНЕЙНО
2 3
УБЫВАЮЩЕЙ ФУНКЦИЕЙ, равной нулю в точке x=N.
Предположим теперь, что список Х СОДЕРЖИТ ДУБЛИКАТЫ,
сдвинутые друг относительно друга на расстояния \ВД\А,.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142
терминологию.)
В дальнейшем, для распределений f_1, f_2, f_3 мы будем
употреблять термин "гистограмма частот". Распределения f_2 и f_3 и
вообще, условные распределения случайной величины \Вз\А при условии
наступления некоторого локального события (напомним, что
локальными мы называем события, наступления которых можно
добиться подбором имен ЛИШЬ В ОДНОЙ главе списка, как, например,
для введенных выше событий A и B), -- мы будем называть
"гистограммами частот разнесений связанных имен".
Оказывается, что распределение \Вз\А (то есть функция f_1) не
зависит от конкретного вида списка Х и его легко посчитать для
широкого класса списков.
2. 3. МАТЕМАТИЧЕСКАЯ ЛЕММА О РАЗНЕСЕНИИ СВЯЗАННЫХ ИМЕН
ЛЕММА. В том случае, когда во всех главах списка Х
содержится одно и то же количество имен, распределение
случайной величины \Вз\А задается формулой:
З 1
| -
если x=0,
P{\Вз\А = x} =| N
{ (1)
2(N -- x)
| --------Д
если 1\Д<\Аx\Д<\АN.
Ю 2
N
Здесь x -- целое. Для остальных целых x соответствующая
вероятность равна нулю.
Таким образом, для всех списков Х с главами постоянного
объема функция f одна и та же -- это линейно убывающая в
1
промежутке от 1 до N-1 функция.
ДОКАЗАТЕЛЬСТВО. Поскольку случайная величина \Вз\А определяется
по номерам глав, содержащих выбранные имена, то можно считать,
что выбираются не сами имена, а главы. Так как объем глав по
предположению постоянен, то выбор любой главы на первом шаге
осуществляется с одинаковой вероятностью равной 1/N. То же верно
и для второго шага выбора.
Рассмотрим сначала случай 1 \Д<\А x \Д<\А N. В этом случае
существует ровно N -- x возможностей фиксировать главу с меньшим
номером в паре глав, разнесенных на расстояние x в списке. Вторая
глава в этой паре имеет номер на x больший, чем первая и этим
определяется (по первой) однозначно. Учитывая, что глава с
меньшим номером может появиться как на первом, так и на втором
шаге выбора, получаем, что общее количество возможностей выбрать
пару глав, разнесенных на расстояние x( с учетом порядка выбора),
равно 2(N -- x). Вероятность выбрать наперед заданную пару глав с
2
учетом порядка выбора равна 1/N. Следовательно, по формуле
2
полной вероятности, P{\Вз\А = x} = 2(N-x)/N.
Пусть теперь x = 0. Тогда на обоих шагах выбора появляется
одна и та же глава. Всего глав N и каждая из них может быть
2
выбрана дважды подряд с вероятностью 1/N. Следовательно, P{\Вз\А=0}
= 1/N. Лемма доказана.
2. 4. НОРМИРОВКА СПИСКА ИМЕН
Как показывают расчеты для РЕАЛЬНЫХ хронологических списков,
распределение \Вз\А имеет вид (1) даже в том случае, когда объемы
глав списка равны друг другу ЛИШЬ ПРИБЛИЗИТЕЛЬНО. Это означает,
что распределение \Вз\А УСТОЙЧИВО К ВАРИАЦИЯМ в объемах глав. Однако
бывают случаи, когда хронологический список имен разбит на главы
разко РАЗЛИЧНЫЕ по объему. В этом случае список необходимо
НОРМИРОВАТЬ, разделив кратности вхождения имен в каждую главу на
объем этой главы (чтобы не рассматривать дробных кратностей можно
предварительно умножить все кратности на произведение объемов
всех глав).
После такой нормировки ОБЪЕМЫ ГЛАВ СТАНУТ ОДИНАКОВЫМИ.
Поэтому мы без ограничения общности будем считать, что
распределение вероятностей P{\Вз\А = x} является линейно убывающей
функцией на множестве целых чисел от 1 до N (причем при x=N она
равно нулю).
2. 5. МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ СПИСКОВ ИМЕН С ПРАВИЛЬНОЙ
ХРОНОЛОГИЕЙ
Исследуем структуру хронологического списка Х, сравнивая
распределение \Вз\А с распределениями \Вз\А и \Вз\А. Естественные
2 3
представления о том, как должен быть устроен правильный
хронологический список имен приводят к следующему интуитивно
очевидному утверждению:
(А) В случае ПРАВИЛЬНОЙ ХРОНОЛОГИИ списка Х, условие и \В=\А и
r s
(или и \Д:\А и ), наложенное на пару имен списка, НЕ ДОЛЖНО ВЛИЯТЬ
r s
на глобальные особенности взаимного расположения всего множества
таких же имен в списке Х.
Ясно, что УТВЕРЖДЕНИЕ (А) ТЕСНО СВЯЗАНО С ПРИНЦИПОМ
ЗАТУХАНИЯ ЧАСТОТ. В самом деле, оно означает, что локальные связи
имен в списке не должны приводить к их глобальным связям.
Так будет, если в списке нет глобальных зависимостей, а
локальные зависимости затухают. Но именно этого требует от
правильных списков принцип затухания частот.
Утверждение (А) можно формализовать с помощью введенных выше
случайных величин \Вз\А, \Вз\А и \Вз\А следующим образом.
2 3
(Б) Распределения случайных величин \Вз\А и \Вз\А, построенные по
2 3
списку с ПРАВИЛЬНОЙ ХРОНОЛОГИЕЙ, в котором отсутствует
зависимость между различными главами, ДОЛЖНЫ СОВПАДАТЬ С
РАСПРЕДЕЛЕНИЕМ \Вз\А. Графики функций f и f, построенные по такому
2 3
списку, разбитому на главы одинакового объема, должны совпадать
на промежутке от 1 до N с графиком ЛИНЕЙНО УБЫВАЮЩЕЙ функции.
Если же между близкими главами списка есть взаимная зависимость,
постепенно затухающая для все более отдаленных пар глав, то
графики функций f и f должны совпадать с графиком линейно
2 3
убывающей функции ЛИШЬ на промежутке от \Ве\А до N, где \Ве\А -- радиус
затухания зависимости в списке.
ЗАМЕЧАНИЕ. Строго говоря, это утверждение верно для
БЕСКОНЕЧНЫХ списков, так как некоторые расхождения между
распределениями \Вз\А и \Вз\А, \Вз\А могут возникать из-за КОНЕЧНОСТИ ДЛИНЫ
2 3
списка Х. Поэтому методика применима лишь к спискам достаточно
большого объема (не менее 150-200 имен).
Ясно, что утверждение (Б) является следствием утверждения
(А).
'
В самом деле, значения \Вз\А, большие, чем \Ве\А, определяются лишь
теми парами имен, которые разнесены в списке не менее, чем на \Ве
глав. Составы карт в главах, удаленных друг от друга не менее,
чем на \Ве\А номеров, по предположению, независимы друг от друга.
Утверждение (А) означает, что такая зависимость не может
возникнуть и в том случае, если мы ограничимся рассмотрением лишь
локально связанных пар имен (сопряженных, ровесников).
Таким образом, из (А) следует, что это ограничение не влияет
(в правильных списках) на вероятность появления того или иного
значения расстояний между именами в выбранной паре имен, при
условии, однако, что это расстояние не меньше, чем \Ве\А. Другими
словами, соответствующие условные распределения \Вз\А совпадают с
безусловными -- что и утверждается в (Б).
ВЫВОД
Итак, для ПРАВИЛЬНЫХ списков имен Х распределения случайных
величин \Вз\А и \Вз\А должны совпадать на отрезке [\Ве\А, N] с ЛИНЕЙНО
2 3
УБЫВАЮЩЕЙ ФУНКЦИЕЙ, равной нулю в точке x=N.
Предположим теперь, что список Х СОДЕРЖИТ ДУБЛИКАТЫ,
сдвинутые друг относительно друга на расстояния \ВД\А,.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142