Оптимизация случайных величин

[alisa-lebovski]

Пусть случайные величины $U$ и $V$ равномерно распределены на $[0,1]$ и их коэффициент корреляции $\rho$, тогда

$${\bf E}UV=\frac{3+\rho}{12}.$$

Требуется найти максимум ${\bf E}\min\{U,V\}$ при этих условиях. Или хотя бы содержательную оценку сверху, зависящую от $\rho$.

Пока понятно, что ${\bf E}\min\{U,V\}\le 1/2$, и получила оценку снизу

$${\bf E}\min\{U,V\}={\bf E}\frac{U+V}{2}-{\bf E}\frac{|U-V|}{2}\ge \frac{1}{2}-\frac{1}{2}({\bf E}(U-V)^2)^{1/2}= \frac{1}{2}\left(1-\sqrt{\frac{1-\rho}{6}}\right),$$

она точная при $\rho=+1$ ($V=U$), но заниженная при $\rho=-1$ ($V=1-U$).

[alisa-lebovski]

Придумала еще оценку сверху

$${\bf E}\min\{U,V\}\le {\bf E}\sqrt{UV}\le \sqrt{{\bf E}UV}=\sqrt{\frac{3+\rho}{12}},$$

но она оказывается содержательной только при $\rho<0$, и конечно не является точной.

[Iam]

Для смеси векторов $(U,U)$ и $(U,1-U)$ (СВ $U$ равномерно распределена на $[0,1]$), если не ошибаюсь, $E \min \{U,V\}= (3+\rho)/8$.

[alisa-lebovski]

Спасибо, отличная идея. Это проходит как нижняя оценка для верхней границы. Причем точная на концах. Но является ли это верхней границей, это вопрос.

[Iam]

Для этой же смеси легко подсчитать и $E\max \{U,V\}$.

[alisa-lebovski]

Это понятно. Я говорю о верхней границе (или максимуме) возможных значений ${\bf E}\min\{U,V\}$ при данных условиях. На данный момент доказано, что

$$\frac{3+\rho}{8}\le\max_{U,V}{\bf E}\min\{U,V\}\le\min\left\{\frac{1}{2},\sqrt{\frac{3+\rho}{12}\right\}.$$

При этом верхняя оценка (моя) явно не является точной, про нижнюю оценку (Вашу) пока непонятно.

[Iam]

Похоже (highly likely :)), что граница точная. Посмотрел (доводить пока не планирую) 2 варианта доказательства, громоздко и нужно прорабатывать множество деталей.
1. 1). Разбиваем квадрат на 4 квадрата.
2). В каждом задаем значения: $p_i, m_i, \sigma_i^2, EU_iV_i, M_i = E \min \{U_i,V_i\}.$
3). Связываем соответствующие параметра соотношениями, следующими из условия задачи, а также условиями
$8M_i -\rho_i <3$.
4). Выражаем параметры $EUV, M=E \min \{U,V\}$ исходного квадрата через заданные в п.2.
5). В ограничениях п. 3 решаем оптимизационную задачу: $Q(p_i, m_i,...| \rho)=8M-\rho \to \max$.
Ясно, что $Q \ge 3$. Если получили $ \max Q =3$, то хорошо – получена точная граница, причем в этом случае экстремальное распределение не зависит от $\rho$. Если же max $Q >3$ , тоже хорошо – получен механизм построения последовательности улучшаемых распределений.
Другой вариант.
2. 1). Разбиваем квадрат на $n^2$ квадратиков (точек).
2). Устанавливаем, что в экстремальном случае число ненулевых точек не более $2n$.
3). Оптимизируем систему этих точек (непосредственно или при наращивании квадрата) и показываем, что Х-конструкция – одна из оптимальных.

alisa-lebovski, если у Вас будет продвижение по задаче, то просьба дать информацию.

[Iam]

Вспомнил про идею, которую обозначил в пред-предыдущем посте - привожу ниже.
Обозначим
$ Q_-[ F]= E_F \min \{U,V\}, Q^-[ F]= E_F \max \{ U,V \},$
$Q_-(\rho)=\max_F Q_-[ F], Q^-(\rho)=\min_FQ_-[ F].$
Ясно, что $Q_-[ F]+ Q^-[ F]=1, Q_-(\rho)+ Q^-(\rho)=1,$ т. е. границы $Q_-(\rho), Q^-(\rho) $ различаются на константу, причем $Q_-(\rho) $ выпукла вверх, а $Q^-(\rho)$ - вниз. Т.о., эти зависимости линейны и по известным значениям на концах отрезка получаем: $Q_-(\rho)=(3+\rho)/8, Q^-(\rho)= (5-\rho)/8.$

[alisa-lebovski]

Спасибо большое, буду думать. Я все-таки надеюсь, что найдется более изящное решение.

[Iam]

alisa-lebovski, по сформулированной задаче имеем решение, состоящее из трех ключевых и по существу элементарных посылок: 1) искомая зависимость (граница) выпукла вверх; 2) она же выпукла (т. е. вниз), и, следовательно, линейна; 3) эта зависимость (как линейная) определена по значениям в двух заданных крайних точках отрезка. Выражение записано.
Если уточните, что понимается под «более изящным решением», возможно, его поиски заинтересуют и других. Готов буду подключиться.

[alisa-lebovski]

Я пока не понимаю. Если есть две оптимальные пары $(U_1,V_1)$ для $\rho_1$ и $(U_2,V_2)$ для $\rho_2$, то для промежуточного значения $\rho=\alpha\rho_1+(1-\alpha)\rho_2$, $\alpha\in (0,1)$, возьмем их соответствующую смесь, которую обозначим через $(U_3,V_3)$ и получим

$${\bf E}\min\{U_3,V_3\}=\alpha{\bf E}\min\{U_1,V_1\}+(1-\alpha){\bf E}\min\{U_2,V_2\},$$

$${\bf E}\max\{U_3,V_3\}=\alpha{\bf E}\max\{U_1,V_1\}+(1-\alpha){\bf E}\max\{U_2,V_2\},$$

так что отсюда (из первого уравнения) следует вогнутость $\max_{U,V}{\bf E}\min\{U,V\}$, но не выпуклость.

И может существовать такая пара $(U_0,V_0)$, что

$${\bf E}\min\{U_0,V_0\}\ge\alpha{\bf E}\min\{U_1,V_1\}+(1-\alpha){\bf E}\min\{U_2,V_2\},$$

$${\bf E}\max\{U_0,V_0\}\le\alpha{\bf E}\max\{U_1,V_1\}+(1-\alpha){\bf E}\max\{U_2,V_2\},$$

почему нет?

[Iam]

alisa-lebovski, тысяча извинений... Плотно займусь и доведу до кондиционного решения.

[Iam]

Описываются подходы и примеры, которые могут быть полезны для решения задачи.
Распределения на $[0,1]\times[0,1]$-квадрате для простоты и наглядности будем представлять плотностью распределения вероятностей $f(x,y)$, имея в виду возможность использования $\delta$-функции Дирака. Впрочем, все нижеизложенное легко перевести на язык функций распределения или вероятностной меры.
Задача:
$M=\int _0^1 \int _0^1 \min \{x,y\} f(x,y)dy dx \to \max_{f \in \Omega_2 (\rho) }⁡ $ ,
где множество $\Omega_2 (\rho)$ определено условиями:
$ \int _0^1 \int _0^1 xyf(x,y)dy dx= \rho/4; $ $ f_X(x) =\int _0^1 f(x,y)dy=1 (x\in [0,1]) , f_Y(y) =\int _0^1 f(x,y) dx =1 (y\in [0,1]) $.

Учитывая, что
$f(y|x)=f(x|y)=f(x,y) $,
можно записать эквивалентные постановки задачи:
$ \int _0^1 \int _0^1 \min \{x,y\} f(y|x)dy dx \to \max_{f \in \Omega_2 (\rho)} $ ;⁡
$\int_0^1[\int _0^x yf(y|x)+x\int _x^1 f(y|x)]dy dx \to \max_{f \in \Omega_2 (\rho)} $ .

Пусть $\rho’ = \rho’(x)$ (не производная), причем $\rho =\int _0^1 \rho ' (x) dx $, тогда
$\max M=\max_{ \rho'(x)} \int _0^1 \max_{ f(y|x)\in \Omega_1 (\rho')} \min \{x,y\} f(y|x) dy dx=$
=\max_{ \rho'(x)} \int _0^1 \max_{ p,,y_1,y_2} [(1-p(x)) \min \{x,y_1(x)\} +p(x) \min \{x,y_1(x)\} ] dx$,
где $(1-p(x)) y_1+p(x)y_2=\rho'(x)/4x$
(максимумы достигаются).

Переход к последнему соотношению сделан на основе теоремы Каратеодори, при этом механизм нахождения точек $y_1,y_2$ в принципе понятен.
Мы видим, что при каждом значении $x$ оптимальная в классе $\Omega_1 (\rho')$ функция распределения $F^* (y|x)$ (по крайней мере, одна из) дискретна и имеет не более двух точек роста (распределение двухатомное). Другими словами, если на $[0,1]\times [0,1]$-квадрате отметить точки с ненулевой плотностью вероятности, то они образуют такие множества, которые будут пересекаться не более чем в двух точках с любой «вертикальной» прямой и с любой «горизонтальной» прямой.

Теперь, если разбить квадрат на $2n\times 2n$ квадратиков (называем точками), к такому же заключению можно придти относительно числа ненулевых точек в каждом столбце и каждой строке квадрата. Множество из $4n$ точек может быть разбито на $n$ прямоугольников, в каждом из которых диагональные вершины (пусть главной диагонали) имеют одинаковые вероятности $p/2$, а побочной диагонали $(p-1)/2.$
Этот же факт непосредственно может быть установлен из теоремы Каратеодори (с учетом теоремы Рисса о распределениях): имеем множество распределений с $4n$ ограничениями ($2n$ по вертикали, $2n-1$ по горизонтали и одно на корреляцию), а также из рассмотрения сформулированной задачи как задачи ЛП. Следовательно, искомый максимум достигается на $4n$-атомном распределении. Анализ свойств экстремального распределения подсказывает, что в экстремальном случае точки будут расположены на диагоналях квадрата (такую конфигурацию точек будем называть - диагональной) Это в перспективе, конечно, нужно проверять.
Вместо этого далее делается попытка оптимизировать распределение вероятностей на диагональной конфигурации и проверить возможность улучшения за счет этого нижней границы.
Предварительно определим параметры квадрата, расположенного на диагонали и содержащего вершину на главной диагонали с вероятностью $p/2$:
$\rho'(p,x)=(2p-1) (2x-1)^2 ;$
$M'(p,x)=\frac p 2+(1-p)x $.

Таким образом, подбирая для диагональной конструкции зависимость $ p(x)= p(x,x)$ и вычисляя параметры $\rho, M$, можно попытаться поднять нижнюю границу.
Чтобы ускорить процесс, я не стал оптимизировать линейные, квадратичные и пр. зависимости, а просто выбрал два «крайних» варианта: 1)$\ p_1(x)=2x$ и 2)$ p_2(x)=1-2x$, для которых $p_i(x)=p_i(1-x)$.
1.$ p_1=2x \to \rho_1=-1/12 , M_1=\frac {1} {6}.$
В соответствии с имеющейся нижней границей при $\rho_1=-1/12$ имеем $M^*=\frac {35} {96}$ ,т. е.
$M_1<M^*$ , значение $M_1$ ниже границы.
2. $p_2=1-2x \to \rho _2=1/4 , M_2=\frac {5} {24}$.
В соответствии с имеющейся нижней границей при $\rho _2=1/4$ имеем $M^*=\frac {13} {32}$ ,т. е.
$M_2<M^*$ , значение $M_2$ ниже границы.

Если все-таки имеющаяся нижняя граница неулучшаема, то решение задачи, таким образом, можно свести к следующим этапам: 1)установить факт оптимальности диагональной конструкции и 2)доказать оптимальность для таких конструкций распределения с $ \rho'(x)=\operatorname{const}t= \rho$.

Рассуждения, формулы и вычисления нужно проверить.

[Iam]

alisa-lebovski, не удивляйтесь погрешностям при записи коэф. корреляции. Сначала записывал для центрированного квадрата, а потом что-то сдвинулось. Поправлю и можем сверить результаты.

[Iam]

Да и идея построения диагональных распределений была не такой. В общем беру паузу для исправлений.