Две интересных задачки по терверу

mtk79

Обе из задачника Коршунов-Фосс.
1) В схеме Бернулли p - вероятность исхода "1", 1- p - вероятность исхода "0". Найти вероятность того, что цепочка 00 появится раньше 111.
2) Два игрока А и В, имеющие соответственно капиталы a и b играют в азартную игру, состоящую из отдельных партий. Предположим, что каждую партию игрок А выигрывает с вероятностью p и проигрывает с вероятностью 1- p. После каждой партии проигравший уплачивает 1 рубль выигрывшему. Игра продолжается до разорения одного из играков. Найти вероятность того, что разорится второй игрок, если а) p=1/2, б) p>1/2.
Если кто в курсе — напишите, плз, намек на решение.
Если большие подозрения, что первая — не сильно корректная
Из-за того, что испытание бесконечно, в испытаниях могут
появляться последовательности вида один 0 — одна
или две 1 сколь угодно долго, а, главное, непериодично, потому что
есть две базовых связки (01 и 011). Каждая посл-ть их задает
дробное двоичное число, причем множество связок можно также
представить в виде дв.числа, ставя в соответствие связке 01 — 0 а
связке 011 — 1 (или наоборот). Очевидно, что теперь уже любая
бесконечная посл. нулей и единиц (новых) реализует как нашу
посл-ть из исходных 0 и 1, для которых есть вер-и, так и
произвольное двоичное число между 0 и 1 т.е. коих мощность
континуума. Поэтому я не представляю, как отноримировать — ни общее
число равновозм.исходов — ни относительное — посчитать
невозможно, а если ограничиться каким-то числом
испытаний N и посчитать P_N — то осмысленное условие будет
— но предела \lim_{N \to \infty}P_N все равно не существует, потому что пределы подпоследовательностей
(если они и будут сущ-ть) будут зависеть от того, какие подпоследовательности взяты
М.б., я гоню.

griz_a

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

vc_orlov

-ая задача-это стандартная задача о случайном блуждании и моменте остановки,можешь посмореть решение в книге Ширяева- "Вероятность 1 " или в Козлове. ПО поводу первой могу предложить следующее.Надо описать все указанные события и проссумировать их вероятности.
событие 00 произойдет до события 111 если будут использоваться следующие наборы для постоения цепи - 01,011, но цепь может начаться еще с 1 и 11 , надо это учесть и закрыть все эти последовательности 00 получится q^2(pq)^k1(p^2q)*k2(1 + p +p^2теперь это надо умножить на вероятность последовательности заканчивающейся 111 , это последовательности состоящие из 10,110,0, потом проссумировать по всем индексам и получится ответ. Вроде так.

mtk79

Спасибо всем, кто написал реплику, тем, кто написал несколько — спасибо в степени кратности реплик.
А Ширяев "Вероятность -1" и А Ширяев "Вероятность" (1980г.) , которую мне из сети удалось выудить — это одно и то же?
"Козлов" — это Козлов М.В. Элементы теории вероятностей в примерах и задачах ?

griz_a

"Козлов" — это Козлов М.В. Элементы теории вероятностей в примерах и задачах ?

да
А Ширяев "Вероятность -1" и А Ширяев "Вероятность" (1980г.) , которую мне из сети удалось выудить — это одно и то же?

нет, но эта задача может быть и там, и там

natunchik

Ты что-то заморочился страшно. Матожидание выпадения двух нулей ты же можешь посчитать? То, что там бесконечная сумма, в которой, страшно подумать, где-то (бесконечно далеко) даже есть слагаемые, соответствующие бесконечным последовательностям, тебе не сильно мешает ведь?
Так и здесь — берёшь и считаешь. Фиксируешь длину цепочки, выписываешь цепочки, в которых выиграл первый, второй, отдельно складываешь цепочки, в которых никто не выиграл. Замечаешь, что доля этих цепочек экспоненциально падает при удлинении длины, что позволяет тебе записать предел.
Кстати, любопытный факт, в такого типа задачах вопросы "у какой последовательности меньше матожидание первого выпадения" и "какая последовательность выпадает раньше" могут быть разные ответы. Причём отношение "выпадает раньше" нетранзитивно.
Кстати, название темы "теория _в_еры", это по обкурке получилось или специально?

manggol

Действительно задача не вполне корректная, поскольку разумного вероятностного пространства нет.
че то я не врубаюсь как это не корректная. по сути задача такая - в пространстве односторонних последовательноатей нулей и единиц с бернуллиевской мерой (p,1-p) найти меру множества тех последовательностей у которых 00 идет раньше чем 111.
Подскажи место, где написано что-то некорректное?
P.S.блин, и фраусоболева - аспирант кафедры Теории Вероятностей.
это даже не стыдно за мехмат, а что то запредельное.

manggol

задача не вполне корректная, поскольку разумного вероятностного пространства нет.
оказывается для схемы Бернулли с бесконечным числом испытаний нет разумного определения вероятностного пространства.
Уважаемый Аспирант ТеорВера, вы изучали вообще Теорию Случайных Процессов или посчитали это лишней тратой времени для вероятностника?

mtk79

Я, кстати, до сих пор не понимаю, если выпали .....00.... и далее не выпали три единицы --- такие слова нужно в полную вер-ть данной задачи включать — или только вида
...00....111.... ?
Кстати, я правильно понимаю, что если обозначить l=01, m=011, n=анти-l=10, s=анти-m=110,
то, если до выпадения 00 подслово было только из букв l и m (с возможными префиксами 1 и 11, что принципиально мало на что влияет) — то после выпадения 00 и перед 111 в подслове, кроме s и n, могут встревать еще произвольные комбинации нулей (например
00(нужный)00000sn0000s111?

griz_a

В общем, если исключить жесткий тупняк и сообразить, что искомое множество (два нуля встретились раньше трех единиц) измеримо, как счетное объединение измеримых (два нуля встретились на отрезке длины n раньше трех единиц то получится, что у него, как у всякого измеримого, есть вероятность, которую для счетного объединения измеримых вложенных (а каждое следующее больше предыдущего, очевидно) считается простым предельным переходом по n->\infty

a101



1) В схеме Бернулли p - вероятность исхода "1", 1- p - вероятность исхода "0". Найти вероятность того, что цепочка 00 появится раньше 111.
Для сокращения дальнейших записей будем считать, что вероятность 0 равна q ( = 1-p).
Рассмотрим первый 0 в последовательности. Логично, что до него цепочка 00 появиться не могла. Если до первого 0 появилось цепочка 111 - то значит первые три цифры последовательности = 1 и вероятность этого p^3.

Будем двигаться теперь по 0. Вероятность того, что к следующему 0 мы получим цепочку 00 равна просто q (следующий символ после 0 равен 0). Что получим цепочку 111 - p^3 (следующие три числа после 0 равны 1). Соответственно x = 1 - q - p^3 вероятность того, что к следующему 0 не получена ни одна из требуемых цепочек.

Итого, вероятность того, что 00 встретится раньше равна:
(1 - p^3) * (q + x * q + x^2 * q + x^3 * q + ...) = (1 - p^3) * q / (1 - x) = (1 - p^3) * q / (q + p^3) = (1 - p^3) * (1 - p) / (1 - p + p^3).
Преобразовывать лень :(

a101



2) Два игрока А и В, имеющие соответственно капиталы a и b играют в азартную игру, состоящую из отдельных партий. Предположим, что каждую партию игрок А выигрывает с вероятностью p и проигрывает с вероятностью 1- p. После каждой партии проигравший уплачивает 1 рубль выигрывшему. Игра продолжается до разорения одного из играков. Найти вероятность того, что разорится второй игрок, если а) p=1/2, б) p>1/2.
Пусть P(x) - вероятность того, что выиграет первый (разорится второй если у первого игрока x монет.
Тогда:
P(0) = 0 (все монеты у второго игрока, первый разорен)
P(a+b) = 1 (все монеты у первого)
P(x) = p * P(x+1) + (1-p) * P(x-1)
Последнее уравнение - рекурента. Ее решение (при p != 1/2)
P(x) = c1 + c2 * 1-p)/p)^x
Итого на с1 и с2 имеем условия
с1 + с2 = 0
с1 + с2 * 1-p)/p)^(a+b) = 1
c2 = 1 / ( 1-p)/p)^(a+b) - 1 )
c1 = -c2 = - 1 / ( 1-p)/p)^(a+b) - 1 )
Итого наш ответ
P(a) = 1 / ( 1 - 1-p)/p)^(a+b) ) - 1-p)/p)^a / ( 1 - 1-p)/p)^(a+b) )
====
Если p = 1/2, то решение рекуренты
P(x) = c1 + c2 * x
Учитывая начальные условия сразу получим, что
c1 = 0
c2 = 1 / (a+b
то есть вероятность победы первого игрока равна
P(a) = a / (a+b)

mtk79

интересная мысль, но можно подоходчивее в нек.местах?
например,
 
P(x) = p * P(x+1) + (1-p) * P(x-1)

например, перед фатальным проигрышем игрока В, у него 1 рупь, а у А — a+b-1 c с вероятностью P(a+b-1). Тогда при выигрыше А (c вер-ю р скорее получается
P(x) = p * P(x-1 x=a+b

a101



Тогда при выигрыше А (c вер-ю р скорее получается
P(x) = p * P(x-1 x=a+b
Если у A (a+b-1) рупь, то с вероятностью p он побеждает (p = p * 1 = p * P(a+b а с вероятностью (1 - p) у него становится (a+b-2) рупей и дальше его вероятность победить P(a+b-2). Что не так? Я не понимаю :(



P(x) = p * P(x+1) + (1-p) * P(x-1)
Это условие как раз на 1 <= x <= a+b-1. В крайний точках условие другое (оно как раз нами и задается, как 0 и 1).

a101



можно подоходчивее в нек.местах?


P(x) = p * P(x+1) + (1-p) * P(x-1)
Если у первого игрока сейчас x монет, то с вероятностью p на следующий ход у него будет (x+1) монета, а с вероятностью (1-p) будет (x-1) монета. Отсюда и получается рекурентное условие на веротность победы первого игрока.

mtk79

Все, я понял: я просто невнимательно прочитал, чего именно вероятность Р(х) — я вбил себе в голову, что это вер-ть самого события, что у А будет х рублей.Спасибо

natunchik

ААА!
Я понял, отчего ты недоумеваешь! Ты первый раз в жизни увидел континуум меры нуль в одномерном пространстве!
Так вот, и такое бывает.
Если ты хочешь решить задачку строго по правилам теории веры, то нужно в процессе решения произнести некоторые ключевые слова.
Переформулируем задачу так, чтобы рассматривать только бесконечные последовательности (ну, типа, чуваки же могут продолжить кидать монетку и после выпадения 00 или 111 сопоставим каждой последовательности число из отрезка [0, 1) в двоичной записи (для p = 0.5 — естественным образом, выяснение того, как следует перекосить распределение для других р, я оставляю в качестве самостоятельного упражнения тогда евклидова мера (длина) любого измеримого множества соответствует вероятности и всё такое. Там ещё есть нюанс с двойным представлением конечных дробей, у него есть остроумное разрешение, но здесь на полях не хватит места, чтобы его изложить =)
Разобьём отрезок на 2^n полуинтервалов, прям по нашим координатным точкам. Я возьму для примера n = 8. Значица, имеем полуинтервалы [0, 0.001 [0.001, 0.010) и так далее, в двоичке, естественно. Заметим, что весь первый полуинтервал принадлежит к выигрышному множеству для первого игрока, как, впрочем, и весь второй, и ещё [0.100, 0.101). А полуинтервал [0.111, 1) — к выигрышному множеству второго игрока. Если выписать формулу для произвольного n, то мы получим два выражения, оценки снизу меры первого и второго множества. Если мы теперь устремим n к бесконечности, то, прямо по определению меры через покрытия, получим меры этих множеств. То есть мы получим два числа, которые в сумме дают единицу, а, значит, множества измеримы и это их меры. Заодно узнаем, что у третьего множества, где ни один игрок не выигрывает, мера нулевая.
Вот как-то так.
Оставить комментарий
Имя или ник:
Комментарий: