Какова вероятность появления последовательности?

Question

[Prudya]

Сам придумал себе задачу и сам ломаю над ней голову. Имеется последовательность из n 0 и 1. Найти вероятность того, что в данной последовательности найдется хотя бы одна подпоследовательность из подряд идущих 0 или 1 длины m, если мы считаем вероятность появления 0 и 1 в ячейке равными 0.5. Если говорить ещё более простыми словами, то нужно найти вероятность того, что из n бросков монетки мы хотя бы раз выбьем m орлов или решек подряд.

Comments

[rPman]

Не играй в казино

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

Если же участники играют по честному то основная стратегия - маргентейл, манипуляции ставками (удвоение при проигрыше), в этом случае сливает игрок с меньшими суммами в кармане.

[Prudya]

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

[Максим Припадчев]

Prudya, Ну тогда при чем здесь нахождение вероятностей для орлов или решек подряд. У тебя дискретная случайная переменная, найди для нее ожидаемую величину и все. Если она отрицательна мы на длинной дистанции будем в убытках, если положительная в плюсе, если 0 то что называется fair game.
p - вероятность успеха стратегии
x1 - полученные деньги при выигрыше
x2 - затраты на стратегию
E(X) = x1 * p + x2 * (1 - p) - где x2 (отрицательное число)

[Prudya]

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

[Максим Припадчев]

Prudya, Смотри, будь внимательным, можно считать есть у нас последовательность размера n и вероятность содержания в этой последовательности подпоследовательности размера m. А есть например ты объявляешь переменную количество бросков, игр, попыток (что там у тебя) что бы ПЕРВЫЙ раз увидеть повторяющееся последовательность размером m. И вероятность в такой переменной будет. Вероятность например 3 попыток что бы ПЕРВЫЙ раз увидеть два ОРЛА или ДВЕ РЕШКИ. И еще формулы будут разнится для четного количества попыток или для нечетного. Я вчера после того как не смог ответить на твой вопрос (что меня задело) да еще рекурсивный подход у меня не давал ответов, нашел научную работу на эту тему на английском, так что изучаю. Вообще вопрос хороший ты задал, тема имеет множество полезных применений.

Answer 1

[Alexandroppolus]

Прямая формула что-то не вырисовывается, а вот рекуррентная - вполне.

Покажу сразу на примере: N бросков, М = 4, т.е. считаем F4(N)
Неважно, что выпало первым броском, пусть, например, 0. Теперь есть следующие варианты:

1) Вторым броском выпадает 1 (т.е. не то, что в первом броске). Вероятность такого дела 1/2, и задача сводится к F4(N-1) - первый бросок прошел впустую, но ещё "не всё потеряно".
2) Вторым и третьим выпадает 0, 1. Вероятность 1/4, задача сводится к F4(N-2)
3) Вторым, третьим и четвертым выпадает 0, 0 ,1. Вероятность 1/8, задача сводится к F4(N-3)
4) Вторым, третьим и четвертым выпадает 0, 0 ,0. Ура!!! Вероятность 1/8, дальше смотреть не надо.

Итого, по полной вероятности, F4(N) = F4(N-1)/2 + F4(N-2)/4 + F4(N-3)/8 + 1/8

Ну и конечно, база рекурсии: Fm(N) = 0, если N < M

Как обобщить, думаю, очевидно (в знаменателях - степени двойки). Для маленьких M можно нарисовать формулу, например,
Для М = 2, будет F2(N) = F2(N-1)/2 + 1/2, тут прямо сразу выскакивает F2(N) = 1 - 1/(2^(N-1))

Для М = 3, получаем F3(N) = F3(N-1)/2 + F3(N-2)/4 + 1/4, тут кури вот это

и т.д.

Программно вычисляется с помощью "динамического программирования". С правильным подходом - за O(N) по времени и O(M) памяти, навскидку тут хорошо зайдет кольцевой буфер. Если надо, могу расписать, но там ничего сложного.

Comments

[Максим Припадчев]

А задачка то получается не простая, я с утра не проснувшись как следует (думал элементарная), быстренько решил 2 * comb(n,m) / 2^n. Даже ответ написал, уже удалил, Подставил побольше числа (держа m постоянной) а она не растет а падает, а должно быть наоборот. Нужно думать как решать, задача должна иметь аналитичское решение.

[Alexandroppolus]

Максим Припадчев, я вбил в ВольфрамАльфа рекурсии для М = 3 и М = 4
Явные формулы получаются кошмарные, непонятно, как их обобщать. Думаю, это не доставит эстетического удовольствия автору вопроса )

[Максим Припадчев]

Alexandroppolus, У меня проблема следующая.
1- Орел
0 - Решка
Возьмем пример n = 4, m =2, И так количество последовательностей 2^n это очевидно., то есть всего у нас возможно 16 последовательностей каждая с одинаковой вероятностью. Например нам выпала последовательность (1,1,1,1) если мы ее посчитаем за ОДИН успех то есть она содержит в себе повторение орлов длинной два то моя формула 2 * comb(m,n) / 2^n. Должна работать (она и работает на каком нибудь n=3 и m =2 ).Но по идее чем длиннее последовательность тем больше шансов встретить повторение.А делитель (количество последовательностей растет значительно быстрее).Вот тут я туплю и что то упускаю. Если мы считаем что такая последовательность содержит в себе 4 успеха, то у меня получается Количество успехов превышает размер пространства выборки, как следствие вероятность получается больше единицы что полный абсурд.

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

[Alexandroppolus]

Максим Припадчев, для М=2 проще смотреть неуспешные варианты. Их всегда только 2: чередование начиная с орла и чередование начиная с решки. Итого получается вероятность неуспеха 2 / 2^N = 1 / 2^(N-1), как у меня и вышло.

Для М=3 всё сразу намного сложнее, там количество разных неуспешных комбинаций растет экспоненциально (формула будет похожа на Фибоначчи).

[Максим Припадчев]

Alexandroppolus, Да, все так это не простая проблема, которые мы решали когда учились, посчитать совпадающие дни рождения у группы людей, для покера вероятность определенной руки подсчитать и тому подобные стандартные задачи. Для m=2 все так то есть вероятность успеха 1 - 2^(n-1). Тут все очевидно одна последовательность начнется с Решки другая с Орла, дальше всегда чередование. А вот для m больше двух какую то функцию найти совсем не получается. И через разницу m и n тоже ничего не выходит. Пока не пойму как выразить количество не успехов через Фибоначчи. но буду решать задачу. Интересный случай, да и освежить комбинаторику не мешает, можно посмотреть еще в сторону random walk, может там насчет повторений что то имеется хотя по моему нет. Так скоро с алгоритмами машинного обучения разучимся вот такие задачки решать, что нежелательно.

[Alexandroppolus]

Максим Припадчев,

Пока не пойму как выразить количество не успехов через Фибоначчи

да так же, рекурсивно

например, М=3. Пусть P(N) - количество неуспешных последовательностей для М=3. Их есть два непересекающихся набора:

1) все, которые оканчиваются на 01 или 10. Количество таких будет P(N-1), т.е. мы отбрасываем последний элемент и смотрим только предыдущие N-1 бросков

2) все, которые оканчиваются на 100 или 011. Таковых всего P(N-2).

далее берем базовые кейсы
P(1) = 2, последовательности 1 и 0
P(2) = 4, тоже все варианты - 11, 00, 10, 01

ну а P(N) = P(N-1) + P(N-2)

выглядит как удвоенное фибоначчи

для М=4 уже будет 3 слагаемых в рекурсии, и т.д.

[Максим Припадчев]

Alexandroppolus, Спасибо буду разбираться, по поводу двух непересекающихся наборов тут все очевидно.

Но вот по поводу остального что то до меня так и не доходит. (Но это уже мои проблемы буду разбираться). Вы уже достаточно объяснили.
Для n=4 и m=3, мы имеем 6 удовлетворяющих условию последовательностей (1,1,1,1),(1,1,1,0),(1,0,0,0) ну и 3 если начнем с 0. итого 6. Ну и соответственно 10 плохих.

Используя фабиначчи я то получил такие цифры (правильно будет сказать подогнал). Но совсем пока не понял и не думаю что я делаю правильно. Ну да ладно спасибо буду разбираться что я упускаю.

[Prudya]

Alexandroppolus, спасибо за ответ. Да, до рекурсии я сам додумался и запрограммировал (правда без ДП) и хотел использовать для проверки формул, которые смогу получить аналитически. Пока что в голове сидит идея замены количества бросков на количество неудачных серий. Можно посчитать среднюю длину серии (мат.ождиание количества бросков). Она равна сумме ряда x/2^x = 2. Таким образом для n > 1000, в принципе, погрешность будет не такой уж и большой, например если мы заменим 1000 бросков на 500 сыгранных серий. В таком случае считается довольно просто:
1-(1-1/2^m)^500.
Но всё же хотелось бы получить более точный аналитический результат, не прибегая к рекурсии(

[Alexandroppolus]

Prudya, для вычислений рекурсия более чем подходит. Врубай ДП, мемоизацию, будет максимально быстрый и точный результат. А если надо построить график F(N), то прям - доктор прописал.

Если нужны прямые формулы, то, повторюсь, рекурсию для конкретных М закинь на ВольфрмАльфа. Он тебе нарисует эти формулы, ты на них посмотришь с некоторым ...изумлением, и далее вопросы отпадут.