Оказалось однако, что
изменение этих параметров для реальных хронологических списков
имен слабо влияет на результат.
В частности, общая структура матрицы связей оставалась
неизменной при всех рассмотренных значениях k и p (1\Д<\Аk\Д<\А7,
3\Д<\Аp\Д<\А17).
НЕНОРМИРОВАННАЯ СВЯЗЬ l_0(u_i, u_j) неудобна тем, что она не
учитывает резких различий В КРАТНОСТЯХ вхождения имен в список Х,
характерных для реальных хронологических списков. В то же время,
часто употреблямые имена естественным образом должны в среднем
чаще "случайно" есближаться в списке Х, чем имена более редкие.
Чтобы исключить влияние кратности имен на их связь, введем
следующее определение.
ОПРЕДЕЛЕНИЕ. Пусть два имени u_i и u_j входят в список Х с
кратностями k_i и k_j соответственно. Назовем НОРМИРОВАННОЙ
СВЯЗЬЮ этих имен (или просто -- СВЯЗЬЮ) число
З
| l_0(u_i, u_j)
|
---------- при iЬj,
|
k_ik_j
l(u_i, u_j) = { (*)
|
| 2l_0(u_i, u_j)
|
| ---------- при i=j, k_i>1.
Ю k_i(k_i- 1)
Для уникального имени в списке (то есть при i=j, k_i=1) понятие
связи такого имени с самим собой не вводится.
Поясним выбор нормировки в этом определении. Эта
нормировка выбиралась так, чтобы связь любой пары имен из
списка Х являлась бы случайной величиной со средним, не
зависящим от выбора этой пары.
При этом предполагалось, что вероятностный механизм
возникновения правильного хронологического списка Х таков, что
при условии, что нам известно все множество имен списка, но
неизвестен их порядок, все перестановки имен (все варианты выбора
их порядка) равновероятны. Другими словами, мы вводим следующее
предположение.
ПРЕДПОЛОЖЕНИЕ.
ЗНАНИЕ ЛИШЬ НЕУПОРЯДОЧЕННОГО МНОЖЕСТВА ИМЕН ПРАВИЛЬНОГО
ХРОНОЛОГИЧЕСКОГО СПИСКА Х НЕ МОЖЕТ НЕСТИ В СЕБЕ НИКАКОЙ
ИНФОРМАЦИИ О ПОРЯДКЕ СЛЕДОВАНИЯ ЭТИХ ИМЕН В СПИСКЕ Х.
В этом предположении справедлива следующая лемма.
ЛЕММА 1. Пусть дан правильный хронологический список Х.
Предположим, что максимальная кратность имени в этом списке, а
также параметр p (длина связывающей окрестности) много меньше
длины списка Х. Тогда среднее значение ненормированной связи двух
имен u_i и u_j, входящих в список Х с кратностями k_i и k_j
соответственно, пропорционально числу
З
| k_ik_j при iЬj,
c(u_i, u_j) = c(k_i, k_j) = {
|
k_i(k_i-1)/2 при i=j.
Ю
ДОКАЗАТЕЛЬСТВО.
а) Рассмотрим случай iЬj. Схему равновероятных размещений
имен в списке Х можно представить как итог последовательного
размещения n имен по n местам в списке. При этом, каждое имя
равновероятно занимает одно из оставшихся свободными мест.
Очередность размещения имен может быть выбрана произвольно, но
будучи выбранной должна быть фиксирована.
Поэтому можно считать, что перед размещением k_j экземпляров
имени u_j все k_i экземпляров имени u_i уже размещены. По
предположению, k_i, k_j, p \а<\А n (напомним, что n обозначает длину
списка Х). Поэтому числом случаев, когда два экземпляра имени u_i
оказались в списке Х рядом (на расстоянии, меньшем, чем p) можно
пренебречь по сравнению с общим числом способов размещения k_i
экземпляров имени u_i в списке Х.
Представим теперь размещение k_j экземпляров имени u_j в виде
последовательности испытаний Бернулли, причем успехом в одном
испытании будем считать попадание в связывающую окрестность к
одному из уже размещенных экземпляров имени u_i. Тогда значение
ненормированной связи l_0(u_i, u_j) равно числу успехов в этой схеме
Бернулли.
Вероятность успеха в одном испытании при этом
пропорциональна числу k_i уже размещенных имен u_i (точнее говоря,
пренебрегая влиянием случайного перекрытия связывающих
окрестностей этих имен, получаем, что эта вероятность равна
2pk_i/n). Общее количество испытаний при этом равно k_j. Среднее
число успехов (=среднее значение ненормированной связи l_0(u_i, u_j))
пропорционально произведению вероятности успеха в одном испытании
на число испытаний, то есть пропорционально k_ik_j. Это и утверждается
в лемме.
б) Рассмотрим случай i=j. Выберем последовательность
размещения имен таким образом, чтобы сначала размещались все k_i
экземпляров имени u_i, а затем -- все остальные имена. Пусть первый
экземпляр имени u_i уже размещен. Вероятность того, что при
размещении второго экземпляра он попадет в связывающую
окрестность к уже размещенному первому экземпляру этого имени,
равна 2p/n (здесь мы пренебрегаем вероятностью того, что первый
экземпляр попал на самый край списка, и захват его связывающей
окрестности оказался меньше, чем 2p, по сравнению с вероятностью
того, что это не так).
Аналогично, пренебрегая малыми вероятностями перекрытий
связывающих окрестностей (слагаемыми второго порядка), получаем,
что третий экзеипляр имени u_i попадает в связывающую окрестность
к одному из уже размещенных экземпляров с вероятностью 2(2p/n) и
т. д. Для i-того экземпляра эта вероятность равно (i-1)2p/n.
Введем случайные величины \Вh\А_i (2 \Д<\А i \Д<\А k_i), положив по
определению \Вh\А_i=1 если i-й экземпляр имени u_i при своем
размещении попал в связывающую окрестность к одному из уже
размещенных (i-1) экземпляров этого имени, и \Вh\А_i=0 иначе. Тогда,
согласно приведенным рассуждениям,
P{\Вh\А_i=1} = (i-1)2p/n, (2 \Д<\А i \Д<\А k_i).
Заметим теперь, что число "встреч" имен u_i в списке Х (где
под встречей понимается попадание пары имен в связывающую
окрестность друг к другу) равняется сумме случайных величин \Вh\А_i:
k_i
l_o(u_i, u_j) = \ВS\А \Вh\А_i.
i=2
Следовательно, математическое ожидание (среднее значение) связи
l_0(u_i, u_j) равно
k_i k_i 2p
M[l_0(u_i, u_j)] = M[ \ВS\А \Вh\А_i] = \ВS\А M[\Вh\А_i] = -- (1+... +(k_i-1))=
i=2 i=2 n
2p k_i(k_i-1)
= -- --------Д.
n 2
Дело в том, что математическое ожидание суммы случайных
величин равно сумме их математических ожиданий, а M[\Вh\А_i] = P{\Вh\А_i=1}
= (i-1)2p/n.)
Лемма доказана.
СЛЕДСТВИЕ. Среднее значение связи l(u_i, u_j) двух имен,
входящих в правильный хронологический список Х, НЕ ЗАВИСИТ от
выбора пары имен (u_i, u_j) и, следовательно, является
ХАРАКТЕРИСТИКОЙ СПИСКА Х и параметров модели.
Это среднее мы будем обозначать через \Ва\А(Х). Из
доказательства леммы следует, что \Ва\А(Х) = 2p/n.
Генеральное (теоретическое) среднее \Ва\А(Х) мы будем называть
СРЕДНИМ ПО РАЗМЕЩЕНИЯМ в отличие от эмпирического СРЕДНЕГО ПО
МАТРИЦЕ, получаемого усреднением фактических значений связи пар
имен по всем парам имен, входящих в данный список Х.
Последнее название объясняется тем, что значения связи пар
имен списка естественным образом составляют некоторую квадратую
матрицу.
ЗАМЕЧАНИЕ. Сформулированное выше предположение aposteriori
подтверждается для реальных правильных хронологических списков
(летописей) тем, что для них ЭМПИРИЧЕСКОЕ СРЕДНЕЕ ПО МАТРИЦЕ
практически совпадает с ГЕНЕРАЛЬНЫМ СРЕДНИМ ПО РАЗМЕЩЕНИЯМ \Ва\А(Х)
(вычисленным с помощью этого предположения).
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
изменение этих параметров для реальных хронологических списков
имен слабо влияет на результат.
В частности, общая структура матрицы связей оставалась
неизменной при всех рассмотренных значениях k и p (1\Д<\Аk\Д<\А7,
3\Д<\Аp\Д<\А17).
НЕНОРМИРОВАННАЯ СВЯЗЬ l_0(u_i, u_j) неудобна тем, что она не
учитывает резких различий В КРАТНОСТЯХ вхождения имен в список Х,
характерных для реальных хронологических списков. В то же время,
часто употреблямые имена естественным образом должны в среднем
чаще "случайно" есближаться в списке Х, чем имена более редкие.
Чтобы исключить влияние кратности имен на их связь, введем
следующее определение.
ОПРЕДЕЛЕНИЕ. Пусть два имени u_i и u_j входят в список Х с
кратностями k_i и k_j соответственно. Назовем НОРМИРОВАННОЙ
СВЯЗЬЮ этих имен (или просто -- СВЯЗЬЮ) число
З
| l_0(u_i, u_j)
|
---------- при iЬj,
|
k_ik_j
l(u_i, u_j) = { (*)
|
| 2l_0(u_i, u_j)
|
| ---------- при i=j, k_i>1.
Ю k_i(k_i- 1)
Для уникального имени в списке (то есть при i=j, k_i=1) понятие
связи такого имени с самим собой не вводится.
Поясним выбор нормировки в этом определении. Эта
нормировка выбиралась так, чтобы связь любой пары имен из
списка Х являлась бы случайной величиной со средним, не
зависящим от выбора этой пары.
При этом предполагалось, что вероятностный механизм
возникновения правильного хронологического списка Х таков, что
при условии, что нам известно все множество имен списка, но
неизвестен их порядок, все перестановки имен (все варианты выбора
их порядка) равновероятны. Другими словами, мы вводим следующее
предположение.
ПРЕДПОЛОЖЕНИЕ.
ЗНАНИЕ ЛИШЬ НЕУПОРЯДОЧЕННОГО МНОЖЕСТВА ИМЕН ПРАВИЛЬНОГО
ХРОНОЛОГИЧЕСКОГО СПИСКА Х НЕ МОЖЕТ НЕСТИ В СЕБЕ НИКАКОЙ
ИНФОРМАЦИИ О ПОРЯДКЕ СЛЕДОВАНИЯ ЭТИХ ИМЕН В СПИСКЕ Х.
В этом предположении справедлива следующая лемма.
ЛЕММА 1. Пусть дан правильный хронологический список Х.
Предположим, что максимальная кратность имени в этом списке, а
также параметр p (длина связывающей окрестности) много меньше
длины списка Х. Тогда среднее значение ненормированной связи двух
имен u_i и u_j, входящих в список Х с кратностями k_i и k_j
соответственно, пропорционально числу
З
| k_ik_j при iЬj,
c(u_i, u_j) = c(k_i, k_j) = {
|
k_i(k_i-1)/2 при i=j.
Ю
ДОКАЗАТЕЛЬСТВО.
а) Рассмотрим случай iЬj. Схему равновероятных размещений
имен в списке Х можно представить как итог последовательного
размещения n имен по n местам в списке. При этом, каждое имя
равновероятно занимает одно из оставшихся свободными мест.
Очередность размещения имен может быть выбрана произвольно, но
будучи выбранной должна быть фиксирована.
Поэтому можно считать, что перед размещением k_j экземпляров
имени u_j все k_i экземпляров имени u_i уже размещены. По
предположению, k_i, k_j, p \а<\А n (напомним, что n обозначает длину
списка Х). Поэтому числом случаев, когда два экземпляра имени u_i
оказались в списке Х рядом (на расстоянии, меньшем, чем p) можно
пренебречь по сравнению с общим числом способов размещения k_i
экземпляров имени u_i в списке Х.
Представим теперь размещение k_j экземпляров имени u_j в виде
последовательности испытаний Бернулли, причем успехом в одном
испытании будем считать попадание в связывающую окрестность к
одному из уже размещенных экземпляров имени u_i. Тогда значение
ненормированной связи l_0(u_i, u_j) равно числу успехов в этой схеме
Бернулли.
Вероятность успеха в одном испытании при этом
пропорциональна числу k_i уже размещенных имен u_i (точнее говоря,
пренебрегая влиянием случайного перекрытия связывающих
окрестностей этих имен, получаем, что эта вероятность равна
2pk_i/n). Общее количество испытаний при этом равно k_j. Среднее
число успехов (=среднее значение ненормированной связи l_0(u_i, u_j))
пропорционально произведению вероятности успеха в одном испытании
на число испытаний, то есть пропорционально k_ik_j. Это и утверждается
в лемме.
б) Рассмотрим случай i=j. Выберем последовательность
размещения имен таким образом, чтобы сначала размещались все k_i
экземпляров имени u_i, а затем -- все остальные имена. Пусть первый
экземпляр имени u_i уже размещен. Вероятность того, что при
размещении второго экземпляра он попадет в связывающую
окрестность к уже размещенному первому экземпляру этого имени,
равна 2p/n (здесь мы пренебрегаем вероятностью того, что первый
экземпляр попал на самый край списка, и захват его связывающей
окрестности оказался меньше, чем 2p, по сравнению с вероятностью
того, что это не так).
Аналогично, пренебрегая малыми вероятностями перекрытий
связывающих окрестностей (слагаемыми второго порядка), получаем,
что третий экзеипляр имени u_i попадает в связывающую окрестность
к одному из уже размещенных экземпляров с вероятностью 2(2p/n) и
т. д. Для i-того экземпляра эта вероятность равно (i-1)2p/n.
Введем случайные величины \Вh\А_i (2 \Д<\А i \Д<\А k_i), положив по
определению \Вh\А_i=1 если i-й экземпляр имени u_i при своем
размещении попал в связывающую окрестность к одному из уже
размещенных (i-1) экземпляров этого имени, и \Вh\А_i=0 иначе. Тогда,
согласно приведенным рассуждениям,
P{\Вh\А_i=1} = (i-1)2p/n, (2 \Д<\А i \Д<\А k_i).
Заметим теперь, что число "встреч" имен u_i в списке Х (где
под встречей понимается попадание пары имен в связывающую
окрестность друг к другу) равняется сумме случайных величин \Вh\А_i:
k_i
l_o(u_i, u_j) = \ВS\А \Вh\А_i.
i=2
Следовательно, математическое ожидание (среднее значение) связи
l_0(u_i, u_j) равно
k_i k_i 2p
M[l_0(u_i, u_j)] = M[ \ВS\А \Вh\А_i] = \ВS\А M[\Вh\А_i] = -- (1+... +(k_i-1))=
i=2 i=2 n
2p k_i(k_i-1)
= -- --------Д.
n 2
Дело в том, что математическое ожидание суммы случайных
величин равно сумме их математических ожиданий, а M[\Вh\А_i] = P{\Вh\А_i=1}
= (i-1)2p/n.)
Лемма доказана.
СЛЕДСТВИЕ. Среднее значение связи l(u_i, u_j) двух имен,
входящих в правильный хронологический список Х, НЕ ЗАВИСИТ от
выбора пары имен (u_i, u_j) и, следовательно, является
ХАРАКТЕРИСТИКОЙ СПИСКА Х и параметров модели.
Это среднее мы будем обозначать через \Ва\А(Х). Из
доказательства леммы следует, что \Ва\А(Х) = 2p/n.
Генеральное (теоретическое) среднее \Ва\А(Х) мы будем называть
СРЕДНИМ ПО РАЗМЕЩЕНИЯМ в отличие от эмпирического СРЕДНЕГО ПО
МАТРИЦЕ, получаемого усреднением фактических значений связи пар
имен по всем парам имен, входящих в данный список Х.
Последнее название объясняется тем, что значения связи пар
имен списка естественным образом составляют некоторую квадратую
матрицу.
ЗАМЕЧАНИЕ. Сформулированное выше предположение aposteriori
подтверждается для реальных правильных хронологических списков
(летописей) тем, что для них ЭМПИРИЧЕСКОЕ СРЕДНЕЕ ПО МАТРИЦЕ
практически совпадает с ГЕНЕРАЛЬНЫМ СРЕДНИМ ПО РАЗМЕЩЕНИЯМ \Ва\А(Х)
(вычисленным с помощью этого предположения).
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