Обработка экспериментальных данных. Роганов В.Р - 123 стр.

N записей, получаем задачу — как корректно выбрать из этого массива n

записей, при условии, что n < N .

    Наиболее очевиден подход, когда любая запись выбирается с одной и той
же вероятностью близкой к n / N . Однако, при использовании такого метода в
выборке получается n записей только в среднем, причем стандартное
отклонение равно             n(1 − (n / N )) , выборка может оказаться или слишком

большой, или слишком малой для достижения желаемых результатов.

    В литературе [Кнут] приводится алгоритм "корректной выборки"
лишенный этого недостатка. Идея такого подхода — если m записей уже
отобрано, мы должны включить (t + 1) -ю запись в выборку с вероятностью
(n − m) /( N − t ) .   Эта вероятность выражается именно такой величиной,
поскольку из всех возможных способов выборка n записей из N таким
образом, что m из них отбираются из первых t , в точности

⎛ N − t − 1⎞ ⎛ N − t ⎞ n − m
⎜⎜          ⎟⎟ / ⎜⎜   ⎟⎟ =    ,
 ⎝ n − m − 1⎠ ⎝ n − m ⎠ N − t

с возможной последующей выборкой t + 1 элемента.

    Рассмотрим алгоритм выборки чисел из заданной последовательности,
решающий задачу выбора n записей из N , где 0 < n ≤ N . Данный алгоритм
реализует описанный выше метод "корректной выборки":

    1. t = 0 ,         m=0

    2. Выработать             псевдослучайное       число     U,      равномерно
распределенное между нулем и единицей.

    3. If ( N − t )U ≥ n − m then Включить запись в выборку; m = m + 1 , t = t + 1
                                  else

    4. t = t + 1 .

    5. Повторить шаги 2-4.



                                           123