Задача коллекционера

Представьте, что вы кидаете игральный кубик, и выпадает число от 1 до 6. Сколько раз в среднем нужно бросить кубик до того момента, как каждое число выпадет хотя бы один раз? Ясно, что число попыток не должно быть меньше 6. Но если при этом попадались одинаковые числа, потребуется больше бросков. Сколько именно?

Это одна из возможных формулировок задачи коллекционера. Под таким названием (Coupon Collector’s Problem) она встречается в англоязычной литературе, а в русскоязычной практически не упоминается (я нашел одну публикацию в «Математическом просвещении»). Давайте исправим несправедливость и разберем эту весьма интересную задачу.

Современному читателю проще прочувствовать смысл этой задачи на примере киндер-сюрприза: сколько нужно купить шоколадных яиц, внутри которых находится одна из $$N$$ машинок, чтобы собрать полную коллекцию?

Стандартное решение

Обозначим через $$T$$ искомое количество попыток сбора $$N$$ элементов коллекции. Оно состоит из суммы числа попыток $$t_i$$ получить элемент $$i$$, когда уже собрано $$i-1$$ элементов: $$T=t_1 + \cdots + t_N$$.

Вероятность найти новый $$i$$-й элемент коллекции, когда уже собрано $$i-1$$ элементов и осталось собрать $$N-i+1$$, равна

$$P(i)={N-i+1\over N}.$$(1)

То есть $$t_i$$ — случайная величина с геометрическим распределением и математическим ожиданием

$$\operatorname{E}(t_i)=\frac{1}{P(i)}=\frac{N}{N-i+1}.$$(2)

С учетом линейности математического ожидания

$$\begin{align*} \operatorname{E}(T) & {}= \operatorname{E}(t_1 + t_2 + \cdots + t_N)=\\ &=\operatorname{E}(t_1) + \operatorname{E}(t_2) + \cdots + \operatorname{E}(t_N)=\\ &=\frac{1}{P(1)} + \frac{1}{P(2)} + \cdots + \frac{1}{P(N)}=\\ &=\frac{N}{N} + \frac{N}{N-1} + \cdots + \frac{N}{1}=\\ &=N \cdot \left(\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{N}\right)=\\ &=N H_N. \end{align*}$$

Здесь $$H_N$$ — частичные суммы гармонического ряда, асимптотика которых выражается через логарифм:

$$\operatorname{E}(T)=NH_{N}=N\ln N+\gamma N+{1\over 2}+O\left({1\over N}\right).$$(3)

Альтернативное решение

Решение выше получилось достаточно простым благодаря тому, что вероятность получения нового элемента коллекции (1) не зависит от истории, то есть от самих величин $$t_i$$. Однако такая зависимость может появиться в более сложном случае. Скажем, если коллекционер обменивается с другими коллекционерами, то чем больше у него накопилось дублей в коллекции, тем больше вероятность получить новый элемент через обмен. В этом примере формула (1) усложняется, а (2) вообще не работает.

В общем случае вероятность появления нового элемента может явно зависеть от номера шага $$t$$. Через $$P_t(n)$$ мы обозначим вероятность того, что после $$t$$ шагов мы собрали $$n$$ элементов коллекции. Я проведу рассуждения в условиях исходной задачи, а вы при необходимости можете их обобщить.

Если после выполнения $$t$$ шагов мы собрали $$n$$ элементов, это значит, что на предыдущем шаге количество элементов могло быть либо $$n-1$$, либо $$n$$. В первом случае мы получаем новый элемент с вероятностью, определяемой формулой (1), во втором случае противоположной вероятностью:

$$P_t(n)=\left(1-{n-1\over N}\right)P_{t-1}(n-1)+{n\over N}P_{t-1}(n).$$(4)

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

О каких граничных условиях идет речь? Ясно, что $$P_0(0)=1$$, $$P_0(n)=0, 0<n\leq N$$ (в начале никакой коллекции нет). Кроме того, на первом шаге мы гарантированно получим один элемент, поэтому $$P_t(0)=0, t>0$$.

Перепишем для удобства (4) в другом виде после подстановки $$n=N-m$$:

$$P_t(N-m)={m+1\over N}P_{t-1}\left(N-(m+1)\right)+{N-m\over N}P_{t-1}(N-m)$$(4a)

Заметим еще, что на каждом шаге должна сохраняться нормировка вероятности — в коллекции точно должно быть хоть сколько-то элементов:

$$\sum_{n=0}^N P_t(n)=1.$$(5)

Нарушение условия нормировки сразу укажет на ошибку в построении математической модели. Давайте проверим, что в (4) подобных ошибок нет:

$$\begin{align*} \sum_{n=0}^N P_t(n)&=P_t(0)+\sum_{n=1}^N \left[\left(1-{n-1\over N}\right)P_{t-1}(n-1)+{n\over N}P_{t-1}(n)\right]=\\ &=\sum_{n=0}^{N-1} \left(1-{n\over N}\right)P_{t-1}(n)+\sum_{n=1}^N {n\over N}P_{t-1}(n)=\\ &=\sum_{n=0}^{N-1}P_{t-1}(n)-{0\over N}P_{t-1}(0)+{N\over N}P_{t-1}(N)=\\ &=\sum_{n=0}^{N}P_{t-1}(n). \end{align*}$$

Мы опустили нулевое слагаемое $$P_t(0)$$ из граничных условий, а также перенумеровали слагаемые в одной из сумм. По индукции видно, что нормировка сохраняется на каждом шаге.

В задаче нам нужно усреднить число попыток $$t$$ до окончания сбора коллекции:

$$\operatorname{E}(T)=\sum\limits_tt\left(P_t(N)-P_{t-1}(N)\right).$$

Чтобы получить вероятность окончания сбора коллекции именно на шаге $$t$$, я вычел из вероятности собрать $$N$$ элементов на шаге $$t$$ вероятность собрать $$N$$ элементов на шаге $$t-1$$ (вычитается вероятность того, что на предыдущем шаге коллекция уже собрана).

Из (4а) при $$m=0$$:

$$P_t(N)={1\over N}P_{t-1}\left(N-1\right)+P_{t-1}(N).$$

Отсюда

$$\operatorname{E}(T)={1\over N}\sum\limits_ttP_{t-1}(N-1).$$(6)

Здесь мы видим другое представление вероятности окончания сбора коллекции: вероятность сбора последнего элемента $$1/N$$ умножается на вероятность наличия $$N-1$$ элементов на предыдущем шаге.

Идея дальнейших вычислений в том, чтобы пользуясь равенством (4а) и дальше понижать аргумент в (6) от $$N-1$$ до 0. Тогда в сумме останется только один ненулевой элемент, соответствующий $$P_0(0)=1$$. Вы можете проделать несколько подстановок (4а) вручную и увидеть закономерность. Я же сразу сформулирую ее в виде утверждения, связывающего $$\operatorname{E}(T)$$ и $$P_{t}(N-m)$$:

Утверждение. Существуют такие числа $$A_m$$ и $$B_m$$, что при любых натуральных $$N$$ и $$m\in [1,N]$$ выполняется равенство

$$\operatorname{E}(T)={m\over N}\sum\limits_ttP_{t-m}(N-m)+A_mN-B_m.$$(7)

Доказательство по индукции. Если $$m=1$$, то из (6) гипотеза верна при $$A_1=B_1=0$$. Пусть она верна для $$m>1$$. Тогда из (4а)

$$\begin{align*}\operatorname{E}(T)&={m\over N}\sum_tt\left[{m+1\over N}P_{t-m-1}\left(N-(m+1)\right)+{N-m\over N}P_{t-m-1}(N-m)\right]+A_mN-B_m=\\ &={m\over N}{m+1\over N}\sum_ttP_{t-m-1}\left(N-(m+1)\right)+{N-m\over N}\underbrace{{m\over N}\sum_ttP_{t-m-1}(N-m)}_{S_1}+A_mN-B_m.\end{align*}$$

Сумма в первом слагаемом похожа на нужную сумму из (7) для $$m$$, увеличенного на 1. Пока отдельно вычислим оставшуюся сумму:

$$\begin{align*}S_1&={m\over N}\sum\limits_ttP_{t-m-1}(N-m)=\\ &={m\over N}\sum_{t+1}(t+1)P_{t-m}(N-m)=\\ &={m\over N}\sum_ttP_{t-m}(N-m)+{m\over N}\sum_tP_{t-m}(N-m)=\\ &=\operatorname{E}(T)-A_mN+B_m+\underbrace{{m\over N}\sum_tP_t(N-m)}_{S_2}.\end{align*}$$

Здесь мы дважды воспользовались изменением индекса суммирования. Так как суммирование идет по всем возможным $$t$$, мы можем спокойно менять индексы. Лишних или отсутствующих слагаемых не будет, так как вероятности зануляются, когда число шагов меньше размера коллекции: $$P_t(n)=0, t<n$$.

Просуммируем теперь (4a) по всем $$t$$:

$$\begin{align*}\sum_tP_t(N-m)&=\sum_t{m+1\over N}P_{t-1}\left(N-(m+1)\right)+\sum_t{N-m\over N}P_{t-1}(N-m)=\\ &={m+1\over N}\sum_tP_t\left(N-(m+1)\right)+{N-m\over N}\sum_tP_t(N-m), \end{align*}$$

откуда

$${m\over N}\sum_tP_t(N-m)=\sum_t{m+1\over N}P_t\left(N-(m+1)\right).$$

Таким образом, по индукции $$\inlineS_2={m\over N}\sum_tP_t(N-m)$$ не зависит от $$m$$ и равно 1, так как при $$m=N$$ переходит в $$P_0(0)+P_1(0)+P_2(0)+\ldots=1+0+0+\ldots=1$$. Возвращаемся к $$\operatorname{E}(T)$$:

$$\begin{align*}\operatorname{E}(T)&={m\over N}{m+1\over N}\sum\limits_ttP_{t-m-1}\left(N-(m+1)\right)+\\ &+{N-m\over N}(\operatorname{E}(T)-A_mN+B_m+1)+A_mN-B_m,\\ N\operatorname{E}(T)&=m{m+1\over N}\sum_ttP_{t-m-1}\left(N-(m+1)\right)+\\&+\operatorname{E}(T)N-A_mN^2+B_mN+N-m\operatorname{E}(T)+mA_mN-mB_m-m+A_mN^2-B_mN,\\ m\operatorname{E}(T)&=m{m+1\over N}\sum_ttP_{t-m-1}\left(N-(m+1)\right)+N+mA_mN-mB_m-m,\\ \operatorname{E}(T)&={m+1\over N}\sum_ttP_{t-m-1}\left(N-(m+1)\right)+(A_m+{1/m})N-(B_m+1).\end{align*}$$

По форме это совпадает с (7) при условии

$$A_{m+1}=A_m+{1\over m},\quad B_{m+1}=B_m+1.$$

С учетом начальных условий $$A_1=B_1=0$$ получаем явные выражения коэффициентов: $$A_m=1+1/2+\ldots+1/(m-1)=H_{m-1}$$ — частичные суммы гармонического ряда, $$B_m=m-1$$. $$\square$$

Подставим теперь $$m=N$$ в (7). Тогда

$$\omeratorname{E}(T)=\sum_ttP_{t-N}(0)+H_{N-1}N-N+1=H_{N-1}N+1=N\left(H_{N-1}+{1\over N}\right)=NH_N,$$

что совпадает с ответом стандартного решения.

Вывод

Мы решили задачу коллекционера, записав уравнение эволюции распределения вероятности (4). Это уравнение можно рассматривать как дискретный вариант уравнения, описывающего поток вероятности.

Такой подход универсален для задач подобного типа, потому что позволяет их решать не только аналитически, но и численно. Например, в нашем случае эволюцию распределения вероятности можно рассчитать на основе уравнения (4) даже в Excel. На скриншоте видно, как распределение вероятности со временем смещается от меньших $$n$$ к большим для $$N=10$$.

Как создается электрическое поле в проводнике с током?

Мотивация

Вопрос, вынесенный в заголовок, в свое время породил большую дискуссию на физическом форуме (1, 2, 3). Вот более точная формулировка вопроса:

Рассмотрим длинный провод, подключенный к батарейке. По нему течет постоянный ток. Ток создается электрическим полем Е, которое, в свою очередь, создается зарядами на полюсах батарейки. Почему вдали от полюсов (например, в середине проводника) поле Е=const, а не убывает при удалении от полюсов, как ему положено по закону Кулона?

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

Обоснование появления зарядов на поверхности проводника с током следующее. Плотность тока внутри проводника по закону Ома пропорциональна напряженности поля:

$$\vec{j}=\lambda \vec{E}.$$

Возьмем дивергенцию обеих частей и воспользуемся первым уравнением Максвелла $$\text{div}\vec{E}=4\pi\rho$$ и законом сохранения электрического заряда в локальной форме $$\text{div}\vec{j}=-\partial\rho/\partial t$$:

$$-{\partial\rho\over\partial t}=4\pi\lambda\rho.$$(1)

Так как протекание тока — стационарный процесс, в котором величины со временем не меняются, то производная в левой части зануляется, поэтому правая часть — плотность зарядов внутри проводника — тоже есть 0. Следовательно, поле в проводнике может создаваться только зарядами на его поверхности.

Почему-то у этого простого обоснования есть противники, которые утверждают, что появление постоянного электрического поля вдоль проводника нельзя объяснить в классической электродинамике, и изобретают свои объяснения, например: источник тока создает избыток электронов с одного конца провода, и эти лишние электроны «расталкивают» другие электроны. Физического содержания в этих объяснениях нет, и мы не будем их рассматривать.

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

Близкая задача из электростатики

К сожалению, мы не можем найти точное распределение поверхностных зарядов по проводнику, если не учтем механизм того, как именно создается разность потенциалов на его концах. Вместо выбора такого механизма сделаем приближение, сказав что никакого механизма нет. Фактически, будем решать упрощенную задачу: как нужно распределить заряд по поверхности, чтобы поле внутри стало таким же, как и при стационарном протекании тока?

Разумеется, распределенный по поверхности проводника заряд без механизма создания разности потенциалов сразу же растечется (характерное время растекания можно найти из уравнения (1)), и, казалось бы, решать такую задачу бессмысленно. Но можно сформулировать задачу из электростатики о проводнике во внешнем однородном электрическом поле с точно таким же ответом:

Цилиндрический проводник длины l и радиуса R помещен во внешнее электрическое поле, так что его ось направлена по полю. Найти распределение поверхностных зарядов.

Действительно, в этом случае заряды так распределятся по поверхности проводника, что линейный потенциал внешнего поля $$\varphi_\text{внеш}=-|E|x$$ будет скомпенсирован их собственным потенциалом $$\varphi=kx$$ во всем объеме проводника.

Для полноты отметим, что аналогичная задача проводнике сферической формы имеет простое точное решение.

Наивный подход

$$ \newcommand{\drawCircle}[3]{ \draw (#1,#2) arc (90:270:#3 and #2); \draw[dashed] (#1,-#2) arc (-90:90:#3 and #2); } \newcommand{\drawTik}[2]{\draw (#1,0.1) -- ++ (0,-0.2) node[fill=white,below,inner sep=0,pos=1.4] {$#2$}} \begin{tikzpicture}[>=latex] \def\rx{4} \def\xx{-1.9} \def\x{1.9} \def\ry{1.2} \def\e{0.48} \node[above right,inner sep=2] at (0,\ry) {$R$} \node[below right,inner sep=2] at (0,-\ry) {$-R$} \node[below right] at (0,0) {$0$} \draw[->,very thin] (-\rx-1,0) -- (\rx+1,0) node[below] {$x$}; \draw[->,very thin] (0,-1.5*\ry) -- (0,2*\ry) node[left] {$r$}; \draw (\rx,0) ellipse (0.48 and \ry); \draw[] (-\rx,-\ry) -- (\rx,-\ry) (-\rx,\ry) -- (\rx,\ry); \drawCircle{-\rx}{\ry}{\e} \drawCircle{\xx-0.1}{\ry}{\e} \drawCircle{\xx+0.1}{\ry}{\e} \node[above] at (\xx,\ry) {$dx_1$} \drawTik{\xx}{x_1} \drawTik{\x}{x} \draw[dashed](\xx,\ry) -- (\x,0) \draw (\rx,0) ellipse (0.25 and 0.62); \draw (\rx,0) ellipse (0.3 and 0.75); \drawTik{-\rx}{-{l\over2}} \drawTik{\rx}{l\over2} \draw[dashed] (\x,0) -- (\rx,0.68) node[inner sep=2,pin={[pin distance=6, pin edge={<-,solid,black},fill=white,inner sep=1]30:$dr$}] {} \draw[->] (2.8,\ry+0.8) -- ++(2,0) node[pos=0.9,above] {$\vec{E}$}; \end{tikzpicture} $$

Обозначим плотность зарядов через $$\sigma_1(x)$$ на боковой поверхности и $$\sigma_2(r)$$ на поверхности оснований. Через эти величины можно выразить электрическое поле или потенциал внутри цилиндра, взяв интегралы по поверхности. Скажем, на оси цилиндра

$$\varphi(x)=\int\limits_{-l/2}^{l/2}{2\pi R\,dx_1\,\sigma_1(x_1)\over\sqrt{R^2+(x-x_1)^2}}+ \int\limits_{0}^{R}{2\pi r\,dr\,\sigma_2(r) \over\sqrt{r^2+\left(x-{l\over2}\right)^2}} -\int\limits_{0}^{R}{2\pi r\,dr\,\sigma_2(r)\over\sqrt{r^2+\left(x+{l\over2}\right)^2}} =Ex.$$(2)

Здесь учтены симметрии задачи: вращательная симметрия вокруг оси повлияла на выбор элементов площади, а зеркальная симметрия выражается в том, что плотности зарядов на основаниях цилиндра имеют противоположный знак ($$\sigma_2$$ и $$-\sigma_2$$), и в том, что функция $$\sigma_1(x)$$ — нечетная.

Мы получили интегральное уравнение на $$\sigma_1(x)$$ и $$\sigma_2(r)$$. Я не смог решить его в явном виде. Можно было бы рассмотреть предельный режим, когда $$l\gg R$$, и поискать приближенное решение в области $$|x|\ll l$$. Тогда вкладом двух последних интегралов можно пренебречь, а в первом интегрировать от минус бесконечности до бесконечности:

$$\int\limits_{-\infty}^{\infty}{R\,dx_1\,\sigma_1(x_1)\over\sqrt{R^2+(x-x_1)^2}}=x.$$(3)

Здесь я опустил коэффициент пропорциональности, не влияющий на дальнейшие рассуждения. Это интегральное уравнение имеет вид свертки ядра $$k(x)=1/\sqrt{1+x^2/R^2}$$ и искомой функции. Такое уравнение можно решить, взяв преобразование Фурье от обеих частей:

$${\cal F}(\sigma_1)\int {e^{-ikx}\over\sqrt{1+\dfrac{x^2}{R^2}}}dx=\int xe^{-ikx}dx.$$

Интегрирование по частям справа дает $$\inline\int xe^{-ikx}dx=-i\delta(k)/k$$. Искомая функция ищется через обратное преобразование Фурье:

$$\sigma_1(x)={-i\over2\pi}\int\dfrac{\delta(k)e^{ikx} dk}{k\int {e^{-iks}\over\sqrt{1+\frac{s^2}{R^2}}}ds}.$$

Дельта-функция просто возвращает подынтегральное выражение при $$k=0$$. Интеграл в знаменателе можно выразить через модифицированную функцию Бесселя второго рода, и знаменатель стремится к 0 при $$k\to0$$. Получается, не существует «достаточно хорошей» функции $$\sigma_1(x)$$, определенной на всей вещественной оси, удовлетворяющей приближенному уравнению. Мы сделали слишком сильное упрощение, перейдя от уравнения (2) к уравнению (3).

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

Аналитические методы заводят в тупик

Наша задача на языке математики формулируется так. Вне цилиндра потенциал подчиняется уравнению Лапласа $$\Delta\varphi=0$$ и стремится к нулю (как поле диполя) на бесконечности. На поверхности цилиндра потенциал фиксирован и описывается начальными условиями

$$\begin{align*}\varphi(x, R)&=Ex,\quad x\in\left[-{l\over2},{l\over2}\right],\\ \varphi\left(\pm{l\over2}, r\right)&=\pm E{l\over2},\quad r\in\left[0,R].\end{align*}$$

Это формулировка задачи Дирихле для уравнения Лапласа. Решение у этой задачи существует и оно единственно. Потенциал определяет электрическое поле вне цилиндра, а скачок нормальной составляющей электрического поля на границе цилиндра пропорционален искомой поверхностной плотности заряда.

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

$${1\over r}{\partial\over\partial r}\left(r{\partial\varphi\over\partial r}\right)+{\partial^2\varphi\over\partial x^2}=0.$$(4)

Стандартный метод решения таких уравнений — метод разделения переменных, он же метод Фурье. Искомая функция ищется в виде суммы (конечной, счетной или интеграла) произведений функций, в которых каждый сомножитель зависит только от своей переменной:

$$\varphi(x,r)=\Sigma_kX_k(x)R_k(r).$$

Мы хотим, чтобы (4) выполнялось не только для всей суммы целиком, но и для каждого элемента $$X_k(x)R_k(r)$$. Подставляем его в (4) и получаем:

$${1\over rR_k}{\partial\over\partial r}(rR_k')=-{1\over X_k}X_k''=-\lambda_k.$$

После такой подстановки получилось представить равенство так, что левая его часть зависит только от координаты r, а правая — только от координаты x. Равенство возможно, только если никакой зависимости нет, то есть и правая, и левая часть равны некоторой константе $$\lambda_k$$. Дальше, в зависимости от вида граничных условий, выбирается одно из двух получившихся дифференциальных уравнений

$$\left\{ \begin{array}{l} R_k'+rR_k''+\lambda_krR_k=0,\\ X_k''-\lambda_kX_k=0,\end{array} $$

и исследуется задача Штурма — Лиувилля: при каких $$\lambda_k$$ с учетом граничных условий у этого дифференциального уравнения возможны решения. Наконец, для этих $$\lambda_k$$ решается оставшееся дифференциальное уравнение и ответ обычно записывается в виде ряда по собственным функциям оператора Штурма — Лиувилля.

Проделать эту процедуру в нашем случае не представляется возможным. Дело в том, что первое уравнение нужно решать на области $$r\in[R,\infty)$$, когда $$x\in\left[-{l/2},{l/2}\right]$$, и на области $$r\in[0,\infty)$$ в противоположном случае. Аналогично со вторым уравнением. Представить решение по всему пространству вне цилиндра в виде одного ряда по собственным функциям какой-либо задачи Штурма — Лиувилля не получается. Есть предложение разбить пространство на несколько частей (как минимум на 3, а то и на 5), решить задачу Дирихле в каждой из них, а затем сшивать эти решения вместе с производными, накладывая дополнительные условия на коэффициенты в рядах и выкидывая слагаемые, которые сшить нельзя. Я не стал заходить в эти дебри, тем более что ответ в виде непонятного ряда по функциям Бесселя вряд ли вызовет известное ощущение завершенности от решения задачи.

Численное решение

Возвращаемся к интегральному уравнению (2) из наивного подхода. Зададимся какими-нибудь конкретными значениями размеров. Пусть длина провода будет 10 сантиметров, а его диаметр — 1 миллиметр. В подходящих единицах измерения можно считать, что $$l=2$$, $$R=0,\!01$$, а коэффициент пропорциональности в уравнении (2) отсутствует. Таким образом, мы будем решать уравнение

$$\int\limits_{-1}^{1}{dx_1\,\sigma_1(x_1)\over\sqrt{1+10000(x-x_1)^2}}+ \int\limits_{0}^{0,01}r\,dr\,\sigma_2(r)\left({1 \over\sqrt{r^2+\left(x-1\right)^2}} -{1\over\sqrt{r^2+\left(x+1\right)^2}}\right) =x.$$

Приближение к его решению можно искать не на всех функциях, а на определенном классе функций, например, на нескольких первых слагаемых разложения в степенной ряд. Отклонение получающейся функции $$\widetilde{\varphi}_a(x)$$ от правой части будем оценивать как интеграл от квадрата разности, и будем подбирать параметры функций a, добиваясь минимума этого интеграла:

$$f(a)=\int\limits_{-1}^{1}\left(\widetilde{\varphi}_a(x)-x\right)^2dx\to \text{min}.$$

Как обычно, решение попробовал найти в Maple. У меня не получилось заставить его минимизировать такой интеграл, зависящий от набора параметров. Поэтому я оставлял только один параметр, заменяя остальные их текущими значениями, строил график по этому параметру и определял его текущее значение в минимуме. Фактически выполнял вручную итерации из метода координатного спуска для функции $$f(a)$$ такого типа:

f := a -> int((
   int((11.485*s + 0.584*s^3 + 0.883*s^5 + 0.587*s^7 + 0.2*s^9 + 3.57*s^11)/
      sqrt(1 + 10000*(x - s)^2), s = -1 .. 1, numeric) +
   int((5.01 + 5.46*10^2*r + 5.71*10^5*r^2 + 3.62*10^6*r^3 + 42.35*10^8*r^4 + a*r^5)*
      r*(1/sqrt(r^2 + (1 - x)^2) - 1/sqrt(r^2 + (x + 1)^2)), r = 0 .. 0.01, numeric)
- x)^2, x = -1 .. 1, numeric)

Здесь все интегралы отмечены как «numeric», чтобы Maple не пытался вычислить их аналитически. В моем случае попытка аналитического вычисления существенно замедляла работу, так что я не мог дождаться результата. Потенциал на оси для моего приближения на глаз отличается от прямой только у краев:

График отклонения от прямой (интеграл от квадрата этой функции я минимизировал, здесь масштаб по осям разный):

Можно также нарисовать графики плотностей на основаниях и на боковой поверхности:

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

Нарисуем сечения эквипотенциальных поверхностей:

Рассмотрим поближе край проводника:

На полученный потенциал можно наложить внешнее электрическое поле и проверить, какая будет поверхность нулевого потенциала. Для правильного решения она должна совпадать с цилиндрической поверхностью проводника. В нашем случае у его краев (от 0,7 до 1) наблюдаются заметные утолщения, наглядно показывающие степень полученного приближения:

Вывод

Мы пытались решить две близких задачи: одна об электрическом поле внутри и снаружи провода с током, вторая о разделении зарядов в проводнике во внешнем электрическом поле. Аналитические методы не привели к успеху. Пришлось искать приближенное численное решение в Maple и использовать встроенные инструменты визуализации решения.

Из этого мини-исследования на третьем курсе получилась бы хорошая курсовая работа. Преподаватели урматов и вычматов были бы довольны.

Брахистохрона под землей

Мотивация

В сборниках задач по физике часто встречается известная задача о свободном падении тела сквозь прямой тоннель, проходящий через центр Земли и соединяющий диаметрально противоположные точки. Для решения нужно знать, что сила притяжения к центру Земли в таком тоннеле уменьшается линейно до нуля, и тело, упавшее в такой тоннель, будет совершать гармонические колебания. Время движения составляет половину периода и для модели однородной Земли составляет 42 минуты. Более того, это время не меняется для любого прямого тоннеля, идущего по хорде (не проходящего через центр), если трением можно пренебречь.

Также в популярных книгах и других источниках есть задача о брахистохроне — кривой скорейшего спуска. В ней требуется найти форму желоба, проложенного между двумя фиксированными точками A и B, чтобы время скатывания тела из A в B было наименьшим. В однородном гравитационном поле брахистохроной является дуга циклоиды.

Вполне естественным кажется желание скрестить эти две задачи и выяснить, какой формы нужно проложить тоннель под землей, чтобы в идеальной ситуации без трения между точками A и B на поверхности (скажем, между двумя городами) поезд проезжал за наименьшее время. Эта новая задача имеет аналитическое решение. Её ответом является гипоциклоида — кривая, которую описывают точки окружности радиуса $$a$$, катящейся без проскальзывания внутри другой окружности радиуса $$b$$. Вот как записывается параметрическое уравнение гипоциклоиды и выглядит ее чертеж:

$$\left\{\begin{array}{lr} x=(b-a)\cos \theta+a\cos(b-a)\theta,\\ y=(b-a)\sin\theta-a\sin(b-a)\theta. \end{array}\right.$$

$$\begin{tikzpicture} \def\clr{black} \def\a{1} \def\b{5} \newcommand{\xt}[1]{(\b-\a)*cos(#1)+\a*cos((\b-\a)*#1/\a} \newcommand{\yt}[1]{(\b-\a)*sin(#1)-\a*sin((\b-\a)*#1/\a} \draw[cyan,very thin] (-\b-1,-\b-1) grid (\b+1,\b+1); \draw[->] (-\b-1,0) -- (\b+1,0); \draw[->] (0,-\b-1) -- (0,\b+1); \draw[\clr,thick] (0,0) circle (\b); \draw[\clr,dashed,very thin] (0,0) circle (\b-\a); \draw[line width=2pt,orange!80!red] plot[samples=60,domain=0:\a*360,smooth,variable=\t] ({\xt{\t}},{\yt{\t}}); \def\t0{40} \draw[\clr!50!black] (\t0:\b-\a) circle (\a); \draw[purple,fill] ({\xt{\t0}},{\yt{\t0}}) circle (2pt) -- (\t0:\b-\a) circle (1pt) node [midway, sloped, above] {\scriptsize $a$} -- (0,0) circle (1pt) node [midway, sloped, above] {\scriptsize $b-a$} node [below right] {$O$}; \node[\clr,fill=white,text width=1cm,align=center] at (-\b,\b) {$a=\a$ $b=\b$}; \end{tikzpicture}$$

Я задумался об этой задаче в старших классах или на первом курсе института, но тогда, разумеется, у меня не хватало знаний для решения в аналитическом виде. Я вернулся к задаче на четвертом курсе и смог довести вычисления до конца, не обращаясь к источникам, но и не без помощи Maple. Эти вычисления были одними из самых сложных среди всех задач с явным аналитическим ответом, которые я решал.

Физическая сторона задачи

$$\begin{tikzpicture} \def\a{1} \def\b{5} \draw ([shift=(-10:\b)]0) arc (-10:90:\b); \draw[-stealth] (\b,0) node[right]{$A$} -- node[pos=0.92,above,inner sep=2] {$\varphi$} (0,0) -- (\b*0.35,\b*0.6) node[below,pos=0.9]{$\vec{r}$} ; \node[above] at (\b*0.32,\b*0.95) {$B$}; \draw[line width=1pt,orange!80!red] plot[samples=12,domain=0:72,smooth,variable=\t] ({(\b-\a)*cos(\t)+\a*cos((\b-\a)*\t/\a},{(\b-\a)*sin(\t)-\a*sin((\b-\a)*\t/\a}); \end{tikzpicture}$$

Движение поезда по подземному тоннелю будем рассматривать в полярных координатах. Считаем потенциал внутри Земли осцилляторным: $$U\sim r^2$$. Запишем закон сохранения энергии с учетом нулевой скорости поезда на поверхности:

$${mv^2\over 2}+{m\omega^2r^2\over 2}={m\omega^2r_0^2\over 2},$$(1)

где $$r_0$$ — радиус Земли, $$\omega=2\pi/T$$ — круговая частота колебаний, соответствующая периоду в 84 минуты. Время движения через тоннель $$\inline t=\int{dl\over v}$$. Выражаем скорость $$\inline v=\omega\sqrt{r_0^2-r^2}$$ из (1) и для времени движения поезда через тоннель получаем следующее выражение:

$$t=\int{dl\over v}={1\over\omega}\int{\sqrt{dr^2+r^2d\varphi^2}\over\sqrt{r_0^2-r^2}}={1\over\omega}\int{\sqrt{r'^2+r^2}\over\sqrt{r_0^2-r^2}}d\varphi,$$

Здесь мы выразили элемент длины пути через полярные координаты. Таким образом, задача свелась к поиску функции $$r(\varphi)$$ с фиксированным значением $$r(\varphi_A)=r(\varphi_B)=r_0$$ на концах отрезка, для которой функционал

$$\omega t=\int\limits_{\varphi_A}^{\varphi_B}\sqrt{{r'^2+r^2}\over{r_0^2-r^2}}d\varphi$$(2)

принимает наименьшее значение.

Математическая сторона задачи

Задача по минимизации интеграла (2) на множестве достаточно хороших с точки зрения физика функций (скажем, дифференцируемых сколько нужно раз) — типовая задача вариационного исчисления. Заметим, что подынтегральное выражение в (2) можно представить в виде функциональной зависимости от $$r$$ и ее производной:

$${\cal L}(r,r')=\sqrt{{r' ^2+r^2}\over{r_0^2-r^2}}$$(3)

Из курса дифференциальных уравнений известно, что экстремальные значения (2) нужно искать на решениях дифференциального уравнения Эйлера — Лагранжа:

$${\partial{\cal L}\over\partial r}-{d\over d\varphi}{\partial{\cal L}\over\partial r'}=0.$$

Если вы вооружитесь бумагой и ручкой и попробуете подставить сюда (3), то быстро заметите сложность получившегося дифференциального уравнения со второй производной и нагромождением корней и осознаете тупиковость этого подхода. В системах компьютерной алгебры есть встроенные пакеты для решения вариационных задач. Вот пример для Maple, где вы видите трехэтажное дифференциальное уравнение:

Кроме того, Maple заботливо подсказывает, что у получившегося дифференциального уравнения есть первый интеграл. И тут вы вспоминаете, что на курсах теоретической механики и дифференциальных уравнений всё-таки рассказывают некоторые полезные вещи. В частности, у уравнений Эйлера — Лагранжа есть интегралы движения. В нашем случае интеграл движения имеет вид

$${\cal L}-r'{\partial{\cal L}\over\partial r'}=const.$$

Если вам проще воспринимать физику, а не математику, вы можете представить некоторую систему, описываемую функцией Лагранжа (3). Движение во «времени» $$\varphi$$ от «момента» $$\varphi_A$$ к $$\varphi_B$$ будет происходить по такой траектории $$r(\varphi)$$, на которой «действие» (2) примет экстремальное значение. Так как функция Лагранжа $$\cal L$$ не зависит от «времени» $$\varphi$$, то у системы есть сохраняющаяся величина — «энергия». Первый интеграл выше как раз и дает величину этой «энергии».

Выполним дифференцирование:

$$k={\cal L}-r'{\partial{\cal L}\over\partial r'}=\sqrt{{r' ^2+r^2}\over{r_0^2-r^2}} -r'{r'\over\sqrt{r_0^2-r^2}\sqrt{r'^2+r^2}}={r^2\over\sqrt{r_0^2-r^2}\sqrt{r'^2+r^2}}.$$

Мы пришли к дифференциальному уравнению первого порядка $$\inline r^2=k\sqrt{r'^2+r^2}\sqrt{r_0^2-r^2}$$, в котором разделяются переменные и получается следующий интеграл:

$$\varphi=\int{dr\over\sqrt{\cfrac{r^4}{k^2(r_0^2-r^2)}-r^2}}.$$

Его можно вычислить аналитически. Например, Maple выдает такой результат:

Чтобы доказать, что это выражение описывает гипоциклоиду, нужно взять её параметрическое уравнение и проделать достаточно громоздкие преобразования обратных тригонометрических функций, которые я не буду сейчас приводить.

В интернете опять кто-то неправ, или учимся избегать ошибок

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

Я предположил, что это чья-то студенческая работа с не очень высокими требованиями. Решил подробнее узнать об авторе, Аманде Максхэм, и нашел заметку в ее блоге как раз об этой статье. Она пишет, что эта статья выдается на первой странице в гугле по запросу «gravity train». Раз так, то тем более нужно разобраться, скрывается ли за нестандартными вычислениями какой-то хитрый прием, или это просто ошибка. Причем моя цель не в том, чтобы показать, что в интернете опять кто-то неправ, а в том, чтобы научиться отличать правильный способ рассуждения от неправильного.

Вот ключевой момент статьи, в котором делается попытка доказать, что гипоциклоида — искомое решение:

Вопросы начинаются с формулы (19), в которой пропущен дифференциал, и поэтому не совсем понятно, по какому параметру дальше берутся производные. Эти же производные сохраняются вплоть до (22), куда подставляются $$x(t)$$ и $$y(t)$$ из (24) и (25). Но параметр $$t$$ в (24) и (25) не может быть временем $$t_\text{физ}$$, так как он является аргументом тригонометрических функций и должен быть безразмерным. Получается, это некоторый параметр, задающий положение точки на траектории, но не являющийся временем.

(Попутно возникает мини-вопрос о том, откуда взялась разность $$x'^2-y'^2$$ вместо соответствующей суммы в правых частях (20) и (21), но эта опечатка в четырех местах не распространяется на дальнейшие рассуждения, и мы к ней придираться не будем.)

Еще возникает вопрос о степенях свободы. В уравнениях (19) и (22) неизвестные величины — $$(x, y, t)$$. Таким образом, эти уравнения содержат лишнюю степень свободы по сравнению с неизвестными $$(r, \varphi)$$ из нашего рассмотрения (и из предыдущего раздела работы Аманды). Эта избыточность мешает корректному применению формализма Лагранжа — Эйлера. Какие признаки этого мы видим?

1. (22) — не единственное возможное следствие из (20) и (21). Если поделить (20) на (21), получим, что $$(y'/x')^2=(dy/dx)^2=const$$, а это есть уравнение, описывающее не гипоциклоиду, а прямую траекторию. Почему это следствие из (20) и (21) менее правильное, чем (22)?

2. (22) с точностью до константы $$C$$ по форме совпадает с законом сохранения энергии, с которого начиналось решение. Действительно, выражение в левой части напоминает квадрат скорости, а в правой — разницу квадратичных потенциалов, то есть изменение потенциальной энергии. Присутствие константы $$C$$ объясняется тем, что производные в (22) берутся не по физическому времени $$t_\text{физ}$$, а по другому параметру $$t$$, который в $$C$$ раз меньше: $$t_\text{физ}=Ct$$. Если бы связь $$t_\text{физ}=Ct$$ нарушилась, то (22) противоречило бы закону сохранения энергии. Таким образом, (22) можно получить без применения лагранжева формализма, просто напрямую из закона сохранения энергии с помощью замены $$t_\text{физ}=Ct$$. Следовательно, (22) не может иметь большего физического содержания, чем закон сохранения энергии, и не несет информацию о траектории, минимизирующей время.

3. (24) и (25) формально являются решением (22), так как зануляют его при выполнении (26). Но они не являются единственным решением. Фактически, любое физически возможное движение из-за сохранения энергии будет удовлетворять уравнению (22). Важно лишь выбрать параметризацию этого движения так, чтобы физическое время было пропорционально параметру. Возьмем для примера движение по хорде $$x(t)=A$$, $$y(t)=B\cos t$$, где $$\inline A^2+B^2=R^2$$, подставим в (22) и при должном выборе константы $$C$$ (то есть при выборе правильного движения во времени вдоль хорды) получим тождество:

$$RB^2\sin^2 t=gC^2(R^2-A^2-B^2\cos^2 t)=gC^2B^2\sin^2 t.$$

Таким образом, осцилляторное движение по тоннелю в виде прямой хорды также является решением (22). Но оно отнюдь не минимизирует функционал (19) для общего времени движения между двумя точками.

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

Я оставил комментарий в блоге Аманды с вопросами. Но никакой реакции не последовало.

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

Добавлено 13.10.2023: я нашел у себя в архиве файлов сохраненную в 2008 году статью о брахистохроне, и это не работа Аманды. Автор не указан, статья располагалась по этой ссылке. Ход решения в этих статьях одинаков, но видно, что написаны они по-разному, и, похоже, разными авторами. «Опечаток» в этой статье меньше, но иногда дифференциал под интегралом тоже пропадает. Разумеется, критика идеи решения относится в равной мере и к этой статье.

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

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

Доказательство теоремы. Из следствия 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$$

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

Условие

Пусть заданы n положительных чисел $$w_1$$, $$w_2$$, … $$w_n$$. Для каждого из них выберем значение $$x_i$$ случайной величины, равномерно распределенной на единичном интервале (0, 1). Существует ли функция $$f_w(x)$$, такая что максимальное значение этой функции $$\inline\max_{i=1,2,...n}\left\{f_{w_i}(x_i)\right\}$$ достигается на k-той выбранной паре $$(w_k, x_k)$$ с вероятностью, пропорциональной $$w_k$$?

Мотивация

Задача возникла из следующей программистской проблемы. Пусть в базе данных есть таблица с колонкой весов w. Нужно выбрать из этой таблицы случайную строку с вероятностью, пропорциональной значению веса w.

Можно было бы провести одно испытание, выбрав значение случайной величины $$x$$, и взять среди сумм $$w_1_$$, $$w_1 + w_2$$, $$w_1 + w_2 + w_3$$, … первую, превосходящую $$x(w_1 + w_2 + ... + w_n)$$. Но такой перебор сделать сложнее в синтаксисе SQL. Проще отсортировать таблицу по некоторой функции от веса и случайного числа:

SELECT * FROM table ORDER BY f(w, random()) DESC LIMIT 1

Какую функцию нужно применить к весу и случайному числу, чтобы значение этой функции на некоторой строке оказалось наибольшим с вероятностью, пропорциональной весу?

Решение

Допустим, что функция $$f_w(x)$$ существует. Пусть в первом выборе случайная величина приняла значение $$x_1$$. Вычислим, с какой вероятностью значение $$f_{w_1}(x_1)$$ будет наибольшим. Нам нужно взять меру множества значений $$x_i$$, на котором выполняется система неравенств:

$$ \begin{equation*} \begin{cases} f_{w_1}(x_1) > f_{w_2}(x_2),\\ f_{w_1}(x_1) > f_{w_3}(x_3),\\ \cdots \end{cases} \end{equation*} $$(1)

Предполагаем, что $$f_w(x)$$ непрерывна и монотонно возрастает по $$x$$. Тогда существует обратная функция $$f^{-1}_w(y)$$. Чтобы упростить рассмотрение на границах, предположим, что $$f_w(x)$$ принимает одинаковые значения на концах отрезка для всех значений параметра:

$$ f_w(0) = a,\quad f_w(1) = b. $$(2)

Тогда решением системы (1) будет множество

$$0<x_i<f^{-1}_{w_i}\left(f_{w_1}(x_1)\right),\quad i>1.$$

Меру этого множества нужно проинтегрировать по всем значениям $$x_1$$, чтобы вычислить вероятность получения максимального значения в первом выборе. С другой стороны, эта вероятность нормирована на 1 и по условию пропорциональна $$w_1$$. Выводим следующее ограничение на функцию $$f_w(x)$$ для произвольных значений $$w_i$$:

$$ \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}. $$(3)

Воспользуемся некоторыми эвристическими соображениями, которые позволяют угадать вид нашей функции. В интеграле можно перейти к новой переменной $$s=f_{w_1}(x_1)$$. Тогда подынтегральное выражение есть произведение величин $$f^{-1}_{w_2}(s)\cdot f^{-1}_{w_3}(s)\cdot\ldots\cdot f^{-1}_{w_n}(s)$$, а соответствующие веса в правой части входят только в виде суммы $$w_2+w_3+\ldots+w_n$$. Логично предположить, что обратная функция обладает показательным свойством по параметру:

$$f^{-1}_{w_2}(s)\cdot f^{-1}_{w_3}(s)\cdot\ldots\cdot f^{-1}_{w_n}(s) =f^{-1}_{w_2+w_3+\ldots+w_n}(s).$$(4)

Если обратная функция $$f^{-1}_w(y)$$ еще и непрерывна по этому параметру $$w$$, она имеет следующий вид: $$x=f^{-1}_w(y)=(g(y))^w$$, где $$g(y)$$ — некоторая новая монотонно возрастающая непрерывная функция. Отсюда следует, что прямая функция $$y=f_w(x)=g^{-1}(x^{1/w})$$.

Подставим полученный вид функций в интеграл из (3):

$$ \begin{align*} P_1&=\int\limits_0^1dx_1\,\left(g\left(g^{-1}(x_1^{1/w_1})\right)\right)^{w_2}\cdot \left(g\left(g^{-1}(x_1^{1/w_1})\right)\right)^{w_3}\cdot\ldots=\\ &=\int\limits_0^1dx_1\,\left(x_1^{1/w_1}\right)^{w_2+w_3+\ldots}= {1\over 1 +{w_2+w_3+\ldots\over w_1}}x_1^{1 +{w_2+w_3+\ldots\over w_1}}\Biggr|_0^1= {w_1\over w_1+w_2+\ldots+w_n}. \end{align*} $$

Таким образом, подстановка $$f_w(x)=g^{-1}(x^{1/w})$$ обращает уравнение (3) в тождество.

Вывод

Функция $$f_w(x)=x^{1/w}$$, а также ее композиция с любой монотонной функцией подходят для выбора из вариантов с заданными весами с помощью описанного в условии способа.

Обсудим единственность этого решения. Помимо естественного требования непрерывности и монотонности, мы наложили дополнительные ограничения (2) и (4). В этих предположениях решение единственно. В следующий раз мы рассмотрим вопрос единственности подробнее, а именно, появляются ли другие решения, если не требовать выполнения (2) и (4), а также можно ли вывести (2) и (4) непосредственно из условия или из более сильных ограничений на искомую функцию вроде дифференцируемости.

туда →