Задача № 4 из ЕГЭ

[Руст]

Однокурсник, занимающийся репетиторством прислал такую задачу (№4 ЕГЭ):
Числовая последовательность состоит из целых чисел и начинается с 0. Вероятность того, что следующее число больше
предыдущего на 1, равна $p=\frac{10}{19}$. Вероятность того, что следующее число меньше
предыдущего на 1, равна $q=\frac{9}{19}$. Найти вероятность первого появления в этой последовательности числа (-1).

Задача сформулировано коряво и я решил вычисляя вероятности $p_n$ оказания в точке -1 первый раз на шаге $2n+1$.
Суммировав этот ряд по всем от 0 до бесконечности получил
$\sum_{n=0}^{\infty}= \frac{q}{p}, q\le p$, $\sum_ n p_n =1, q \ge p}$.
Потратив на это почти час. Он сказал, что ответ правильный и он решил задачу за 3 мин без вычисления $p_n$.
Я послал ему свое решение, где возникают числа Каталана (и вряд ли подходит для школьников). От него так и не дождался простого решения за 3 дня.
Возникает вопрос есть ли вообще простое решение. Хотелось бы обсудить

[EUgeneUS]

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

Простого решения задачи о разорении игрока не знаю . Но может быть это давалось в курсе, и надо помнить ответ?

[mihaild]

"Вероятность первого появления" - это просто вероятность появления?
Тут обсуждалось: «Интересная и сложная задача по теории вероятностей из ЕГЭ.». ТС предложил вариант который ИМХО предполагается для школьников, ответ - корень уравнения $x = q + px^2$ (мы либо сразу пошли налево, либо пошли направо, и потом придется два раза добраться до более левой точки).

[zykov]

Руст в сообщении #1579713 писал(а):

Найти вероятность первого появления в этой последовательности числа (-1).

Странно звучит.
Нужно либо "вероятность, что когда-либо достигнет -1", либо "матожидание числа шагов до первого появления -1".

[Руст]

Да, сформулировано коряво, что я отметил . Я написал так, как прислали мне.
Формулировка как вероятность разорения предпочтительнее.
Считая что игрок на каждом шаге выигрывает 1р с вероятностью р и проигрывает 1р с вероятностью 1-р.

[zykov]

Да, тут $q<p$, так что вероятность что никогда не достигнет больше нуля.
Решается за "3 минуты" рекурентно (mihaild дал ссылку, где недавно такое же решали).
Если $q \geq p$, то достигнет -1 с вероятностью 1. Тут можно только ставить вопрос о матожидании числа шагов.

[Руст]

По сути мое решение такое же, только я считал каждое $p_n$ - вероятность разорения на шаге 2n+1.
Пусть $P_n$ вероятность вернутся к начальному состоянию через 2n шагов не разорившись до этого.
Тогда $p_n=P_nq$. Обозначим через $Q_n$ вероятность вернуться к начальному состоянию через 2n шагов,
находясь все время в выигрыше после первого шага. $P_0=1=Q_0$. Тогда $Q_n=pP_{n-1}q$.
Таким образом

$$P_n=\sum_{k=0}^{n-1} Q_kP_{n-k}.$$

Обозначим $P_n=c_n(pq)^n.$ Тогда $c_n$ удовлетворяет рекурентному соотношению:

$$c_n=1+\sum_{k=0}^{n-1}c_kc_{n-1-k}.$$

Для производящей функции $y(x)=\sum_{n=0}^{\infty}c_nx^n$ получаем то самое квадратное уравнение

$$y(x)=1+xy^2(x) \to y(x)=\frac{1-\sqrt{1-4x}}{2x}.$$

Это производящая функция чисел Каталана $c_n=Ca_n=\frac{1}{2n+1}C_{2n}^n.$
Соответственно $p_n=Ca_np^nq^{n+1}.$ Можно было догадаться об этом, считая что $p_n$
это сумма всех слов длины 2n+1 из $p,q$ содержащих $n$ букв $p$ (открывающие скобки) и $n+1$ букв $q$ (закрывающие скобки),
когда до шага 2n количество открывающихся скобок не меньше закрывающихся.
Соответственно

$$\sum_n p_n=q\frac{1-\sqrt{1-4pq}}{2pq}=\frac{1-\sqrt{1-4p(1-p)}}{2p}=\frac{1-|1-2p|}{2p}=1, p\le q, \ =\frac{q}{p}, p>q.$$

[пианист]

(Оффтоп)

А не мог бы кто-нибудь прокомментировать, каким образом теория вероятностей появилась в школьной программе? и когда это случилось? Во время моей учебы в школе ничего подобного не было
И для чего это было сделано - чтобы вот такие задачи давать, что ли?

[Mirage_Pick]

(Оффтоп)

пианист в сообщении #1579835 писал(а):

А не мог бы кто-нибудь прокомментировать, каким образом теория вероятностей появилась в школьной программе?

В 2003, по этому поводу инструктивное письмо № 03–93ин/13–03 от 23.09.2003 Министерства образования РФ «О введении элементов комбинаторики, статистики и теории вероятностей в содержание математического образования основной школы». Документ можно найти в издании «Математика в школе», № 9 за 2003 г.

Цитата:

И для чего это было сделано - чтобы вот такие задачи давать, что ли?

Да. Школьники, умеющие решать подобные задачи, будут ковать мощь Отечественной промышленности в будущем. 8-)

-- 02.02.2023, 09:12 --

А задачу действительно можно решить без $p_n$ и Каталанов за пару минут.

[F111mon]

Школьная программа - это несколько абстрактное понятие, сейчас единой школьной программы не существует. В программе "Математическая вертикаль" (это полуповышенный уровень математики в московских школах) есть вообще целый предмет: Статистика.
В ЕГЭ задачи на вероятность появились в 2012 году.
Сейчас (с 2022 года) в ЕГЭ входит две задачи по теории вероятностей:
1. под номером 4 простая ("бросили кубик, какая вероятность, что число четное")
2. под номером 10 более сложная. В материалах для подготовки задачи, подобные приведенной, встречаются, но на реальном экзамене была стандартная задача на формулу Байеса.

И, разумеется, надо иметь в виду, что на ЕГЭ необязательно решать все задачи; если какая-нибудь задача не решается, надо переходить к другим.

[пианист]

(Оффтоп)

Mirage_Pick
Большое спасибо, ознакомился.
А кто "проталкивал" приказ, не знаете?

F111mon в сообщении #1579848 писал(а):

Школьная программа - это несколько абстрактное понятие, сейчас единой школьной программы не существует

Упс. Все страньше и страньше. Совсем я от жизни отстал
Так ЕГЭ сейчас уже не является единым для всех? а как тогда оно вообще (предполагается, что) работает?
Кстати, Байес находится существенно за пределами того, что явно рекомендовано письмом 03-93ин/13-03.

[Mirage_Pick]

(Оффтоп)

пианист в сообщении #1579850 писал(а):

А кто "проталкивал" приказ, не знаете?

Нет, но безусловно отношение к этому имеет отец ЕГЭ Болотов В.А. Он же член рабочей группы по созданию проекта Концепции модернизации образования образца 2001 года.

[пианист]

(Оффтоп)

Mirage_Pick
Ясно, спасибо.

[Klein]

Решение школьника гуманитария. Потратил 10-15 минут не больше.

Событие $A$ - первое появление числа $-1$ в последовательности
Событие $B$ - число $0$ в последовательности
Событие $C$ – число $-2$ в последовательности
Вероятность первого появление числа $-1$ в последовательности и следующего на $1$ больше $\Pr(A|B) = \frac{10}{19}$
Вероятность первого появление числа $-1$ в последовательности и следующего на $1$ меньше $\Pr(A|C) = \frac{9}{19}$
Вероятность появления числа в последовательности $\frac{1}{19}$ . Начало последовательности начинается с $0$.

Найти $\Pr(A)$

$\Pr(A)=\Pr(B)\Pr(A|B)+\Pr(C)\Pr(A|C)$

$\Pr(A)=\frac{1}{19}(\frac{10}{19})+\frac{1}{19}(\frac{9}{19})=\frac{1}{19}$

Что не так?

[mihaild]

Klein в сообщении #1579939 писал(а):

Событие $A$ - первое появление числа $-1$ в последовательности

Это не событие. Событие - это то, что может произойти, а может не произойти, а что такое "произошло первое появление числа $-1$ в последовательности" - непонятно.

А еще ответ очевидно не меньше $q$, т.к. мы можем сразу пойти налево.