Задача о взвешенном выборе и случайной величине: единственность решения

13 июня 2020 года, 00:12

В прошлый раз мы решали задачу о взвешенной сортировке и показали, что существует функция $f_w(x)$ , такая что максимальное значение этой функции $\inline\max_{i=1,2,...n}\left\{f_{w_i}(x_i)\right\}$ будет достигнуто на k-той паре $(w_k, x_k)$ с вероятностью, пропорциональной $w_k$ , где $x_i$ — значение случайной величины, равномерно распределенной на единичном отрезке $[0, 1]$ .

Мы потребовали непрерывности и монотонности функции $f_w(x)$ по $x$ , а также зафиксировали значения на концах отрезка: $f_w(0) = a, f_w(1) = b$ . В этих предположениях показали, что функция должна удовлетворять условию

$\int\limits_0^1dx_1\,f^{-1}_{w_2}\left(f_{w_1}(x_1)\right)\cdot f^{-1}_{w_3}\left(f_{w_1}(x_1)\right)\cdot\ldots\cdot f^{-1}_{w_n}\left(f_{w_1}(x_1)\right) ={w_1\over w_1+w_2+w_3+\ldots+w_n}$ (1)

для любых наборов значений $w_i>0$ . Мы нашли целый класс подходящих под это условие функций:

$f_w(x)=h(x^{1/w}),$ (2)

где $h(y)$ — любая строго монотонная функция.

Теперь докажем, что других решений у этой задачи не существует.

Теорема о единственности. Пусть для каждого значения $w>0$ функция $f_w(x)$ непрерывна и строго монотонна по $x$ на отрезке $[0,1]$ , принимает на концах отрезка фиксированные значения $f_w(0) = a, f_w(1) = b$ и удовлетворяет (1). Тогда найдется такая строго монотонная функция $h(y)$ , для которой выполняется тождество (2).

Доказательство будет конструктивным: мы построим конкретный пример $h(y)$ на основе вида функции $f_w(x)$ .

Лемма 1. Обратная функция $f^{-1}_w(s)$ при каждом фиксированном значении аргумента $s\in[a,b]$ непрерывна по параметру $w$ на всем допустимом множестве значений этого параметра $w>0$ .

Доказательство от противного. Пусть существует точка $w_2$ , в которой $f^{-1}_w(s)$ не является непрерывной. Это значит, что

$\exists\varepsilon>0\ \forall\delta_1>0\ \exists s_1\in[a,b]\ \exists w_3:|w_2-w_3|<\delta_1,\left|f^{-1}_{w_2}(s_1)-f^{-1}_{w_3}(s_1)\right|>\varepsilon.$ (3)

Так как функция $f^{-1}_w(s)$ непрерывна по $s$ на отрезке $[a,b]$ , она равномерно непрерывна на нем в силу теоремы Кантора — Гейне. Из равномерной непрерывности следует, что $|f^{-1}_{w_2}(s)-f^{-1}_{w_3}(s)|>\varepsilon/2$ в некоторой $\delta_2$ -окрестности точки $s_1$ , причем $\delta_2$ зависит только от $\varepsilon$ , не от $s_1$ . (Иными словами, разрыв по $w$ будет наблюдаться не только в одной точке $s_1$ , но и в ее окрестности.)

Аналогично функция $f_w(x)$ непрерывна и равномерно непрерывна на отрезке $[0,1]$ . По $\delta_2$ -окрестности точки $s_1$ можно найти $\delta_3$ -окрестность точки $x_1=f^{-1}_{w_1}(s_1)$ , для каждого $x$ из которой $\left|f^{-1}_{w_2}(f_{w_1}(x))-f^{-1}_{w_3}(f_{w_1}(x))\right|>\varepsilon/2$ (значение $w_1$ выбирается произвольно и фиксируется для следующих рассуждений).

Это значит, что следующий интеграл от квадрата разности функций в соседних точках $w_2$ и $w_3$ ограничен снизу ненулевой величиной, не зависящей от $\delta_1$ :

$\int\limits_a^bdx\left[f^{-1}_{w_2}(f_{w_1}(x))- f^{-1}_{w_3}(f_{w_1}(x))\right]^2>{\delta_3\varepsilon^2\over 4}$

Теперь непосредственно вычислим интеграл, раскрыв скобки и воспользовавшись условием (1):

$\begin{align*} &\int\limits_a^bdx\left[f^{-1}_{w_2}(f_{w_1}(x))- f^{-1}_{w_3}(f_{w_1}(x))\right]^2=\\ =&\!\int\limits_a^b\!dx\left[f^{-1}_{w_2}(f_{w_1}(x))\right]^2-2\!\int\limits_a^b\!dx\,f^{-1}_{w_2}(f_{w_1}(x))\, f^{-1}_{w_3}(f_{w_1}(x))+\!\int\limits_a^b\!dx\left[ f^{-1}_{w_3}(f_{w_1}(x))\right]^2=\\ =&{w_1\over w_1+2w_2}-2{w_1\over w_1+w_2+w_3}+{w_1\over w_1+2w_3}=\\ =&{2w_1\over(w_1+2w_2)(w_1+2w_3)(w_1+w_2+w_3)}(w_2-w_3)^2=\\ =&{2w_1\over(w_1+2w_2)(w_1+2w_2-2(w_2-w_3))(w_1+2w_2-(w_2-w_3))}(w_2-w_3)^2. \end{align*}$

Оценка этого выражения снизу дает неравенство:

${2w_1(w_2-w_3)^2\over(w_1+2w_2)(w_1+2w_2-2(w_2-w_3))(w_1+2w_2-(w_2-w_3))}>{\delta_3\varepsilon^2\over 4}.$

Но согласно отрицанию определения непрерывности (3) $\delta_1$ можно выбрать сколь угодно малым, при этом $\varepsilon$ , $\delta_3$ и $w_1$ зависят только от выбора $w_2$ и остаются фиксированными. Так как $|w_2-w_3|<\delta_1$ , выбором $\delta_1$ также можно сделать левую часть неравенства сколь угодно малой при фиксированной правой. Противоречие. $\square$

Лемма 2. Для любых значений $k,m\in\mathbb{N}$ , $w>0$ , $s\in[a,b]$ выполняется равенство

$\left[f^{-1}_{w/k}(s)\right]^k=\left[f^{-1}_{w/m}(s)\right]^m.$

Доказательство. Введем в (1) новую переменную $s=f_{w_1}(x_1)$ :

$\int\limits_a^bds\ {\partial f^{-1}_{w_1}(s)\over\partial s}\ f^{-1}_{w_2}(s)\cdot f^{-1}_{w_3}(s)\cdot\ldots\cdot f^{-1}_{w_n}(s) ={w_1\over w_1+w_2+w_3+\ldots+w_n}.$

Разделим набор весов $w_2$ , $w_3$ , … $w_n$ на две группы количеством $k$ и $m$ , в каждой из которых веса совпадают и равны $w/k$ и $w/m$ соответственно. Тогда:

$\int\limits_a^bds\ {\partial f^{-1}_{w_1}(s)\over\partial s}\ \left[f^{-1}_{w/k}(s)\right]^k \left[f^{-1}_{w/m}(s)\right]^m ={w_1\over w_1+2w}\quad\forall k,m\in\mathbb{N}.$

Последний интеграл можно интерпретировать как скалярное произведение функций $[f^{-1}_{w/k}(s)]^k$ и $[f^{-1}_{w/m}(s)]^m$ в пространстве с положительной в силу монотонности $f^{-1}_{w_1}$ метрикой $\partial f^{-1}_{w_1}(s)/\partial s$ . По неравенству Коши — Буняковского скалярное произведение не превосходит произведения норм, и равенство достигается при коллинеарности сомножителей. Из последнего уравнения видно, что скалярное произведение совпадает с квадратом нормы каждого элемента. Поэтому в нашем случае имеет место равенство. Действительно, вычислим норму от квадрата разности функций:

$\begin{align*} &\int\limits_a^bds\ {\partial f^{-1}_{w_1}(s)\over\partial s}\ \left\{\left[f^{-1}_{w/k}(s)\right]^k- \left[f^{-1}_{w/m}(s)\right]^m\right\}^2=\\ =&\int\limits_a^bds\ {\partial f^{-1}_{w_1}(s)\over\partial s}\ \left\{\left[f^{-1}_{w/k}(s)\right]^{2k} -2\left[f^{-1}_{w/k}(s)\right]^k\left[f^{-1}_{w/m}(s)\right]^m +\left[f^{-1}_{w/m}(s)\right]^{2m}\right\}=0. \end{align*}$

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

Несмотря на присутствие в выражениях производной $\partial f^{-1}_{w_1}(s)/\partial s$ , дифференцируемость по $s$ в этом доказательстве не требуется. Замена переменной $x_1$ на $s$ была проведена для удобства и наглядности. Аналогичные рассуждения имеют место и без замены переменных. $\square$

Следствие 1. Для любых значений $r\in\mathbb{Q}_+$ , $w>0$ , $s\in[a,b]$ выполняется равенство

$f^{-1}_w(s)=\left[f^{-1}_{w/r}(s)\right]^r.$

Доказательство. Представим положительное рациональное число $r=m/k$ как отношение натуральных чисел. В утверждении леммы 2 выполним замену $w\to wk$ и возведем обе части в степень $1/k$ :

$f^{-1}_w(s)=\left[f^{-1}_{wk/m}(s)\right]^{m/k}=\left[f^{-1}_{w/r}(s)\right]^r.\ \square$

Следствие 2. Для любых значений $p\in\mathbb{R}_+$ , $w>0$ , $s\in[a,b]$ выполняется равенство

$f^{-1}_w(s)=\left[f^{-1}_{w/p}(s)\right]^p.$

Доказательство. Рассмотрим выражение $[f^{-1}_{w/p}(s)]^p$ как функцию от $p$ . По следствию 1 в рациональных точках $p$ ее значение равно $f^{-1}_w(s)$ . По лемме 1 функция непрерывна по параметру. Поэтому ее значение в иррациональных точках $p$ также равно $f^{-1}_w(s)$ . $\square$