Аннотация 2
Введение 4
1. Постановка задачи 6
2. Алгоритм предложенный С. Н. Постоваловым 9
2.1 Модифицированное моделирование функций вероятностей ошибок первого
и второго рода 12
2.2 Изменённый метод выделения точек пересечений линий уровня 15
3. Итерационный метод уточнения границ в SPRT 22
4. Выбор структуры данных 25
5. Реализация программы с использованием структуры S 30
5.1 Реализация программы с раздельным построением нескольких поддеревьев .. 39
6. Результаты численного моделирования 40
Заключение 45
Список использованной литературы 47
Приложение А 49
Приложение Б 50
Приложение В 51
Приложение Г 52
Приложение Д 53
Приложение Е 54
Приложение Ж 55
Приложение З 56
Приложение И 57
Приложение К 59
Приложение Л 61
Приложение М 62
Приложение Н 63
Приложение О 64
Приложение П 65
Приложение Р 66
Приложение С 70
Приложение Т 73
Приложение У 74
Приложение Ф 75
Приложение Х 76
Приложение Ц
В наше время неотъемлемой частью эксперимента является статистическая обработка результатов наблюдений. Эти результаты представляют собой значения случайных велин X, распределения которых Fe, как правило, хотя бы частично нам неизвестно. Следствием этого незнания, есть не возможность в выборе наилучшего поведения. Поэтому одной из основных задач первичной обработки эмпирических наблюдений является определение закона распределения, наиболее хорошо описывающего случайную величину, выборку которой мы наблюдали.
Для решения данной задачи мы выдвигаем ряд гипотез о принадлежности наблюдаемой выборки конкретному теоретическому закону. После чего используя статистические критерии, а именно критерии согласия, выполняем проверку насколько хорошо описывается тем или иным теоретическим законом, наблюдаемая выборка. Необходимость такой проверке обусловлена стремлением удостовериться в том, что предполагаемая модель теоретического закона не противоречит наблюдаемым данным, и использование её в дальнейшем не приведет к значительным ошибкам.
Представленный в 1933 году в работе [19] и популярный по сей день - критерий Неймана-Пирсона. Он относится к классическим методам математической статистики, в которых количество наблюдений, то есть объем выборки, на которых основывается проверка, считается постоянным для каждой конкретной задачи. К настоящему времени, также известно множество других классических критериев согласия [5,6], предназначенных для проверки как простых, так и сложных гипотез.
Однако в данной работе нас будет интересовать предложенный А. Вальдом в 1945 году подход последовательной проверки гипотез [21]. Его отличительной чертой от классического является то, что количество наблюдений, необходимых для принятия решения, зависит от значений наблюдаемых данных и, следовательно, является не определенным заранее, а случайной величиной. А. Вальд также описал последовательный метод, названый им критерием последовательных отношений вероятностей (SPRT). Позже в работе [22] была доказана оптимальность указанного критерия, как в случае принятия основной гипотезы, так и альтернативы в классе всех последовательных методов.
К преимуществам последовательного подхода можно отнести значительное сокращение количества наблюдений, необходимое для принятия решения с заданными а и в, соответственно ошибками первого и второго рода. Так для SPRT А. Вальд отмечал «It will be seen that these sequential tests usually lead to average savings of about 50% in the number of trials as compared with the current most powerful test» [21]. Но следует быть предельно осторожным обобщая данное высказывание. Так, например, в работе [9] было показано, что при определенных ситуациях последовательный подход не только не экономит в 2 раза объем требуемой выборки, а даже наоборот требует большее количество наблюдений.
Также последовательный подход обладает недостатком, заключающийся в отсутствии ограничения верхней границы наблюдений, следовательно процедуры последовательной проверки гипотез могут продолжаться неопределённо долго. Теоретически доказано, что одна из конкурирующих гипотез принимается за конечное число шагов [5, с. 115.], но для практики это неприемлемо.
Более того, для того чтобы получить критерий силы (а, в) необходимо определить критические границы - постоянные A (а, в) и B (а, в). Их точное аналитическое определение обычно чрезвычайно сложно1, поэтому на практике пользуются их оценками. Но использование оценочных значений, приводит к уменьшению фактических вероятностей ошибок первого и второго рода, следовательно, к увеличению требуемого количества испытаний.
С развитием компьютерного моделирования, стало возможно с заданной точностью вычислить точные критические границы. Так С. Н. Постовалов [7] разработал алгоритм, позволяющий это сделать и на приведенных им примерах получить сокращение объема выборки от 3% до 17%, что в случае проведения дорогостоящих экспериментов является существенным фактором. Этот алгоритм основан на переборе с достаточно малым шагом значений критических границ, построением линий равного уровня и дальнейшим определением их точек пересечения.
Однако по приведенным вычислительным затратам можно сделать вывод о необходимость значительных вычислительных ресурсов. Конечно, как отмечает автор, время работы можно уменьшить при «распараллеливании» процессов вычислений, однако это лишь незначительно позволит сократить время работы.
Таким образом, возникает потребность в создание более эффективного алгоритма для определение с заданной точностью критических границ в SPRT.
Целью данной выпускной квалификационной работы является разработка алгоритма, позволяющего с меньшими вычислительными затратами и более высокой точности находить критических границ последовательного критерия отношения правдоподобия Вальда, что обеспечит при заданных вероятностях ошибок первого и второго рода минимальное количество требуемых экспериментов при проверке простой и сложной гипотез относительно заданной альтернативы.
Для достижения указанной цели в работе необходимо решить следующие задачи:
1) изучить теоретические аспекты вычисления критических границ;
2) исследовать более детально подход предложенный С. Н. Постоваловым;
3) рассмотреть итерационные способы решения поставленной задачи;
4) разработать более эффективный алгоритм, вычисляющий критические границы с заданной точностью;
5) провести сравнительный анализ полученных алгоритмов.
В частном случае известны точные формулы для A (а, в), B (а, в) и среднего размера выборки. Например, смотреть [15]
В данной выпускной квалификационной работе мы изучили теоретические аспекты вычисления критических границ в последовательном критерии Вальда, рассмотрели и проанализировали предложенный ранее С. Н. Постоваловым и С. Я. Гродзенским подходы к численному моделированию границ. Привели пример, показывающий необходимость в ряде случаев дополнительных изменений в итерационном методе С. Я. Гродзенского. Разработали иной итерационный алгоритм без необходимости дополнительных настроек и реализовали его в виде программы на языке C++.
Помимо итерационного метода в данной работе представлен алгоритм с использованием структуры данных, эффективность которого в ходе проведения тестов оказалась выше ранее предложенных методов. Его реализация также представлена в работе.
Таким образом, были выполнены все поставленные задачи и достигнута цель данной работы.
[1] Боровков А. А. Теория вероятностей: Учеб. пособие для вузов. - 2-е изд., перераб. и доп. - М.З Наука. Гл. ред. физ.-мат. лит. 1986. - 432 с.
[2] Вальд А. Последовательный анализ. - Гос. изд-во физико-математической лит-ры, 1960.
[3] Вентцель Е. С. Исследование операций. М., Советское радио, 1972. 552 с.
[4] Гродзенский С. Я., Чесалин А. Н. Уточнение границ последовательных статистических критериев с помощью компьютерного моделирования //Метрология. - 2019. - №. 3. - С. 30-45.
[5] Леман Э. «Проверка статистических гипотез» Издательство: Главная редакция физико-математической литературы издательства. - 1979.
[6] Лемешко Б. Ю., Лемешко С. Б., Постовалов С. Н. Сравнительный анализ мощности критериев согласия при близких конкурирующих гипотезах. I. Проверка простых гипотез //Сибирский журнал индустриальной математики. - 2008. - Т. 11. - №. 2. - С. 96-111.
[7] Постовалов С. Н. Проверка простых и сложных гипотез с использованием последователь-ного критерия Вальда //Доклады Академии наук высшей школы Российской Федерации. - 2011.-№. 2.-С. 140-150.
[8] Чеонг О. [и др.]. Вычислительная геометрия. Алгоритмы и приложения / О. Чеонг, М. де Берг, М. ван Кревельд, М. Овермарс, Litres, 2022. 440 c.
[9] Bechhofer R. A note on the limiting relative efficiency of the Wald sequential probability ratio test //Journal of the American Statistical Association. - 1960. - Т. 55. - №. 292. - С. 660-663.
[10] Blelloch G. E. Space-efficient dynamic orthogonal point location, segment intersection, and range reporting //SODA. - 2008. - Т. 8. - С. 894-903.
[11] Brass P Advanced Data Structures / P. Brass, Cambridge University Press, 2019. 472 c.
[12] Chazelle B. A Functional Approach to Data Structures and Its Use in Multidimensional Searching // SIAM Journal on Computing. 1988. № 3 (17). C. 427-462.
[13] Gabow H. N., Bentley J. L., Tarjan R. E. Scaling and related techniques for geometry problems Not Known: ACM Press, 1984.C. 135-143.
[14] Gabrielsen P. Three-sided Range Reporting in External Memory : дис. - Aarhus Universitet, Datalogisk Institut, 2016.
[15] Girshick M. A. Contributions to the theory of sequential analysis, II, III //The Annals of Mathematical Statistics. - 1946. - С. 282-298.
..22