Марковский процесс

[Null]

Пусть $X_0=1$, $P(X_{i+1}=2X_i|X_i)=0.5$, $P(X_{i+1}=X_i-1|X_i)=0.5$ Если $X_i=0$ процесс останавливается. Какова вероятность что процесс будет бесконечным?

[Sinus]

Видимо, вычислить искомую вероятность с некоторой степенью точности (например, $10^{-3}$) нетрудно. У меня получилось примерно $\frac{7}{23}$.

Однако какую-то общую закономерность уловить пока не удалось...

[Sinus]

Не $\frac{7}{23}$, а $\frac{7}{46}$ :)

[Cash]

Sinus в сообщении #492668 писал(а):

Не $\frac{7}{23}$, а $\frac{7}{46}$ :)

Странный результат, причем первый гораздо ближе к истине...
Вычислить можно следующим образом.
Пусть $p_k$ вероятность процессу закончиться если $X = k$,
Тогда имеем $p_k=\frac{1} {2}(p_{k-1}+p_{2k}), p_0=1$
Рассмотрим пространство с элементами
$P = (1, p_1,p_2,\dots)$
Пусть $A$ - оператор $AP \rightarrow P':p'_k = \frac{1} {2}(p_{k-1}+p_{2k})$
Возьмем $ P_0=(1, 0 ,0,\dots)$
Последовательность $A^nP_0$ сходится к некоторому $P^*$ (не спрашивайте почему!), откуда $AP^*=P^*$ и $P^*$ - искомый набор вероятностей.
Стартовав с $ (1, 0 ,0,\dots)$ за 20 итераций мы получим 3-ю цифру после запятой, 50 итераций дают 7-ю цифру.
$p^*_1 =0.70435050$
$1-p^*_1 =0.29564949$

[Хорхе]

Cash в сообщении #493400 писал(а):

Стартовав с $ (1, 0 ,0,\dots)$ за 20 итераций мы получим 3-ю цифру после запятой, 50 итераций дают 7-ю цифру.
$p^*_1 =0.70435050$
$1-p^*_1 =0.29564949$

Да, похоже, ничего хорошего не выйдет:

Inverse symbolic calculator писал(а):

Mixed constants with 5 operations
2956494946373975 = Zeta(1,2)^exp(1/E)/GAM(7/24)

Mixed constants with 5 operations
2956494976366704 = (ln(5)*exp(1/Pi)+Gibbs)/exp(1/Pi)

Product(1 (+/-) P(n)/2**n,n=1..infinity), P(n) is a polynomial
2956494909102313 = Prod(1+(1/3*n^3+11/2*n^2-53/6*n+27)/2^n,n=1..inf)

[Sinus]

Cash в сообщении #493400 писал(а):

Sinus в сообщении #492668 писал(а):

Не $\frac{7}{23}$, а $\frac{7}{46}$ :)

Странный результат, причем первый гораздо ближе к истине...

(Оффтоп)

Мда, что-что я напутал Видимо, все же у меня получилось $\frac{7}{23}$, и так как считял я вручную и округлял при этом очень смело, то погрешность превышает $10^{-3}$ :)

Cash в сообщении #493400 писал(а):

Вычислить можно следующим образом.
Пусть $p_k$ вероятность процессу закончиться если $X = k$,
Тогда имеем $p_k=\frac{1} {2}(p_{k-1}+p_{2k}), p_0=1$
Рассмотрим пространство с элементами
$P = (1, p_1,p_2,\dots)$
Пусть $A$ - оператор $AP \rightarrow P':p'_k = \frac{1} {2}(p_{k-1}+p_{2k})$
Возьмем $ P_0=(1, 0 ,0,\dots)$
Последовательность $A^nP_0$ сходится к некоторому $P^*$ (не спрашивайте почему!), откуда $AP^*=P^*$ и $P^*$ - искомый набор вероятностей.
Стартовав с $ (1, 0 ,0,\dots)$ за 20 итераций мы получим 3-ю цифру после запятой, 50 итераций дают 7-ю цифру.
$p^*_1 =0.70435050$
$1-p^*_1 =0.29564949$

Скорее всего, ваш ответ верен (хотя схема все равно нуждается в обосновании, особенно момент со сходимостью к неподвижной точке!).

Вот немного другая схема, которую легко обосновать. Имеем (в ваших обозначениях)

$p_{2n}=\frac{1}{4}p_{2n-2}+\frac{1}{4}p_{4n-2}+\frac{1}{2}p_{4n}$,
и для любого $m$ последовательно применяя эту формулу можно представить $p_{2}$ как выпуклую комбинация $p_{0}=1$ и $p_{2j}$, $j\[ \ge \] m$. Именно:
$p_{2}=\frac{1}{4}p_{0}+\frac{1}{4}p_{2}+\frac{1}{2}p_{4}$, откуда $p_{2}=\frac{1}{3}p_{0}+\frac{2}{3}p_{4}$,
$p_{4}=\frac{1}{4}p_{2}+\frac{1}{4}p_{6}+\frac{1}{2}p_{8}=\frac{1}{4}(\frac{1}{3}p_{0}+\frac{2}{3}p_{4})+\frac{1}{4}p_{6}+\frac{1}{2}p_{8}$,
откуда $p_{4}=\frac{1}{10}p_{0}+\frac{3}{10}p_{6}+\frac{3}{5}p_{8}$; точно также $p_{6}=\frac{1}{37}p_{0}+\frac{6}{37}p_{8}+\frac{10}{37}p_{10}+\frac{20}{37}p_{12}$ и т.д., и на каком-то этапе просто воспользоваться тем, что $p_{j}\[ \to \] 0$ достаточно быстро.

Таким путем можно вычислить искомую вероятность с любой степенью точности, вот только точный ответ найти пока что не удается.

[Cash]

Вообще говоря, я не ставил задачи строгого обоснования. Я ставил конкретную цель - посчитать. Ваш способ вполне удовлетворителен для начала прошлого века, и действительно, если оценить снизу $p_k$ величиной $\frac {2^k-1}{2^k}$ уже представление $p_1$ через $p_6$ и $p_8$ (это до чего и у меня терпения хватило) дает погрешность всего лишь $2\cdot 10^{-3}$.
Но ведь это все надо делать вручную! В моем случае всю работу проделывает машина. Алгоритм прост до безобразия, прога пишется за пару минут, выполняется моментально. 14 знаков за 5 минут - получите, распишитесь.
А возможно, что и в каком-нибудь PARI-GP есть возможность встроенного или библиотечного решения счетного числа уравнений.

Цитата:

Таким путем можно вычислить искомую вероятность с любой степенью точности, вот только точный ответ найти пока что не удается

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

[Cash]

Цитата:

оценить снизу $p_k$ величиной $\frac {2^k-1}{2^k}$

это, конечно же, оценка сверху

[Sinus]

(Оффтоп)

Cash в сообщении #493400 писал(а):

Пусть $p_k$ вероятность процессу закончиться если $X = k$,

Забыл написать раньше: вы ведь имели ввиду $X_0 = k$, не так ли?

Cash в сообщении #493684 писал(а):

Вообще говоря, я не ставил задачи строгого обоснования. Я ставил конкретную цель - посчитать...

Для меня первоочередной целью было решить задачу без использования вычислительных устройств и найти точный ответ. Все же тема находится в разделе "Олимпиадные задачи (М)", а на большинстве математических олимпиад до сих пор запрещатся пользоваться даже калькулятором! Зато много задач решается методами, которые были известны задолго до начала прошлого столетия :) Но так как решить задачу я не смог, то попытался найти хотя бы приближенный ответ.

Позвольте мне обосновать, что предложенный вами алгоритм действительно позволяет вычислить искомую вероятность со сколь угодно малой погрешностью.

Рассмотрим последовательность $x= (x_1,x_2,\dots)$ как элемент пространства $l_1$, так, что $||x||=\sum_n\ |x_n|$. Тогда последовательность $P = (p_1,p_2,\dots)$ является решением уравнения $Ax=x$, где $(Ax)_1=\frac{1}{2}+\frac{1}{2}x_2$, и $(Ax)_n=x_{n-1}+x_{2n}$ при $n>1$. Кроме того, $p_1>0$. Существует наибольшее одна последовательность с положительным первым членом, являющаяся решением уравнения $Ax=x$. В самом деле, если $Ax=x$ и $Ay=y$, то

$||x-y||=||Ax-Ay||\leqslant\frac{1}{2}|x_1-y_1|+\frac{1}{2}\sum_{n \geqslant 2}\ (|x_{n-1}-y_{n-1}|+|x_{2n}-y_{2n}|)= \sum_{2|n}\ |x_{n}-y_{n}|+\frac{1}{2}\sum_{2\not| n}\ |x_{n}-y_{n}|<||x-y||$.

Далее, пусть $P_0=(0,0,\dots)$ и $P_n=A^nP_0=(p^{(n)}_1,p^{(n)}_2,\dots)$. По индукции можно доказать, что последовательность $p^{(1)}_m,p^{(2)}_m,p^{(3)}_m,\dots$ возрастает, значит, для каждого $m$ существует предел $limp^{(n)}_m={p_m}$, и числа $p_m$ удовлетворяют соотношениям $p_m=p_{m-1}+p_{2m}$.

Что касается скорости убывания последовательности $(p_n)$, то из вероятностных соображений нетрудно вывести, что для всех натуральных $n$ и $m$ выполняется неравенство $p_{n+m}\leqslant p_{n}p_{m}$, откуда в частности следует, что $(p_n)\in{l_1}$.

Интересно было бы узнать, какое решение имел ввиду автор темы?

[Null]

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

[Sinus]

Единичный вектор не принадлежит $l_1$. Следовало написать так:

Цитата:

...
Существует наибольшее одна последовательность из $l_1$ с положительным первым членом, являющаяся решением уравнения $Ax=x$.
...

При этом отношение $(p_n)\in{l_1}$ вытекает из того, что $p_{n+m}\leqslant p_{n}p_{m}$.

[Null]

$p_{n+m}\leqslant p_{n}p_{m}$
- $p_k=1$ удовлетворяет. Этот ответ непросто отбросить.

[Sinus]

Так как в нашей марковской цепи все состояния сообщаются, то из неравенства $p_{n}<1$, $\[n \in \]N$, будет следовать неравенство $p_{1}<1$.

Рассмотрим процесс $\[\{ Y(n),n \in N\} \]$, такой, что $Y(n) = \sum\limits_{j = 1}^n {{\xi _j}} $, где $\[\{ {\xi _j}\} \]$ - последовательность независимых одинаково распределенных величин, $\[P\{ {\xi _j} = - 1\} = P\{ {\xi _j} = 3\}=\frac{1}{2} \]$. Согласно усиленному закону больших чисел $\[\frac{{Y(n)}}{n} \to 1\]$ с вероятностью 1, и $\[Y(n) \to + \infty \]$ с вероятностью 1. Поэтому $\[\eta = \mathop {\min }\limits_n Y(n)\]$ - конечная с вероятностью 1 случайная величина. Пусть $m>10^6$ - такое натуральное число, что $\[P\{ \eta > -m\} > \frac{1}{2}\]$.

Покажем, что $p_{2m}<1$. Пусть $\[{X_0} = 2m\]$. Рассмотрим одновременно процесс $\{ {Z_n}\} $, определенный так: если ${X_n} = {X_{n - 1}} - 1$, то ${Z_n} = {Z_{n - 1}} - 1$; если же $\[{X_n} = 2{X_{n - 1}}\]$, то $\[{Z_n} = {Z_{n - 1}} + 3\]$. С вероятностью большей чем $\frac{1}{2}$ процесс ${Z_n} $ никогда не опустится до уровня $m$. При этом, как несложно видеть, для всех натуральных $n$ будет выполняться $X(n)>Z(n)$. Значит, $p_{2m}<\frac{1}{2}$.

Утверждение $p_{1}<1$ наверняка вытекает из общей теории Марковских процессов, но незнание этой теории не позволяет мне привести ссылку :). Получилось только такое довольно искусственное доказательство...