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

[Андрей1]

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

В самом простом случае она выглядит так:

Есть случайная величина X и вероятности P{X=i} принять этой величине значения 0, 1, 2,...
Допустим известно, что эта величина есть сумма двух величин Y1 и Y2, значения которых лежат в том же множестве.

Задача состоит в том, чтобы найти все вероятности для Y1 и Y2, для которых минимальна квадратичная форма
(P\{Y1=0\} - C_0)^2 + (P\{Y1=1\} - C_1)^2 ... + (P\{Y2=0\} - D_0)^2 + (P\{Y2=1\} - D_1)^2 + ...

Где можно почитать о такого типа задачах?

На какие ключевые слова можно искать литературу?

Задача, по идее, должна уже быть хорошо изучена (видно, что тут должна быть какая-то красивая теория...).

[PAV]

Во-первых, хорошо бы оформить формулы так, как тут принято, см. здесь

Во-вторых, правильно ли я понял, что числа $C_i$ и $D_i$ нам заданы изначально?

[Андрей1]

PAV писал(а):

Во-первых, хорошо бы оформить формулы так, как тут принято, см. здесь

Ок.

PAV писал(а):

Во-вторых, правильно ли я понял, что числа $C_i$ и $D_i$ нам заданы изначально?

Да, конечно, о функционале, который нужно минимизировать все известно (в реальной задаче X зависит еще от параметров и значения C_i, D_i - это вероятности для Y1 и Y2 в некоторой близкой точке по этим параметрам).

[mag_marilyn]

Уважаемый Андрей!
У меня меня появились следующие мысли:
1) Тут мы имеем дело с МНК для бесконечномерного пространства оцениваемых величин. О решении прям такого случая я не знаю.
По моему мнению о хитрых применениях МНК хорошо изложено в книге Алберт А. Регрессия, псевдоинверсия и рекуррентное оценивание. М.: Наука, 1977. Может там что то есть.
2) Если вы в практическом использовании "отбрасываете хвост" у последовательности реализаций и получаете конечномерный случай - то такое решение точно есть. Т.е. вы можете говорить, что для любой конечной последовательности реализаций можно найти сколь угодно точное решение.

Желаю Вам удачи

[Андрей1]

mag_marilyn писал(а):

2) Если вы в практическом использовании "отбрасываете хвост" у последовательности реализаций и получаете конечномерный случай - то такое решение точно есть. Т.е. вы можете говорить, что для любой конечной последовательности реализаций можно найти сколь угодно точное решение.

Желаю Вам удачи

Спасибо за ответ.
Вопрос в том, как его найти .
Книгу Алберта А. постараюсь найти.

[mag_marilyn]

Андрей1 писал(а):

Вопрос в том, как его найти .
Книгу Алберта А. постараюсь найти.

ИМХО ход рассуждения должен быть такой:
Будем рассматривать конечное количество реализаций.
Пусть
P \left( X=i \right) =X_{{i}} - известные вероятности,
P \left( {\it Y1}=i \right) ={\it y1}_{{i}}, P \left( {\it Y2}=i \right) ={\it y2}_{{i}} - вероятности реализаций случайных величин, которые мы ищем.
{{\it C1}\ldots {\it Cn}}, {{\it D1}\ldots {\it Dn}} - известные константы.
Введем следующие обозначения:
1) Переобозначим вектор искомых вероятностей, таким образом получим вектор z, а из известных констант составим вектор С.
2) После такого переобозначения получим ограничения на компоненты вектора z:
Например если z_{{1}}={\it y1}_{{1}}, а z_{{2}}={\it y2}_{{1}} то
z_{{1}}+z_{{2}}=X_{{1}},
Все такие ограничения можно переписать в виде:
Hz=B, где B - известный вектор, состоящий из X_{{i}}.
Критерий для минимизации перепишется в виде:

\[ \left( {Hz - C} \right)^T \left( {Hz - C} \right) \to \mathop {\min }\limits_z \]

при ограничениях
Hz=B.

Это систему можно решить после ещё одной замены перемынных, т.к. для задачи:

\[ z^T z \to \mathop {\min }\limits_z \]

при ограничениях
Hz=B
решение имеет вид (Если ограничения совместны, т.е. HH^{+}B=B)
z=H^{+}B+ \left( I-H^{+}H \right) q, где H^{+} - псевдообратная матрица по Муру-Пенроузу, q - любое.

Совет: разберитесь с МНК и все будет понятно. Замечательная книга: Магнус Я., Нейдекер Х.. Матричное дифференциальное исчисление с приложениями к статистике и эконометрике. М.: Физматлит, 2002.

[PAV]

mag_marilyn

Вы хотите сказать, что $P(Y_1+Y_2=i)=P(Y_1=i)+P(Y_2=i)$ ???

[mag_marilyn]

PAV писал(а):

mag_marilyn
Вы хотите сказать, что $P(Y_1+Y_2=i)=P(Y_1=i)+P(Y_2=i)$ ???

ыыыЫЫыы.. кажись я не так все понял )))
я думал что нужно разделить одну величину на две таки образом, что если

\[ P[X = i] = X_i \]

, то

\[ P[Y1 = i] + P[Y2 = i] = X_i \]

По опорным вероятностям

\[ C_1 ...C_n ,D_1 ...D_n \]

В этом случае надо по другому сформировать матрицу ограничений.
Верно ли, что

\[ P\left\{ {Y_1 + Y_2 = i} \right\} = \sum\limits_{j = 0}^i {\left( {P\left\{ {Y & _1 = j} \right\} P\left\{ {Y & _2 = i - j} \right\}} \right) = P\left\{ {X = i} \right\}} \]

?

[PAV]

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

[PAV]

Я бы по поводу этой задачи сказал следующее.

Можно попробовать лобовой способ. А именно: нам даны последовательности чисел $\{X_i\}$, $\{C_i\}$ и $\{D_i\}$ (как я понимаю, по смыслу задачи две последние будут распределениями вероятностей, как и первая). Введем неизвестные $v_i=P(Y_1=i)$ и $w_i=P(Y_2=i)$.

Требуется решить задачу минимизации

$$ F(v,w|X,C,D)=\sum_{i=0}^\infty(v_i-C_i)^2+\sum_{i=0}^\infty(w_i-D_i)^2\to\min $$

Будем сейчас рассматривать невырожденный случай, когда $X_0>0$. Из условия на распределения можно выразить неизвестные $w$ через $v$, поскольку

$$ X_i=P(Y_1+Y_2=i)=\sum_{k=0}^i v_kw_{i-k}. $$

Имеем последовательно: $w_0=X_0/v_0$, $w_1=(X_1-v_1w_0)/v_0$ и так далее.

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


Я бы посоветовал взять случай, когда с.в. $X$ (а с нею и $Y_1$ и $Y_2$) принимают конечное небольшое число значений, попробовать аккуратно все выписать и довести до ответа. Может быть, удастся заметить какю-нибудь общую закономерность, которая позволит "угадать" правильный ответ.


Другой путь (связанный, правда, с изменением условий задачи) заключается в том, чтобы рассмотреть какое-нибудь другое расстояние между распределениями. Ведь, насколько я понял, требуется найти распределения, достаточно близкие к имеющимся. Используемый Вами функционал (разности квадратов) известны для других задач, но есть ряд специфических вероятностных расстояний между распределениями (например, расстояние Кульбака, расстояние Хеллингера). Может быть, с ними удастся что-то сделать, используя какие-нибудь их специфические вероятностные свойства. Правда, уверенности в этом у меня нет.

Было бы очень хорошо, если бы нашлось такое расстояние, которое бы выражалось через характеристические или производящие функции. Дело в том, что для всех "известных" распределений эти функции известны, а также условие того, что сумма $Y_1+Y_2$ дает известное распределение через эти функции выражается тривиально, так как соответствующая функция от суммы независимых с.в. равна произведению функций. Тогда бы задача решилась бы наверняка.

Кстати, в расстоянии Хеллингера тоже рассматриваются разности вероятностей, возведенные в квадрат, только не самих вероятностей, а квадратных корней от них. Тогда если мы раскроем скабки, то суммы вероятностей дадут постоянные слагаемые, а останутся только произведения. Может, это несколько облегчит задачу?

[Андрей1]

Большое спасибо за подробный ответ.

Способом "в лоб" я уже занимаюсь пару недель . В настоящий момент я разработал некоторую эвристику, которая позволяет быстро находить почти правильное решение: вероятности оцениваются последовательно для P{X=0}, P{X=1}, однако в некоторый момент выясняется, что нельзя удовлетворить связям следующего уровня на P{X=i} (обычно, начиная с i=2)... Тогда я сделал алгоритм для вычисления неравенств, которым должны удовлетворять P{X=i}. Но, чтобы он эффективно работал, нужно знать все P{X=0}, при которых решение существует. Вот тут то я и решил поспрашивать у знающих людей ...

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

Это новое расстояние, возможно, нужно выбирать так, чтобы решение было статистически корректным: то есть решения для большого числа задач должны удовлетворять статистическим закономерностям (каким-то образом с этими закономерностями должны будут соотносится и входные параметры C_i и D_i). Возможно задачу нужно как-то переформулировать...

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

PAV писал(а):

...

Другой путь (связанный, правда, с изменением условий задачи) заключается в том, чтобы рассмотреть какое-нибудь другое расстояние между распределениями. Ведь, насколько я понял, требуется найти распределения, достаточно близкие к имеющимся. Используемый Вами функционал (разности квадратов) известны для других задач, но есть ряд специфических вероятностных расстояний между распределениями (например, расстояние Кульбака, расстояние Хеллингера). Может быть, с ними удастся что-то сделать, используя какие-нибудь их специфические вероятностные свойства. Правда, уверенности в этом у меня нет.

Было бы очень хорошо, если бы нашлось такое расстояние, которое бы выражалось через характеристические или производящие функции. Дело в том, что для всех "известных" распределений эти функции известны, а также условие того, что сумма $Y_1+Y_2$ дает известное распределение через эти функции выражается тривиально, так как соответствующая функция от суммы независимых с.в. равна произведению функций. Тогда бы задача решилась бы наверняка.

Кстати, в расстоянии Хеллингера тоже рассматриваются разности вероятностей, возведенные в квадрат, только не самих вероятностей, а квадратных корней от них. Тогда если мы раскроем скобки, то суммы вероятностей дадут постоянные слагаемые, а останутся только произведения. Может, это несколько облегчит задачу?

Да, возможно - это правильный путь. Буду копать в этом направлении...

[Андрей1]

PAV писал(а):

Кстати, в расстоянии Хеллингера тоже рассматриваются разности вероятностей, возведенные в квадрат, только не самих вероятностей, а квадратных корней от них.

А вот здесь в расстояние Хеллингера входит еще arccos... Это нормальное явление или не очень? ...
http://ami.nstu.ru/~headrd/MSA/MSA%20_1 ... 3%E5%F0%E0

[PAV]

Не могу сказать. Я видел определение безо всяких арккосинусов.

[Андрей1]

И все таки, я не понимаю....

Если взять две независимые случайные величины, которые могут принимать значения 0 или 1 и составить таблицу:
Y1(1), Y2(1); Y1(1)+Y2(1)=X(1);
Y1(2), Y2(2); Y1(2)+Y2(2)=X(2);
...
Затем найти частоты P{X=i} и принять их за вероятности (P0,P1,P2), и затем, решив систему, найти вероятности для
P\{Y1=0\}=1/2(2P0+P1-C)
P\{Y2=0\}=1/2(2P0+P1+C)
(где C=\sqrt{-4P0+4P0^2+4P0 P1+P1^2})
, то получится, что решение существует, только в случае c>=0 =>:
0<=P0<=1 \& 2\sqrt{P0}(1-\sqrt{P0})<=P1<=1 (*)

То есть получается, что не любую случайную величину, которая принимает значения (0,1,2) можно представить как сумму независимых слагаемых?

У меня есть такая таблица, но для этих данных условие (*) не выполнено... Но при этом нет оснований считать, что Y1 и Y2 зависимы... Как такое может быть?...

[Андрей1]

Андрей1 писал(а):

У меня есть такая таблица, но для этих данных условие (*) не выполнено... Но при этом нет оснований считать, что Y1 и Y2 зависимы... Как такое может быть?...

Отвечаю сам себе: Легко может быть, черт возьми, поскольку вероятности P{X=i} точно не известны . Поэтому нужно вводить интервалы (или меру?) для P{X=i}, отвечающие заданному уровню значимости, и понимать уравнение P{Y1=i}&P{Y2=j}=P{X=Y1+Y2=i+j} (& - свертка) как интервальное (или искать корень, при котором мера на P{X=i} - минимальна).

И еще мысль: составить "честный" статистический вес, куда включить как зависимую величену P{X=Y1+Y2} и минимизировать его. Вопрос лишь, как его, "честный", найти то?