Бросаю монетку.

[toser]

Решил написать после чтения темы «Сколько бросать монетку, чтобы два раза подряд решка выпала?», topic98788.html.
Только в качестве примера рассматриваю задачу подбрасывания монетки до выпадения трех гербов подряд.
Данную задачу можно описать с помощью графа

$$\xymatrix{B_1\ar@/^10pt/[rr]^{a}&&B_2\ar@/^10pt/[ll]_{a}\ar@/^10pt/[rr]^{a}&&B_3\ar@/^20pt/[llll]_{a}\ar@/^10pt/[rr]^{a}&&B_4}$$

В качестве вершин графа принимаю состояния
$B_1$- не выпало ни одного герба
$B_2$- герб выпал однин раз
$B_3$- герб выпал два раза подряд
$B_4$- герб выпал три раза подряд
Традиционно, в качестве характеристики перехода рассматривается вероятность перехода из одного состояния в другое. В нашем случае $a=\frac 12$
При желании, для данной задачи можно определить матрицу перехода
$V =\left( \begin{array}{cccc} 1/2 & 1/2 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 \\ 1/2 & 0 & 0 & 1/2 \\ 0 & 0 & 0 & 1 \end{array} \right) $
и вектор состояния ${B_1,B_2,B_3,B_4 }$.
Состояние данной системы после каждого броска определяется произведением вектора состояния на матрицу перехода. Используя данный алгоритм, положив начальное условие ${1,0,0,0}$, можно определить функцию распределения случайной величины и ее характеристики, например математическое ожидание, то есть решить задачу «сколько раз надо бросить монету, что бы выпало 3 герба». К сожалению, этого сделать не удается, так как ряд, определяющий математическое ожидание расходится (см. topic98788.html) . Это совсем не значит, что искомое математическое ожидание не существует. Для достижения поставленной цели, в среднем, достаточно сделать 14 бросков. (см. там же topic98788.html).
Решил построить функцию распределения, правильность которой хочу проверить по математическому ожиданию. За основу беру ту же матрицу перехода V, которую несколько модернизирую.
В результате модернизации получаю целочисленную матрицу
$M =\left( \begin{array}{cccc} 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 2 \end{array} \right) $
Матрица M получается из матрицы V, если строки 1-4 матрицы V умножить на 2. Матрица M обладает следующим свойством, сумма всех элементов по ее строкам равняется 2.
Определение $i$-го значения функции распределения случайной величины ${F_1,F_2,…,F_i,…}$ происходит по следующему правилу. Матрица $M$ возводится в $i$-ю степень. В результате получается матрица $M^i$, которая умножается на вектор исходного состояния. В результате умножения получается вектор ${B_{i,1},B_{i,2},B_{i,3},B_{i,4} }$, на основании которого вычисляется значение $F_i$
$F_i = \frac{B_i_4}{\sum^4_{j=1}B_i_j}$
По $F_i$ определяются значения $f_i$ как
$f_i=F_i-F_{i-1}$
Математическое ожидание числа бросков определяется по традиционной форме
$E=\sum _{i=1}^{\infty} {if_i}$
Вычисления выполнены в Microsoft Excel с точностью до 5 знаков после запятой. После $i=212$ Excel воспринимает вычисленную сумму, как 14.
Используемый в вычислениях подход взят из тем topic105812.html и topic111233.html. Предупреждаю, последняя тема закрыта за агрессивное невежество.
Не удержался, значения $B_i_4$ посмотрел в энциклопедии целочисленных последовательностей. Оказывается, это последовательность A050231(см. https://oeis.org/A050231), которая описана на английском языке, как
«${a(n)}$ is the number of $n$-tosses having a run of 3 or more heads for a fair coin (i.e., probability is $\frac{a(n)} {2^n}$)».
Яндекс сделал перевод данной фразы
« ${a(n)}$-количество $N$-бросков, имеющих пробег 3 или более голов для справедливой монеты (т. е. вероятность равна $\frac{a(n)} {2^n}$ )».
Буду признателен за более корректный перевод на русский язык.
В заметке по данной последовательности есть ссылка на первый том В. Феллера «Введение в теорию вероятностей и ее приложения».
Признаюсь, информации по рассматриваемой задаче в книге не нашел. Может быть, кто-нибудь даст более точную ссылку?

[arseniiv]

toser в сообщении #1394083 писал(а):

К сожалению, этого сделать не удается, так как ряд, определяющий математическое ожидание расходится

worm2 в конце той темы пишет, что ничего не расходится. И это действительно так.

toser в сообщении #1394083 писал(а):

Это совсем не значит, что искомое математическое ожидание не существует.

Или значило бы.

-- Пн май 20, 2019 01:36:15 --

Ваш граф с вероятностями — это марковская цепь; я тоже как-то раз переоткрыл её с нуля. Её можно применить к этой задаче сразу же, не вводя целочисленную матрицу и не занимаясь лишний раз делением в следующих вычислениях. Вероятность за $n$ бросков попасть в нужное состояние получается равной $\mathbf e^4 V^n \mathbf e_1$, где $\mathbf e_1 = (1, 0, 0, 0)^t$ и $\mathbf e^4(x_1,\ldots,x_4) = x_4$. Чтобы не корректировать дальше неудобное определение (нам же нужно отмечать ровно тот бросок, который приводит к желаемому), надо дополнить всё состоянием $B_5$, в которое мы безусловно перейдём из $B_4$ при любом броске. Матрица перехода цепи (и тут я её транспонирую как надо для своей формулы) станет иметь вид

$$\begin{bmatrix} 1/2 & 1/2 & 1/2 & & \\ 1/2 & & & & \\ & 1/2 & & & \\ & & 1/2 & & \\ & & & 1 & 1 \end{bmatrix}$$

(нули опущены). Вот теперь $\mathbf e^4 V^n \mathbf e_1$ — это уже вероятность за ровно $n$ бросков достичь нужного состояния, $n+1$ бросок уже даст перелёт. Это уже удобно использовать в вычислении матожидания: $\sum\limits_{n=0}^\infty n\mathbf e^4 V^n \mathbf e_1$. Это можно посчитать, сделав некоторые наблюдения о степенях $V$ — найдя её характеристический многочлен или просто собственные значения и векторы. Это позволит свести ряд по степеням $V$ в ряд не по степеням $V$, который легко будет посчитать.

[toser]

arseniiv
Прежде, чем последовать Вашему совету, а именно,

arseniiv в сообщении #1394087 писал(а):

свести ряд по степеням $V$ в ряд не по степеням $V$, который легко будет посчитать.

меня интересует Ваше мнение по математическому ожиданию рассматриваемого случайного процесса.
Математическое ожидание существует?
Если математическое ожидание существует, то чему оно равно?
Хочу обратить внимание на то, что решается задача подбрасывания монетки до выпадения трех гербов подряд, а не рассчитывается приведенный в стартовом сообщении граф.

[arseniiv]

toser в сообщении #1394254 писал(а):

меня интересует Ваше мнение по математическому ожиданию рассматриваемого случайного процесса.
Математическое ожидание существует?

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

toser в сообщении #1394254 писал(а):

а не рассчитывается приведенный в стартовом сообщении граф

К чему это противопоставление? Не так трудно аккуратно доказать, что «через граф» (через цепь Маркова), получается ровно та же величина ($\sum\limits_{n=0}^\infty n\mathbf e^4 V^n \mathbf e_1$), то есть или оба этих значения не определены, или определены и равны.

[--mS--]

toser в сообщении #1394254 писал(а):

Математическое ожидание существует?
Если математическое ожидание существует, то чему оно равно?
Хочу обратить внимание на то, что решается задача подбрасывания монетки до выпадения трех гербов подряд, а не рассчитывается приведенный в стартовом сообщении граф.

В чём проблема-то? Математическое ожидание числа подбрасываний до выпадения $k$ гербов подряд равно

$$ \dfrac{1-p^k}{qp^k}, $$

где $p$ - вероятность герба, $q$ - вероятность решки.

Для $k=2$. Пусть $M$ - искомое матожидание. Ждём до первого успеха время в среднем $\frac1p$.
С вероятностью $p$ следующий снова успех, и испытания закончились, матожидание равно $\frac1p+1$.
С вероятностью $q$ следующая неудача, и испытания после неё начнутся заново, и снова надо ждать в среднем время $M$.
Тогда матожидание равно $\frac1p+1+M$. Итого по формуле полной вероятности для матожиданий

$$M=p\cdot \left(\frac{1}{p}+1\right) + q \cdot \left(\frac1p+1+M\right).$$

Откуда $M=\dfrac{p+1}{p^2}=\dfrac{1-p^2}{qp^2}$.

То же самое для произвольного $k$: после первого успеха может быть
Н с вероятностью $q$ - тогда $M=\left(\frac1p+1+M\right)$,
УН с вероятностью $pq$ - тогда $M=\left(\frac1p+2+M\right)$,
УУН с вероятностью $p^2q$ - тогда $M=\left(\frac1p+3+M\right)$ и т.д.,
УУ..УН с вероятностью $p^{k-2}q$ - тогда $M=\left(\frac1p+k-1+M\right)$ и, наконец,

$k-1$ успех УУ..УУ с вероятностью $p^{k-1}$ - тогда $M=\left(\frac1p+k-1\right)$.

Итого

$$M=q\left(\frac1p+1+M\right)+pq\left(\frac1p+2+M\right)+p^2q\left(\frac1p+3+M\right)+\ldots $$ $$+p^{k-2}q\left(\frac1p+k-1+M\right)+p^{k-1}\left(\frac1p+k-1\right).$$

Выражая отсюда $M$, получим $M=\dfrac{1-p^k}{qp^k}$.

[toser]

Спасибо,--mS--
Решение, приведенное Вами полностью повторяет решение, приведенное в сообщении http://dxdy.ru/post1030096.html . темы «Сколько бросать монетку, чтобы два раза подряд решка выпала?», topic98788.html. Возможно, я плохо написал об этом в стартовом сообщении.
Сейчас мне ничего не остается, как подставить значения $p=q=\frac 1 2$ в предлагаемые формулы и снова получить величину 14. Я не возражаю, что математическое ожидание рассматриваемого случайного процесса существует и оно равно 14 броскам монеты. Кстати, моделирование данного процесса методом Монте-Карло дает примерно такой же результат.
Пытаюсь получить уже известное значение математического ожидания методом, который предлагает arseniiv, «через граф» (через цепь Маркова). У меня ничего не получается. Возможно, я что-то делаю не так. В связи с этим, меня интересует, - как получить уже известное значение математического ожидания через цепь Маркова, с помощью матрицы переходов $V$. У меня получается, что ряд, построенный на основе цепи Маркова, расходится.

[Someone]

toser в сообщении #1394450 писал(а):

У меня получается, что ряд, построенный на основе цепи Маркова, расходится.

Ну так напишите своё решение, а мы посмотрим. Глядишь, кто-нибудь что-нибудь и подскажет.

[Lia]

toser в сообщении #1394450 писал(а):

Решение, приведенное Вами полностью повторяет решение, приведенное в сообщении http://dxdy.ru/post1030096.html . темы «Сколько бросать монетку, чтобы два раза подряд решка выпала?», topic98788.html .

Ничего подобного.

[toser]

Someone
Спасибо за совет. Справился сам. Проверил простым расчетом.
arseniiv
Вы правы. Целочисленную матрицу можно было и не вводить.
Самое интересное, что число итераций для вычисления величины математического ожидания через матрицы M и V одинаковое.

[arseniiv]

Тут всё просто, они же отличаются на умножение на константу.