Анализ шаров и бинов в режиме m >> n.

Хорошо известно, что если вы бросите n шаров в n корзин, то в самой загруженной корзине, скорее всего, будет шариков. В общем, можно спросить о шарах в корзинах. В статье из RANDOM 1998, опубликованной Раабом и Стегером, это подробно рассматривается, показывая, что с ростом вероятность того, что даже немного превысит ожидаемое значение быстро уменьшится. Грубо говоря, установив , они показывают, что вероятность увидеть больше, чем составляет . $O(\log n)$ $m > n$ $n$ $m$ $m/n$ $r = m/n$ $r + \sqrt{r\log n}$ $o(1)$

Эта статья появилась в 1998 году, и я не нашел ничего более свежего. Есть ли новые и даже более концентрированные результаты в этом направлении, или есть эвристические / формальные причины подозревать, что это лучшее, что можно получить? Я должен добавить, что в соответствующем документе по варианту с множественным выбором, написанном в соавторстве с Анжеликой Стегер в 2006 году, также нет ссылок на более поздние работы.

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

Во-первых, мне нужно знать, какую ссылку цитировать, и кажется, что это самая последняя работа по этому вопросу.
Во-вторых, это правда, что результат достаточно плотный в диапазоне r = 1. Меня интересует диапазон m >> n, в частности, область, где r может быть poly log n или даже n ^ c. Я пытаюсь вставить этот результат в лемму, которую я доказываю, и конкретное ограничение на r контролирует другие части общего алгоритма. Я думаю (но не уверен), что диапазон r, предоставленный в этой статье, может быть достаточным, но я просто хотел убедиться, что не было более жесткой границы (это дало бы лучший результат).

reference-request pr.probability Суреш Венкат
источник

Я узнал название «проблема занятости» из тега, так что спасибо за размещение учебного вопроса. :)

Tsuyoshi Ito

Глядя на статью Рааба и Стегера, мне трудно понять, каких еще результатов вы бы хотели достичь в этом направлении. Есть ли конкретный вопрос, на который вам нужно знать ответ? Если это так, вы должны спросить об этом, либо здесь, либо в MathOverflow. В частности, если , Рааб и Стегер дают точную границу где - правильная постоянная.

r = m / n

$r=m/n$

r + \sqrt{2 r \log n}

$r + \sqrt{2r \log n}$

2

$2$

Питер Шор

@Peter Я отредактирую вопрос: это верная точка.

Суреш Венкат

Не совсем полный ответ (и не полезная ссылка), а просто расширенный комментарий. Для любого данного бина вероятность того, что в нем будет ровно шаров, будет определяться как . Мы можем использовать неравенство из-за Sondow, , чтобы получить , где . Обратите внимание, что эта граница довольно узкая, так как a . $B$ $p_B = \binom{m}{B} \left(\frac{1}{n}\right)^B \left(\frac{n-1}{n}\right)^{m-B}$ $\binom{(b+1)a}{a}<\left(\frac{(b+1)^{b+1}}{b^b}\right)^a$ $p_B < \left(\frac{(r+1)^{r+1}}{r^r}\right)^B \left(\frac{1}{n}\right)^B \left(\frac{n-1}{n}\right)^{m-B}$ $r=\frac{m}{B}-1$ $\binom{(b+1)a}{a}>\frac{1}{4ab}\left(\frac{(b+1)^{b+1}}{b^b}\right)^a$

Таким образом, мы имеем . Теперь, так как вас интересует вероятность нахождения или более шаров в корзине, мы можем рассмотреть . Переставляя термины, мы получаем $p_B < e^{B(r+1)\ln(r+1) - Br\ln r - m\ln n + (m-B)\ln (n-1)}$ $B$ $p_{\geq B} = \sum_{b=B}^{m} p_b < \sum_{b=B}^{m} e^{b(r+1)\ln(r+1) - br\ln r - m\ln n + (m-b)\ln (n-1)}$

p_{\geq B} < e^{- m \ln \frac{n}{n - 1}} \times e^{B (r + 1) \ln (r + 1) - B r \ln r - B \ln (n - 1)} \sum_{b = 0}^{m - B} e^{b (r + 1) \ln (r + 1) - b r \ln r - b \ln (n - 1)} .

$p_{\geq B} < e^{-m\ln \frac{n}{n-1}} \times e^{B(r+1)\ln(r+1) - Br\ln r - B\ln (n-1)} \sum_{b=0}^{m-B} e^{b(r+1)\ln(r+1) - br\ln r - b\ln (n-1)}.$

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

p_{\geq B} < e^{- m \ln \frac{n}{n - 1}} \times e^{B (r + 1) \ln (r + 1) - B r \ln r - B \ln (n - 1)} \times \frac{1 - {(\frac{(r + 1)^{r + 1}}{r^{r} (n - 1)})}^{m - B + 1}}{1 - (\frac{(r + 1)^{r + 1}}{r^{r} (n - 1)})} .

$p_{\geq B} < e^{-m\ln \frac{n}{n-1}} \times e^{B(r+1)\ln(r+1) - Br\ln r - B\ln (n-1)} \times \frac{1-\left(\frac{(r+1)^{r+1}}{r^r (n-1)}\right)^{m-B+1}}{1-\left(\frac{(r+1)^{r+1}}{r^r (n-1)}\right)}.$

\frac{(r + 1)^{r + 1}}{r^{r} (n - 1)}

$\frac{(r+1)^{r+1}}{r^r (n-1)}$

p_{\geq B} < e^{- m \ln \frac{n}{n - 1}} \times e^{B (r + 1) \ln (r + 1) - B r \ln r - B \ln (n - 1)} \times \frac{1 - {(e^{(r + 1) \ln (r + 1) - r \ln r - \ln (n - 1)})}^{m - B + 1}}{1 - e^{(r + 1) \ln (r + 1) - r \ln r - \ln (n - 1)}},

$p_{\geq B} < e^{-m\ln \frac{n}{n-1}} \times e^{B(r+1)\ln(r+1) - Br\ln r - B\ln (n-1)} \times \frac{1-\left(e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}\right)^{m-B+1}}{1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}},$

p_{\geq B} < \frac{e^{- m \ln \frac{n}{n - 1}} \times (e^{B ((r + 1) \ln (r + 1) - r \ln r - \ln (n - 1))} - e^{(m + 1) ((r + 1) \ln (r + 1) - r \ln r - \ln (n - 1))})}{1 - e^{(r + 1) \ln (r + 1) - r \ln r - \ln (n - 1)}} .

$p_{\geq B} < \frac{e^{-m\ln \frac{n}{n-1}} \times \left(e^{B((r+1)\ln(r+1) - r\ln r - \ln (n-1))} -e^{(m+1)((r+1)\ln (r+1) - r \ln r - \ln(n-1))}\right)}{1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}}.$

Теперь, я так понимаю, вы заботитесь о том, чтобы найти некоторый такой, что для некоторой константы , поскольку это дает полную вероятность того, что любой бин, имеющий или более шаров, будет сверху . Этот критерий выполняется, если взять что может переписать как $B$ $p_{\geq B} < \frac{C}{n}$ $C$ $B$ $C$

\frac{e^{- m \ln \frac{n}{n - 1}} \times (e^{B ((r + 1) \ln (r + 1) - r \ln r - \ln (n - 1))} - e^{(m + 1) ((r + 1) \ln (r + 1) - r \ln r - \ln (n - 1))})}{1 - e^{(r + 1) \ln (r + 1) - r \ln r - \ln (n - 1)}} = \frac{C}{n},

$\frac{e^{-m\ln \frac{n}{n-1}} \times \left(e^{B((r+1)\ln(r+1) - r\ln r - \ln (n-1))} -e^{(m+1)((r+1)\ln (r+1) - r \ln r - \ln(n-1))}\right)}{1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}} = \frac{C}{n},$

B = \frac{\ln (\frac{C}{n} e^{m \ln \frac{n}{n - 1}} (1 - e^{(r + 1) \ln (r + 1) - r \ln r - \ln (n - 1)}) + e^{(m + 1) ((r + 1) \ln (r + 1) - r \ln r - \ln (n - 1))})}{(r + 1) \ln (r + 1) - r \ln r - \ln (n - 1)} .

$B = \frac{\ln\left(\frac{C}{n} e^{m\ln \frac{n}{n-1}} \left(1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}\right) + e^{(m+1)((r+1)\ln (r+1) - r \ln r - \ln(n-1))}\right)}{(r+1)\ln(r+1) - r\ln r - \ln (n-1)}.$

Я не совсем уверен, насколько этот комментарий будет вам полезен (вполне возможно, что я где-то допустил ошибку), но, надеюсь, он может быть полезным.

Джо Фитцсимонс
источник

это довольно круто спасибо за наброски.

Суреш Венкат

@Suresh: рад, что это полезно.

Джо Фицсимонс

Анализ шаров и бинов в режиме m >> n.

Ответы: