матожидание для количества подбрасываний

[fd8]

Задачка: Игральную кость с n гранями (и числами от 1 до n на этих гранях) подбрасывают до тех пор, пока сумма выпавших очков не станет больше или равна n. Все грани кости выпадают с одинаковой вероятностью. Найдите математическое ожидание числа бросков.

Правильно ли я понимаю, что ее нужно решать так:
1. Подбрасываний может быть от 1 (если сразу выпало n) до n (если каждый раз выпадала единица);
2. Чтобы посчитать МО, нужно вычислить вероятности каждого числа подбрасываний: с какой вероятностью нам потребуется подбросить кубик k раз, чтобы получить сумму, больше или равную n;
3. Чтобы посчитать вероятности, нужно вычислить число вариантов для каждого количества подбарсываний.

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

[venco]

Динамическое программирование должно помочь.
1. Сколько нужно бросков если осталось набрать 1 очко?
2. Сколько нужно бросков если осталось набрать 2 очка?
...
n. Сколько нужно бросков если осталось набрать $n$ очков?

[fd8]

Если правильно понимаю, то матожидание в данном случае - это среднее число подбрасываний, которое требуется выполнить для получения суммы, больше либо равной $n$.
Если так, то:
1. Если осталось набрать еще 1 очко, то требуется 1 бросок - в среднем 1 бросок.
2. Если осталось набрать еще 2 очка, то требуется от 1 до 2 бросков - в среднем 1,5 броска.
3. Если осталось набрать еще 3 очка, то требуется от 1 до 3 бросков - в среднем 2 броска.
...
n. Если осталось набрать еще $n$ очков, то требуется от 1 до n бросков - в среднем $(1+n)n/2$ бросков.

Таким образом, теперь мы можем получить среднее количество подбрасываний, необходимых для получения $n$ очков - это среднее арифметическое среди полученных $n$ результатов. Мы получаем среднее число подбрасываний, требуемых на последнем шаге для того, чтобы набрать $n$ очков. Но это как будто и есть то, что мы ищем - неважно, на последнем шаге или на очередном. То есть получаем матожидание числа подбрасываний для достижения $n$ или более очков.
Правильно ли я рассуждаю?..

[grizzly]

fd8 в сообщении #1127108 писал(а):

2. Если осталось набрать еще 2 очка, то требуется от 1 до 2 бросков - в среднем 1,5 броска.

Это, извините, чем-то напоминает о "вероятности встретить динозавра на улице".

[arseniiv]

fd8
Составьте рекуррентные соотношения. Пусть $E_m$ — матожидание количества бросков, нужного для набора $\geqslant m$ очков.

[Aritaborian]

fd8 в сообщении #1127108 писал(а):

2. Если осталось набрать еще 2 очка, то требуется от 1 до 2 бросков - в среднем 1,5 броска.

Начиная отсюда — неверно.

[fd8]

Спасибо, что не бросаете. Попытаюсь продолжить. Для начала попробую исправить про среднее количество бросков.
Если осталось набрать еще 2 очка, то потребуется от 1 до 2 бросков - это ведь верно? Либо выбрасываем сразу от 2 до $n$, либо первой выпадает единица, тогда на втором броске подойдет что угодно (от 1 до $n$).
Вероятность того, что потребуется только один бросок равна вероятности получить при первом броске от 2 до $n$, то есть $\frac{n-1}{n}$, правильно?
Вероятность того, что потребуется 2 броска, равна $\frac{1}{n}$, т.к. 1 выпадает с вероятностью $\frac{1}{n}$, а далее - любое значение выпадет с вероятностью 1; в произведении получаем $\frac{1}{n}$.

Проверяем вычисление вероятностей: $\frac{n-1}{n} + \frac{1}{n} = 1$ - верно.
Тогда матожидание количества бросков равно $\frac{n-1}{n}\cdot1 + \frac{1}{n}\cdot2 = \frac{2n-1}{n}$
Например, если $n=6$, то МО в данном случае будет равно 1,8(3) - похоже на правду.

Это правильно?

[grizzly]

fd8 в сообщении #1127576 писал(а):

$\frac{n-1}{n}\cdot1 + \frac{1}{n}\cdot2 = \frac{2n-1}{n}$

Это как понимать?

fd8 в сообщении #1127576 писал(а):

если $n=6$, то МО в данном случае будет равно 1,8(3) - похоже на правду.

Стало ещё больше, чем было в прошлый раз. Немного странно даже, чтобы интуиция так подводила.

[arseniiv]

fd8
Попробуйте написать что-то про $E_k$ для произвольного $k$.

[fd8]

Охх, про интуицию - немилосердно, но правда :(( Конечно, в среднем гораздо чаще потребуется один бросок, чем 2, поэтому значение 1,8 должно было вызвать подозрения.
arseniiv
Опасаюсь про $E_k$ написать что-то еще менее правдоподобное, если мне пока не удается вычислить МО даже для случая в 2 очка :( В общих чертах среднее количество подбрасываний будет стремиться примерно к 2,7 (вычислила с помощью программки - ну этот результат вроде бы похож на правду). Но для построения рекуррентного соотношения нужно понять закономерность изменения МО в зависимости от оставшегося количества очков, а это мне пока не удается :(

[arseniiv]

Потому и выразите $E_k$ через другие $E_m,m<k$. Сосчитаем потом.

Может быть, пользу принесёт принять $E_m = 0$ для всех целых $m\leqslant0$. Тогда можно одной формулой всё остальное охватить.

[DeBill]

fd8
Похоже, задача Ваша имеет не очень красивый ответ...
Ну, по крайней мере, у меня получилось так - какая-то здоровенная и неприглядная сумма...
Я даже не смог углядеть из нее сходимость при $n \to \infty$ к решению известной задачи: Из равномерного на единичном отрезке распределения, берут слагаемые, пока сумма не превысит 1. Найти МО числа слагаемых.

(Оффтоп)

Ответ: $e$.

Хорошее решение этой "предельной" задачи можно получить примерно так. Рассмотрим событие
$A_k$, состоящее в том, что сумма $k$ слагаемых меньше 1. Эти события - вложенные, и через их вероятности все легко считается.
Может, и здесь попробовать такой подход? Вероятность , что сумма первых $k$ меньше $n$, равна количеству способов разложить $n$ шаров в $k+1$ ящик так, что все ящики - непустые (в последнем - сколько не хватает до $n$...), деленному на $n^k$...

[venco]

DeBill в сообщении #1128043 писал(а):

Похоже, задача Ваша имеет не очень красивый ответ...

Не знаю, у меня вполне компактный и красивый ответ получился.

[DeBill]

venco
А, ну да, дурной ответ был для lheuju vjtuj - дурного - решения. А для предложенной методы - поленился сосчитать...

(Оффтоп)

$(1+\frac{1}{n})^{n-1}$.

-- 01.06.2016, 21:51 --

Кстати, а как бы это получить совсе просто? Ну, вот, в числителе у нас стоит число деревьев ...Может, это неспроста?

[grizzly]

fd8 в сообщении #1127594 писал(а):

если мне пока не удается вычислить МО даже для случая в 2 очка :(

(С запозданием) Всё там у Вас получилось с МО. Не получилось только дроби правильно сложить