close

Вход

Забыли?

вход по аккаунту

?

Об односторонней сходимости процесса Роббинса—Монро при малых шагах.

код для вставкиСкачать
УДК 519.245
Вестник СПбГУ. Сер. 1, 2007, вып. 4
Т. П. Красулина
ОБ ОДНОСТОРОННЕЙ СХОДИМОСТИ
ПРОЦЕССА РОББИНСА—МОНРО ПРИ МАЛЫХ ШАГАХ
1. Введение
В последнее время как в отечественной, так и в зарубежной литературе много внимания уделяется односторонней сходимости модифицированных процессов стохастической аппроксимации [1, 2]. Эти алгоритмы находят применение в медицине, биологии, сельском хозяйстве и других областях.
В данной работе доказывается односторонняя сходимость модифицированного процесса Роббинса—Монро для случая 2 A a < 1, где A — параметр шага, а — значение
производной функции регрессии в точке в, в — корень функции регрессии. Ранее рассматривался модифицированный алгоритм Роббинса—Монро при условии 2Aa > 1 [3].
2. Постановка задачи
Пусть Y ( x ) — случайная величина, зависящая от параметра x,
— функция регрессии. Необходимо оценить корень функции регрессии в , м ( в ) = и. Предполагается, что H ( y \ x ) и M ( x ) неизвестны, но можно производить наблюдения
Y ( x ) при любом фиксированном x.
Вероятностное пространство ( Q , A, P ) для определения случайных величин Y ( x , ш ) , ш G О, вводится обычным в теории стохастической аппроксимации образом
(см., например, [4], стр.108-110).
Рассмотрим модификацию процесса Роббинса—Монро, введённую Даном Анбаром. Определим следующую процедуру:
Xn + 1 = X n - a n ( Y ( X n ) + b n ) ,
(1)
где an > 0,bn > U — заданные последовательности чисел, Xi —начальная случайная величина, Y ( X n ) —наблюдения случайной величины Y ( x ) при фиксированном значении Xn.
Пример применения процесса Роббинса—Монро [5] для определения 5U% минимальной летальной дозы лекарственного препарата для подопытных животных
рассмотрен подробно [3]. Для экономии препарата и животных желательно, чтобы с некоторого момента дозы, определяемые процессом Роббинса—Монро, были меньше
оптимальной дозы. Таким свойством обладает указанный выше модифицированный процесс Роббинса—Монро.
©
Т.
П.
Красулина,
2007
где N ( ш ) — некоторое достаточно большое число.
Доказательству теоремы предпошлём ряд лемм.
Легко доказать следующее утверждение.
Лемма 1. Пусть bn > 0 — последовательность действительных чисел, для которых
P\h о.
- J ъп + —
n/ n
Ьп+1 < ( 1 - - ) &гг + НТ +¥ ' " = 1 > 2 > - - :
А
1
где 0 < p < q, A > 0.
B
Тогда Ьп < —, где B > 0 — константа, зависящая от A1 p, Ъ\. np
Далее без потери общности будем предполагать, что в = 0.
Лемма 2. Пусть Xn —процесс (1), удовлетворяющий условиям теоремы при в = 0.
Тогда для любого достаточно малого S > 0 существует w-множество F такое, что P( F ) > 1
— S и для достаточно больших n выполнено соотношение:
jxlAP<1, ^<X<p<Aa,
F
где
C'
> 0 — некоторая константа.
ДОКАЗАТЕЛЬСТВО леммы 2. Рассмотрим Xn+1.
Выберем e' > 0 и n > 0, некоторые числа, такие что
M (x) = ax + e(x)x,
где |e(x)| < e' при \x\ < n (это возможно в силу условия 3 леммы).
Возьмём натуральное число no, такое что
P ļ П W : | X k ( " ) l <п } 1 > 1 - S ,
yfc>n o
J
где S > 0 —достаточно малое число. Это можно сделать вследствие сходимости Xn ^ 0 при n ^
ж с вероятностью 1 [3]. Обозначим
3
4
Расходимость ряда C(1, ж) следует из неравенства в < Aa. Рассмотрим теперь ряд A ( 1 ,
ж). Заметим, что \ U ( X i ) < C X i 2 при \ X i \ < n в силу условия 3 теоремы, где C > 0 —
некоторая константа.
Тогда находим (множество F определено в лемме 2)
5
Очевидно, B ( l , n ) является мартингалом. Кроме того, имеем ( A a < ^ )
где C > 0 — некоторая константа.
Следовательно, по теореме Дуба (см. [6], стр. 287-288) B(1, ж) сходится с вероятностью 1.
Далее полагаем в (2) n = 1, а m ^ ж. Так как A(1, ж), B(1, ж) сходятся с вероятностью 1, а C(1,n)
стремится при n ^ ж к ж, находим
lim n A a X n +i = —ж
n —> ж
с вероятностью 1.
Значит справедливо соотношение
P ( X n < 0, n > N (w)) = 1,
где N ( w ) —некоторое достаточно большое число. Теорема
доказана.
Автор выражает благодарность В.А. Якубовичу за внимание к данной работе.
Summary
T. P. Krasulina. On one-sided convergence of the Robbins—Monro process with small steps.
In present paper we consider one-sided convergence of the Robbins—Monro process for the cases that were not
investigated earlier.
Литература
1. Красулина Т. П., Ятел Ю. О. Об оценке вероятности непревышения искомого порога алгоритмом Роббинса—
Монро // Автоматика и телемеханика. 2005. №3. С. 91-96.
2. Граничин О. Н., Поляк Б. Т. Рандомизированные алгоритмы оценивания и оптимизации при почти
произвольных помехах. М., 2003. 291 с.
3. Красулина Т. П. О стохастической аппроксимации // Автоматика и телемеханика. 1980. № 12. С. 72-75.
4. Невельсон М. Б., Хасьминский Р. З. Стохастическая аппроксимация и рекуррентное оценивание. М., 1972. 304 с.
5. Robbins H., Monro S. A stochastic approximation method // Ann. Math. Statist. 1951. Vol. 22. N1. P. 400-407.
6. ДубДж. Вероятностные процессы. М., 1956. 605 с.
Статья поступила в редакцию 17 мая 2007 г.
Документ
Категория
Без категории
Просмотров
3
Размер файла
303 Кб
Теги
сходимость, процесс, шагал, малыш, роббинс, монро, односторонней
1/--страниц
Пожаловаться на содержимое документа