Задачка о переворачивании монет

Katrine

Возникла одна вероятностная задача, которую легче всего рассказать на монетках.
Пусть на столе N монет, все изначально лежат орлом вверх. За каждый ход каждая из монет независимо от других может быть перевернута на другую сторону. При этом, если она лежит орлом вверх, то вероятность переворота равна А, а если решкой вверх - вероятность переворота равна B.
Как зависит вероятность иметь на столе не больше K монеток, повернутых решкой вверх, от номера хода?
Может быть есть любители подумать на тему теорвера? Был бы благодарен!

griz_a

Я сразу скажу, что рассматриваю только случай [math]$ A+B\neq 1$ [/math], [math]$A,B\in (0,1)$[/math], остальные случаи тривиальны, но их много.
Поскольку монетки независимы, то посмотрим на одну из них. Вероятность того, что она будет на орле есть [math]$p_n$[/math], удовлетворяющая уравнению
[math]$p_n = p_{n-1}(1-A) + B (1-p_{n-1}) = B + p_{n-1}(1-A-B) $[/math]
Отсюда
[math]$\tilde{p}_n = p_n - B/(A+B\ \tilde{p}_n = \tilde{p}_{n-1}(1-A-B)  = \tilde{p}_0 (1-A-B)^n = A(1-A-B)^n/(A+B\ p_n = (B+A(1-A-B)^n)/(A+B)$[/math]
Отсюда вероятность найти не больше [math]$K$[/math] монет решкой вверх есть
[math]$\sum\limits_{k=N-K}^{N} C_n^k p_n^k (1-p_n)^{N-k}$[/math]
В силу эргодичности нашей марковской цепи (число решек) при [math]$n\rightarrow\infty$[/math]
получим вероятность
[math]$\sum\limits_{k=n-K}^{n} C_N^k B^k A^{N-k}/(A+B)^N.$[/math]

mtk79

есть любители подумать на тему теорвера?
есть даже профессионал подумать на тему теорвера

Katrine

Спасибо огромное! Элегантно придумано насчет p с тильдой! Я вот решал с помощью приведения марковской матрицы 2x2 к диагональному виду, а потом искал корни векового уравнения, чтобы возвести ее в степень n. Существенно дольше получилось. Но ответы совпали.
Вообще на самом деле это сердцевина задачи, в которой "монеты переворачиваются" на самом деле в непрерывном времени с характерными периодами T1 и T2, соответствующими вероятностям А и B. А посчитать нужно распределение времени, необходимого для появления хотя бы K "решек на столе".
Я делал так. Если выбрать дискретизацию времени dt, то за "ход", вероятности А и B рассчитываются как A=1-exp(-dt/T1 B= 1-exp(-dt/T2). Дальше рассчитывается вероятность P (большое) иметь хотя бы K решек на n-м ходу, например, как описано у . В этой формуле делается подстановка n=t/dt. Чтобы подсчитать распределения времен до появления K решек, p (малое я считал произведение вероятностей того, что за n-1 ходов решка не выпадает, а на n-м выпадает, т.е

Почему-то у меня не сходится итог с численным стохастическим рассчетом на Матлабе. К тому же не могу понять, как сделать, чтобы ответ не менялся в зависимости от выбора дискретизации времени. Где я ошибаюсь ?

griz_a

Спасибо огромное! Элегантно придумано насчет p с тильдой! Я вот решал с помощью приведения марковской матрицы 2x2 к диагональному виду, а потом искал корни векового уравнения, чтобы возвести ее в степень n. Существенно дольше получилось. Но ответы совпали.

Да, можно через n-ую степень матрицы перехода. Довольно таки нехитро, особенно если не связывать с ЖНФ, а просто по индукции формулу вывести. Хотя у меня в том году была группа алгебраистов, они через ЖНФ делали за несколько минут :)
А про пэ с тильдой - это же стандартная штука с однородным и неоднородным дифурами. Тут то же самое, только с разностным уравнением, что суть то же.
Чтобы подсчитать распределения времен до появления K решек, p (малое я считал произведение вероятностей того, что за n-1 ходов решка не выпадает, а на n-м выпадает,

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

griz_a

Я бы решал задачу в непрерывном случае как-нибудь так:
Рассмотрим цепь Маркова [math]$Y_t$[/math] с непрерывным временем такого сорта:
пока на столе не появлялось K решек, это просто число решек в данный момент;
как только появилось K решек [math]$Y_t$[/math] становится равной [math]$K$[/math] навсегда.
Эта цепь имеет [math]$K+1$[/math] состояние и матрицу переходных интенсивностей
[math]$Q$[/math] с [math]$q_{i,i+1} = (N-i)A$[/math] при [math]$i<K$[/math], [math]$q_{i,i-1} = iB$[/math] при [math]$0<i<K$ [/math], [math]$ q_{i,i} = -NA + i(A-B)$ [/math] при [math]$0\leq i<K$[/math], [math]$ q_{K,i} = 0,$ [/math] при всех i.
Тогда вероятность того, что время ожидания K решек меньше t, есть просто [math]$p_{K}(t)$[/math]. Вероятности [math]$p_i(t)$[/math] определяются системой [math]$ p'_{i}(t) = p_{i-1}(t) q_{i-1,i} + p_{i}(t) q_{i,i} + p_{i+1}(t) q_{i+1,i}$[/math] c условиями [math]$p_i(0)=0,$[/math] [math]$ i>0$[/math], [math]$p_0(0)=1$[/math]
Последнее уравнение здесь вообще не нужно, оно просто определяет [math]$p_{K}$[/math] по остальным, с этим мы и так справимся.
Дальше метод производящих функций - умножаем i-ое уравнение на s^i и складываем по всем i. Получаем урчп на функцию [math]$f(t,s) = \sum_{i=0}^{K-1} p_i(t) s^i$[/math].

Katrine

Спасибо за ответы и помощь!
Оставить комментарий
Имя или ник:
Комментарий: