Быстрая оценка квадратичной суммы

[MGM]

Необходимо вычислить сумму:
$\frac{1}{{{{\left( {N - 1} \right)}^2}}}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {\left( {1 - {\delta _{ij}}} \right)\left| {{{\bf{r}}_i} - {{\bf{r}}_j}} \right|} } $
${{{\bf{r}}_i}}$ - случайная величина в 3D пространстве с неизвесным распределением.
Главное условие - вычислительная сложность должна быть не $O\left( {{N^2}} \right)$(точная оценка), а $O\left( N \right)$.
Очевидно, что так как распределение случайной величины заранее не известно, то "быстрая" оценка будет приближением.
Поэтому вопрос, как достичь лучшего приближения? Наверняка ведь такая задача кем-то решена. Естесвенно, через различные моменты, первые, вторые.

P.S. ${\delta _{ij}}$ - дельта Кронекера. Несущесвенный элемент.

[Deggial]

Думаю, надо что-то сказать о $\delta_{ij}$, иначе только $O(N^2)$.

[MGM]

Deggial в сообщении #741008 писал(а):

Думаю, надо что-то сказать о $\delta_{ij}$, иначе только $O(N^2)$.

${\delta _{ij}}$ - дельта Кронекера. Не особо сущесвенный элемент.
Сумма, по сущесву, среднее расстояние между всеми элементами выборки.
Я понимаю, что точная оценка только со сложностью $O(N^2)$. Но наверняка грубое приближение как-то коррелирует с корреляционной матрицей выборки. Разве нет?

-- Чт июн 27, 2013 14:52:32 --

лишнюю цитату стёр

Вообще-то дельта Кронекера излишняя.
Там и так ноль. Можно похерить. Но почему-то первый пост не правиться.

[Deggial]

Ещё:

MGM в сообщении #740999 писал(а):

${{{\bf{r}}_i}}$ - случайная величина в 3D пространстве с неизвесным распределением.

Опять же: если распределение совсем отфонарное, то и приближения быть не может тоже. Надо какие-то слабые условия налагать. Например, существует матожидание координат $\bf{r}_i$.
Если есть матожидание $m=M(|\bf{r}_i-\bf{r}_j|)$, то будет примерно $\frac{N-1}{N}m$. Матожидание можно оценить по случайно выбранным $O(N)$ членам.

MGM в сообщении #741016 писал(а):

Но почему-то первый пост не правиться.

Через час возможность править сообщения исчезает.

Тема перемещена из форума «Математика (общие вопросы)» в форум «Помогите решить / разобраться (М)»
Перенёс в соответствующий раздел

[MGM]

Deggial в сообщении #741024 писал(а):

Ещё:

MGM в сообщении #740999 писал(а):

${{{\bf{r}}_i}}$ - случайная величина в 3D пространстве с неизвесным распределением.

Опять же: если распределение совсем отфонарное, то и приближения быть не может тоже. Надо какие-то слабые условия налагать. Например, существует матожидание координат $\bf{r}_i$.
Если есть матожидание $m=M(|\bf{r}_i-\bf{r}_j|)$, то будет примерно $\frac{N-1}{N}m$. Матожидание можно оценить по случайно выбранным $O(N)$ членам.

Очень не хотелось бы делать случайную выборку. По ряду причин. И соседству по индексам.
А, допустим, распределение по Гауссу относительно мат. ожидания самой величины? Есть формулы?

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

Ну, начну с того, что значение матожидания тут совсем не важно. Они вычитаются и взаимоуничтожаются (с меня фуражка прапорщика Ясненько не слетела?) Вот существенно ли то, что оно существует - сходу не скажу, но, видимо, если у нас распределение вовсе без МО, то, значит, и у искомой величины МО нет, и оценивать странненько. Дисперсия или ещё какая мера разброса - существены. Если задана корреляционная матрица для r, то можно будет получить распределение для разности r.

[mihiv]

Можно получить верхнюю оценку этой суммы со сложностью $O(N)$ независимо от того, известны ли нам характеристики распределения случайных величин. Для этого поместим начало координат в "центр масс", то есть перейдем к векторам $\vec q_i=\vec r_i- \vec a$, где

$$\vec a=\frac {\sum \limits _{i=1}^{N}\vec r_i}N$$

Очевидно $|\vec r_i-\vec r_j|=|\vec q_i-\vec q_j|$ и, кроме того:

$$\sum \limits _{i=1}^{N}\vec q_i=\vec 0\qquad (1)$$

Из равенства (1),возводя его в квадрат, получим :

$$-2\sum \limits _{1\leq i<j\leq N}\vec q_i\vec q_j=\sum \limits _{i=1}^{N}q_i^2\qquad (2)$$

С помощью неравенства Коши-Буняковского и с учетом равенства (2) получим верхнюю оценку :

$$S_1^2=\left (\sum \limits _{1\leq i<j\leq N}|\vec q_i-\vec q_j|\right )^2\leq \frac {N(N-1)}2\sum \limits _{1\leq i<j\leq N}(\vec q_i-\vec q_j)^2=\frac {N^2(N-1)}2\sum \limits _{i=1}^{N}q_i^2\qquad (3)$$

Исходная сумма с учетом неравенства (3) удовлетворяет неравенству:

$$S=\frac 2{(N-1)^2}S_1\leq \sqrt 2\left (\frac N{N-1}\right )^{\frac 32}\sqrt {q_0^2},$$

где $q_0^2=\dfrac {\sum \limits _{i=1}^Nq_i^2}N$.