Задача по теории вер.

первый член последовательности равен 0. Каждый следующий с вероятностью р=4/13 на единицу больше предыдущего и с вероятностью 1-р меньше предыдущего. Найти вероятность, что какой-то член последовательности равен 1.

Один из вариантов решения — составить и решить бесконечное рекуррентное соотношение на x_i — вероятность достигнуть 1 начиная с числа (-i).

Вообще, это классическая задача о разорении.

1-р/р=(1-4/13):4/13=9/13:4/13=9/4=2,25

Ответ: 4/9

Проще будет нарисовать схему и составить квадратичное уравнение. Т.к. вероятность из 0 в 1 будет 4/13, а из 0 в -1 будет 9/13. Затем из -1 мы так же спустя два хода можем прийти обратно к числу 1. Получается, что вероятность пойти любым способом из 0 в 1 равна Х=4/13 + 9/13 * Y, где Y — вероятность попасть из -1 в 1. Вспоминая, что шанс попасть из -1 в 1 это по сути вероятность из 0 в 1 дважды: Y = X*X, то получаем квадратное уравнение, где один из корней будет 1, а другой 4/9. 1 нам не нужна, т.к. вероятность того, что мы попадем изначально в 1 из 0 меньше, чем из 0 в -1. Поэтому берем 4/9

Да, можно так посчитать.

Только мне кажется, если говорить о строгом рассуждении, не равенство единице всё-таки требует обоснования.

Представим поиск каждого следующего члена последовательности в виде блуждания по лабиринту.
Каждое положение в лабиринте — некоторое число k. Отсюда можно сделать шаг вверх в положение k+1 и шаг вниз в положение k–1.
Будем различать вероятность прийти из k в k+1 сейчас, на ближайшем шаге (эта вероятность равна p по условию) и вероятность прийти из k в k+1 вообще, когда-нибудь в будущем (эта вероятность неизвестна, и именно её надо найти в задаче).

Заметим, что вероятности когда-либо в будущем оказаться на шаг выше текущего положения одинаковы для всех положений k в лабиринте, так как лабиринт воспроизводит сам себя в каждом следующем положении (лабиринт — своего рода «фрактал»).

Обозначим эту вероятность за x.
Искомая в задаче величина — вероятность прийти из «0» в «1» когда-либо в будущем — тогда также равна x.
С другой стороны, попасть из «0» в «1» можно, сделав шаг вверх сейчас (и тогда цель достигнута) или же сделав сначала шаг вниз в «–1» и затем два шага вверх когда-либо в будущем (сначала когда-нибудь из «–1» в «0» и затем когда-нибудь из «0» в «1»).

Вероятность сделать шаг вверх сейчас равна p.
Вероятность сделать шаг вниз сейчас равнa 1–p.
Вероятность сделать два шага вверх когда-нибудь равна x * x.
Получаем: x = p + (1–p) * x * x;
(1 – p) * x ^ 2 – x + p = 0.
D = 1 – 4 * (1 – p) * p = 1 – 4p + 4p^2 = (2p – 1) ^ 2.
x = (1 ± (2p – 1)) / (2 * (1 – p))
x_1 = 1
x_2 = p / (1–p)

Т.к. 1 не подходит, получаем
о т в е т: p / (1–p) = 4/13 / (9/13) = 4/9.

Павел, добрый вечер.
С расчётом согласен.
Такой вопрос: есть ли у Вас какое-то простое и строгое объяснение, почему 1 не подходит?
Просто обоснования, которые мне известны, не проще, чем, собственно, поиск искомой вероятности.

Ну как минимум потому, что существует ненулевая вероятность не прийти в «1» никогда, если каждый раз спускаться вниз?

Для p = 1/2 шанса не вернуться в 1 нет — следует из Вашего же рассуждения.
Почему для p <1/2 она есть?

О, это очень хорошее замечание, Константин, спасибо!
Я хоть и записал решение в общем, казалось бы, виде, ориентировался всё-таки на конкретную задачу с p=4/13 и не подумал рассмотреть случаи, когда p >= 1/2.
Так как параллельно смоделировал ситуацию на пайтоне и не прогонял её на других p, а для р=4/13 у меня сошёлся результат )

Тогда Вы правы, для обоснования сходимости придётся уходить в дебри более дремучие, чем сама задача!

Прогоняю свою модельку сейчас для p=1/2 и вижу, что сходится к 1 она очень медленно, существенно медленнее, чем для p<1/2. И результат в хотя бы 0.999 не получается даже на десяти тысячах итераций.

Так что случай с p=1/2 заслуживает отдельного рассмотрения.
Признаю, что p = 4/9 в исходной задаче получается после предельного перехода, а значит, требует бесконечного числа итераций...

Так что если отталкиваться от практики, а не от теории, можно утверждать, что 1 не подходит просто потому, что с вероятностью в 100% не происходит ничего 😬

Ну, на практике проверить равен ли «какой-то» член бесконечной последовательности 1 в принципе невозможно.

Если говорить о проверке для определённого кол-ва шагов, при p > 1/2 нетрудно указать номер, для которого 1 будет достигаться с вероятностью, не отличимой от 100% (из ЦПТ)

По поводу доказательства у меня были такие соображения:

1) Из ЦПТ должно быть несложно сделать оценку, которая показывает, что в задаче ответ < 1, — но это выглядит как оверкил.

2) Напрямую оценивать кол-во траекторий вообще не хочется

3) Можно рассмотреть шанс вылета из полосы [-x, 1] в ту или иную сторону и устремить x->inf.
Из того, что мне известно, это самый простой вариант, вроде.
Там придётся решать систему уравнений на вероятности с краевыми условиями, примерно как в Вашем рассуждении — но там ответ однозначный при любом x.

4) Хочется сказать, что ответ непрерывно зависит от p и устремить p → 0.
Но непрерывность шанса «достигнуть 1 когда-либо» совсем не очевидна (в отличие от непрерывности шанса «достигнуть 1 за < i шагов»)

В своей модели я как раз рассчитывал количество траекторий напрямую. Там получается что-то вроде обрезанного треугольника Паскаля, когда я считаю число путей в 1 «снизу» и отрезаю пути «сверху»... а алгоритмизируется он довольно просто. Опять же, это не имеет отношения к строгому доказательству, исхожу из практики )
Иначе говоря, я сначала посчитал на калькуляторе, а только потом сел искать математическое решение, потому что довольно красивый вышел ответ... И в конце концов главное для меня как педагога — объяснить решение так, чтобы был понятен каждый шаг (а это, насколько я понимаю, задача из ЕГЭ! — что удивительно). И интуитивно понятно, почему ответ не единица. Раз уж вероятность свалиться вниз выше вероятности подняться вверх — то никак я не могу гарантированно подняться. Сами же написали в начале — это задача о разорении! 📉
С радостью послушаю строгие решения )

Вроде, в описании задачи не указано, что это из ЕГЭ

============

Вообще говоря, то, что мы «чаще» вниз двигаемся не всегда означает невозможность вернуться наверх (например, если суммировать что-то вроде распределения Коши)
Но если есть матожидание и дисперсия, как в данном случае, то из ЦПТ это следует.

Строго, из ЦПТ примерно так должно получаться:
Много шагов подряд ~ нормальное распределение, со средним ~N и отклонением ~sqrt(N).
Если среднее не 0, то на дистанции оно сильнее сказывается, чем отклонение.

Количественно, можно показать, что если с самого начала мы достаточно много раз шагнём вниз, дальше есть ненулевая вероятность вообще не всплыть — для этого нужно группировать шаги большими пачками и аккуратно оценивать «хвосты» распределения.

==========

Если интересует строгое док-во с рассмотрением отрезка [-x 1] — посмотрите на вики в статью про задачу о разорении, там вывод формулы в общем случае есть.

==========

Ваше дерево, кстати, интересно тем, что сверху числа Каталана стоят — кол-во правильных скобочных последовательностей — которые равны 1/(n+1) * C^n_2n.
А сумма в чётных столбцах, собственно, равна C^n_2n [сходу не придумал комбинаторное объяснение, но, зная формулу для чисел Каталана, можно по индукции доказать].

Соответственно, для p=1/2, за каждые 2 шага доля таких путей (от всех) домножается на (2n-1)/2n — из чего можно вывести асимптотику, с которой она стремится к 0 [что-то порядка С/sqrt(n)]

Для p <> 1/2 это тоже можно использовать, чтобы оценить, как меняется доля всех путей со временем, по идее — но я не считал, не знаю, насколько просто будет доказать, что при n->0 предел больше 0 в итоге

спасибо

… из предыдущего путем прибавления к нему начального значения помноженного на текущий номер элемента
Например, если начальное значение равно 1, то последовательность будет такой: 1, (1+1*2=3), (3+1*3=6), (6+1*4=10) и т.д.
Нужна формула, по которой можно рассчитать значение n-элемента при известном начальном значении.