Бесконечное бросание монетки

[Sirion]

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

[gris]

С вероятностью $1/2$ доля гербов хотя бы раз превысит любое число из $[0,1)$.
Ваша вероятность будет увеличиваться от $0$ до $0,5$ в зависимости от "известного числа" в этом интервале.
А Вы как думаете?

[Aritaborian]

Разве не с вероятностью $1$? И почему интервал открыт только справа?

[gris]

Я полагаю, что доля считается кумулятивно, начиная с первого броска. Если доля считается по скользящему фиксированному интервалу в $n$ бросков, то она достоверно примет все значения от $0$ до $1$ с известным шагом.
Строго превысить $1$ доля не может, а $0$ превысит с вероятностью $1$ (я помню, что "все решки в бесконечной серии" событие не невозможное, хотя и имеет вероятность $0$).
ТС обычно размещает олимпиадные задачи, а в этом разделе приводить решения нельзя, так что замолкаю

[Sirion]

Доля считается кумулятивно, начиная с первого броска. Честно говоря, я не знаю, как решать такую задачу. Наверное, меня слишком рано выперли с мехмата :) Но вопрос мне очень интересен, если кто-нибудь может навести меня на метод решения - сделайте это, пожалуйста.

[faruk]

Sirion в сообщении #676506 писал(а):

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

Число бросаний монеты надо обозначить буквой $n$. Биномиальное распределение при $n \to \infty$ заменяется на нормальное. Тогда

$\sigma=\sqrt{n \cdot p \cdot (1-p)}=\dfrac{\sqrt{n}}{2}$

Дальше уже можно считать.

[gris]

Вообще надо быть осторожным с этими бесконечными делами. Бывает, что в конечных случаях всё работает, а в бесконечном вообще нельзя построить вероятностное пространство, возникают какие-то неизмеримые множества.
Для конечной серии бросаний можно определить случайную величину, равную максимальной кумулятивной доле гербов в серии.

Например, для $n=1:\; P(0)=0.5; P(1)=0.5$

$n=2:\; P(0)=0.25; P(1/2)=0.25; P(1)=0.5$

$n=3:\; P(0)=0.125; P(1/3)=0.125; $
$P(1/2)=0.125; P(2/3)=0.125; P(1)=0.5$

Мы можем построить функцию распределения СВ для конкретного $n$, и она будет отвечать на вопрос: какова вероятность того, что доля гербов хотя бы раз превысит некоторое значение. Это событие противоположно событию, что доля гербов ни разу не превысит данного значения.

Надо смотреть, есть ли какая-то сходимость функций распределения при устремлении числа бросков к бесконечности. Вполне возможно, что они сходятся к функции, которая не может трактоваться как функция распределения. Например, она в некоторой точке не непрерывна ни с одной стороны. И что тогда делать?

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

[--mS--]

Хм. Правильно понимаю, что под "долей" орлов ТС действительно имеет в виду долю, т.е. отношение числа орлов к числу бросков?

Пусть $\xi_1,\xi_2,\ldots$ - независимые бернуллевские величины, $\mathsf P(\xi_i=0)=\mathsf P(\xi_i=1)=\frac12$, $\nu_n=\xi_1+\ldots+\xi_n$ - число орлов после $n$ бросаний, и нас интересует предел при $n\to\infty$ вероятности

$$\mathbf P_n=\mathsf P\left(\frac{\nu_1}{1}\leqslant x, \frac{\nu_2}{2}\leqslant x,\ldots,\frac{\nu_n}{n}\leqslant x\right) = \mathsf P\left(\nu_1\leqslant x, \nu_2\leqslant 2x, \ldots, \nu_n \leqslant nx\right).$$

Эта вероятность не превосходит вероятности последнего события в пересечении, поэтому при $x < \frac12$ её предел равен нулю по любому из законов больших чисел:

$$\mathbf P_n \leqslant \mathsf P\left(\frac{\nu_n}{n}\leqslant x\right) \to 0 \ \text{при} \ n\to\infty.$$

При остальных $1>x\geqslant \frac12$ введём случайные величины $\xi_i'=\xi_1-x$, $\mathsf E\xi'_i\leqslant 0$. И обозначим через $S_n=\xi_1'+\ldots+\xi_n'$ частичные суммы этих величин. Интересующая нас вероятность перепишется в виде

$$\mathbf P_n=\mathsf P(S_1 \leqslant 0, S_2\leqslant 0,\ldots, S_n\leqslant 0). $$

Таким образом, это есть вероятность случайному блужданию с нулевым или отрицательным матожиданием ни разу не попасть на положительную полуось до момента $n$ включительно. Если $x=\frac12$, то это блуждание с нулевым сносом, и для него такая вероятность стремится к нулю с ростом $n$, поскольку супремум этого блуждания равен $+\infty$ п.н.

А вот если $\frac12 < x < 1$, то $\mathbf P_1$ имеет собственный предел, равный

$$\mathbf P_n \to \mathsf P\left(\sup_n S_n \leqslant 0\right) =\dfrac{\mathsf E\xi_1'}{\mathsf E\chi_0^{-}}= \dfrac{1}{\mathsf E\eta_0^{-}} \in (0,\,1),$$

где (в обозначениях А.А.Боровкова, см. ТВ, гл.11, параграф 1, следствие 2) $\eta_0^{-}=\min\{k\geqslant 1\,:\,S_k\leqslant 0\}$ - номер первой неположительной суммы, $\chi_0^{-}=S_{\eta_0^{-}}$ - значение первой неположительной суммы.

К сожалению, значения $\mathsf E\chi_0^{-}$ или $\mathsf E\eta_0^{-}$ вычислить аналитически возможно в редких ситуациях. Одна из таких ситуаций - когда наше блуждание целочисленно и полунепрерывно сверху, т.е. максимальное положительное значение скачка равно 1. Наши скачки равны $1-x$ и $0-x$ с равными вероятностями, целочисленностью тут не пахнет, но если поделить значения (суммы тогда тоже поделятся) на $1-x$, то при $\frac{x}{1-x}\in \mathbb N$ искомую вероятность можно посчитать.

Пусть $\eta_i=\frac{\xi_i'}{1-x}$ и $\frac{x}{1-x}=k\in\mathbb N$, т.е. $x=\frac{k}{k+1}$ для некоторого натурального $k>1$. Пусть $\tilde S_n = \eta_1+\ldots+\eta_n$. Снабдим тильдами номер первой неположительной суммы и её значение для этой новой последовательности сумм.

Тогда

$$\mathbf P_n \to \mathsf P\left(\sup_n \tilde S_n \leqslant 0\right) =\dfrac{\mathsf E\eta_1}{\mathsf E\tilde\chi_0^{-}}= \dfrac{1}{\mathsf E\tilde\eta_0^{-}}=1-p,$$

где число $0<p<1$ таково, что для производящей функции $f(s)=\mathsf Es^{\eta_1}$ выполнено $f(\frac1p)=1$. У уравнения $f(s)=1$ два корня: $1$ и $\frac1p> 1$, нам нужен второй.

П.ф. легко выписывается, уравнение получается $s^{k+1}-2s^k+1=0$.

Например, если $x=2/3$, т.е. $k=2$, то $\frac1p=\frac{1+\sqrt{5}}{2}$, и $\mathbf P_n \to 1-p=\frac{\sqrt5-1}{\sqrt5+1}$.

В случаях, когда $x\neq \frac{k}{k+1}$, значения $\mathsf E\chi_0^{-}$ или $\mathsf E\eta_0^{-}$, а следовательно, и искомый предел вероятности, можно получать разве только моделированием.

[--mS--]

Чисто на всякий случай: никакой $1/2$ или, тем паче, $1$ в пределе не будет ни при каком фиксированном $x<1$. Разве что при $x \nearrow 1$ вероятность того, что доля орлов ни разу не превысит $x$, стремится к $1/2$.

[Sirion]

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

[gris]

А кто упоминал $1/2$, а тем паче, $1$?
Только я.Чисто на всякий случай оправдываюсь. Первый бросок с вероятностью $1/2$ это орёл. При этом сразу достигается максимальная доля орлов — $1$. Если выпадает решка, то максимальную долю можно получить лишь в пределе, когда начиная с некоторого момента почти все броски будут орлами. Вероятность такого события равна нулю, поэтому вероятность того, что в бесконечной серии хотя бы раз будет достигнута ровно максимальная доля, то есть $1$, равна ровно $1/2$. А $1$ больше любого числа из интервала $[0,1)$. Поэтому

gris в сообщении #676513 писал(а):

С вероятностью $1/2$ доля гербов хотя бы раз превысит любое число из $[0,1)$.

Но это же не та вероятность, о которой спрашивается в задаче, хотя она даёт нестрогую оценку сверху требуемой вероятности. Впрочем, достаточно очевидно, что для конкретного числа, меньшего $1$, эта оценка вполне строгая, а $1/2$ достигается именно в пределе при стремлении к $1$. Для самой же $1$ чисто формальный ответ будет $1$, ибо доля орлов ни разу не может превысить $1$.
Я сам представлял график этой вероятности так: ноль до $x=0.5$, потом некая гладкая кривулька до $1/2$ и единица, начиная с $1$. Вчера сквозь сон прикинул этот график для небольшого числа бросаний. Интересно посмотреть на сходимость, посчитав точные значения функции распределения для различных значений $n$.

[nikvic]

Кривулька ступеньчатая, а не гладкая.

[--mS--]

gris в сообщении #676689 писал(а):

Поэтому

gris в сообщении #676513 писал(а):

С вероятностью $1/2$ доля гербов хотя бы раз превысит любое число из $[0,1)$.

Но это же не та вероятность, о которой спрашивается в задаче, хотя она даёт нестрогую оценку сверху требуемой вероятности.

Как это не та - именно та, точнее - обратная. Доля гербов хотя бы раз превысит произвольное число $x$ из $[0,\,1)$ с вероятностью $1$ - для $x\leqslant \frac12$, и с вероятностью $p=p(x)\in\left(\frac12,\,1\right)$ - для $\frac12<x<1$.
И никогда - с вероятностью $\frac12$.

[gris]

"Как это не та - именно та, точнее - обратная."
Восхищён!!!

Но я говорю про другое событие.
У Вас: $\forall x\in [0,1) P(d>x)<1/2$.
У меня: $P(d>x|\forall x\ x\in [0,1) )=1/2$
Нет противоречия.
Впрочем, я не отвергаю гипотезу, что я не прав. Разве вероятность того, что макимальная доля орлов в бесконечной серии бросаний будет равна 1, не равна ровно $1/2$? Я, правда, боюсь, что точное значение максимальной доли нельзя корректно определить в данной задаче.

nikvic, я надеялся, что она вообще линейна от половинки до единицы .
А Вы имеете в виду бесконечный случай?

[--mS--]

gris в сообщении #676738 писал(а):

Разве вероятность того, что макимальная доля орлов в бесконечной серии бросаний будет равна 1, не равна ровно $1/2$? Я, правда, боюсь, что точное значение максимальной доли нельзя корректно определить в данной задаче.

Равна, разумеется. Просто потому, что $\mathsf P\left(\sup_n \frac{\nu_n}{n}=1\right) = \mathsf P(\xi_1=1)=\frac12$. Всё тут корректно определено.

Это равенство очевидно, например, отсюда:

$$\mathsf P\left(\sup_n \frac{\nu_n}{n}=1\right) =1-\mathsf P\left(\sup\limits_{n\geqslant 1} \frac{\nu_n}{n}<1\right) =1-\mathsf P(\nu_1-1<0, \nu_2-1<0,\ldots, \nu_n-n<0,\ldots)=$$ $$=1-\mathsf P(\sup\limits_{n\geqslant 1} S_n<0),$$

где $S_n$ - сумма слагаемых $\xi_i-1$, принимающих значения $-1$ и $0$. Ну а событие $\left\{\sup\limits_{n\geqslant 1} S_n<0\right\}$, очевидно, есть событие $\{\xi_1-1=-1\}=\{\xi_1=0\}$, поскольку скачков вверх не бывает вообще. Это и есть в точности то, что Вы писали выше, обосновывая одну вторую.

З.Ы. Вместо $\ldots$ под вероятностями (это уже для маньяков) можно рисовать точку и брать предел по сужающейся последовательности событий, превращая конечный максимум в супремум.

-- Вс янв 27, 2013 20:12:53 --

Только к вопросу ТС в первом сообщении это всё никак не относится.