Правильный хронологический список имен

В главе 1 было введено понятие хронологического списка имен, снабженного разбиением на главы и приведены примеры реальных хронологических списков. В настоящем разделе мы рассмотрим задачу проверки гипотезы Н_0 о том, что хронология того или иного хронологического списка имен является правильной.

Уточним понятие правильного списка по сравнению с определением, данным в главе 1. А именно, будем называть хронологию списка имен Х правильной, если список не является результатом размножения и последующего «поблочного тасования» (склейки со сдвигом и локального перемешивания) некоторого другого, более короткого списка Y. В противном случае будем говорить, что список Х содержит дубликаты. Под дубликатами понимаются первоначально одинаковые (при тасовании они могут быть искажены) отрезки различных экземпляров списка Y, содержащиеся в Х (см рис. 17).

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

2. 2. Сопряженные имена и имена-ровесники.
Математический формализм

Следуя описанной в предыдущем разделе методике, рассмотрим вероятностную схему случайного равновероятного выбора с возвращением двух имен из списка Х и определим случайную величину з – разнесение выбранной пары имен.

Напомним обозначения характеристик списка Х: n – общее число имен в списке Х (с учетом кратности их вхождения в список); m – число различных имен списка Х;

N – число глав списка Х.

Имена списка Х мы будем обозначать буквами a_i, где индекс указывает на порядковый номер данного имени в списке:

X = a_1, a_2,…, a_N.

Обозначим через I множество различных имен списка Х. Это множество состоит из m имен (m «x «N).

Здесь x – целое. Для остальных целых x соответствующая вероятность равна нулю.

Таким образом, для всех списков Х с главами постоянного объема функция f1 одна и та же – это линейно убывающая в промежутке от 1 до N-1 функция.

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

Поскольку случайная величина з определяется по номерам глав, содержащих выбранные имена, то можно считать, что выбираются не сами имена, а главы. Так как объем глав по предположению постоянен, то выбор любой главы на первом шаге осуществляется с одинаковой вероятностью равной 1/N. То же верно и для второго шага выбора.

Рассмотрим сначала случай 1 «x «N. В этом случае существует ровно N – x возможностей фиксировать главу с меньшим номером в паре глав, разнесенных на расстояние x в списке. Вторая глава в этой паре имеет номер на x больший, чем первая и этим определяется (по первой) однозначно. Учитывая, что глава с меньшим номером может появиться как на первом, так и на втором шаге выбора, получаем, что общее количество возможностей выбрать пару глав, разнесенных на расстояние x (с учетом порядка выбора), равно 2(N – x). Вероятность выбрать наперед заданную пару глав с учетом порядка выбора равна 1/N^2. Следовательно, по формуле полной вероятности, Pз = x = 2(N-x^2)/N.

Пусть теперь x = 0. Тогда на обоих шагах выбора появляется одна и та же глава. Всего глав N и каждая из них может быть выбрана дважды подряд с вероятностью 1/N^2. Следовательно, Pз = 0 = 1/N. Лемма доказана.

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