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

В прошлый раз мы решали задачу о взвешенной сортировке и показали, что существует функция $$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_1>0$$ для применения формулы (1) во всём доказательстве.

Доказывать лемму будем методом от противного. Пусть найдется такое значение $$s_1$$, для которого в некоторой точке $$w_2$$ функция $$w\mapsto f^{-1}_w(s)$$ не является непрерывной. Это значит, что

$$\exists s_1\in[a,b]\ \exists w_2>0\ \exists\varepsilon>0\ \forall\delta_1>0\ \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)

По условию теоремы функция $$s\mapsto f^{-1}_w(s)$$ — обратная к непрерывной монотонно возрастающей функции $$f_w(x)$$, принимающей на концах отрезка $$[0,1]$$ значения $$a$$ и $$b$$, поэтому она непрерывна и монотонна по $$s$$ на отрезке $$[a,b]$$ и принимает значения $$f^{-1}_w(a)=0$$ и $$f^{-1}_w(b)=1$$. Непрерывность по $$w$$ на концах отрезка (при $$s_1\in\{a,b\}$$) константных функций очевидна.

Будем доказывать противоречие (1) и (3) для внутренней точки $$s_1\in(a,b)$$. Запишем для этой точки и параметра $$w_2$$ определение непрерывности обратной функции:

$$\begin{align*} &\forall\varepsilon'>0\ \exists\delta'>0:\forall s, |s-s_1|<\delta'\Rightarrow |f^{-1}_{w_2}(s)-f^{-1}_{w_2}(s_1)|<\varepsilon'.\\ \end{align*}$$

Выберем для $$\varepsilon'=\varepsilon/2$$ даваемое этим определением значение $$\delta'=\delta_2>0$$. Оно зависит от уже зафиксированных $$w_2$$ и $$s_1$$, но не от $$w_3$$.

Предположим, что модуль в (3) раскрывается с «плюсом», то есть

$$f^{-1}_{w_2}(s_1)-f^{-1}_{w_3}(s_1)>\varepsilon\implies f^{-1}_{w_3}(s_1)<f^{-1}_{w_2}(s_1)-\varepsilon.$$

Из монотонности $$f^{-1}_{w_3}$$ и непрерывности $$f^{-1}_{w_2}$$ на интервале $$s\in(s_1-\delta_2,s_1)$$:

$$f^{-1}_{w_3}(s)<f^{-1}_{w_3}(s_1)<f^{-1}_{w_2}(s_1)-\varepsilon <f^{-1}_{w_2}(s)-\varepsilon/2.$$

Если модуль в (3) раскрывается с «минусом», то по аналогии на интервале $$s\in(s_1,s_1+\delta_2)$$:

$$f^{-1}_{w_3}(s)>f^{-1}_{w_3}(s_1)>f^{-1}_{w_2}(s_1)+\varepsilon >f^{-1}_{w_2}(s)+\varepsilon/2.$$

Таким образом, разрыв по $$w$$ будет наблюдаться не только в одной точке $$s_1$$, но и как минимум рядом с ней на некотором интервале длиной $$\delta_2$$, причем величина этого разрыва составляет как минимум $$\varepsilon/2$$.

Так как функция $$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$$ и $$w_3$$:

$$\int\limits_0^1dx\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_0^1dx\left[f^{-1}_{w_2}(f_{w_1}(x))- f^{-1}_{w_3}(f_{w_1}(x))\right]^2=\\ =&\!\int\limits_0^1\!dx\left[f^{-1}_{w_2}(f_{w_1}(x))\right]^2-2\!\int\limits_0^1\!dx\,f^{-1}_{w_2}(f_{w_1}(x))\, f^{-1}_{w_3}(f_{w_1}(x))+\!\int\limits_0^1\!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_2$$ и остаются фиксированными. Так же зафиксировано и $$w_1$$. Так как $$|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$$. По неравенству Коши — Буняковского скалярное произведение не превосходит произведения норм, и равенство достигается при коллинеарности сомножителей. Из последнего уравнения видно, что скалярное произведение совпадает с квадратом нормы каждого элемента (правая часть не зависит от $$k$$ и $$m$$). Поэтому в нашем случае имеет место равенство. Действительно, вычислим норму от квадрата разности функций:

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

Доказательство теоремы. Из следствия 2 для любых $$p>0$$ выполняется равенство $$f_w(x)=f_{w/p}(x^{1/p})$$. Пусть $$p=w$$. Тогда

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

где $$h(y)\equiv f_1(y)$$ — строго монотонная функция. $$\square$$