June 19th, 2006

red dragon

Эволюция со случайными переходами

Дана система, которая находится в одном из N состояний.

В каждый момент времени она случайно переходит в новое состояние или остается в старом не зависимо от состояния, в котором система находилась.

Выберем одно из состояний. Пусть вероятность перехода в него из любого состояния будет p. Эта вероятность постоянна во времени и не зависит от прошлого.

Средний период сохранения Tc(p) – среднее число тактов данного сохранения состояния.до его потери.
Средний период возврата Tr(p) – среднее число тактов, через которое система вернется в данное состояние после его потери.

Пусть в некоторый момент времени t0=0 система находилась в некотором состоянии с вероятностью перехода p и q = 1-p


Средний период сохранения Tc(p)

В момент t = 1 вероятность сохранения состояния будет p1 = p, а вероятность потери – q1 = q.
В момент t = 2 вероятность сохранения будет p2 = p1p = p2, вероятность потери – q2 = p q.
Для произвольного момента t > t0 вероятность сохранения будет pt = pt, вероятность потери qt = pt-1q.
Легко показать, что q1 + q2 +...+ qt +... = 1.

Средний период сохранения равен
Tc(p) = 1 q1 + 2 q2 +...+ t qt +... = q (1 p + 2 p2 +...+ t pt +...) = q / (1-p)2 = 1 / (1-p) ,
а его средняя вариация равна
Vc(p) = √ [ (1 q1 + 4 q2 +...+ t2 qt +...) - Tc2(p) ] = √(p) / (1-p) = √(p) Tc(p)


Средний период возврата Tr(p)

В момент t = 1 вероятность потери будет q1 = q = 1-p, а вероятность возврата – p1 = p.
В момент t = 2 вероятность потери будет q2 = q1q = q2, а вероятность возврата – p2 = q1p.
Для произвольного момента t > t0 вероятность потери будет qt = qt, а вероятность возврата – pt = qt-1p.
Нетрудно видеть, p1 + p2 +...+ pt +... = 1.

Средний период возврата равен
Tr(p) = 1 p1 + 2 p2 +...+ t pt +... = p (1 + 2 p +...+ t pt-1 +...) = 1 / (1-q)2 = 1 / p ,
а его средняя вариация равна
Vr(p) = √ [ (1 p1 + 4 p2 +...+ t2 pt +...) - Tr2(p) ] = √(1-p) / p = √(1-p) Tr(p)


Связь между p, Tc(p) и Tr(p)

(1-p) Tc(p) = p Tr(p) = 1 / Tc(p) + 1 / Tr(p) = 1

Таким образом, вероятности p и (1-p) играют роль частот.

Если все состояния равновероятны, то p = 1 / N и
Tc(N) = N / (N-1);         Tr(N) = N
Vc(N) = √(N) / (N-1);     Vr(N) = [ N (N-1)]

Для очень больших N имеем
Tc = 1;   Tr = N
Vc = 0;   Vr = N