Цепи Маркова (1121219), страница 78

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 78)

§ 1.11).Пример 3.6.1. Рассмотрим н.о.р.с.в. X1 , . . . , Xm , Xj ∼ U(0, 1). (Можносчитать, что Xj соответствует «качеству» объекта j, выбранного случайным образом из «неограниченной популяции», без возвращения.) Каки в примере 1.11.1, мы рассматриваем задачу о секретаре с единственнымвыбором, имеющую целью выбор объекта наивысшего качества путемсравнения текущего объекта с предыдущими, при невозможности возвратиться к ранее отвергнутым объектам. Напомним, что в § 1.11 окончательные (и относительно простые) значения вероятности наилучшеговыбора возникали в пределе при m → ∞. Например, если позволитьне единственный выбор, а выбор двух объектов, то вероятность успехаповышается с 0,3678 до 0,5910. Сейчас же мы будем рассматривать случайединственного выбора при полностью известном распределении и будемопределять оптимальную стратегию.

Как будет видно из примера 3.6.2, этаинформация о распределении увеличивает вероятность успеха до 0,5802,что ненамного меньше, чем 0,5910.Решение. Нетрудно убедиться, что для любых i = 1, . . . , m существуеттакое оптимальное пороговое значение bi ∈ (0, 1), что на шаге m − i + 1следует выбрать появившийся объект, если Xm−i+1 = max[Xl : 1 6 l 66 m − i + 1] > bi , и отвергнуть его, если Xm−i+1 < bi или Xm−i+1 << max[Xl : 1 6 l 6 m − i] . (В случае, когда Xm−i+1 = max[Xl : 1 6 l 66 m−i+1] = bi , любое из двух решений ведет к одной и той же вероятностиуспеха.) Действительно, b1 = 0 (это означает, что выбирается последнийиз появившихся объектов, если он доставляет глобальный максимум, и доэтого выбор не сделан), тогда как b2 = 1/2 (что является медианойравномерного распределения U(0, 1)).

Остальные b i будут превышать 1/2(и монотонно растут по i); чтобы вычислить их точно, нужно использоватьвышеупомянутое условие нейтральности.Предположим, что выбор не сделан на (m − i)-м шаге и Xm−i+1 == max[Xl : 1 6 l 6 m − i] (в этом случае назовем объект m − i + 1500Глава 3. Статистика цепей Маркова с дискретным временемкандидатом). Остался i − 1 шаг.

Тогда x = bi это решение уравненияx i− 1 =i− 1Xj=11jCji−1 xi−1−j (1 − x) j .В самом деле, если мы остановимся (сделаем выбор), то вероятностьуспеха равна xi−1 . Если мы продолжим, то может появиться j 6 i − 1значений, больших чем x. Если мы остановимся при первом появлениитакого значения, то вероятность того, что это абсолютный максимум, равна1/j в силу симметрии.

Для i = 2 получим x = 1 − x, т. е. x = 1 /2. Поэтомуb2 = 1/2, как и утверждалось. Для i = 3 после упрощения получим5x2 − 2x − 1 = 0, или√x = b3 = (1 + 6) /5 ≈ 0,6899Для не слишком больших значений i + 1 можно bi+1 найти численно:i+1234561015i+120253035404550bi+10,50000000,689897950,775845080,824589580,855949220,916044170,94482887bi+10,958916630,967273670,972805610,976727830,979676550,981956080,98377582§ 3.6.

Элементы теории управления и теории информации501Решение. Выражение для P(1) получаем немедленно: 1 − d m1 даетвероятность того, что по крайней мере один из объектов имеет качествопо крайней мере d1 и 1/m — это условная вероятность того, что принаступлении указанного события, наилучшее качество имеет объект X 1(в силу симметрии). Для произвольного значения r возьмем i, 1 6 i 6 r,и рассмотрим вероятность того, что первые r шагов не привели к выбору, и что (глобально) наилучший объект находится среди оставшихсяm − r объектов. Эквивалентным образом, это вероятность того, что ∀ i == 1, .

. . , r таких, что качество Xi наивысшее среди X1 , . . . , Xr , имеем,что Xi < di и Xi < max [X1 , . . . , Xn ] . Как и ранее, вероятность событияXi = max[X1 , . . . , Xr ] 6 di равна dri /r.В рамках этого события существует возможность того, что выбор неосуществится, хотя Xi будет глобальным максимумом max[X1 , . . . , Xm ] .Вероятность того, что Xi = max[X1 , . . . , Xm ] < di равна dmi /m. Значит,mзадаетвероятностьтакогособытия:а) Xi < di ,разность dri /r − dm/iб) Xi = max[X1 , .

. . , Xr ] и в) Xi < max[X1 , . . . , Xm ] . Поскольку порогиd1 , . . . , dm были выбраны монотонно убывающими, в рамках последнегособытия ни один Xl с l < i не может превзойти dl . Суммируя разностиdri /r − dmi /m по 1 6 i 6 r, получим вероятность того, что выбор небудет сделан среди первых r объектов и что объект наилучшего качестванаходится среди оставшихся m − r возможностей.При наличии этой информации вероятность того, что (r + 1) -й объектXr+1 является глобальным максимумом, равнаr1 X r(di /r − dmi /m).m−rЗаметим, что оптимальный порог bi не зависит от m > i.i=1Проблема Генерального Секретаря(Из серии «Фильмы, которые не вышли на большой экран».)Пример 3.6.2.

Продолжая предыдущий пример, зафиксируем стратегию (не обязательно оптимальную) с порогами d1 > d2 > d3 . . . > dm , где0 6 di 6 1. Это означает, что мы выбираем первый объект, чье качествоXj доставляет максимум max[Xl : 1 6 l 6 j] и превосходит dj . Докажите,что вероятность успеха на первом шаге равнаP(1) =1 − dm1,mтогда как P(r + 1) на шаге r + 1 задается формулойP(r + 1) =rXi=1drir(m − r)−rXi=1drim(m − r)−dmr+1m, 1 6 r 6 m − 1.Это выражение задает вероятность того, что выбор не будет сделан средипервых r возможностей, и что Xr+1 = max[X1 , . .

. , Xm ] , т. е. Xr+1 имеетглобально наивысшее качество. Если мы выберем (r + 1) -й объект, когдаXr+1 имеет глобально наивысшее качество, мы добились успеха. Но естьшанс, что мы не выберем (r + 1)-й объект при том,что он глобально наилучший, и эта вероятность равна dmr+1 /m. Это слагаемое нужно вычесть, имы получим уравнение для P(r + 1).При выборе оптимальной стратегии, когда di = bm−i+1 , i = 1, . . .

, m,получаем оптимальную вероятность Pопт (успеха):Pопт (успеха) =1 − bmm+m+" r−1mXXr=2i=1r−1#r−1r−1Xbmbmbm−i+1−i+1−− m−r+1 .(r − 1) (m − r + 1)m(m − r + 1)mi=1503величина J( ), определяемая как 2 .P ∂f(x;)f(x; ),x∈S ∂22 .J( ) = E (V (X; )) = Z ∂f(x;)f(x; ) dx.∂Следующая таблица содержит эти вероятности для выборок при различных m.§ 3.6.

Элементы теории управления и теории информацииPопт0,5942000,5894720,5871260,5857250,580164(3.6.2)SИными словами, J( ) = Var V (X; ).Аналогичное определение можно дать в более общем случае, когда∈ Θ ⊆ Rd , а x заменен вектором x ∈ Rn . (Например, многомернаянормальная плотность с неизвестным средним и неизвестной ковариа= ( , Σ) ∈ Rn+n(n+1) /2 .)ционной матрицей соответствует S = Rn иТогда вместо скалярной величины говорят об информационной матрицеФишера J( ) = (Jij ( )), гдеm20304050∞Pопт0,750000,6842930,6553960,6391940,608699Секретари делают это без проблем.P ∂ ln f (x; ) .f(x; )x∈S∂Z.E V (X; ) =∂ ln f (x; )f(x; ) dx∂= 0.S(Достаточно записать ∂ [ln f(x; )] /∂ = [∂ f(x; ) /∂ ] /f(x; ) и вынестипроизводную ∂ /∂ за знак суммы/интеграла.) Информация Фишера (которую содержит случайная величина X, имеющая д.р.в.

/в.п.р. f(x; )), этоV1 (X; ).. — это векторная оценочная функция:Здесь V(X; ) =.Vd (X; )∂ln f(X; ),∂ iVi (X; ) =i = 1, . . . , d.(3.6.4)Как и ранее, при достаточно мягких предположениях средние значенияEVi (X; ) = 0, а элементы Jij ( ) — это ковариации Vi (X; ) и Vj (X; ):Jij ( ) = Cov [Vi (X; ), Vj (X; )] .Далее будем ссылаться на определения (3.6.1) – (3.6.2) как на «скалярный случай», а на (3.6.3) – (3.6.4) — как на «векторный случай».Определение 3.6.4.

Пусть f0 и f1 — это два дискретных распределения/две плотности распределения на R или на Rn . ПоложимPf1 (x), 1(f1 (x) > 0)f1 (x) lnf0 (x)D(f1 k f0) = Z(3.6.5) 1(f1 (x) > 0)f1 (x) ln f1 (x) dx.При достаточно мягких предположениях(3.6.3)(3.6.1)i, j = 1, . . . , d.S∂ln f(X; ).∂V (X; ) =Jij ( ) = E [Vi (X; )Vj (X; )] =.P ∂∂f(x; )f(x; ) f(x; ),x∈S ∂ i∂ j.= Z ∂∂f(x;)f(x;)f(x; ) dx,∂ i∂ jВ оставшейся части этого параграфа мы обсудим взаимосвязь междустатистикой и теорией информации. Часть этого материала будет использована в § 3.8.

Будем использовать обозначения в.п.р. (вероятностнаяплотность распределения) и д.р.в. (дискретное распределение вероятности)и рассмотрим оба случая одновременно.Определение 3.6.3. Пусть X — случайная величина с д.р.в./в.п.р.f(x; ), x ∈ R, зависящим от параметра ∈ Θ. Предположим, что Θ —это интервал на действительной прямой R и все д.р.в.

/в.п.р. f(x; ) имеютодин и тот же носитель — множество S ⊆ R, которое будет конечным илисчетным дискретным множеством в случае д.р.в. или интервалом в случаев.п.р.. (Это означает, что f(x; ) > 0 для любых ∈ Θ тогда и только тогда,когда x ∈ S.) Предположим, что f(x; ) зависит от ∈ Θ гладким образом.Оценочная функция (случайной величины X) это случайная величинаV (X; ), полученная при подстановке случайного аргумента X в логарифмправдоподобия:(Из серии «Как они делают это».)m234510Глава 3. Статистика цепей Маркова с дискретным временем502f0 (x)Величину D(f1 k f0) называют по-разному: расстоянием Кульбака (илиКульбака—Лейблера) между f1 и f0 или дивергенцией Кульбака (или∈ Θ.1, J( ) + o(|| ||2) ∀2∈ Rd , дивергенция(3.6.8)Д о к а з а т е л ь с т в о.

Характеристики

Список файлов лекций