Интересная и сложная задача по теории вероятностей из ЕГЭ.

[bitcoin]

Добрый день! Есть вопрос по задаче профильного ЕГЭ, помогите, пожалуйста, разобраться. Исходник ниже

Цитата:

Первый член бесконечной последовательности целых чисел равен 0. Каждый следующий член последовательности с вероятностью $p=\dfrac{20}{23}$ на единицу больше предыдущего и с вероятностью $1-p$ на единицу меньше предыдущего. Какова вероятность того, что среди членов этой последовательности найдётся число $-1$?

Это один из возможных прототипов заданий открытого банка задач для подготовки к ЕГЭ по математике.

Можно обозначить за $x$ вероятность того, что из фиксированной целочисленной точки числовой прямой мы сможем попасть на одну единицу левее за любое возможное количество шагов. Тогде эту же вероятность мы сможем переписать иначе.
Мы рассмотрим 2 случая.

1) Мы попадаем в $-1$ сразу из $0$, вероятность этого будет равна $x=\dfrac{3}{23}$

2) Мы сначала попали в $1$ с вероятностью $x=\dfrac{20}{23}$, а потом сместимися в итоге в $0$ с вероятностью $x$, а из $0$ в $-1$ c с вероятностью $x$.

Тогда получаем уравнение

$x=\dfrac{3}{23}+\dfrac{20}{23}\cdot x\cdot x$

Оно имеет 2 корня $x=0,15$ и $x=1$, второй корень не подходит по смыслу. Вроде бы все гладко, но почему мы не могли рассмотреть тогда вот так.

1) Мы попадаем в $-1$ сразу из $0$, вероятность этого будет равна $x=\dfrac{3}{23}$

2) Мы сначала попали в $1$ с вероятностью $x=\dfrac{20}{23}$, а потом сместимися в итоге в $0$ с вероятностью $x$, а из $0$ в $-1$ c с вероятностью $x$.

3) Мы за 2 шага попадем в $2$ с вероятностью $\dfrac{20}{23}\cdot\dfrac{20}{23}$, а дальше в $-1$ за любое количество шагов вероятность попасть $x^3$

Получаем уравнение

$x=\dfrac{3}{23}+\dfrac{20}{23}\cdot x^2+\dfrac{20}{23}\cdot\dfrac{20}{23} \cdot x^3$

Понятно дело, что это уравнение уже другие корни будет иметь. Вопрос в том, почему свет клином сошелся на $1$, а не на $2$, к примеру, что не так в моих рассуждениях, помогите, пожалуйста, разобраться. Понятно, что можно и дальше двойки пойти вправо)

[мат-ламер]

bitcoin в сообщении #1577772 писал(а):

Вопрос в том, почему свет клином сошелся на $1$, а не на $2$,

Можете популярнее объяснить, в чём вопрос?

bitcoin в сообщении #1577772 писал(а):

что не так в моих рассуждениях

Почему вы решили, что у вас что-то не так?

Если что, я пока детально ваш пост не прочитал. Написал первое, что бросилось в глаза.

[zykov]

bitcoin в сообщении #1577772 писал(а):

Получаем уравнение

$x=\dfrac{3}{23}+\dfrac{20}{23}\cdot x^2+\dfrac{20}{23}\cdot\dfrac{20}{23} \cdot x^3$

Не верно, потому что $\dfrac{20}{23}\cdot x^2$ уже учитывает "попадание в 2 и потом в -1".
Т.е. в $\dfrac{20}{23}\cdot\dfrac{20}{23} \cdot x^3$ вы это учитываете второй раз.

[mihaild]

bitcoin, вы посчитали траекторию $0 \to 1 \to 2$ два раза (она уже включена в $x$ который отвечает за переход $1 \to \ldots \to 0$ в первом пункте).

мат-ламер в сообщении #1577782 писал(а):

Почему вы решили, что у вас что-то не так?

Потому что два разных способа рассуждения дают разные ответы на один вопрос.

[bitcoin]

zykov в сообщении #1577787 писал(а):

Не верно, потому что $\dfrac{20}{23}\cdot x^2$ уже учитывает "попадание в 2 и потом в -1".
Т.е. в $\dfrac{20}{23}\cdot\dfrac{20}{23} \cdot x^3$ вы это учитываете второй раз.

Спасибо! А можно ли через двойку получить тот же результат? И правильно ли вообще было решено через 1. Есть ли какие-то еще способы другие, которые будут рациональнее?

[mihaild]

bitcoin в сообщении #1577791 писал(а):

А можно ли через двойку получить тот же результат?

Рассмотрите отдельно сценарии $0 \to -1$, $0 \to 1 \to 0 \to \ldots$, $0 \to 1 \to 2 \to \ldots$.

[zykov]

bitcoin в сообщении #1577791 писал(а):

А можно ли через двойку получить тот же результат?

$x=\dfrac{3}{23}+\dfrac{20}{23}\left(\dfrac{3}{23} x + \dfrac{20}{23}x^3\right)$

-- 18.01.2023, 17:17 --

bitcoin в сообщении #1577791 писал(а):

Есть ли какие-то еще способы другие, которые будут рациональнее?

Это рекурсивное решение - короткое и в некоторой степени "олимпиадное".
Более теоретически глубокое решение будет через цепи Маркова, но оно более громоздкое. (Вот пример с другой задачей.)

[wrest]

Численный эксперимент показал следующее.
Будучи запущенной с нуля, последовательность попадает в минус единицу в среднем $0,203$ раза.
Максимальный номер шага, на котором последовательность попала в минус единицу (возможно не первый раз) 35, проверка заканчивалась на 100-м шаге.
Максимальный номер первого попадания в минус единицу 31, проверка последовательности заканчивалась на первом попадании в минус единицу или на 100-м шаге (что наступало раньше).
Доля последовательностей, которые попадают в минус единицу хотя бы один раз $0,150$
Последовательность запускалась около $10^7$ раз.

[Combat Zone]

$x=\frac{3}{23}+\frac{20}{23}x^2$, где $x$ - вероятность попасть за некоторое шагов из какой-то точки на шаг влево, в том числе и из нуля в минус единицу, путь произволен.

А, у вас уже это было. А почему другие пути не смотрят - а потому что они уже туда включены.

[Doctor Boom]

bitcoin в сообщении #1577772 писал(а):

Оно имеет 2 корня $x=0,15$ и $x=1$, второй корень не подходит по смыслу

А кстати, почему?

-- 19.01.2023, 02:34 --

Интересно, а на двухмерной сетке уже такое не прокатит, и надо честно считать пути?

[Padawan]

Пусть $x_{-1}=1$, и при $i\geq 0$ пусть $x_i$ обозначает вероятность попасть в $-1$, стартуя с числа $i$. Тогда $x_i=(1-p) x_{i-1}+px{i+1}$ при всех $i\geq 0$. Это линейное однородное рекуррентное уравнение с постоянными коэффициентами. Его решение $x_i=C_1\lambda_1^i+C_2\lambda_2^i$, где $\lambda_{1, 2}$ -- корни уравнения $\lambda=(p-1) \lambda ^{-1}+p\lambda$, константы находятся из граничных условий $x_{-1}=1$, $x_i\to 0$ при $i\to\infty$. Либо по-школьному можно понять, что разности $x_i-x_{i-1}$ образуют геометрическую прогрессию.
Получилось $x_0=1/p-1=3/20=0, 15$

[Shadow]

Doctor Boom в сообщении #1577865 писал(а):

А кстати, почему?

Потому что

$x=\begin{cases}\frac{1-p}{p}, \text{ при } p>\frac 1 2\\1,\text{ при } p\le \frac 1 2 \end{cases}$

$E=\dfrac{1}{1-2p}$ - мат. ожидание числа ходов до попадания при $p<\dfrac 1 2$

Doctor Boom в сообщении #1577865 писал(а):

Интересно, а на двухмерной сетке уже такое не прокатит, и надо честно считать пути?

Конкретно задачу сформулируйте.

[bitcoin]

Спасибо большое всем за идеи и подсказки.

zykov в сообщении #1577797 писал(а):

$x=\dfrac{3}{23}+\dfrac{20}{23}\left(\dfrac{3}{23} x + \dfrac{20}{23}x^3\right)$

Действительно это работает. спасибо. Я попробовал раскрутить через тройку, но у меня не получилось.

Я составил такую схему для наглядности.
В моем представлении уравнение, когда раскручиваем через тройку, в соотвествии со схемой, должно быть таким.

$$x=\dfrac{3}{23}+\dfrac{20}{23}\cdot\left(\dfrac{2}{23}\cdot x +\dfrac{20}{23}\cdot \left(\dfrac{3}{23}\cdot x^2+\dfrac{20}{23}\cdot x^4\right)\right)$$

Но корни этого уравнения (калькулятор помог) уже другие, видимо я что-то не так понимаю?

[mihaild]

bitcoin в сообщении #1577914 писал(а):

$$x=\dfrac{3}{23}+\dfrac{20}{23}\cdot\left(\dfrac{\textcolor{red}{2}}{23}\cdot x +\dfrac{20}{23}\cdot \left(\dfrac{3}{23}\cdot x^2+\dfrac{20}{23}\cdot x^4\right)\right)$$

[bitcoin]

mihaild в сообщении #1577915 писал(а):

bitcoin в сообщении #1577914 писал(а):

$$x=\dfrac{3}{23}+\dfrac{20}{23}\cdot\left(\dfrac{\textcolor{red}{2}}{23}\cdot x +\dfrac{20}{23}\cdot \left(\dfrac{3}{23}\cdot x^2+\dfrac{20}{23}\cdot x^4\right)\right)$$

Спасибо, понял, не заметил)