Доказательство

а) Рассмотрим случай 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 иначе. Тогда, согласно приведенным рассуждениям,

Ph_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) равно

Дело в том, что математическое ожидание суммы случайных величин равно сумме их математических ожиданий,

а M[h_i] = Ph_i=1 = (i-1)2p/n.

Лемма доказана.

Следствие. Среднее значение связи l(u_i, u_j) двух имен, входящих в правильный хронологический список Х, не зависит от выбора пары имен (u_i, u_j) и, следовательно, является характеристикой списка Х и параметров модели.

Это среднее мы будем обозначать через а(Х). Из доказательства леммы следует, что а(Х) = 2p/n.

Генеральное (теоретическое) среднее а(Х) мы будем называть средним по размещениям в отличие от эмпирического среднего по матрице, получаемого усреднением фактических значений связи пар имен по всем парам имен, входящих в данный список Х.

Последнее название объясняется тем, что значения связи пар имен списка естественным образом составляют некоторую квадратую матрицу.

Замечание. Сформулированное выше предположение aposteriori подтверждается для реальных правильных хронологических списков (летописей) тем, что для них эмпирическое среднее по матрице практически совпадает с генеральным средним по размещениям а(Х) (вычисленным с помощью этого предположения).

Если же список содержит дубликаты, то для него, как показали расчеты, среднее по матрице обычно чуть больше, чем среднее по размещениям.

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

В соответствии с описанной в главе 1 моделью возникновения дубликатов в хронологический списках (см., например, модельную задачу о колодах карт), введем меру связи двух произвольных определяющих окрестностей Д_r, Д_s в списке Х.

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

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

Поиск по сайту: