Вероятность s-грамм

[Stasya7]

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

[DeBill]

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

[Евгений Машеров]

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$.

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

[Stasya7]

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

[upgrade]

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}$ не одно и тоже?

[Stasya7]

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

[upgrade]

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$.
или я неверно рассуждаю?

[upgrade]

Перепишу лучше так:
Предположим, слагаемых по одному ($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.

[Stasya7]

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$.

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

[upgrade]

Stasya7 в сообщении #1495623 писал(а):

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

Stasya7 в сообщении #1495395 писал(а):

сгенерированных случайно равновероятно и независимо:

Распределения $m_1, m_2,...$ одинаковые.

[Stasya7]

upgrade в сообщении #1495644 писал(а):

Распределения $m_1, m_2,...$ одинаковые.

Но суммы коррелируют между собой.

[DeBill]

Stasya7 в сообщении #1495520 писал(а):

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

Ааа, я плохо смотрел...Ну так это - совсем другое дело! Т.е., Вам надо найти матожидание количества тех сумм (среди первых $k=N-s+1$ штук), которые меньше $M$. В силу линейности матожидания, оно в точности равно
$k\cdot P\{S<M\}$, где $S$ - одна из сумм (все они распределены одинаково, как Вам уже писали - хотя и не независимы; для матожидания суммы это неважно). Осталось найти эту вероятность.
Я сосчитаю ее для случая, когда все слагаемые распределены равномерно на $[0,n]$ (Ваш дискретный случай можно сделать аналогично - где то тут - типа под названием "комбинаторные тождества" - это обсуждалось. Ну, или - в случае больших $s$ - используйте ЦПТ). Легко видеть , что (при $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\}$

[Евгений Машеров]

Stasya7 в сообщении #1495579 писал(а):

А как учесть эту связь между суммами при аппроксимации? Можно об этом поподробнее.

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

[Евгений Машеров]

Мне вот ещё что приходит в голову...
Положим, что нам известно значение $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)$

[upgrade]

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}$ что поменяется? Это всё ещё тоже самое распределение.