2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Ожидаемое количество бросаний кости
Сообщение09.12.2007, 11:13 


25/07/07
9
Привет!

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

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

 Профиль  
                  
 
 
Сообщение09.12.2007, 13:56 
Заслуженный участник


09/02/06
4401
Москва
Для вычисления этого надо определить коэффициент перед $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}$ и тогда легко вычислить искомоую вероятность. Только возится мне этим дальше не охота.

 Профиль  
                  
 
 
Сообщение10.12.2007, 12:58 
Модератор
Аватара пользователя


11/01/06
5710
Рустем, в твоей дроби сокращается множитель 5-й степени. :D

Поясню ход решения. Пусть $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)}.$$
Как нетрудно видеть, полученный результат совпадает с тем, что получил Рустем. И от разложения на простейшие дроби тут никуда не уйдешь.

 Профиль  
                  
 
 
Сообщение11.12.2007, 06:04 
Заслуженный участник
Аватара пользователя


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

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

Руст писал(а):
Для этого надо найти корни знаменателя

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

 Профиль  
                  
 
 
Сообщение11.12.2007, 06:06 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение11.12.2007, 06:09 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение11.12.2007, 06:36 
Модератор
Аватара пользователя


11/01/06
5710
незваный гость писал(а):
: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 минут:

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

 Профиль  
                  
 
 
Сообщение11.12.2007, 15:01 
Заслуженный участник


09/02/06
4401
Москва
незваный гость писал(а):
: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$ вычисляются явно.

 Профиль  
                  
 
 
Сообщение11.12.2007, 15:45 
Заслуженный участник
Аватара пользователя


01/08/06
3158
Уфа
Думается, что для программистов более подходит такой путь решения:

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)$ как по времени, так и по памяти, зато можно обойтись без глубокого знания математики 8-)

 Профиль  
                  
 
 
Сообщение11.12.2007, 19:43 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Руст писал(а):
На самом деле их точный подсчёт нужен только для асимптотических формул. Так как из-за симметрии между корнями … коэффициенты $a_k$ вычисляются явно.

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: drzewo, YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group