сложная задача по теории вероятностей

[Dogmat-iGwt]

Простая формулировка задачи звучит так: Какова вероятность того, что сумма значений игрального кубика, брошенного 10000 раз будет равна 40000?

Для знатоков попробую пояснить подробнее. Важно здесь чтобы сумма была именно равна 40000, а не < >. Меня в принципе интересует вопрос, какова вероятность конкретного отклонения среднего арифметического результатов большого количества испытаний от мат ожидания. Мне нужно установить прямую зависимость этой вероятности от двух параметров: от абсолютного значения этого отклонения (здесь это 40000, что на 5000 отклонено от мат ожидания - 35000) и от количества испытаний (я так понимаю через среднеквадратичное отклонение).

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

Пробовал применить неравенства Чебышева и функцию Лапласа Ф(х), но во-первых неравенства Чебышева при определенных обстоятельствах имеют большую погрешность (хотя, если Вы поможете мне выяснить, от чего она зависит, то это решение тоже сгодится), к тому же этот метод рассматривает неравенства (хотя я готов рассматривать вариант с небольшим диапазоном), но самое главное, что интегральная функция Лапласа (интеграл вероятностей) не рассчитывается, а берется из таблиц, в которых все округлено, а мне могут понадобиться расчеты с точностью до миллионных (хотя я пока в этом не уверен).

В конце концов, я пытался даже составить таблицу зависимости количества разных вариаций сложения суммы очков кубика от количества испытаний, но не пока не смог найти, как учитывать потолок количества элементарных исходов (здесь 6: 1 2 3 4 5 6).

Очень прошу, подскажите, что делать? на предыдущем форуме мне посоветовали обратиться к Вам. Спасибо.

[RIP]

Dogmat-iGwt в сообщении #279007 писал(а):

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

А чё её искать-то? Дисперсия одного испытания умножить на количество испытаний.

Dogmat-iGwt в сообщении #279007 писал(а):

Простая формулировка задачи звучит так: Какова вероятность того, что сумма значений игрального кубика, брошенного 10000 раз будет равна 40000?

Каково точное значение этой вероятности, сказать не могу, но её легко оценить (она будет ничтожная, меньше $10^{-100}$). Для этих целей есть неравенство Чернова.

Теорема (неравество Чернова). Пусть $\xi_1,\ldots,\xi_n$ --- независимые в совокупности действительные случайные величины с конечными матожиданиями, причём при всех $1\le j\le n$ справедливо неравенство $|\xi_j-\mathbf E\xi_j|\le1$ (почти всюду). Положим $X=\xi_1+\ldots+\xi_n$, $\sigma=\sqrt{\mathbf DX}$. Тогда для любого $\lambda\ge0$ выполнено

$$\mathbf P\{|X-\mathbf EX|\ge\lambda\sigma\}<2\max\{e^{-\lambda^2/3},e^{-\lambda\sigma/2}\}.$$

P.S. Более того,

$$\max\bigl\{\mathbf P\{X-\mathbf EX\ge\lambda\sigma\},\mathbf P\{X-\mathbf EX\le-\lambda\sigma\}\bigr\}\le\max\{e^{-\lambda^2/3},e^{-\lambda\sigma/2}\}.$$

В нашем случае можно взять $\xi_j=2n_j/5$, где $n_j$ --- результат $j$-го броска, $n=10^4$, $\sigma=100\sqrt{7/15}$, $\lambda=20\sqrt{15/7}$, откуда получаем $\mathbf P\{|S-35000|\ge5000\}<2e^{-2000/7}<10^{-100}$, где $S$ --- искомая сумма значений.
В случае $n$ бросков $\mathbf P\{|S_n-7n/2|\ge c\sqrt n\}<2e^{-4c^2/35}$ при $0\le c\le7\sqrt n/4$. При больших $n$ ЦПТ, конечно, даёт лучший результат, но зато тут неравенство справедливо при всех $n$.
P.S. Мог наврать в арифметике.
P.P.S. Вот, статью нашёл. Также можно глянуть книгу автора, где доказывается чуть более сильный результат (п. 2.2). Правда, при малом количестве испытаний (скажем, $<10^6$) погрешность получается не шибко маленькой.
P.P.S. Впрочем, при достаточно маленьких $n$ можно и точно вероятность посчитать. Для этого нужно найти коэффициент при $x^S$ в многочлене $(x+x^2+\ldots+x^6)^n=x^n(1-x^6)^n(1-x)^{-n}$. Поэтому вероятность равна

$$6^{-n}\sum_{0\le k\le(S-n)/6}(-1)^k\binom nk\binom{S-6k-1}{n-1}.$$

Плюс можно на симметрии сыграть: для $S$ и $7n-S$ вероятности совпадают, поэтому можно считать $S\le7n/2$. Тогда и неравенство Чернова не нужно, т. к. вероятности при фиксированном $n$ убывают с ростом $|S-7n/2|$, поэтому надо начинать считать с серединки и остановиться, как только вероятность упадёт ниже интересуемой точности.

[Dogmat-iGwt]

Большое спасибо. Правда, пока еще не во всем разобрался. Но по поводу первого предложения, если действительно оптимальное количество испытаний должно быть >1000000, то это не обнадеживает, поскольку в моем случае, там, где я собираюсь применять это решение, количество испытаний варьирует от 0 до 50000.

Точность меня интересует максимальная. Для примера: Меня интересует вероятность получения среднего арифметического 9,201 при случайном выборе чисел от 1 до 10 в 43359 испытаниях. Результат должен быть рассчитан с точностью до первых 3-4 цифр отличных от 0 после запятой. То есть примерно так: 1,234*10^-43345. Тут понятно, что само среднее арифметическое при таком количестве испытаний весьма не точно, поэтому лучше рассматривать вероятность в диапазоне от 9,2005 до 9,2014(9).

По второму варианту (в P.P.S.) не совсем понятен ход мысли. Что означают переменные x, k, S, возможно я их неправильно трактую?

Тут еще могут возникнуть проблемы с вычислениями. если не будет способа где степени считаются отдельно (вручную), то ни один движок у меня не осилит такую арифметику.

[PAV]

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

[Dogmat-iGwt]

ну хоть так бы решить. это тоже приемлемо. Это не экзаменационная задачка, это разработка метода составления топов на сайтах с более чем двухбалльной системой голосования. Виденные мною способы не устанавливают прямой связи между средним арифметическим по баллам и количеством голосов, что по моему мнению - важно. Я подумал, что если представить каждое голосование, как случайную величину, то вероятность отклонения конечного результата от мат ожидания с учетом количества испытаний и будет той самой характеристикой, соединяющей эти две величины. Но не думал, что это будет так напряжно.

[PAV]

Рекуррентно совсем несложно. Пусть $P_n(S)$ - вероятность получить ровно $S$ очков при бросании $n$ костей. Очевидно, что эти величины рекуррентно вычисляются по формуле:

$$P_{n+1}(S)=\frac{P_n(S-1)+P_n(S-2)+\cdots+P_n(S-6)}{6}$$

Из этой формулы и начальных условий (да и просто по смыслу задачи) также очевидно, что $P_n(S)$ имеет вид:

$$P_n(S)=\frac{Q_n(S)}{6^n}$$

где $Q_n(S)$ - целые числа, удовлетворяющие соотношению:

$$Q_{n+1}(S)=Q_n(S-1)+\cdots+Q_n(S-6)$$

Таким образом, можно точно вычислять числители $Q_n(S)$, правда они будут очень большими, так что потребуется длинная арифметика. А в конце останется только разделить на соответствующую степень шестерки.

-- Вс янв 10, 2010 14:22:46 --

Вообще говоря, есть и теоретические результаты подобного типа, хотя они и достаточно сложные. Их можно найти, в частности, в книге Петров В.В. — Суммы независимых случайных величин, раздел "Локальные предельные теоремы". Наиболее сильный результат, описывающий асимптотические разложения в этих теоремах, имеет следующий вид (теорема 13 на стр. 253):

Теорема. Пусть $\{X_n\}$ - последовательность независимых случайных величин, имеющих одинаковое распределение и принимающих лишь целочисленные значения. Пусть $\mathbf{D}X_1=\sigma^2>0$, $\mathbf{E}|X_1|^k<\infty$ для некоторого целого $k\ge 3$ и максимальный шаг распределения величины $X_1$ равен 1. Тогда

$$ \sigma\sqrt{n}P_n(N)=\frac{1}{\sqrt{2\pi}}\exp\{-x^2/2\}+\sum_{\nu=1}^{k-2}\frac{q_\nu(x)}{n^{\nu/2}}+\bar o\left(\frac{1}{n^{(k-2)/2}}\right) $$

равномерно относительно $N$ ($-\infty<N<\infty$). Здесь $x=\frac{N-n\mathbf{E}X_1}{\sigma\sqrt{n}}$, а $q_\nu(x)$ - функции, алгоритм вычисления которых приводится раньше.

В этой теореме, правда, отсутствуют точные оценки о-малого, но наверное где-нибудь тоже можно найти. Хотя это более специальная вещь. Возможно, в этом смысле может помочь книга 1987 года: Петров В.В. — Предельные теоремы для сумм независимых случайных величин

-- Вс янв 10, 2010 14:25:52 --

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

-- Вс янв 10, 2010 14:30:41 --

Какие-то точные оценки отклонений есть во второй книге Петров В.В. — Предельные теоремы для сумм независимых случайных величин в главе "Неравенства Эссеена и Берри-Эссеена". Можно попробовать поискать их современные и точные формулировки.

[RIP]

Не знаю, актуально ли это до сих пор, но в прошлый раз я слегка перемудрил. Ведь в данном случае производящая функция очень простая, поэтому асимптотика для вероятности очень легко выписывается без привлечения общих теорем (которые, впрочем, доказываются точно так же). Конкретно, вероятность, что после $n$ бросков выпадет в сумме $S=7n/2+x\sqrt{35n/12}$ (это определение величины $x$), равна

$$\frac1{2\pi}\int_{-\pi}^\pi\left(\frac{\cos(\phi/2)+\cos(3\phi/2)+\cos(5\phi/2)}3\right)^n\cos(S-7n/2)\phi\,{\mathrm{d}}\phi=\sqrt{\frac6{35\pi n}}\,e^{-x^2/2}\left(1-\frac{37(x^4-6x^2+3)}{700n}\right)+O(n^{-2.5})$$

(равномерно по $S$), если я нигде не наврал в арифметике (при желании можно и больше членов асимптотики выписать). Впрочем, считать постоянную в $O(\cdot)$ явно мне лень (если верить компьютеру, то уже при $n\ge10$ она порядка $10^{-2}$).

[Kornelij]

Подскажите, пожалуйста, где можно почитать про упомянутое неравенство Чернова? Интересует доказательство теоремы. По указанной ссылке http://eqworld.ipmnet.ru/ru/library/mathematics/numtheory.htm есть список книг, а какую из них смотреть, не понятно.

[RIP]

Я встречал доказательство в книге T. Tao & V. Vu, Additive combinatorics (параграф 1.3). Только там оценка чуть слабее, чем я сформулировал ($e^{-\lambda^2/4}$ вместо $e^{-\lambda^2/3}$); сформулированную мной (и даже лучшую) оценку можно получить из приведённого там док-ва, если оценивать менее грубо. В принципе, для приложений константа не важна; я сформулировал так, как сформулировал, только потому, что исходной оценки не хватало для $10^{-100}$.
Вообще, неравенство Чернова --- это скорее теория вероятностей, чем теория чисел.

-- Mon 03.05.2010 00:14:15 --

Впрочем, док-во короткое, поэтому напишу его сюда. Во-первых, без потери общности можно считать, что $\mathbf E\xi_j=0$, $\lambda\sigma>0$, и достаточно доказать нер-во $\mathbf P\bigl\{X\ge\lambda\sigma\bigr\}<\mathrm e^{-t\lambda\sigma/2}$, где $t=\min\bigl\{\frac{2\lambda}{3\sigma},1\bigr\}$. Поскольку $|t\xi_j|\le1$, то $\mathrm e^{t\xi_j}\le1+t\xi_j+0.72(t\xi_j)^2$, поэтому $\mathbf E\mathrm e^{t\xi_j}\le1+0.72t^2\mathbf D\xi_j\le\mathrm e^{0.72t^2\mathbf D\xi_j}$, следовательно,

$$\mathbf P\bigl\{X\ge\lambda\sigma\bigr\}=\mathbf P\bigl\{\mathrm e^{tX}\ge\mathrm e^{t\lambda\sigma}\bigr\}\le\mathrm e^{-t\lambda\sigma}\mathbf E\mathrm e^{tX}=\mathrm e^{-t\lambda\sigma}\prod_{j=1}^n\mathbf E\mathrm e^{t\xi_j}\le\mathrm e^{-t\lambda\sigma+0.72t^2\sigma^2}<\mathrm e^{-t\lambda\sigma+\frac34t^2\sigma^2}\le \mathrm e^{-t\lambda\sigma/2}.$$

[Kornelij]

Спасибо

[AndriyMarevich]

Данная задача (нахождение числителя в данной задаче) решается практически так же как и комбинаторная задача в которой требуется найти количество всех чисел обладающих условиями:
1.Количество цифр их это K
2.Сумма цифр это S (обязательное условие s/k<=9)
В решении той задачи применялись:
1.Формула сочетаний с повторениями
2.Формула включений-исключений (чтоб вычесть те ненужные множества заполнений различных ящиков еденицами, которые (множества) обладают хоть одним из нижеперечисленных условий:
1). В первый ящик попадает более 9-ти едениц (надо бросить туда десять едениц)
2). Во второй ящик попадает более 9-ти едениц
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
к). В к-тый ящик попадает более 9-ти едениц
к+1). В первый ящик попадает 0 едениц (заполнять еденицами все ящики кроме первого)

Там потребовалось только немного внимантельности и в конечном итоге получилась весьма компактная формула. Т. е. запросто можно считать даже без компьютера.

Это всё - теперь каждый из вас может её решить таким же способом.