Полное факториальное моделирование равномерных последовательностей целых случайных величин

8 / 18

Полное факториальное моделирование равномерных последовательностей…
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 5 139
Необходимость. Доказательство необходимости заключается в том, что следует
указать последовательность действий, позволяющих вычислить номер r для любой
случайной последовательности .
r d D Воспользуемся верхними индексами для
обозначения произвольной последовательности 1 2 1 , , , , , , , z n n d d d d d d     
явно подчеркивая, что индекс 1, . z n     Всего в множестве D находятся ! n после-
довательностей. Разобьем D на n непересекающихся подмножеств 1 2 ... n D D D  
по условию упорядоченности. Отметим свойство, что в подмножество 1, D в силу
упорядоченности D, войдут все последовательности, начиная с числа 1, в подмно-
жество 2 D — все последовательности, начиная с 2 и т. д. Размер каждого подмно-
жества, по свойству факториала  
! 1 !, n n n  одинаковый
       
1 2 ... 1 !.
n card D card D card D n    
Представим результирующий номер r последовательности d как частичную
сумму
1 2 . . .. n r r r r    
В зависимости от значения 1
z d D вычислим
     
1
1
1
1 1 !.
z
i
i
r card D z n


    
Перебирая итерационно числа 2 1 , , n d d   в заданной последовательности
d, получаем соответствующие частичные значения 2 3 1 , , , . n r r r   Последнее
значение 1. n r  Итоговый номер r определяется вычисленной суммой
1
.
n
i
i
r r

 
Необходимость доказана.
Достаточность. Пусть задан номер 1, ! , r n      используя который функ-
ция r f F позволяет получить соответствующую последовательность .
r d D
По прежнему будем полагать, что получаемая последовательность будет состо-
ять из элементов 1 2 1 , , , , . n n
r r r r r d d d d d     Разобьем D на n непересекающихся
подмножеств 1 2 ... n D D D   по условию упорядоченности. Опять используем
свойство, что в подмножество 1, D в силу упорядоченности D, войдут все после-
довательности, начиная с числа 1, в подмножество 2 D — последовательности,
начиная с 2 и т. д. Размер каждой группы, по свойству факториала  
! 1 !, n n n 
одинаковый
       
1 2 ... 1 !.
n ng card D card D card D n     
Это позволяет определить номер m предыдущей группы, относительно элемен-
та 1
r d как результат целочисленного деления на число элементов ng в подмноже-
стве факториального представления: