Задача о подбрасывании монеты и смене знака

[an2ancan]

Здравствуйте, помогите разобраться со следующей задачей:

Когда студент пришел в аудиторию, на доске было написано число $0$. В ожидании лекции студент подкидывает монетку и, если выпадает орел, он прибавляет к числу $1$, а если решка - то вычитает $1$. Орел и решка выпадают с равной вероятностью. Найдите вероятность того, что на момент после $(2n+1)$-го подбрасывания число на доске сменило знак (с положительного на отрицательный или наоборот)
(а) ровно $n$ раз;
(б) ни разу.

Условие $a$) Предположим, что первый раз выпал орел, т.е. число увеличилось на 1. Для того чтобы сменился знак число должно уменьшиться на 2. Чтобы число поменяло знак $n$ раз все дальнейшие шаги должны быть определенными. Т.е. Вероятность такого события будет $\frac{1}{2}^{2n}$. Но первый раз может выпасть и решка. Тогда полная вероятность будет равна:
$P = 2 \cdot \frac{1}{2}^{2n} = \frac{1}{2}^{2n-1}$

Условие (б) напоминает условие задачи о разорении игрока. Но ни к чему вразумительному я не пришел.

[grizzly]

an2ancan в сообщении #1260247 писал(а):

Тогда полная вероятность будет равна:
$P = 2 \cdot \frac{1}{2}^{2n} = ...$

Что-то здесь не так. Проверьте формулу при $n=1$.

[an2ancan]

При $n = 1 $ у нас в наличие 3 броска. Если при первом броске наше число выросло на 1, для того что бы знак сменился последующие 2 броска должны приводит к уменьшению, для смены знака. Т.е. $1 \rightarrow 0 \rightarrow -1$. Шансы такого перехода равны $P_1 = \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}$
Но первый бросок может привести к тому, что число уменьшится на один. Тут ситуация зеркальная, $P_{-1} = \frac{1}{4}$
Тогда полная вероятность равна $P = \frac {1} {2} P_1 + \frac {1}{2} P_{-1} = \frac{1}{4}$

Да я забыл Про еще 1 $\frac{1}{2}$, Тогда выходит общая формула равна

$P = \frac{1}{2} ^ {2n} $

[Roger]

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

[DeBill]

an2ancan
В книге Виленкина "Комбинаторика" есть такая задача: В очереди стоит $2n$ чел, у половины из них - рубли, у половины - полтинники. Билет стоит полтинник, в начале в кассе денег нет. Найти вер-ть, что у кассира всегда будет сдача.
Решение - а читал я ее школьником - меня поразило...
Виленкин грит: будем изображать процесс в виде ломаной, с вершинами (номер чела, кол-во полтинников в кассе).
Вариантов - $C^n_{2n}$.
Плохие варианты - когда ломаная уходит в отрицательные числа (и, тем самым, пересекает (имеет общую точку с)горизонтальную прямую на высоте $-1$. Отразим часть плохой ломаной (после первой точки ее пересечения с этой прямой) относительно этой прямой; получим ломаную, оканчивающуюся на высоте $-2$. Таких ломаных - ....., и каждая из них соответствует ровно одной плохой (это надо проверить!). Значит, плохих - столько же.....

[an2ancan]

Простите, долго не мог ответить... да и сообразить тоже

DeBill,
Спасибо. Начну про задачу с очередью:

Ну вы вроде все рассписали, ломанных, которые заканчиваются в точке $ - 2 $  всего $C^{n-2}_{2n}$, выходит, что вероятность равна:
$ P = 1 - \frac{C^{n-1}_{2n}}{C^n_{2n}} = \frac{1}{n+1}$

Теперь вернемся к самой теме,

Если я правильно понял к чему вы меня подталкивали, выходит следующее:
Предположим, мы сделали первый бросок и пребавили единичку. Количество всех оставшихся вариантов равно $2^n$.

Чтобы удовлетворять условию, что число не сменит знак ни разу, на момент $2n$ шага после выпадания единички, число может принимать значения: $1, 3, 5, \dots 2n + 1$,
Таких возможностей: $C_{2n}^{n} + C_{2n}^{n-1} + C_{2n}^{n-2} ... + C_{2n}^{0}$

Но среди этих вариантов есть те, что ведут через смену знака. Тогда, воспользовавшись методом, который напомнил DeBill, можно сказать, что количество ломанных заканчивающихся $1$ и меняющие знак равно количеству ломанных заканчивающихся на $-3$ (отражая ломаную относительно -1 в месте смены знака): $ C_{2n}^{n-2}$. Аналогично для ломанных заканчивающихся:
$3 ~ -5 \rightarrow C_{2n}^{n-3}$
$5 ~ -7 \rightarrow C_{2n}^{n-4}$
$\vdots$
$2n-3 ~ -(2n-1) \rightarrow C_{2n}^{0}$

Тогда, в конечном итоге получаем, что количество ломанных, которые не меняют знак за 2n шагов начиная с 1 равна:
$p = C_{2n}^{n} + C_{2n}^{n-1} + C_{2n}^{n-2}+\dots + C_{2n}^{0} - (C_{2n}^{n-2} + C_{2n}^{n-3} + \dots + C_{2n}^{0}) = C_{2n}^{n} + C_{2n}^{n-1} = C_{2n+1}^{n}$
Тогда вероятнось равна $p_1 = \frac{C_{2n+1}^{n}}{2^n}$

Вероятность не сменить знак, если первый шаг привел к $-1$ равна: $p_{-1} = p_1$,

Тогда общая вероятность равна:

$p = \frac{1}{2} p_1 + \frac{1}{2}p_{-1} = p = \frac{C_{2n+1}^{n}}{2^n}$

Вот, посмотрите пожалуйста решение.

[DeBill]

Вроде, все правильно. Главное, что идею Вы четко уловили.
А для проверки решения, бывает полезно для малых $n$ ручками посчитать. Сходится!

[Someone]

Очень интересно почитать на эту тему учебник В. Феллера "Введение в теорию вероятностей и её приложения", том 1 (Москва, "Мир", 1984). Глава III называется "Флуктуации при бросании монеты и случайные блуждания".