Максимизация времени выхода управляемого случайного блуждания на границу квадранта

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 519. 217. 8−330. 46
МАКСИМИЗАЦИЯ ВРЕМЕНИ ВЫХОДА УВРАВЛЯЕМВГВ СЛУЧАЙНОГО БЛУЖДАНИЯ ВА ГРАНИЦУ КВАДРАНТА1
С.В. Анулова
В каждый момент времени управление воздействует только на одну из двух координат блуждания, величина его фиксирована. Находится стратегия, оптимальная сразу для ряда критериев (среднее время выхода, вероятность невыхода и др.). Решение уравнения Беллмана для этого не потребовалось благодаря свойствам модели: симметрия, монотонность, возможность декомпозиции. Модель возникла при изучении экономических задач.
Ключевые слова: управляемое случайное блуждание, уравнение Беллмана.
ВВЕДЕНИЕ
В работе рассматривается задача управления марковским процессом. Известен подход к решению таких задач: выписывается уравнение Беллмана, находится его решение — функция выигрыша, отправляясь от функции выигрыша, находят оптимальную стратегию [1]. Главная трудность — найти функцию выигрыша. В некоторых случаях эту трудность можно обойти: напрямую предлагается некоторая стратегия и доказывается ее оптимальность. Это удается сделать, если рассматриваемый объект допускает декомпозицию, обладает свойствами симметрии или монотонности. Именно таким оказался наш объект, и мы реализовали изложенную программу. Общая постановка задачи взята из работы [2].
Рассмотрим две различные государственные политики налогообложения компаний: республиканская политика дает налоговые льготы успешным компаниям, в то время как демократическая политика дает льготы слабым компаниям, чтобы уберечь их от банкротства и не допустить роста безработицы. Какая политика эффективнее? В работе [2] показано, что это зависит от критерия оптимизации. Если требуется минимизировать среднее число обанкротившихся компаний, то численные методы дают оптимальную стратегию в виде комбинации республиканской и демократической
1 Работа выполнена при финансовой поддержке РФФИ (гранты № 07−08−739 и 07−01−541) и Президиума РАН (программа № 29).
политик. Если требуется максимизировать вероятность отсутствия банкротств, то аналитически доказана оптимальность демократической политики. Мы усиливаем последний результат: демократическая политика оптимальна и для целого ряда других критериев. В качестве математической модели мы рассматриваем случайное блуждание в целочисленном неотрицательном квадранте. Первая (вторая) координата выражает размер капитализации первой (второй) фирмы, время дискретно. Управление реализуется как придание блужданию некоторой степени асимметрии (скачок в положительном направлении более вероятен, чем в отрицательном), но только одной из координат в каждый момент времени.
Рассмотрим задачу максимизации среднего дисконтированного времени выхода на границу квадранта (без дисконтирования среднее бесконечно). Цель — найти оптимальную стратегию. В симметричном случае, т. е. когда допустимая степень асимметрии одинакова для обеих координат, мы нашли решение. Оптимальная стратегия — действовать на ту координату, которая ближе к нулю.
При этом мы реализовали идею [2]: вместо того чтобы решать соответствующее уравнение Беллмана, прямо доказать оптимальность определенной стратегии.
В работе [2] задача максимизации вероятности невыхода на границу рассматривалась для вине-ровского процесса с управляемым сносом, и для уравнения Беллмана было получено аналитическое решение. Для случайного блуждания это вряд ли возможно.
1. ОБОЗНАЧЕНИЯ
Обозначим: Т1 — множество целых чисел, Т+ -
-п2
множество неотрицательных целых чисел, Т+ - неотрицательный квадрант Т+ х Т+ = {(і, у), і, у, ^ Т1}. Далее, (О, у, ?, Р) — вероятностное пространство с потоком ст-алгебр? = (У (п), п = 0, 1, 2, …).
Все случайные процессы рассматриваются в дискретном времени п = 0, 1, … Обозначим через АХ процесс, составленный из приращений процесса X: АХ (п + 1) = Х (п + 1) — Х (п), п = 0, 1, …
'-1
Константа p є
2
І
обозначает вероятность
скачка вправо асимметричного блуждания.
2. УПРАВЛЯЕМОЕ СЛУЧАЙНОЕ БЛУЖДАНИЕ В КВАДРАНТЕ
Процесс Х называется случайным блужданием
в неотрицательном квадранте, если Х (п) є Т+, п = 0, 1, …, и АХ (п) є {(±1, ±1)}, п = 1, … Таким образом, в каждый момент времени каждая из координат переходит в одну из соседних точек.
Перейдем к определению управляемого случайного блуждания. Пусть дан ?-согласованный процесс и (п) є {1, 2}, п = 0, 1, …, — стратегия управления. Для х є Т+ обозначим Хх, и процесс, определяемый соотношениями:
Xx’u^) = x,
І
P (AX x’u (n + 1) = (1, 1)|F (n)) = ip, P (AXx, u (n + 1) = (-1, -1)|F (n)) = 2 (1 — p),
P (AX x, u (n + 1) = (1, -1)|F (n)) =
2p, если u (n)
І,
L2-(1 -p), если u (n) = 2,
P (AX x’u (n + 1) = (-1, 1)|F (n)) = ^(1 -p), если u (n) = 1,
p, если u (n)
п = 0, 1, 2, … Совокупность всех процессов Хх, и, где и пробегает множество всех стратегий, называется управляемым случайным блужданием в неотрицательном квадранте.
Пусть дана неубывающая функция /: Т+ и оо ^
^ [0, 1]. Рассмотрим задачу Е/(т (Хх, и)) ^ тах, где максимум берется по множеству всех стратегий и, а т — момент выхода траектории на границу квадранта.
Основная теорема. Оптимальная стратегия (не единственная на биссектрисе квадранта) имеет вид:
u*(x) =
i, если xt = min{x1, x2}, x1 ^ x2, i = 1, 2, 1 если x1 = x2. ¦
Беря в качестве / функцию, принимающую значение 1 в бесконечности и 0 во всех остальных точках (соответственно, — е -л, где X — положительная константа), получим задачу максимизации вероятности невыхода на границу (соответственно, среднего дисконтированного времени выхода на границу квадранта). Поясним:
Т — 1 -і -їх
E? e-It = E1 — e
о
1 — e
максимизация правой час-
-їх
ти по т эквивалентна максимизации — е
Замечание. Утверждение об оптимальности стратегии и* нетривиально только в том случае, если выигрыш действительно зависит от стратегии. Например, в задаче максимизации вероятности невыхода на границу гипотетически эта вероятность могла бы равняться нулю для всех стратегий. Покажем, что это не так. Сравним две стратегии: и = 1 и и (2п) = 1, и (2п + 1) = 2, п = 0, 1, … Для первой стратегии вероятность равна нулю при любом начальном условии, потому что вторая координата — неуправляемое случайное блуждание, которое с вероятностью 1 достигает 0. Для второй стратегии, напротив, при любом начальном условии вероятность положительна: координаты независимы, и каждая подобна винеровскому процессу со сносом [3]. ¦
3. ДЕКОМПОЗИЦИЯ
Введем в квадранте новые координаты (Ур 1^) =
= 2 (X — Х2, X + Х2). В этих координатах динамика блуждания такова:
если ДХ (п) е {(-1, 1), (1, -1)}, то ДУ2(п) = 0, а Д УДп) = ±1-
если ДХ (п) е {(1, 1), (-1, -1)}, то ДУДп) = 0, а ДУ2(п) = ±1.
Таким образом, координата У2 движется с течением времени так: либо стоит на месте, либо совершает скачок ±1. В те (и только те) моменты,
когда координата стоит, движется координата Ур совершая скачок ±1.
Пусть Х — управляемое случайное блуждание. Легко видеть, что в новых координатах (Ур У^) управление действует только на координату У1. Таким образом, задача автоматически свелась к управлению одномерным процессом в множестве Х.
4. УПРАВЛЯЕМЫЕ ОДНОМЕРНЫЕ СЛУЧАЙНЫЕ БЛУЖДАНИЯ
Перейдем к определению управляемого одномерного случайного блуждания. Пусть на пространстве (О, у, ?, Р) задано простое одномерное ?-случайное блуждание Ж (п), п = 0, 1, 2, …, т. е. ?-согласованный процесс со значениями в множестве Т1 такой, что Ж (0) = 0 и
Р (АЖ (п) = 1|?(п — 1)) =
= Р (АЖ (п) = -1|?(п — 1)) = 1, п = 1, 2, …
И пусть ^(п), п = 1, 2, … — одинаково распределенные ?-бернуллиевские случайные величины, т. е. ?-согласованный процесс со значениями в множестве {0, 1} такой, что для некоторого р є [0, 1]
Р (?(п) = 1|?(п — 1)) = р,
Щ (п) = 0|?(п — 1)) = 1 — р.
Наконец, пара (А Ж (п), ^(п)) независима и не зависит от ?(п — 1), п = 1, 2, … Пусть и (п) є {-1, +1}, п = 0, 1, … —? — согласованный процесс (стратегия
управления). Для у є Т+ обозначим Уу, и процесс, определяемый соотношениями: Уу, и (0) = у,
А У (п) =
_ [аЖ (п), если п) = 0,
и (п — 1), если ^(п) = 1,
п = 1, 2, … Таким образом, процесс У'-'& quot- совершает скачок вместе с блужданием Ж, если ^ = 0, и совершает скачок в направлении и, если ^ = 1 (^ можно рассматривать как «шанс для управления»). Процесс Уу’и допускает представление
блуждания (сравните с конструкцией двумерного), потому что она нужна при доказательстве теоремы 2.
Множество всех стратегий и будет обозначаться
и. Для полной строгости следует писать Уу’и (Ж, ^)
и УУ’И (Ж,, п), чтобы явно указать ведущие процессы управляемого случайного блуждания.
Для любой функции у: 2+ ^ {-1, +1} и любого
у е 2+ можно однозначно определить у1 е и и 1 1 1 Уу'4, удовлетворяющие у (п) = у (Уу'4 (п)), п = 1,
2, … (рекуррентно). Соответственно, для данного
у е 2+ можно определить стратегию и*, отвечающую функции -8§ п и зависящую от у. Таким образом, существует единственная стратегия и* е и,
удовлетворяющая соотношению и*(п) = 8§ пУу'& quot- (п), п = 0, 1, 2, … (б§ п0 = -1).
Теорема 1. Пусть у1, у2 е 2+, у1 & lt- у2, у1 — у2 четно. Для любой стратегии и е и существуют расширение вероятностного пространства (О, у, Р) с новым потоком ?'-,? с ?'-, и новое простое одномерное случайное блуждание Ж'-(п), п = 0, 1, 2, …, такие, что
У1,. Уо,& quot-
|у (Ж, ^)| т |уУ2 (Ж, ^)|.
Это неравенство выполнено на каждом элементарном событии. ¦
5. ОДНОМЕРНОЕ УПРАВЛЯЕМОЕ СЛУЧАЙНОЕ БЛУЖДАНИЕ С ОТРАЖЕНИЕМ
Рассмотрим вспомогательную задачу управления случайным блужданием в полуоси 2+.
Пусть Ж — траектория блуждания в множестве
21. Определим
ф (Ж)(0) = Ж (0),
/ = п
ф (Ж)(п) = Ж (0) +? Дф (Ж)(п),
где
Уу, и (п) = у + Ж (п) +? ^(п)Ди (п — 1), АЖ (п)), к = 1 п = 0, 1, …
где
/(1, 1) = 0, /(1, -1) = 2,
/(-1, -1) = 0, /(-1, 1) = -2.
Таким образом, управляющее воздействие аддитивно по отношению к исходному ведущему блужданию. Ради этой аддитивности мы выбрали такую конструкцию одномерного управляемого
Аф (Ж)(п) = [а Ж (п), если ф (Ж (п — 1 0,
[+1, если ф (Ж)(п — 1) = 0,
п = 1, 2,… Функционал ф называется функционалом отражения (в нуле) Скорохода [5].
Вернемся в парадигму управляемого одномерного случайного блуждания. Определим «оптимальную стратегию» и+ как и+ (п) = -1, п = 1, 2, … (она оптимальна для управления блужданием в
полуоси Т+, поэтому помечена знаком +).
1
П
Теорема 2. Пусть у 1, у2 є Т+, у1 & lt- у2, и разность у1 — у2 четна. Тогда для любой стратегии и є и
, Уі& gt-
ф (Гх -)(п) т ф (У^)(п), п = 0, 1, 2, … ¦
Замечание. Стратегия и* не обладает соответствующим свойством, поэтому нам и пришлось обратиться к процессам с отражением. Действительно, пусть у = -1, и (0) = -1, ?(1) = 1, ?(2) = = ?(3) = 0, ДЖ (2) = ДЖ (3) = 1. Тогда Уу’и*(3) = 1, а Уу'& quot-(3) = 0. ¦
6. ПЕРСПЕКТИВЫ ПРИМЕНЕНИЯ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ И ДАЛЬНЕЙШИХ ИССЛЕДОВАНИЙ
Пусть имеются к одинаковых государственных унитарных предприятий. Они ведут хозяйственную деятельность и ежемесячно отчитываются суммой прибыли с начала года Х (п), п = 0, 1, 2, …, 12, Х (0) = 0, / = 1, …, к, Х (п) принимает целочисленные значения в тысячах рублей. Государство резервирует ресурс для поддержки предприятий и направляет его для предотвращения их убыточности. Ежемесячно расходуется фиксированная сумма. Математическая модель: без поддержки государства прибыль с начала года X — симметричное
случайное блуждание в множестве 21, / = 1, …, к, причем процессы {X, I = 1, …, к} независимы в совокупности- применение ресурса смещает распределение скачка в положительном направлении {1, 2}- критерий оптимизации — минимизировать вероятность случая убыточности среди предприятий в течение года, т. е.
Р
тіп Х (п) I ^ тах.
і = 1, к п = 1,…, 12
В случае к = 2 и блуждания со скачками размера ±1 основная теорема дает оптимальную стратегию при дополнительном предположении: ежемесячно выбирается одно из предприятий и поддержка оказывается только ему. А именно, оптимальная стратегия — поддерживать предприятие с наименьшей суммарной прибылью с начала года.
Обобщение основной теоремы на блуждания в множестве 2к (размерности к) со скачками не только единичного размера позволит доказать оптимальность сформулированной стратегии в общем случае. Дальнейшее обобщение — гибкое распределение ресурса между предприятиями.
ЗАКЛЮЧЕНИЕ
Для управляемого случайного блуждания в квадранте аналитически найдена стратегия, максимизи-
рующая время выхода на границу и ряд других критериев. Функция выигрыша при этом не находилась. Рассмотренная модель имеет универсальное применение, она уже использовалась при решении задач математической экономики [2].
Автор весьма признателен профессору Я. Ре-шапИе (и8А), давшему ему принципиальную идею решения задачи, и намеревается опубликовать окончательные результаты в совместной работе. Автор благодарен рецензенту, посоветовавшему написать § 6.
ПРИЛОЖЕНИЕ
Доказательство теоремы 2. Обозначим для
У, и+ У2& quot- и
краткости ф*(и) = ф (У)(и) и ф (и) = ф (У)(и),
и = 0, 1, 2, … Заметим, что (ф* - ф)(и) сохраняет четность (как функция и). В самом деле, (ф* - ф)(и + 1) — (ф* - ф)(и) = Аф (и + 1) — Аф (и), и поскольку слагаемые в правой части принимают значения ±1, сама правая часть принимает значения 0, ±2, и = 0, 1, 2, … Поэтому шш (ф* - ф)(и) & lt- 0 влечет существование такого
п = 0, 1,…
и, что (ф* - ф)(и) = 0, а (ф* - ф)(и + 1) & lt- 0. Но это невозможно:
если ф (и) = ф*(и) = 0, то ф (и + 1) = ф*(и + 1) = 1-
если ф (и) = ф*(и) & gt- 0, то ф (и + 1) = ф*(и + 1) в случае ^(и + 1) = 0 и ф (и + 1) & gt- ф*(и + 1) в случае ^(и + 1) = 1 — это следует из определения и+.
Для доказательства теоремы 1 нужны следующие две леммы и следствие.
Лемма 1. Для любых у е 1+, и е и процесс Уу, и (Ж, у| можно представить как ф (УУ"и (Ж, ?)), где
и (к) =
У2, и У2, и
sgn У (к) и (к), если У (к)* 0,
У2, и
и (к), если У (к) = 0,
к = 0, 1, …, а Ж определяется формулами Ж (0) = 0 и АЖ (к) =
У, и У, и
sgn У (к — 1) А Ж (к), если У (к — 1)* 0-
У2, и
АЖ (к), если У (к — 1) = 0,
к = 1, 2, … ¦
У, и
Доказательство. Представим У как отраженный процесс. Очевидно, что
А УУ2'-и (к) =
У-& gt-, и у-, и у-, и
8§ пУ 2 (к- 1) ДУ 2 (к), если У 2 (к- 1)*0-
У2, и
1, если У 2 (к — 1) = 0,
10
СОЫТВОЬ БСІЕМСЕБ № 1 * 2010
У2, и
к = 1, 2, … Далее, если Y (к — 1) ф 0,
У2, U уъ U
sgn Y 2 (к — 1) Д Y 2 (к) =
Л
sgn Y (к — 1) Д W (к), если ?,(к) = 0,
У2, U
sgn Y (к — 1) и (к — 1), если ?,(к) = 1,
к = 1, 2, … Теперь
Д| Y У2, и|(к) =
У2, U
ДЖ (к), если Y (к — 1) ф 0, ?,(к) = 0-
у2, U
и (к), если У (к — 1)* 0, С (к) = 1-
У2, и
1, если Г2 (к — 1) = 0, к = 1, 2, … Очевидно,
У2, и. У2, И —
у (Ж С)! = ф (у 2 (Ж, У).
Лемма доказана. ¦
Следствие. Для любого у е 1+ распределения
уу и*(Ж, С) и ф (уУ' +(Ж, С)) совпадают.
Лемма 2. Пусть у е 1+ и на (О, у,? Р) задан процесс Я, распределенный как Уу’и. Тогда существуют расширение исходного вероятностного пространства и определенные на нем поток а-алгебр И'- и процесс Ж'- такие, что (Ж'-, С) является И'--ведущим процессом, и
, У л, И*
Я = У 1 (Ж, С). ¦
Доказательство. Превратим пространство последовательностей (я, А)(и) е {-1, 1}х{-1, 1}, и = 1, 2, …, в вероятностное пространство с мерой так, чтобы (я, А)(и), и = 1, 2, …, стали независимыми случайными величинами с независимыми одинаково распределенными координатами, причем? (соответственно, А) принимает значение 1 с вероятностью р (соответственно, ½). Теперь возьмем прямое произведение построенного вероятностного пространства и исходного и положим
Г (0) = у (0), у (и) = а (У (и), (я, А)(0, I = 1, …, и), и = 1, 2, …
Определим последовательность марковских моментов (возможно, конечную) т0 = 0, т-+1 = шш{и & gt- т-: Я (и) = 0}, I = 0, 1, … Заметим, что по определению т-, I = 0, 1, …, строго возрастает. Определим процессы
Я (и) = 1[т0,т1] (и)Я (и) +

+ Е + 1] (и)Я (и)(1{0}(Ц + 1) sgn + 1(1}(Ц + 1 ЭХ
I = 1
п
Щи) = Е (1(0 }№)АЯ (1) + /{1}(С (0)А (0),
г = 1
и = 0, 1, … Построенные объекты удовлетворяют всем требованиям леммы. Действительно, после каждого
попадания процесса Я в 0 мы разыгрываем его экскурсию (отрезок траектории до следующего попадания в 0) для построения экскурсии процесса Я'- в соответствии со стратегией и*: если? т. +1 = 0, то экскурсии
распределены симметрично (относительно нуля). А если Ст. +1 = 1, то процесс Я'- детерминированно переходит в 1, и его экскурсия совпадает с экскурсией Я. Далее, процесс, А позволяет заменить скачки ведущего случайного блуждания, искаженные управлением (когда имелся «шанс для управления», С (0 = 1). ¦
Доказательство теоремы 1. Идея состоит в том, чтобы представить У у, и как отраженный процесс и воспользоваться теоремой 2. Согласно лемме 1,
Уу, и (Ж, С) = ф (УУ'"(Ж, С)). Введем процесс Я =
= ф (уУ' + (Ж, С)). В силу теоремы 1 Я & lt- Уу, и. Но в силу следствия леммы 1 процесс Я распределен как процесс Уу, и. Применим к процессу Я лемму 2 и получим утверждение теоремы. ¦
Доказательство основной теоремы. Перейдем к координатам (У1, У2) (см. § 3). Любой стратегии и соответствует стратегия и1 управления процессом У1 (в те моменты, когда он совершает скачки):
, ч [ + 1, если и (и) = 1, и1(и) =
[ -1, если и (и) = 2.
Таким образом, заявленной в теореме оптимальной стратегии соответствует стратегия и* теоремы 1. Применим теорему 1: для любой альтернативной стратегии и можно расширить исходный стохастический базис так, что для процессов Хх, и и Хх, и выполнено: т (Хх, и) т т (Хх, и), что доказывает теорему. ¦
ЛИТЕРАТУРА
1. Беллман Р. Динамическое программирование. — М.: Изд-во иностр. лит. — 1960. — 400 с.
2. McKean H.P., Shepp L.A. The Advantages of Capitalism vs. Socialism Depends on the Criterion. Presented April 25−29, 2005 at the Linnik meeting, St. Petersberg, Russia // Записки научных семинаров ПОМИ (СПб.). — 2005. — Т. 328. — C. 160−168.
3. Бородин А. Н., Салминен П. Справочник по броуновскому движению. Факты и формулы. — СПб.: Лань. — 2000. — 639 с.
4. Ватанабэ С., Икэда Н. Стохастические дифференциальные уравнения и диффузионные процессы. — М.: Наука, 1986. — Гл. 4, § 7.
Статья представлена к публикации членом редколлегии Е. Я. Рубиновичем.
Анулова Светлана Владимировна — канд. физ. -мат. наук, ст. науч. сотрудник, Институт проблем управления им. В. А. Трапезникова РАН, г. Москва,
(r) (495) 334−90−49, И anulovas@ipu. rssi. ru.

ПоказатьСвернуть
Заполнить форму текущей работой