close

Вход

Забыли?

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

?

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

код для вставкиСкачать
УДК 519.245
Вестник СПбГУ. Сер. 1. 2012. Вып. 1
О СХОДИМОСТИ СНИЗУ ПРОЦЕССА РОББИНСА—МОНРО
ПРИ МАЛЫХ ШАГАХ∗
Т. П. Красулина
С.-Петербургский государственный университет,
канд. физ.-мат. наук, доцент, theorcyb@yandex.ru
Введение. В последнее время в научной литературе много внимания уделяется
односторонней сходимости модифицированных процессов стохастической аппроксимации [1, 2]. Эти алгоритмы применяются в медицине, биологии и сельском хозяйстве.
В данной работе приводятся новые условия сходимости снизу модифицированного процесса Роббинса—Монро для случая 2Aα < 1, где A — параметр шага, α —
значение производной функции регрессии в точке θ, θ — корень функции регрессии.
Эти условия являются менее ограничительными, чем в статье [3], посвященной
той же задаче.
Постановка задачи. Пусть Y (x) — случайная величина, зависящая от параметра x,
H(y/x) = P (Y (x) < y),
и пусть
+∞
Z
M (x) =
y dH(y/x)
−∞
— функция регрессии. Необходимо оценить корень функции регрессии θ, M (θ) = 0.
Предполагается, что H(y/x) и M (x) неизвестны, но можно производить наблюдения
Y (x) при любом фиксированном x.
Вероятностное пространство (Ω, U, P) для определения величин Y (x, ω), ω ∈ Ω,
вводится обычным в стохастической аппроксимации образом (см., например, [4],
с. 108–110).
Рассмотрим модификацию Роббинса—Монро, введенную Анбаром [5]. Определим
следующую процедуру:
Xn+1 = Xn − an (Yn (Xn ) + bn ),
(1)
где an ≥ 0, bn ≥ 0 — заданные последовательности чисел, X1 — начальная случайная величина, Yn (Xn ) — наблюдения случайной величины Y (x) при фиксированном
значении Xn . Предполагается, что Zn (Xn ) = Yn (Xn ) − M (Xn ) — мартингал-разность
(см. [6]).
Пример применения процесса Роббинса—Монро для определения 50% минимальной летальной дозы лекарственного препарата для подопытных животных рассмотрен в [7]. С целью экономии препарата и животных желательно, чтобы с некоторого
момента дозы, определяемые с применением процесса Анбара, были меньше искомой
дозы.
∗ Работа
c
выполнена при финансовой поддержке РФФИ (грант № 09.01.00245).
Т. П. Красулина, 2012
31
Основные результаты. Имеет место следующее утверждение.
Теорема. Пусть выполняются условия:
1) M (x) > 0 для x > θ, M (x) < 0 для x < θ, M (θ) = 0, inf |M (x)| > 0 при
ε < |x − θ| < ε−1 и любом 0 < ε < 1;
2) E Z 2 (x) ≤ K < ∞, Z(x) = Y (x) − M (x), где K > 0 — некоторая константа;
3) M (x) дифференцируемо в точке θ и M ′ (θ) = α;
4) |M (x)| ≤ C|x| + D, где C ≥ 0, D ≥ 0 — некоторые константы;
5) an = A/n, 2Aα < 1, bn = b/nβ , b > 0, A > 0, β < Aα.
Тогда
P (Xn → θ, n → ∞) = 1,
P (Xn ≤ θ, n ≥ N (ω)) = 1,
где N (ω), ω ∈ Ω, — некоторое достаточно большое число.
Условия 3 и 5 данной теоремы являются менее ограничительными, чем соответствующие условия в статье [3], а также выполняется условие, что функция регрессии
M (x) дифференцируема в искомой точке θ один раз, а не дважды. Кроме того, не
требуется, чтобы в условии 5 теоремы выполнялось β > Aα/2, как в предыдущей
работе.
Прежде, чем приступить к доказательству теоремы, приведем несколько предложений, которые используются далее.
Напомним, что последовательность чисел f (n) называется медленно меняющейся
в смысле Зигмунда, если f (n)nδ ↑, f (n)n−δ ↓ при n ≥ n0 (δ) для любого δ > 0 [8].
В дальнейшем потребуется следующий результат.
Лемма [8]. Пусть dj — сходящаяся последовательность чисел, lim dj = a > 0,
j → ∞,
j0 = min{j : dk /k < 1, k ≥ j}.
Тогда при n → ∞
γn =
n
Y
j=j0
(1 − dj /j) ≃ n−a τn ,
где τn — некоторая медленно меняющаяся последовательность чисел.
Доказательство теоремы. При выполнении условий 1, 2, 4, 5 процесс Анбара
сходится при n → ∞ с вероятностью 1,
lim Xn = θ,
n→∞
(см. [5]).
Без потери общности полагаем θ = 0. Основное соотношение (1) можно записать
в виде
Xn+1 = Xn (1 − dn /n) − an Zn (Xn ) − an bn ,
(2)
где
dn = A(α + ψ(Xn )),
32
ψ(x) → 0, x → 0,
Zn (Xn ) = Yn (Xn ) − M (Xn ).
Итерируя (2), получаем
Xn+1 = β0n X1 −
где
βkn =
n
Y
j=k+1
n
X
k=1
n
X
ak Zk (Xk )βkn −
(1 − dj /j),
ak βkn bk ,
k=1
0 ≤ k ≤ n − 1,
βnn = 1.
Далее имеем (n ≥ j0 )
n
n
X
X
ak bk γk−1 ,
ak Zk (Xk )γk−1 −
Xn+1 = γn ε0 −
k=j0
k=j0
ε0 = β0(j0 −1) X1 −
jX
0 −1
k=1
ak βk(j0 −1) Zk (Xk ) −
jX
0 −1
ak βk(j0 −1) bk ,
k=1
γn и j0 — те же самые случайные величины, что в лемме.
При n ≥ j0 справедливо представление
n
n
X
X
ak Zk (Xk )γk−1 −
ak bk γk−1 ,
Xn+1 = γn ε̄ −
k=1
где
ε̄ = ε0 +
jX
0 −1
ak Zk (Xk )k a +
jX
0 −1
ak b k k a ,
k=1
k=1
−a
(3)
k=1
γk = k при 1 ≤ k ≤ j0 , случайная величина j0 конечна с вероятностью 1.
Докажем сначала, что с вероятностью 1
n β γn
n
X
k=1
k −1 γk−1 Zk (Xk ) → 0,
n → ∞.
(4)
Используя теорию мартингалов [9] и условие 5 теоремы, нетрудно доказать, что ряд
∞
X
k −1+β Zk (Xk )
k=1
сходится с вероятностью 1.
Далее, γn nβ → 0, n → ∞ с вероятностью 1 вследствие леммы.
Кроме того, справедливо соотношение
dn+1 1 β
γn+1 (n + 1)β = γn nβ 1 −
1+
.
n+1
n
Теперь в силу условия 5 теоремы находим, что
1 dn+1 β − dn+1
1 β
1−
=1+
+o 2 <1
1+
n+1
n
n
n
при достаточно больших n.
33
Следовательно, γn nβ ↓ 0, n → ∞ с вероятностью 1. Отсюда получаем, используя
лемму Кронекера [10], что с вероятностью 1 справедливо утверждение (4).
Вследствие леммы и свойств медленно меняющихся последовательностей чисел
[8] находим, что с вероятностью 1
n β γn
n
X
k=1
ak bk γk−1 → Ab/(a − β),
n → ∞.
Очевидно также, что nβ γn ε̄ → 0, n → ∞ с вероятностью 1, так как ε̄ < ∞ с вероятностью 1, а nβ γn → 0, n → ∞ с вероятностью 1.
Из (3) следует, что с вероятностью 1
lim nβ Xn = −Ab/(a − β).
n→∞
Отсюда в силу условий теоремы вытекает ее утверждение.
Автор выражает благодарность В. А. Якубовичу и А. Х. Гелигу за внимание к
данной работе.
Литература
1. Красулина Т. П., Ятел Ю. О. Об оценке вероятности непревышения искомого порога
алгоритмом Роббинса—Монро // Автоматика и телемеханика. 2005. № 3. С. 91–96.
2. Граничин О. Н., Поляк Б. Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. М.: Наука, 2003. 291 с.
3. Красулина Т. П. Об односторонней сходимости процесса Роббинса—Монро при малых
шагах // Вестник С.-Петерб. ун-та. 2007. Сер. 1. Вып. 4. С. 67–72.
4. Невельсон М. Б., Хасьминский Р. З. Стохастическая аппроксимация и рекуррентное
оценивание. М.: Наука, 1972. 304 с.
5. Anbar D. A modified Robbins—Monro procedure approximating the zero of a regression
function from below // Ann. Statist. 1977. Vol. 5. N 1. P. 229–234.
6. Harold J., Kushner G., George Yin. Stochastic approximation algorithms and applications,
Springer Verlag. New York, 1997. 416 p.
7. Красулина Т. П. О стохастической аппроксимации // Автоматика и телемеханика.
1980. № 12. С. 72–75.
8. Гапошкин В. Ф., Красулина Т. П. О законе повторного логарифма в процессах стохастической аппроксимации // Теория вероятн. и ее прим. Т. XIX. 1974. Вып. 4. С. 879–886.
9. Дуб Дж. Вероятностные процессы. М., 1956. 605 с.
10. Лоэв М. Теория вероятностей. М., 1962. 719 с.
Статья поступила в редакцию 26 октября 2011 г.
34
Документ
Категория
Без категории
Просмотров
7
Размер файла
207 Кб
Теги
сходимость, снизу, процесс, шагал, малыш, роббинс, монро
1/--страниц
Пожаловаться на содержимое документа