Марковская цепь генов в популяции

[Sonic86]

Следующий процесс описывает как меняется множество генов (одной аллели) в популяции со временем в результате размножения и гибели особей.

Есть $n$ различных чисел $1,..,n$ в момент $t=0$. В каждом промежутке $(t,t+1)$ берется наугад одно произвольное число из имеющихся и копируется, а затем берется наугад еще одно число и стирается. В результате с вероятностью 1 при $t \to \infty$ при исходный набор переходит в набор, состоящий только из одной цифры

Можно ли без долгих муторных вычислений оценить среднее количество шагов от $n$, после которых набор переходит в конечное состояние (асимптотику желательно)?

[jetyb]

Сначало решим такую задачку: Пусть у нас есть $a$ "нужных" и $b$ "ненужных" генов, $a+b=n$. Найдем $P^m_{a,b}$ - вероятность, что за $m$ описанных выше шагов получится n "нужных" генов. Для $m=1,a=0,b=0$ $P_{a,b}^m $ легко находится. Если для всех $a,b:0\leq a,b\leq n $ известны $P_{a,b}^m$, то $P_{a,b}^{m+1}=\frac{ab}{n^2}P_{a-1,b+1}^m+\frac{ab}{n^2}P_{a+1,b-1}^m+\frac{a^2+b^2}{n^2}P^m_{a,b}$.
Компьютер это переварит, и самому вычислять ничего не надо.
Теперь можно, фиксировав один ген, посчитать вероятность $P_{1,n-1}^m$, что именно он останется через $m$ шагов. Вероятность, что через m шагов набор перейдет в конечное состояние, равна $nP_{1,n-1}^m$.

[faruk]

Sonic86 в сообщении #227908 писал(а):

Есть $n$ различных чисел $1,..,n$ в момент $t=0$. В каждом промежутке $(t,t+1)$ берется наугад одно произвольное число из имеющихся и копируется, а затем берется наугад еще одно число и стирается. В результате с вероятностью 1 при $t \to \infty$ при исходный набор переходит в набор, состоящий только из одной цифры

Можно ли без долгих муторных вычислений оценить среднее количество шагов от $n$, после которых набор переходит в конечное состояние (асимптотику желательно)?

Я думаю, эта задача в чем-то перекликается с "Coupon collector's problem".

[fiktor]

Уфф, решал когда-то эту задачу. Решение такое:

Давайте найдем матожидание интересующего Вас количества шагов (обозначим количество шагов за S, а его матожидание за E(S)).

Понятно, что с равными вероятностями (для k от 1 до n) набор перейдет в набор k, k, k, ..., k. Все эти вероятности равны 1/n. Давайте это событие обозначим через $B_k$.

Тут очень хочеться верить, что Вы знакомы с понятиями условной вероятности и условного матожидания. Если нет, напишите об этом или прочитайте, что это такое. Хотя для того, чтобы освоиться с подобными вычислениями нужно некоторое время.
1. Утверждается что наше искомое матожидание E(S) равно условному $E(S|B_k)$, которое, в свою очередь, не зависит от k. (попробуйте подумать, почему это так)

2. Зафиксируем k=1 и сосчитаем $E(S|B_1)$. Для этого, как писал jetyb, поставим несколько более общую задачу. Пусть в последовательности, изменяющейся по описанному Вами правилу есть m чисел "1" и, соответственно, n-m других (назовем это состояние $a_m$). Нас будут интересовать 2 объекта:
во первых $E(S|B_1)$ в описанных только что начальных условиях, которое мы обозначим за $E_m$,
и вероятность $P(B_1)$ (в тех же условиях), которую мы обозначим за $P_m$.

3. Из условий Вашей задачи вероятности перехода из состояния a_m равны:
в $a_{m+1}$ --- $\frac{m(n-m)}{n(n+1)}$
в $a_m$ --- $1-2\frac{m(n-m)}{n(n+1)}$
в $a_{m-1}$ --- $\frac{m(n-m)}{n(n+1)}$

4. Напишем уравнения на $P_m$:
$P_0=0$ (если первых уже нет, то они не появятся)
$P_n=1$ (если все числа --- первые, то мы достигли конечного состояния)
Из пункта 3 получаем, что при остальных m
$P_m=\frac{m(n-m)}{n(n+1)}(P_{m-1}+P_{m+1})+(1-2\frac{m(n-m)}{n(n+1)})P_m$, откуда $P_m=\frac{P_{m-1}+P_{m+1}}{2}$.

Напрашивается (верное) решение: $P_m = \frac{m}{n}$, то есть вероятность того, что "единички победят" равна отношению количества "единичек" к количеству всех (то есть к n). Можно было до этого догадаться и без длинных формул.

5. Перед подсчетом $E_m$ сделаем еще один важный шаг: вычислим вероятности увеличения или уменьшения количества единичек (если их было m) при условии, что они все-таки победят. Обозначим их за $P^+_m$ и $P^-_m$ соответственно. Тогда их количество останется неизменным с вероятностью $P^0_m=1-P^+_m-P^-_m$. В этом пункте $m=1,\dots,n-1$.

Для примера $P^-_1$ = 0: если единички победят, а сейчас их одна штука, то не может же их количество уменьшится.

Используя формулу $P(A|B)=P(B|A) \frac{P(A)}{P(B)}$ и сосчитанные в предыдущих двух пунктах вероятности находим
$P^+_m= P_{m+1} \frac{\frac{m(n-m)}{n(n+1)}}{P_m} = \frac{m+1}{m}\frac{m(n-m)}{n(n+1)} = \frac{(m+1)(n-m)}{n(n+1)}$.
Аналогично $P^-_m= \frac{(m-1)(n-m)}{n(n+1)}$.
Отсюда $P^0_m = 1-P^+_m-P^-_m =1-2\frac{m(n-m)}{n(n+1)}$.

6. Теперь подумаем, сможем ли мы сосчитать $E_m$.
$E_0$ не определено, т.к. в этом случае условие (что "единички победят") заведомо ложно. Его вероятность $P_0=0$.
$E_n=0$ (если единички уже победили, то мат.ожидание количества ходов до победы единичек равно 0)
$E_m=1+$ "то же мат.ожидание на следующем ходу" $=1+P_m^- E_{m-1} + P_m^0 E_m + P_m^+ E_{m+1}$, откуда получаем уравнение
$m E_m - \frac{m-1}{2} E_{m-1} - \frac{m+1}{2}E_m = \frac{n(n+1)}{2(n-m)}$.
Если ввести обозначение $e_m = m E_m,\;e_0=0$, то получается, что интересующее нас матожидание равно $e_1$, а уравнения на $e_m$ имеют вид
$e_0=e_n=0$,
$e_m- \frac{e_{m-1} + e_{m+1}}{2}=\frac{n(n+1)}{2(n-m)}$.
Осталось решить систему уравнений. То есть найти $e_1$.

7. Решим вспомагательную систему уравнений. $e_m- \frac{e_{m-1} + e_{m+1}}{2}=0$, где m пробегает все целые числа. Решение такой системы --- $e_m = c_1 + c_2 m$.

8. Теперь решим чуть более сложную систему.
$e_0=e_n=0$,
$e_m- \frac{e_{m-1} + e_{m+1}}{2}=0$ при всех m от 1 до n-1, кроме некоторого значения k и
$e_m- \frac{e_{m-1} + e_{m+1}}{2}=1$ при m=k.
Понятно, что везде, кроме m=k решение должно иметь вид, полученный в пункте 7. Подумав, находим
$e_m = \frac{2 m (n-k)}{n}\textrm{ при }m\leq k $,
$e_m = \frac{2 k (n-m)}{n}\textrm{ при }m\geq k $ (при m=k определения согласуются).
В частности $e_1 = \frac{2 (n-k)}{n}$.

9. Складывая решения из пункта 8 с коэффициентами из правой части пункта 6 находим, что нужной нам системе (той, что в п. 6) удовлетворяют $e_m$ с
$e_1 = \sum_{k=1}^{n-1}\frac{2 (n-k)}{n}\frac{n(n+1)}{2(n-k)} = n^2-1$

Если выше нет ошибки, то ответ: в среднем придется подождать $n^2-1$ шагов.
Так при n=1 ждать придется 0 шагов (правда)
При n=2 ждать в среднем придется 3 шага. Тоже правда. На каждом шаге с вероятностью 1/3 заканчиваем, с вероятностю 2/3 продолжаем. Посчитав получаем 3. Так что можно надеятся, что ошибки действительно нет.

P.S. если придумаете, как сократить эти вычисления, напишите.

[Хорхе]

Мне условие не вполне понятно. Вот есть у нас числа 1,2,3. Наугад выбрали, допустим, 1 и скопировали. Теперь имеем 1,2,3,1. Из чего выбираем теперь, что стереть: а) из 1,2,3; б) из 2,3; в) из 1,2,3,1?

[venco]

в.

[Sonic86]

Спасибо за решение!
Честно говоря, я когда сам решал, стормозил - не додумался рассматривать те буквы, которые исчезнут, как одинаковые. Тогда мне понятнее. Но я еще почитаю.
С условным матожиданием не знаком, только с условной вероятностью, хотя догадываюсь. Есть литература?

[Хорхе]

Sonic86 в сообщении #228763 писал(а):

Есть литература?

Ширяев Вероятность