Файл: Растригин Л.А. Автоматная теория случайного поиска.pdf

P u h A l {У\У2

•••УМ--

./*1*2 . . . X N . . . ) =

= Pufl{yiy2---yN..Jxlx2...xN...)

(0.3.26)

при всех

парах

входных

и выходных

последовательнос­

тей XiX2...xN...

и У\У2-..Ун---

• Здесь

{UA'}

и {UA>} —

множества

внутренних

состояний

автоматов

А{ и А2

соответственно;

ри1А{

(У\Уг • • -1х\Х2

... )

—•

вероятность

появления на выходе автомата Л*

( i = l , 2 )

последова­

тельности у\у2...,

если на вход была подана

последова­

тельность Х\х2...

и в начальный момент автомат Лг- на­

ходился В СОСТОЯНИИ Uj.

Стохастическая

эквивалентность

автоматов.

Вероят­

ностные

автоматы А\

и

Л 2

называются

стохастически

деления

Р г ^ ' ^ Р д , 1 0 ' }

найдется

такое

начальное распре­

деление

Р ; - ( 0 ) е { Р д 2 ( 0 ) } , что

Pptml

(УМ* • • • W * i * 2 ...xN)

=

=Pv.^i{y\y2-.-yNlxlx2...xN)

(0.3.27)

и для каждого

начального

распределения

Р ь ( 0 ) е { Р А 2 ( 0 ) }

найдется

такое

начальное

распределение

Рг( 0 >е{Рл,< 0 ) },

что

PpkW2

(У\У2 • • • Un/XiX2

...xn)

=

=PP ; ( 0 ) т ' (У1У2 •. • Ук1ххх2

...xN)

(0.3.28)

для всех пар входных

и выходных

последовательностей

x\X2...xN

и У\У2---Уя

и для

всех

N.

Здесь { Р А , ( 0 ) } И

морфизма

автоматов.

Гомоморфизм

вероятностных

автоматов

[22]. Вероят­

ностный автомат Ai = (X, Y, {T^X/Y)}}

гомоморфно

ото­

бражается

на

вероятностном

автомате

А2

= (Х,

Y,

{T2(XjY)}y,

если

существует такая

матрица

В, число

24

автомата

А2, все строки

матрицы

В

стохастические, а

все ее столбцы линейно независимые,

и для всех х е Х ,

г/еУ справедливо равенство

Т1(у1/х)В

= ВТ2(у/х).

(0.3.29)

Если

вероятностный автомат А\

гомоморфно отобра­

жается

на

вероятностном

автомате

А2,

то они стохасти­

эквивалентен начальный вектор

Рг'0 ', т. е.

Р2 (0) = Р1 (о)5.

(0.3.30)

добятся в дальнейшем при исследовании

эквивалент­

ности алгоритмов поиска.

Ах и

1. Для того чтобы два вероятностных автомата

А2 со случайными реакциями были

эквивалентны

по со­

стояниям, необходимо и достаточно, чтобы

существовал

автомат Аз со случайными реакциями, на котором

гомо­

морфно отображаются автоматы Ах

и А2 [21].

экви­

2. Любой вероятностный автомат

стохастически

u{t+\)=Q>(u(t),x[t+\))\

(0.4.1)

y(t)=F(u(t)).

(0.4.2)

принимает

целочисленные

значения

t=

1,2,...,

N,....

Предполагается,

что входная

переменная

автомата

x(t)

может принимать лишь два значения: 0 и 1, т. е.

* = { 0 , 1 } .

(0.4.3)

Значение

х = 0 соответствует

единичному

выигрышу ав­

томата,

а

значение х=\

— его единичному проигрышу.

Предполагается,

что

выходная

переменная

y(t)

авто­

мата

А

может

принимать

к

различных

значений

Значения переменной

y(t)

будем

также

называть

действиями автомата. В момент времени t

автомат А

произвел действие уа,

если y(t)=ya

( а = 1 , 2, . . . , х ) . Ав­

U\,...,um.

Число

m

называется памятью автомата. Оче­

видно, что для автомата с детерминированной

функ­

цией выхода F(u(t))

m ^ x . Автомат А

в момент

времени

t находится в /-м состоянии

( / = 1 , 2, . . . , т ) ,

если

« ( 0 =

= «j.

Действие

уа

соответствует

состоянию

Uj, если

F(Uj)

=уа.

описывает

зависимость

действия

Уравнение (0.4.2)

автомата

от его состояния,

а уравнение (0.4.1)

—

изме­

нения

его состояния

под воздействием

входной

перемен­

ной

x(t).

В

случае

детерминированных

автоматов

Q)(u(t),x(t+1))

и

F(u(t))

являются

детерминирован­

ными

функциями,

а в

случае

вероятностных

автома­

тов — функциями плотности вероятностей.

Входная переменная

x(t)

принимает лишь

два

значе­

ния:

0 и

1. Поэтому формула

(0.4.1)

задает

пару

«ото­

\\ац(х) ||

(0.4.4)

(i,/ = 1, 2, . . . , m;

х = 0, 1).

atj(x(t+l))

= l.

(0.4.5)

ац(х) = B E P ( u ( * + 1) =Uj/u(t) =щ, х).

(0.4.6)

чаем вероятностного

автомата.

Случайная

среда.

Обычно различают стационарную

ходится в с т а ц и о н а р н о й

с л у ч а й н о й

с р е д е

[28]

С={ах,а2

Он),

(0.4.7)

если действия автомата и значения его входной

перемен­

ной связаны

следующим

образом: действие

уа

(а =

= 1, 2

х), произведенное автоматом

в момент

t,

влечет за собой в момент £ +1 значение

х=\

(проиг­

рыш, штраф)

с вероятностью

* а = - Ц ^ -

(0.4.8)

и х = 0 (выигрыш)

с вероятностью

l - s . - i ± ^ .

(0.4.9)

Здесь аа — средний выигрыш автомата при действии

уа.

При этом предполагается, что

| а а | ^ 1 .

(0.4.10)

Пусть

в момент

t автомат

находится

в

состоянии

щ

(i=l,

2 , . . . ,

т),

которому

соответствует

действие

г/а ,=