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

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. Лемма доказана.