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

[marting]

Привет!

Задача взята с TopCoder-a (соревнования для программистов). Там она помечена как примитивная, видимо это правда, просто я давно не занимался теорией вероятностей . Итак:

Каково ожидаемое количество бросков одной игральной кости, при которых сумма выпавших очков не меньше $N$?

[Руст]

Для вычисления этого надо определить коэффициент перед $x^{N}$ в разложении $\frac{6(6x+5x^2+4x^3+3x^4+2x^5+x^6)}{(6-x-x^2-x^3-x^4-x^5-x^6)^2}$. Для этого надо найти корни знаменателя $x_0=1,x_1,...,x_5$ и записать это в виде дроби $\sum_{i=0}^5 \frac{a_i}{x-x_i}+\frac{B_i}{x-x_i)^2}$ и тогда легко вычислить искомоую вероятность. Только возится мне этим дальше не охота.

[maxal]

Рустем, в твоей дроби сокращается множитель 5-й степени.

Поясню ход решения. Пусть $S_k$ - это сумма выпавших очков в $k$ бросаниях кости. Тогда для целого $m$ имеем:

$$Prob(S_k \leq m) = [x^m] \frac{(x+x^2+x^3+x^4+x^5+x^6)^k}{6^k (1-x)}.$$

Соответственно,

$$Prob(S_k > m) = 1 - [x^m] \frac{(x+x^2+x^3+x^4+x^5+x^6)^k}{6^k (1-x)}$$

и

$$Prob(S_k > m,\ S_{k-1}\leq m) = Prob(S_k > m) - Prob(S_{k-1} > m) =$$

$$= [x^m] \frac{(x+x^2+x^3+x^4+x^5+x^6)^{k-1}(6-(x+x^2+x^3+x^4+x^5+x^6))}{6^k (1-x)}.$$

Откуда искомое ожидаемое количество бросков равно:

$$\sum_{k=1}^{\infty} k\cdot Prob(S_k > N-1,\ S_{k-1}\leq N-1) =$$

$$=\sum_{k=1}^{\infty} k\cdot [x^{N-1}] \frac{(x+x^2+x^3+x^4+x^5+x^6)^{k-1}(6-(x+x^2+x^3+x^4+x^5+x^6))}{6^k (1-x)}=$$

$$=[x^{N-1}] \frac{(6-(x+x^2+x^3+x^4+x^5+x^6))}{6(1-x)} \sum_{k=1}^{\infty} k \left(\frac{x+x^2+x^3+x^4+x^5+x^6}{6}\right)^{k-1} =$$

$$=[x^{N-1}] \frac{6}{(1-x)(6-(x+x^2+x^3+x^4+x^5+x^6))} = [x^N] \frac{6x}{(1-x)^2(6+5x+4x^2+3x^3+2x^4+x^5)}.$$

Как нетрудно видеть, полученный результат совпадает с тем, что получил Рустем. И от разложения на простейшие дроби тут никуда не уйдешь.

[незваный гость]

Вариант последней формулы: $[x^N]\frac{6x}{6-7x + x^7}$. К содержанию ничего не добавляет, но программировать удобнее.

Добавлено спустя 4 минуты 24 секунды:

Руст писал(а):

Для этого надо найти корни знаменателя

Не будут они считаться… Потому и задача была по программированию.

[Юстас]

Если уж программировать, то сразу Монте-Карло, моделируем нашу функцию и среднее арифметическое берем.

[незваный гость]

Э, нет: задача состоит, небось, в вычислении точного матожидания, а не оценке. Я думаю, предполагает длинную арифметику…

[maxal]

незваный гость писал(а):

:evil:
Вариант последней формулы: $[x^N]\frac{6x}{6-7x + x^7}$. К содержанию ничего не добавляет, но программировать удобнее.

Ага, она дает формулу:

$$[x^N]\frac{6x}{6-7x + x^7} = \sum_{i=0}^{\lfloor (N-1)/7\rfloor} {N-1-6i\choose i} 7^{N-1-7i} 6^{6i+1-N} (-1)^i$$

пригодную для программирования. Для вычисления потребуется $O(N^2)$ арифметических операций. Если бы не биномиальный коэффициент, было бы $O(N)$.

Добавлено спустя 12 минут:

Хотя нет, рекурсия тут гораздо лучше - линейное время по числу арифметических операций.

[Руст]

незваный гость писал(а):

:evil:
Вариант последней формулы: $[x^N]\frac{6x}{6-7x + x^7}$. К содержанию ничего не добавляет, но программировать удобнее.

Добавлено спустя 4 минуты 24 секунды:

Руст писал(а):

Для этого надо найти корни знаменателя

Не будут они считаться… Потому и задача была по программированию.

На самом деле их точный подсчёт нужен только для асимптотических формул. Так как из-за симметрии между корнями ответ будет типа $\sum_{k=0}^5 a_k\sum_i x_i^{-(m+k)}$ внутренние суммы $y_{m+k}=\sum_i x_i^{-(m+k)}$ выражаются по рекуренции через младшие, коэффициенты $a_k$ вычисляются явно.

[worm2]

Думается, что для программистов более подходит такой путь решения:

1) Обозначим через P(m,n) вероятность того, что при m бросаниях кости выпадет ровно n очков. Положим P(m,n) = 0 если m либо n меньше 1.
2) Очевидно, P(m,n) = 0 при m > n и при 6m < n, P(1,1)=P(1,2)=...=P(1,6)=1/6.
3) Также вполне очевидна рекуррентная формула:

$$P(m,n) = \frac 1 6 \sum\limits_{i=1}^6P(m-1,n-i)$$

.
Пользуясь ею, удобно заносить значения P(m,n) по мере вычисления в двумерный массив размерностью NxN.
4) Дальше всё, как у maxalа здесь, только все вычисления проводятся с плавающей точкой. Тут, правда, получается $O(N^2)$ как по времени, так и по памяти, зато можно обойтись без глубокого знания математики

[незваный гость]

Руст писал(а):

На самом деле их точный подсчёт нужен только для асимптотических формул. Так как из-за симметрии между корнями … коэффициенты $a_k$ вычисляются явно.

Конечно… Я писал о Вашем высказывании, а не от том, что на самом деле.

worm2 писал(а):

только все вычисления проводятся с плавающей точкой

Нет необходимости. Можно вести рациональные вычисления. Особенно удобно, поскольку все знаменатели $6^n$. И, если присмотреться, у Вас получается некое обобщение бинома Ньютона. Думается, и явная формула для него есть.