Вероятность определённой последовательности
Вероятность определённой последовательности
Здраствуйте. При разборе этой задачи возник у меня вопрос, который сейчас оформился в самостоятельную задачу.
Предположим, что игральную кость бросают много раз, скажем, 200. Какова вероятность, что хотя бы раз выпадет последовательность 1,2,3,4,5,6 ?
Как подступиться к такой задаче?
Предположим, что игральную кость бросают много раз, скажем, 200. Какова вероятность, что хотя бы раз выпадет последовательность 1,2,3,4,5,6 ?
Как подступиться к такой задаче?
Вероятность определённой последовательности
Посчитать количество подходящих вариантов и поделить на .Dolly писал(а):Source of the post Как подступиться к такой задаче?
Думаю, что точно это не выразить в простой форме.
А вот приближенно оценить это не сложно. Учитывая, что вероятность выпадение такой последовательности начиная с первого элемента равна - т.е. велична очень маленькая, можно отбросить более высокие порядки (выпадение последовательности более одного раза). Тогда приближенная оценка итоговой вероятности (195 случаев объедененных по "или") будет ().
Это оценка сверху.
Вероятность определённой последовательности
zykovzykov писал(а):195 случаев объедененных по "или"
А Вы можете расшифровать эту фразу? Не поняла.
Вероятность определённой последовательности
Последовательность "начинается с 1" или "начинается с 2" или "начинается с 3" или ... или "начинается с 194" или "начинается с 195".
(Ещё раз повторю, что сумма этих вероятностей равна нужной вероятности не точно, а приближенно, т.к. события не являются независимыми.)
(Ещё раз повторю, что сумма этих вероятностей равна нужной вероятности не точно, а приближенно, т.к. события не являются независимыми.)
Вероятность определённой последовательности
1) мне кажется, формула включений-исключений тут в лоб не идет, если знаете как -покажите.
2) однако рекуррентность 6-го порядка тут, кажется, возможна.Используем то, что 123456 не имеет в конце начала самой себя.
Обозначим [math] вероятность наличия хоть одной "123456" в последовательности n бросаний.
Все последовательности n бросаний разобьем на 2 непересекающиеся группы -начинающиеся с 1 и иные Вероятность иных, годящихся нам [math] . Среди начинающихся с 1 опять 2 случая -продолжаются 2-кой или иные. Тут вероятность иных, но годящихся нам опять известна [math], прем дальше...
2) однако рекуррентность 6-го порядка тут, кажется, возможна.Используем то, что 123456 не имеет в конце начала самой себя.
Обозначим [math] вероятность наличия хоть одной "123456" в последовательности n бросаний.
Все последовательности n бросаний разобьем на 2 непересекающиеся группы -начинающиеся с 1 и иные Вероятность иных, годящихся нам [math] . Среди начинающихся с 1 опять 2 случая -продолжаются 2-кой или иные. Тут вероятность иных, но годящихся нам опять известна [math], прем дальше...
Вероятность определённой последовательности
И что получается?
Например вот это:
При будет .
При будет .
Это неверно. Это грубая оценка снизу. ()
В этой формуле не все случаи учтены (например первый элемент равен 1, но последовательность начинается не с первого элемента).
А если попробовать учесть все случаи, то сложно избавится от двойного учёта (когда например одна и та же последовательность учтена несколько раз - в и в ).
Например вот это:
При будет .
При будет .
Это неверно. Это грубая оценка снизу. ()
В этой формуле не все случаи учтены (например первый элемент равен 1, но последовательность начинается не с первого элемента).
А если попробовать учесть все случаи, то сложно избавится от двойного учёта (когда например одна и та же последовательность учтена несколько раз - в и в ).
Последний раз редактировалось zykov 11 окт 2019, 12:05, всего редактировалось 2 раз.
Вероятность определённой последовательности
Вообще:
При будет .
При будет .
Дальше сложнее.
И так далее, с каждым шагом сложнее.
Точный ответ будет имееть сложную форму. Но как я ранее писал, пока , ответ хорошо оценивается как .
При будет .
При будет .
Дальше сложнее.
И так далее, с каждым шагом сложнее.
Точный ответ будет имееть сложную форму. Но как я ранее писал, пока , ответ хорошо оценивается как .
Вероятность определённой последовательности
Ответ стремится к 1. И даже интересно, что это за формула, где ответ стремится к 1
Похожие задачи были в "Конкретной математике" но не могу найти. Рекуррентная формула и производящая функция чисел [math] (это не распределение вероятностей!) точно есть какие-то
Похожие задачи были в "Конкретной математике" но не могу найти. Рекуррентная формула и производящая функция чисел [math] (это не распределение вероятностей!) точно есть какие-то
Вероятность определённой последовательности
Ian писал(а):Source of the post И даже интересно, что это за формула, где ответ стремится к 1
Ну можно взять другую оценку - через "И": .
Она и при неплохо даёт. А при больших даёт правильную асимптотику.
Вероятность определённой последовательности
Ну ведь с точки зрения человека сидящего и просматривающего последовательность слева направо все ясно. он может находиться только в 6 состояниях: ждет начала комбинации, 1цу; только что была 1ца. ждет 2ки; ...только что было 12345, ждет 6, или перейдет в состояние 0 с вер 2/3, или в состояние 1 с вер 1/6.
таким образом строка из 6ти вероятностей состояний по-марковски пересчитывается только через предыдущую. Ну у меня это ексель делает за секунду. Получилось 0,004171289<[math]
За n бросаний [math]равно последней координате 7-мерного вектора
[math]
, соответствующего вероятности попадания в поглощающее состояние 6
таким образом строка из 6ти вероятностей состояний по-марковски пересчитывается только через предыдущую. Ну у меня это ексель делает за секунду. Получилось 0,004171289<[math]
Код: Выбрать все
n pn(0) pn(1) pn(2) pn(3) pn(4) pn(5)
0 0 0 0 0 0 0
1 0 0 0 0 0 0,166666667
2 0 0 0 0 0,027777778 0,166666667
3 0 0 0 0,00462963 0,027777778 0,166666667
4 0 0 0,000771605 0,00462963 0,027777778 0,166666667
5 0 0,000128601 0,000771605 0,00462963 0,027777778 0,166666667
6 2,14335E-05 0,000150034 0,000793038 0,004651063 0,027799211 0,1666881
......
199 0,004149942 0,004278023 0,00491841 0,008760655 0,031813629 0,170128509
200 0,004171289 0,004299367 0,004939741 0,008781903 0,031834383 0,170146298
[math]
, соответствующего вероятности попадания в поглощающее состояние 6
Вероятность определённой последовательности
Действительно, Марковские процессы тут подходят.
И точный ответ выражается в виде степени матрицы 7x7.
И точный ответ выражается в виде степени матрицы 7x7.
Вероятность определённой последовательности
Maxima даже выдала точный ответ:
Вероятность определённой последовательности
У матрицы 7x7 собственные значения: 1, 0.9999786 и ещё пять (одно действительное и две пары комплексных) с модулем менее 0.12.
При возведении в степень 200 только первые два будут иметь сколько-нибудь значимую величину.
1 соответствует тому, что сумма вероятностей сохраняется (всегда равна 1).
0.9999786 близко к , но оно немного отличается.
Все эти собственные значения являются точными корнями полинома .
Если туда подставить , то будет маленькое значение (примерно ), но не ноль.
При возведении в степень 200 только первые два будут иметь сколько-нибудь значимую величину.
1 соответствует тому, что сумма вероятностей сохраняется (всегда равна 1).
0.9999786 близко к , но оно немного отличается.
Все эти собственные значения являются точными корнями полинома .
Если туда подставить , то будет маленькое значение (примерно ), но не ноль.
Вероятность определённой последовательности
zykov писал(а):Source of the post А при больших даёт правильную асимптотику.
Тут я немного погорячился. Асимптотика качественно правильная и даже довольно точная, но имеет небольшую ошибку.
Точная асимптотика: , где находится через собственные вектора.
А - это корень полинома чуть меньше 1 (примерно равен ).
Вероятность определённой последовательности
Я даже не подозревала о таких глубинах в этой задаче. Я и четверти всего написанного не поняла с первого раза. Щас сижу, врубаюсь.
Спасибо всем. Если появятся вопросы, задам.
Спасибо всем. Если появятся вопросы, задам.
Вероятность определённой последовательности
Элементарными методами эта задача не решается (только если приближенно).
Но как Ian заметил, это классический случай Марковских цепей.
Марковские процессы - это мощный инструмент. Обычно эту тему кратко затрагивают в конце курса по теорверу.
В данном случае можно рассмотреть конечный автомат с 7 состояниями, которому на вход подают последовтельность цифр (каждая от 1 до 6).
(В компьютерной области такое называют парсер, как например регулярные выражения в качестве частного случая парсера.)
Вначале автомат находится в состянии 1.
При получении нового входа он переходит из текущего состояния в новое (возможно тоже самое) в соответствии с таблицей (графом автомата).
Так из состояния 1 он переходит в состояние 2, если вход был "1". Иначе остается в состоянии 1.
Из состояния 2 переходит в состояние 3 при входе "2" или в состояние 2 (остается в нём) при входе "1". Иначе переходит в состояние 1.
Из 3 в 4 по входу "3", в 2 по входу "1", в 1 по остальным входам.
Аналогично для состояний 4 и 5.
Из состояния 6 переходит в 7 по входу "6", в 2 по входу "1", в 1 по любому другому входу.
Из состояния 7 всегда переходит обратно в 7 независимо от входа.
Переход в состояние 7 означает что автомат распознал последовательность "123456". После этого автомат остается в этом состоянии.
Таким образом, если автомат оказался в состянии 7 после 200 входов, значит где-то он встретил последовательность "123456" во время этих 200 входов. Если он оказался в любом другом состоянии, то такой последовательности не было.
Теперь рассмотрим вероятности.
Вначале автомат был в состоянии 1 с вероятность 100% процентов.
После первого входа он может перейти в состояние 2 с вероятность 1/6 или остатся в 1 с вероятностью 5/6.
Далее, если он был в состянии 1, будет тоже самое. Если он был в состоянии 2, то он может перейти в состоние 3 с вероятностью 1/6, остатся в 2 с вероятность 1/6 или перейти в 1 с вероятностью 4/6.
И так далее.
Вобщем если перед новым входом автомат имел распределение вероятностей по состониям (их сумма равна 1), то после получения нового входа (где все 6 вариантов имеют одинаковую вероятность, независимую от состояния автомата) вектор нового распределения вероятностей по состояниям автомата получается умножением строки-вектора старых вероятностей справа на матрицу, которую привел Ian.
Если взять вектор и умножить его на эту матрицу 200 раз (или 1 раз на эту матрицу в степени 200), то получим вектор веротностей найти автомат в каждом из его 7 состояний после 200 входов. Вероятность - это вероятность того, что автомат где-то встретил последовательность "123456".
Но как Ian заметил, это классический случай Марковских цепей.
Марковские процессы - это мощный инструмент. Обычно эту тему кратко затрагивают в конце курса по теорверу.
В данном случае можно рассмотреть конечный автомат с 7 состояниями, которому на вход подают последовтельность цифр (каждая от 1 до 6).
(В компьютерной области такое называют парсер, как например регулярные выражения в качестве частного случая парсера.)
Вначале автомат находится в состянии 1.
При получении нового входа он переходит из текущего состояния в новое (возможно тоже самое) в соответствии с таблицей (графом автомата).
Так из состояния 1 он переходит в состояние 2, если вход был "1". Иначе остается в состоянии 1.
Из состояния 2 переходит в состояние 3 при входе "2" или в состояние 2 (остается в нём) при входе "1". Иначе переходит в состояние 1.
Из 3 в 4 по входу "3", в 2 по входу "1", в 1 по остальным входам.
Аналогично для состояний 4 и 5.
Из состояния 6 переходит в 7 по входу "6", в 2 по входу "1", в 1 по любому другому входу.
Из состояния 7 всегда переходит обратно в 7 независимо от входа.
Переход в состояние 7 означает что автомат распознал последовательность "123456". После этого автомат остается в этом состоянии.
Таким образом, если автомат оказался в состянии 7 после 200 входов, значит где-то он встретил последовательность "123456" во время этих 200 входов. Если он оказался в любом другом состоянии, то такой последовательности не было.
Теперь рассмотрим вероятности.
Вначале автомат был в состоянии 1 с вероятность 100% процентов.
После первого входа он может перейти в состояние 2 с вероятность 1/6 или остатся в 1 с вероятностью 5/6.
Далее, если он был в состянии 1, будет тоже самое. Если он был в состоянии 2, то он может перейти в состоние 3 с вероятностью 1/6, остатся в 2 с вероятность 1/6 или перейти в 1 с вероятностью 4/6.
И так далее.
Вобщем если перед новым входом автомат имел распределение вероятностей по состониям (их сумма равна 1), то после получения нового входа (где все 6 вариантов имеют одинаковую вероятность, независимую от состояния автомата) вектор нового распределения вероятностей по состояниям автомата получается умножением строки-вектора старых вероятностей справа на матрицу, которую привел Ian.
Если взять вектор и умножить его на эту матрицу 200 раз (или 1 раз на эту матрицу в степени 200), то получим вектор веротностей найти автомат в каждом из его 7 состояний после 200 входов. Вероятность - это вероятность того, что автомат где-то встретил последовательность "123456".
Вероятность определённой последовательности
Меня тут спросили какие задачи можно предложить на олимпиаду топовым IT-студентам, чтобы не были решены в сети, я сразу подумал про эту. Но для этого она должна стать досчитываемой до точного ответа. Сделал дауншифт с 6 исходов до 3, типа корни уравнения 3й степени всегда есть явные.Но и там непросто
Вторая попытка
Вторая попытка
Вероятность определённой последовательности
Ian писал(а):Source of the post Найти линейный алгоритм нахождения этой вероятности
Если под линейным алгоритмом имелось ввиду возведение матрицы в степень, то там всё намного проще.
Например , и т.д.
Учитывая, что , то нужно всего 9 умножений матриц - 3 возведения в квадрат и два раза возведение в 5 степень (на каждое по 3 умножения - 2 раза возведение в квадрат и ещё одно умножение на исходную матрицу).
Вероятность определённой последовательности
Ian писал(а):Source of the post какие задачи можно предложить на олимпиаду топовым IT-студентам
Мне кажется, что это типовая задача на цепи Маркова. А типовая задача не очень подходит для олимпиады.
Если же студенты не изучали цепи Маркова, то предлагать им изобрести их - как-то жестко...
Вероятность определённой последовательности
zykov писал(а):Ian писал(а):Source of the post Найти линейный алгоритм нахождения этой вероятности
Если под линейным алгоритмом имелось ввиду возведение матрицы в степень, то там всё намного проще.
Нет конечно линейный значит рекуррентный расчет, число операций линейно по N.
То что Вы говорите может быть реализовано за число операций логарифмическое по N. Хоть нахождение степени матрицы, хоть степеней характеристических корней. А полный перебор экспоненциальный конечно. И я подумал что именно так вопросы поставить интересно, нашел линейный (рекуррентное уравнение) получил 3 балла, нашел формулу (и возможность найти ответ за C*lnN) получил еще 7.
По формулировке - задача должна входить в 100 самых фундаментальных задач теории вероятностей, быть во всех учебниках, а почему в России еще не вошла - потому что не все знают решение. В "Конкретной математике", гл. 8.4, учат получать компактный вид производящих функций чисел [math], но именно эту задачу- не разбирают.
Но кто прочел главу- конечно решит и эту.
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 0 гостей