2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Вероятность s-грамм
Сообщение06.12.2020, 22:23 


15/10/15
82
DeBill
А что касательно более общей формулировки задачи? Как-то можно оценить эту вероятность для сумм?

 Профиль  
                  
 
 Re: Вероятность s-грамм
Сообщение07.12.2020, 00:39 
Заслуженный участник


10/01/16
2318
Stasya7
Задача общая - интересная. Такое впечатление, что это какой-то общий вопрос. Может, что то такое есть в общей теории случайных процессов? (Если рассматривать нарастающие суммы наших случайных величин - получим случайный процесс, с независимыми приращениями. Ваш вопрос - о распределении величины "приращение за $s$
шагов". Этот -второй- процесс, видимо, стационарный, и его корреляционную функцию , видимо, сосчитать можно. Может, с этой стороны что-то можно надыбать?)

 Профиль  
                  
 
 Re: Вероятность s-грамм
Сообщение07.12.2020, 08:19 
Заслуженный участник
Аватара пользователя


11/03/08
9885
Москва
Stasya7 в сообщении #1495520 писал(а):
DeBill, в более общем виде задача звучит так:

Есть довольно длинная последовательность чисел (числа принимают значения из дискретного множества мощностью $n$), сгенерированных случайно равновероятно и независимо: $m_1, m_2,..., m_s, m_{s+1},...$

Составляется последовательность сумм из $s$ слагаемых:
$m_1+m_2+...+m_s$,
$m_2+m_3+...+m_{s+1}$,
$m_3+m_4+...+m_{s+2}$,
$...$

$...$

$...$

Нужно оценить вероятность, что сумма $m_i+m_{i+1}+...+m_{i+s-1}$ меньше $M$.

То есть, если было сгенерировано $N$ чисел, то таких сумм будет $N-s+1$. Нужно найти (возможно оценить сверху/снизу), какую долю от общего количества таких сумм составят суммы, не превышающие $M$.


А аппроксимировать нормальным распределением, учитывая, что последовательные суммы коррелированы?

 Профиль  
                  
 
 Re: Вероятность s-грамм
Сообщение07.12.2020, 12:17 


15/10/15
82
Евгений Машеров
А как учесть эту связь между суммами при аппроксимации? Можно об этом поподробнее.

 Профиль  
                  
 
 Re: Вероятность s-грамм
Сообщение07.12.2020, 12:28 


07/08/14
4231
Stasya7 в сообщении #1495395 писал(а):
есть довольно длинная последовательность целых чисел (от $1$ до $n$), сгенерированных случайно равновероятно и независимо: $m_1, m_2,..., m_s, m_{s+1},...$
А для такого условия, разве $m_1+m_2+...+m_{s}$ и $m_2+m_3+...+m_{s+1}$ не одно и тоже?

 Профиль  
                  
 
 Re: Вероятность s-грамм
Сообщение07.12.2020, 12:48 


15/10/15
82
upgrade
Одно и то же. Но каждая следующая сумма существенно зависит от предыдущей.

 Профиль  
                  
 
 Re: Вероятность s-грамм
Сообщение07.12.2020, 12:59 


07/08/14
4231
Stasya7 в сообщении #1495583 писал(а):
Но каждая следующая сумма существенно зависит от предыдущей.

Предположим, слагаемых по одному ($S_1=m_1$ и $S_2=m_2$), по условиям задачи они независимы.
Предположим, слагаемых два ($S_1=m_1+m_2$ и $S_2=m_2+m_3$), по условиям задачи частичные суммы ($S_1=m_1$, $S_2=m_2$ и $S_3=m_3$) независимы.
...
Значит, $P(S_n\leqslant M)=P(S_m\leqslant M)$, при $n=m$.
или я неверно рассуждаю?

 Профиль  
                  
 
 Re: Вероятность s-грамм
Сообщение07.12.2020, 14:11 


07/08/14
4231
Перепишу лучше так:
Предположим, слагаемых по одному ($S_1=\sum\limits_{i=1}^1{m_i}=m_1$ и $S_2=\sum\limits_{i=2}^2{m_i}=m_2$), по условиям задачи они независимы.
Предположим, слагаемых два ($S_1=\sum\limits_{i=1}^2{m_i}=m_1+m_2$ и $S_2=\sum\limits_{i=2}^3{m_i}= m_2+m_3$), по условиям задачи частичные суммы ($S_1=m_1$, $S_2=m_2$ и $S_3=m_3$) независимы.
...
Значит, $P(\sum\limits_{i=1}^m{m_i} \leqslant M)=P(\sum\limits_{i=j}^k{m_i} \leqslant M)$, при $m-1=k-j.

 Профиль  
                  
 
 Re: Вероятность s-грамм
Сообщение07.12.2020, 18:45 


15/10/15
82
DeBill в сообщении #1495548 писал(а):
Такое впечатление, что это какой-то общий вопрос.

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


upgrade
Цитата:
Значит, $P(\sum\limits_{i=1}^m{m_i} \leqslant M)=P(\sum\limits_{i=j}^k{m_i} \leqslant M)$, при $m-1=k-j$.

Пока не очень понятно, как сделан этот переход.

 Профиль  
                  
 
 Re: Вероятность s-грамм
Сообщение07.12.2020, 21:26 


07/08/14
4231
Stasya7 в сообщении #1495623 писал(а):
Пока не очень понятно, как сделан этот переход.

Stasya7 в сообщении #1495395 писал(а):
сгенерированных случайно равновероятно и независимо:
Распределения $m_1, m_2,...$ одинаковые.

 Профиль  
                  
 
 Re: Вероятность s-грамм
Сообщение08.12.2020, 00:59 


15/10/15
82
upgrade в сообщении #1495644 писал(а):
Распределения $m_1, m_2,...$ одинаковые.
Но суммы коррелируют между собой.

 Профиль  
                  
 
 Re: Вероятность s-грамм
Сообщение08.12.2020, 03:42 
Заслуженный участник


10/01/16
2318
Stasya7 в сообщении #1495520 писал(а):
Нужно найти (возможно оценить сверху/снизу), какую долю от общего количества таких сумм составят суммы, не превышающие $M$.

Ааа, я плохо смотрел...Ну так это - совсем другое дело! Т.е., Вам надо найти матожидание количества тех сумм (среди первых $k=N-s+1$ штук), которые меньше $M$. В силу линейности матожидания, оно в точности равно
$k\cdot P\{S<M\}$, где $S$ - одна из сумм (все они распределены одинаково, как Вам уже писали - хотя и не независимы; для матожидания суммы это неважно). Осталось найти эту вероятность.
Я сосчитаю ее для случая, когда все слагаемые распределены равномерно на $[0,n]$ (Ваш дискретный случай можно сделать аналогично - где то тут - типа под названием "комбинаторные тождества" - это обсуждалось. Ну, или - в случае больших $s$ - используйте ЦПТ). Легко видеть :D , что (при $0<M<ns$) она равна
$\frac{1}{n^s}\cdot \frac{1}{s!}\cdot\sum\limits_{0\leqslant m<\frac{M}{n}}^{}(-1)^m\cdot C^m_s\cdot (M-mn)^s$...

(Оффтоп)

Это следует из формулы включений-исключений и формулы для объема $s$-мерной пирамиды при решении задачи "каков объем части $s$-мерного куба $Q=\{x=(x_1,...,x_s): 0<x_i<n, i=1,...,s\}$, лежащей в полупространстве $x_1+...+x_s<M$". Порисуйте картинки в двумерном и трехмерном случаях - и увидите, что правда это...

(Оффтоп)

Вывод общей формулы стандартен: пусть $\theta_i$ равна 1, если $i$-я сумма меньше $M$, и равна 0 - иначе. Тогда $\eta =\sum\limits_{i=1}^{k} \theta_i$ - и есть кол-во сумм, меньших $M$. Значит, ожидаемое кол-во сумм, меньших $M$, равно $M\eta = \sum\limits_{i=1}^{k}M\theta_i=k\cdot P\{S<M\}$

 Профиль  
                  
 
 Re: Вероятность s-грамм
Сообщение08.12.2020, 09:13 
Заслуженный участник
Аватара пользователя


11/03/08
9885
Москва
Stasya7 в сообщении #1495579 писал(а):
А как учесть эту связь между суммами при аппроксимации? Можно об этом поподробнее.


Ну, я бы так попробовал. Рассмотрим две последовательные суммы, сдвинутые на k. Каждая имеет дисперсию $n\sigma^2$. При этом каждая равна сумме общей составляющей с дисперсией $(n-k)\sigma^2$ и различных для разных сумм независимых составляющих с дисперсией $k\sigma^2$ ("голова" одной и "хвост" другой). Отсюда находим корреляцию между ними, равную $\frac {n-k} n$

 Профиль  
                  
 
 Re: Вероятность s-грамм
Сообщение08.12.2020, 10:41 
Заслуженный участник
Аватара пользователя


11/03/08
9885
Москва
Мне вот ещё что приходит в голову...
Положим, что нам известно значение $m_1=z$. Тогда можно найти вероятность того, что $\Sigma_{i=2}^s m_i \le M-z$ (что, очевидно, эквивалентно $\Sigma_{i=1}^s m_i \le M$)
А поскольку нам известно, что неравенство выполняется, то можно, используя Байеса, найти апостериорное распределение $P(m_1=z|\Sigma_{i=1}^s m_i \le M)$ для $z=1\ldots n$ и затем найти $p=\Sigma_{z=1}^n P(\Sigma_{i=1}^{s+1} m_i \le (M+z))P(m_1=z|\Sigma_{i=1}^s m_i \le M)$

 Профиль  
                  
 
 Re: Вероятность s-грамм
Сообщение08.12.2020, 14:05 


07/08/14
4231
Stasya7 в сообщении #1495667 писал(а):
Но суммы коррелируют между собой.

А как это влияет на результат?
$m_1+m_2+m_3+...+m_n$
и
$m_1+m_2+m_3+...+m_n$
тоже коррелируют между собой, но если известно распределение $m_1+m_2+m_3+...+m_n$, оно такое же как у $m_1+m_2+m_3+...+m_n$
заменим $m_1$ на $m_2$,... $m_n$ на $m_{n+1}$ что поменяется? Это всё ещё тоже самое распределение.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 49 ]  На страницу Пред.  1, 2, 3, 4  След.

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



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

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


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

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