Задача о разборчивой невесте

[mihaild]

lel0lel в сообщении #1362595 писал(а):

Не понял о какой перестановке речь.

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

[lel0lel]

Теперь понятно, как-то не додумался сначала. Действительно, есть информация о том, каким по счёту пришёл на собеседование любой участник позиционного рейтинга. Если невеста любит тесты IQ, то, увидев строго возрастающую последовательность, она будет ждать последнего кандидата (а если эта последовательность начнёт нарушаться, может поменять стратегию). Но все же без дополнительной информации сложно это использовать рационально.

[wrest]

Вот тут разбирается оригинальная задача https://www.mccme.ru/mmmf-lectures/book ... ook.25.pdf
С. М. Гусейн-Заде. Разборчивая невеста. — МЦНМО, 2003. — Т. 25. — 20 с. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-076-3.

И кратко написано про другую стратегию -- что делать если цель не лучший жених а попадание в топ-$n$ хотя я не вполне понял, там есть формула для топ-2, формулы для топ-$n$ нет.

Но интересно, что стратегия меняется так: из стоящих в очереди $n$ пропустить сколько-то $a$ первых, затем среди следующих $b$ искать лучшего из предыдущих, а если не найден, то среди оставшихся $n-(a+b)$ искать лучшего или второго по рейтингу.

[grizzly]

wrest в сообщении #1362636 писал(а):

Но интересно, что стратегия меняется так:...

Интересно, какая-то из этих стратегий позволяет достичь большего мат.ожидания при равномерном распределении? (простая стратегия давала 87,7; задача для топ-$k$ выглядит менее естественной для любого $k$, имхо)

[wrest]

grizzly в сообщении #1362643 писал(а):

Интересно, какая-то из этих стратегий позволяет достичь большего мат.ожидания при равномерном распределении?

Я всё ещё думаю, что это существенно зависит от параметров распределения рейтингов (от коэффициентов сдвига и масштаба).
Думаю, что позволяет: если невеста может сделать выбор даже если жених не лучший из предыдущих, то и при пропуске всех женихов кроме последнего и выборе последнего матожидание не будет меньше 50 (при равномерном распределении от 1 до 100). Плюс еще тонкий вопрос про штраф за невыбор.

[mihaild]

wrest в сообщении #1362653 писал(а):

Я всё ещё думаю, что это существенно зависит от параметров распределения рейтингов (от коэффициентов сдвига и масштаба).

Не зависит: максимизация ожидания величины и линейного преобразования от нее (с положительным коэффициентом) - это одно и то же.

[lel0lel]

Приведу алгоритм расчёта мат. ожидания рейтинга жениха для определённой стратегии, в дальнейшем он будет полезен. Когда рассматривал случай трёх кандидатов и стратегию $\left\lbrace{(0),(0,1),(1,1,1)\right\rbrace}$, первое что пришло в голову это посчитать мат. ожидание в лоб: для рейтингов женихов $p_1<p_2< p_3$ составляем 6 возможных перестановок, что соответствует случайному порядку встреч кандидатов с невестой; вероятность каждого варианта 1/6; затем применяем выбранную стратегию к каждому варианту, после чего считаем мат. ожидание финального рейтинга. Но уже в случае четырёх кандидатов такой подход может охладить интерес к задаче. Поэтому нужно найти другой способ расчёта.

Рассмотрим для $n$ кандидатов произвольную стратегию $S$. Для определённости положим, что она начинается следующим образом $\left\lbrace(0),(0,1),(0,0,1),(1,1,0,1),(1,0,0,1,0),\ldots\right\rbrace$. Напомню, что элементы этой последовательности (будем называть их строками) -- это правила принятия-отклонения кандидатов с аналогичными порядковыми номерами прохождения собеседования. Поскольку всё что знаем о рейтингах кандидатов это $p_1<p_2<\ldots<p_n$ (порядок встреч кандидатов с невестой неизвестен), то текущий кандидат с равной вероятностью может занять любое место в порядковом рейтинге, создаваемом невестой. Поэтому вероятность того, что невеста отклонит $m$-ого равна количеству нулей в $m$-ой строке делённому на $m$. Теперь можем посчитать вероятность того, что до него дойдёт очередь и он встретится с невестой. В случае выбранной выше $S$ эти вероятности для первых 5-ти участников соответственно равны: 1,1,1/2,1/3,1/12.

Перейдём к вопросу о вкладе в мат. ожидание рейтинга от $m$-го участника. Предположим, что до него очередь дошла, как посчитать вероятность этого уже знаем. Далее смотрим на единицы в $m$-ой строке (перебрать потребуется все), если единица стоит на $k$-ой позиции ($k<m$), то наш $m$-ый кандидат может "оказаться" этой единицей только в случае если его рейтинг $\pi_m$ принимает одно из следующих значений $p_k,p_{k+1},\ldots,p_{n-(m-k)}$. В более простых словах -- если единичка отстоит от правого и левого краёв строки на некоторое количество позиций, то $m$-ый участник может попасть на это место в рейтинге невесты только если его рейтинг в исходной упорядоченной последовательности рейтингов не стоит к "краям" ближе. Далее комбинаторика: нам нужно посчитать число вариантов составить упорядоченную строку длины $m$ из $n$ различных чисел с условием, что на $k$-ой позиции должно стоять определённое число (любое из $n$, не нарушающее "правило краёв"). В нашем случае $n$ чисел это рейтинги, число на $k$-ой позиции это некоторое $p_s$, здесь $k\leqslant s \leqslant n-(m-k)$. Тогда число вариантов равно $A_{s-1}^{k-1}A_{n-s}^{m-k}$, здесь $A_n^k=\frac{n!}{(n-k)!}$. Учитывая в каких пределах изменяется $s$, получим полное число вариантов при которых $m$-ый кандидат будет выбран невестой благодаря единице на $k$-ой позиции $m$-ой строки стратегии $S$; оно равно соответствующей сумме по $s$. Вероятный вклад от $k$-ой единицы в мат. ожидание имеет вид (пока не учитываем вероятность того, что сработает именно она и дойдёт ли дело до $m$-ой строки):

$$\frac{\sum_{s=k}^{n-(m-k)}A_{s-1}^{k-1}A_{n-s}^{m-k}p_s}{\sum_{s=k}^{n-(m-k)}A_{s-1}^{k-1}A_{n-s}^{m-k}}$$

Вклад в от всей $m$-ой строки равен сумме вкладов от всех её единиц делённой на $m$. Остаётся учесть вероятность, что $m$-ый кандидат поучавствует в собеседовании, обозначим эту вероятность $r_m$, тогда ожидание рейтинга жениха при использовании стратегии $S$:

$$M[S]=\sum\limits_{m=1}^{n}\frac{r_m}{m}\sum\limits_{\text{units of line }m}\frac{\sum_{s=k}^{n-(m-k)}A_{s-1}^{k-1}A_{n-s}^{m-k}p_s}{\sum_{s=k}^{n-(m-k)}A_{s-1}^{k-1}A_{n-s}^{m-k}}$$

Хотя вид у формулы немного пугающий, работать с ней удобно (особенно в некоторых частных случаях). Для наглядности приведу пример расчёта ожидания для случая четырёх кандидатов и стратегии $\left\lbrace(0),(0,1),(0,0,1),(1,1,1,1)\right\rbrace$. Хотя в четвертой строке единиц много, но вклад в мат. ожидание от неё очевиден (так как каждой единице соответствует только один рейтинг), этот вклад равен $1/6(p_1+p_2+p_3+p_4)/4$, множитель 1/6 это $r_4$. Тогда

$$M[S]=\frac{1}{2}\frac{A_1^1\,p_2+A_2^1\,p_3+A_3^1\,p_4}{A_1^1+A_2^1+A_3^1}+\frac{1}{6}\frac{A_2^2\,p_3+A_3^2\,p_4}{A_2^2+A_3^2}+\frac{p_1+p_2+p_3+p_4}{24}.$$

[lel0lel]

Вернусь к задаче о невесте в её исходной (как у ТС) формулировке. И хотя эта задача детально разобрана, но нужно проверить вышенаписанные выкладки и посмотреть не получится ли ещё что-нибудь интересное (обобщения или уточнения).

Итак, выбор стратегий у невесты невелик. Единицы в строках возможны только на последних позициях, так как она ищет лучшего. В этом случае, как раз на это указывал wrest, ей не придётся составлять полный рейтинг прошедших кандидатов, достаточно знать только лучшего из прошедших, а текущего с ним сравнивать. Остаётся узнать какие вариации в стратегии допустимы, чтобы при этом она всё ещё претендовала на оптимальность. Например, может ли быть так, что в оптимальной стратегии строка полностью из нулей расположена между строками в которых единицы на последних позициях присутствуют. Другими словами -- может ли быть так что за $(m-1)$-го и $(m+1)$-го кандидата невеста выйдет, если он окажется лучше всех предыдущих, а вот $m$-го отошьёт в любом случае. Житейская логика подсказывает, что это не будет оптимальной стратегий, если уж невеста на $(m-1)$-ом была готова, то нет причин менжеваться с $m$-ым. Есть этому и строгое доказательство -- нужно из формулы для мат. ожидания жениха выделить вероятность выйти за лучшего (формально её легко получить если рейтинги не лучших сделать нулевыми, а рейтинг лучшего единицей). И применить эту формулу для двух стратегий: первой -- с нулевой строкой между ненулевыми, второй -- заменив нулевую строку на строку с единичкой. Посчитав, получится, что нулевых строк между ненулевыми в оптимальной стратегии быть не должно. Хотя житейская логика и подсказывала правильный ответ, но такое доказательство не лишнее, поскольку есть два конкурирующих фактора в нулевых строках: с одной стороны они не дают никакого вклада в мат. ожидание (и в вероятность выйти за лучшего), но с другой стороны они увеличивают шансы последующих кандидатов. Итак, выяснилось, что оптимальная стратегия может иметь только один вариационный параметр -- это номер строки с которой начинаются строки с единицами. Пусть $S(n,a)$ стратегия для $n$ кандидатов, в которой невеста "уже готова" начиная с кандидата с номером $a$. Тогда, применяя полученную формулу:

$$M=\frac{1}{a}\frac{\sum_{j=0}^{n-a}A_{a-1+j}^{a-1}\,p_{a+j}}{\sum_{j=0}^{n-a}A_{a-1+j}^{a-1}}+\frac{a-1}{a(a+1)}\frac{\sum_{j=0}^{n-a-1}A_{a+j}^{a}\,p_{a+1+j}}{\sum_{j=0}^{n-a-1}A_{a+j}^{a}}+ \frac{a-1}{(a+1)(a+2)} \frac{\sum_{j=0}^{n-a-2}A_{a+1+j}^{a+1}\,p_{a+2+j}}{\sum_{j=0}^{n-a-2}A_{a+1+j}^{a+1}}\ldots$$

Выделяя вероятность лучшего:

$$\omega(p_n|S(n,a))=\frac{1}{a}\frac{A_{n-1}^{a-1}}{\sum_{j=0}^{n-a}A_{a-1+j}^{a-1}}+\frac{a-1}{a(a+1)}\frac{A_{n-1}^{a}}{\sum_{j=0}^{n-a-1}A_{a+j}^{a}}+ \frac{a-1}{(a+1)(a+2)} \frac{A_{n-1}^{a+1}}{\sum_{j=0}^{n-a-2}A_{a+1+j}^{a+1}}\ldots$$

Дальше не получается, нужна помощь. Пробовал поступать так: замена $a=\alpha n$, где $\alpha\in(0,1)$; далее для факториалов асимптотическое поведение при $n\to\infty$. Но как оценивать суммы? Думал перейти к интегралам, но пугает интеграл в знаменателе и гамма-функции под знаком интеграла. Если всё верно, то должно получаться, что уравнение $\frac{\partial\omega}{\partial \alpha}=0$ даёт $\alpha=1/e$. Поначалу предполагал, что удастся получить более точную оценку, зависящую ещё и от $n$.

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

[lel0lel]

Решил в конце-концов "натравить" на это дело компьютер (Wolfram Mathematica). К своему удивлению обнаружил, что суммы в знаменателях вычисляются и имеют удобную форму. Удобно записать исследуемую вероятность выбрать лучшего в виде:

$$\omega(p_n|S(n,a))=(a-1) \sum_{k=0}^{n-a}\frac{1}{(a-1+k)(a+k)}\frac{A_{n-1}^{a-1+k}}{\sum_{i=0}^{n-a+k}A_{a-1+k+i}^{a-1+k}}$$

Суммы в знаменателях вычисляются, получаем:

$$\omega(p_n|S(n,a))=(a-1)\sum_{k=0}^{n-a}\frac{1}{n(a-1+k)}=\frac{(a-1)(\psi(a-1)+\psi(n))}{n},$$

Здесь $\psi(z)=\Gamma'(z)/\Gamma(z)$ полигамма функция. Замена $a=\alpha n$, $\alpha\in(0,1)$. При $n\to \infty$:

$$\omega(p_n|S(n,a))=-\alpha \ln (\alpha)+\frac{3-\alpha +2 \ln(\alpha )}{2n}+O\left(\frac{1}{n^2}\right)+\ctg(\pi \alpha n)\, O\left(\frac{1}{n^2}\right)$$

Котангенс создаёт угрозу, если $\alpha n$ целое, этот случай надо рассмотреть отдельно; впрочем, окончательный ответ останется тем же. Если $\alpha n$ не лежит в малой окрестности целых чисел, тогда уравнение $\frac{\partial \omega}{\partial \alpha}=0$ имеет вид:

$$\frac{2-\alpha}{2\alha n}-\ln (\alpha)=1,$$

его решение при больших $n$, с точностью до членов $1/n$, имеет вид:

$$\alpha=\frac{1}{e}+\frac{2 e-1}{2 e n}$$

[lel0lel]

Самое удивительное, что такого типа задачи -- на нахождение оптимальной стратегии для достижения требуемого в условии
результата, представляют в основном техническую сложность. Алгоритм такой:
1) Выбор класса стратегий, в котором содержится оптимальная; стратегии в этом классе зависят от набора вариационных
параметров. Потребуется доказать, что вне этого класса оптимальная содержаться не может.
Это единственный пункт, где нужно подумать, остальные чисто технические.
2) Использование формулы для финального мат. ожидания и выделение из неё вероятности требуемого события.
Суммы с количествами размещений вычисляются.
3) Нахождение параметров, при которых достигается оптимальная вероятность. В этом пункте можно работать при $n\to\infty$.

[grizzly]

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

В первую очередь я рассматриваю задачу с равномерным распределением рейтинга "женихов" при условии, что мы можем сравнивать каждого с каждым. Нам известно количество попыток (для определённости я беру 100 попыток с рейтингами от 1 до 100). Оказывается, что можно найти стратегию, которая даёт возможность выбрать жениха со средним рейтингом 97 из 100 возможных.

В общих чертах опишу стратегию. Пропускаем 25 женихов и запоминаем несколько лучших из них: с номерами в таблице лучших $N_1,...,N_s$, по убыванию. Среди следующих $k_1$ женихов ищем только самого лучшего (лучшего, чем $N_1$). Само $k_1$ я брал динамически -- 25 по умолчанию плюс столько, сколько женихов попалось по дороге лучше $N_2$, но хуже $N_1$. Среди следующих $k_2$ ищем лучшего, чем $N_2$. Подобным образом действуем на следующих этапах, уменьшая $k_i$. Если до конца никто не выбран, забираем последнего.

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

Не думаю, что существует стратегия существенно лучше этой. В частности, я уверен, что среднее 98 при равномерном распределении достичь невозможно никакой стратегией.

Upd. Чуть упростил алгоритм: избавился от динамического изменения $k_1$, но обновляю массив $N_1,...,N_s$ после каждого следующего жениха. Добился среднего 97,25 и это примерно потолок для такой стратегии. Дальше уже за каждую сотую приходится долго бороться.

[lel0lel]

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

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

lel0lel в сообщении #1363282 писал(а):

$$\frac{2-\alpha}{2\alha n}-\ln (\alpha)=1,$$

должно быть

$$\frac{2-\alpha}{2 n \alpha}-\ln (\alpha)=1$$

Теперь неточное изложение мыслей и ошибка:

lel0lel в сообщении #1363038 писал(а):

Далее комбинаторика: нам нужно посчитать число вариантов составить упорядоченную строку длины $m$ из $n$ различных чисел с условием, что на $k$-ой позиции должно стоять определённое число (любое из $n$, не нарушающее "правило краёв"). В нашем случае $n$ чисел это рейтинги, число на $k$-ой позиции это некоторое $p_s$, здесь $k\leqslant s \leqslant n-(m-k)$. Тогда число вариантов равно $A_{s-1}^{k-1}A_{n-s}^{m-k}$, здесь $A_n^k=\frac{n!}{(n-k)!}$. Учитывая в каких пределах изменяется $s$, получим полное число вариантов при которых $m$-ый кандидат будет выбран невестой благодаря единице на $k$-ой позиции $m$-ой строки стратегии $S$; оно равно соответствующей сумме по $s$.

Корректнее так:

Цитата:

нам нужно посчитать число вариантов составить упорядоченную строку длины $m$, имея для заполнения строки $n$ различных чисел ($n\geqslant m$), при этом на $k$-ой позиции должно стоять определённое число (одно из имеющихся $n$ чисел, не нарушающее "правило краёв").

Это неточность, но есть и ошибка: для упорядоченной строки нужны не размещения, а сочетания. Тем самым все $A$ необходимо заменить на $C$. Хорошая новость в том, что на вычисление вероятности эта досадная ошибка не повлияла, так как соответствующие факториалы в числителе и знаменателе финальной формулы просто сокращаются, но всё же поправить нужно.

$$M[S]=\sum\limits_{m=1}^{n}\frac{r_m}{m}\sum\limits_{\text{units of line }m}\frac{\sum_{s=k}^{n-(m-k)}C_{s-1}^{k-1}C_{n-s}^{m-k}p_s}{\sum_{s=k}^{n-(m-k)}C_{s-1}^{k-1}C_{n-s}^{m-k}}$$

Ещё одна ночная неаккуратность -- использование $s$ как индекса суммирования, и $S$ -- обозначение стратегии.

И замечательное тождество:

$$\sum_{s=k}^{n-(m-k)}C_{s-1}^{k-1}C_{n-s}^{m-k}=C_n^m.$$

Если бы я его знал раньше, было бы не так тяжело)

[lel0lel]

Продолжу вносить правку -- есть места в вышеизложенном, которые её требуют. Заметил, что в формуле для мат. ожидания "подвисает" индекс суммирования $k$, это порядковый номер единиц в $m$-ой строке, но из формулы этого никак понять нельзя. Поэтому ещё раз к финальной формуле. Учитывая тождество приведенное постом выше, можно записать:

$$M[S]=\sum\limits_{m=1}^{n}\frac{r_m}{m}\frac{1}{C_n^m}\sum\limits_{k=1}^{m}S_{m, k}\sum_{j=k}^{n-(m-k)}C_{j-1}^{k-1}C_{n-j}^{m-k}p_j$$

Здесь $S_{m,k}$ это элемент стратегии, находящийся в $m$-ой строке на $k$-ой позиции, это может оказаться ноль или единица. Таким образом, сумма по $k$ пробегает всю $m$-ую строку, но учитываются только вклады от единичек. Так формула смотрится лучше чем раньше.

Далее, я перемудрил с котангенсом -- это из-за пагубной привычки свято доверять мат. пакетам. Если проделать руками, то проблема котангенсов решается. Примерно так: учитывая формулу $\psi (n)=H_{n-1}-\gamma$, вероятность выбрать лучшего можно записать через гармонические числа (они роднее). Имеем (в формуле исправлена ещё одна опечатка -- правильный знак в скобках, конечно, минус):

$$\omega(p_n|S(n,a))=\frac{(a-1)(\psi(n)-\psi(a-1))}{n}=\frac{(a-1)(H_{n-1}-H_{a-2})}{n}.$$

Замена $a=\alpha n$, при $n\to \infty$:

$$\omega(p_n|S(n,a))=-\alpha \ln (\alpha)+\frac{3-\alpha +2 \ln(\alpha )}{2n}+O\left(\frac{1}{n^2}\right)$$

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

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

[lel0lel]

lel0lel в сообщении #1363524 писал(а):

И замечательное тождество:

$$\sum_{s=k}^{n-(m-k)}C_{s-1}^{k-1}C_{n-s}^{m-k}=C_n^m.$$

Это тот случай, когда доказать сложнее, чем понять правильность. Кроме $C_n^m$ получиться ничего не может, так как по смыслу это число способов сформировать упорядоченную строку длины $m$, имея для формирования $n$ различных чисел. Надо было сразу додуматься до этого, но так всегда -- сначала пробираешься окольными путьми.

Чтобы завершить сюжет, разберу вариант задачи про топ-2, она оказалась классненькой. Сначала про переоценку рейтингов невестой. Нужно задаться вопросом: что означают фразы невесты "Хочу только самого лучшего, остальные мне не нужны!" или "Хочу самого лучшего! В крайнем случае второго после него, но в два раза с меньшим желанием чем самого лучшего". Этими фразами невеста присваивает дополнительные рейтинги (или веса) кандидатам в зависимости от их позиций в "истинном" общем рейтинге (который ей и, возможно, никому не известен). Разумно считать, что если она совсем кого-то не хочет это присвоение кандидату веса ноль (хотя "истинный" рейтинг у него может быть каким угодно, даже самым большим), в таком случае веса тех кого она хочет будут положительными и можно соотносить их друг с другом. Итак, слова "Хочу только самого лучшего, остальные мне не нужны!" означают что для рейтингов $p_1<p_2<\ldots<p_n$ соответствующие веса равны $b_1=b_2=\ldots=b_{n-1}=0$, $b_n=1$. Для удобства вес самого желанного будем выбирать равным единице.
Слова "Хочу самого лучшего! В крайнем случае второго после него, но в два раза с меньшим желанием чем самого лучшего" означают что $b_1=b_2=\ldots=b_{n-2}=0$, $b_{n-1}=1/2$, $b_n=1$. А вот пример про невесту, которая любит впадать в крайности: "Только лучшего или худшего -- без разницы!", тогда веса $b_1=b_n=1$, остальные нулевые. Иначе говоря, если невеста изрекла свои пожелания в понятной форме, то имеются $n$ пар $(p_1,b_1), (p_2,b_2),\ldots,(p_n,b_n)$. Первые числа в парах -- это ключи ("истинные" рейтинги), точное значение которых нам не известны (и нет никакой возможности узнать), но есть возможность их сравнивать друг с другом; вторые числа -- веса, напрямую их узнавать не можем (нет такой возможности), но если все $n$ пар отсортировать по возрастанию первых чисел, то получаем "доступ" к весам и узнаём их точные численные значения. Если располагаем только одной парой, то ничего конкретного про эту пару сказать нельзя. Задача советников невесты предложить алгоритм максимизирующий вес жениха (только не тот, что в ньютонах). Замечу, что уважаемый grizzly исследовал вопрос о нахождении стратегии максимизирующей вес жениха для следующего распределения весов: $(p_1,1), (p_2,2),\ldots,(p_{100},100).$

Теперь задача про топ-2 в более общей формулировке, а именно так: "Хочу самого лучшего или второго после него, но второго в $x$ раз с меньшим хотением чем самого лучшего. Остальные не нужны", тогда $(p_1,0), (p_2,0),\ldots,(p_{n-1},1/x),(p_{n},1).$ Вероятно, на текущий момент решена задача для случая $x=1$, т.е. лучший или следующий за ним -- без разницы.
Сначала нужно выбрать класс стратегий, в котором находится оптимальная. Можно показать, что стратегии в этом классе отличаются друг от друга только номерами кандидатов (строк) начиная с которых невеста готова идти за лучшего, идти за второго. Пусть $a$ -- номер строки начиная с которой невеста готова выйти за лучшего (в конце строки появляется единица, все строки за ней также с единицей в конце); $b$ -- номер строки начиная с которой невеста готова идти за второго (на предпоследней позиции этой строки появляется единица, все строки за ней также с единицей на этой позиции). Нужно узнать за кого невеста будет готова выйти раньше, то есть что меньше $a$ или $b$. Это во многом зависит от величины $x$. Если бы $x$ было меньше $1$, то вес второго по лучшести был бы больше чем вес лучшего; при $x$ близком к нулю (вес второго очень большой) стратегия свелась бы к охоте за вторым, в этом случае было бы $b<a$, то есть сначала появляются строки с единицами на предпоследней позиции, затем строки с единицами на двух последних позициях. Пусть $x\geqslant 1$ (жизненный случай -- вес второго не выше веса первого), тогда $a<b$. Требуется пояснение: почему при $x=1$ (это случай равных весов) охота за лучшим должна начаться раньше? Причина такая: единички на последней позиции (если это не последняя строка) способны приводить к выходу замуж как за лучшего, так и за второго по лучшести, а вот единицы на предпоследней способны приводить к выходу замуж только за второго. Итак, при $x\geqslant 1$ в оптимальной стратегии $a<b$. Далее уже техника. Имеем:

$$S(n,a,b)=\lbrace(0),\ldots,(0,\ldots,0,),\overbrace{(0,\ldots,0,1)}^{\text{line } a }, \ldots,(0,\ldots,0,1),\overbrace{(0,\ldots,0,1,1)}^{\text{line } b },\ldots,\overbrace{(0,\ldots,0,1,1)}^{\text{line } n }\rbrace$$

Формула для мат. ожидания веса жениха (она получается из формулы для мат. ожидания рейтинга жениха заменой всех рейтингов на соответствующие веса):

$$M[S]=\sum\limits_{m=1}^{n}\frac{r_m}{m}\frac{1}{C_n^m}\sum\limits_{k=1}^{m}S_{m, k}\sum_{j=k}^{n-(m-k)}C_{j-1}^{k-1}C_{n-j}^{m-k}b_j$$

Применяя её к стратегии (в этом месте нужно сесть с ручкой и бумагой), получим:

$$M[S(n,a,b)]=\sum\limits_{m=a}^{b-1}\frac{r_m}{m\, C_n^m}(C_{n-2}^{m-1}/x+C_{n-1}^{m-1})+\sum\limits_{m=b}^{n}\frac{r_m}{m\, C_n^m}((C_{n-2}^{m-1}+C_{n-2}^{m-2})/x+C_{n-1}^{m-1})$$

Теперь нужно посчитать вероятности "дохождения" до кандидатов $r_m$ $(a \leqslant m \leqslant n)$, как их считать уже обсуждалось, получаем:

$$r_m= \begin{cases} \frac{a-1}{m-1}, &a \leqslant m \leqslant b\\ \frac{(a-1)(b-2)}{(m-1)(m-2)}, &b+1 \leqslant m \leqslant n \end{cases}$$

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

$$M[S(n,a,b)]=\frac{(a-1)(x+1)}{n\, x}\left(H_{b-2}-H_{a-2}+\frac{n+1-b}{n-1}\right)-\frac{(a-1)(b-a)}{n(n-1)x}.$$

Можно заметить, что при $x\to\infty$ (вес второго по лучшести нулевой) и при $b=n+1$ (нет строк с единицами на предпоследней позиции) получается уже знакомая формула. Замены $a=\alpha n$, $b=\beta n$. При $n\to\infty$ имеем:

$$M[S(n,a,b)]=\alpha \left(1-\beta+\ln \frac{\beta }{\alpha } +\frac{1}{x}\left(1+\alpha -2 \beta +\ln \frac{\beta }{\alpha }\right)\right)+O\left(n^{-1}\right).$$

Из уравнения $\frac{\partial M}{\partial \beta}=0$ находим, что $\beta=\frac{1+x}{2+x}$. Уравнение $\frac{\partial M}{\partial \alpha}=0$ имеет вид:

$$2 \alpha -(x+1) \ln \alpha=(x+1)\left(1+ \ln\frac{x+2}{x+1}\right).$$

Если $x=1$, тогда $\alpha\approx 0.347$, $\beta= 2/3$. Это совпадает с ответом в работе

wrest в сообщении #1362636 писал(а):

С. М. Гусейн-Заде. Разборчивая невеста. — МЦНМО, 2003. — Т. 25. — 20 с. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-076-3.

Если $x=2$, тогда $\alpha\approx 0.348$, $\beta =3/4$.
Если $x\to\infty$, тогда $\alpha\to 1/e\approx 0.368$, $\beta \to 1$.

[grizzly]

lel0lel в сообщении #1363524 писал(а):

И замечательное тождество:

$$\sum_{s=k}^{n-(m-k)}C_{s-1}^{k-1}C_{n-s}^{m-k}=C_n^m.$$

Чем-то напоминает свёртку Вандермонда.

$${\displaystyle {m+n \choose r}=\sum _{k=0}^{r}{m \choose k}{n \choose r-k}}$$

Доказывать пока лень, но не удивлюсь, если оно выводится из этого или доказывается как-то аналогично.

lel0lel

(Оффтоп)

Вы задали неслабый уровень рассмотрения вопроса. Я то планировал только поиграться параметрами, не особо напрягаясь :) Но это становится всё интереснее. Попрошу модераторов перенести тему (или её часть) в более подходящий раздел.