Analiza kulek i pojemników w systemie m >> n.

Powszechnie wiadomo, że jeśli wrzucisz n piłek do n pojemników, najprawdopodobniej w najbardziej załadowanym pojemniku będą znajdować się kulki $O(\log n)$ . Ogólnie można zapytać o $m > n$ piłek w $n$ pojemnikach. Artykuł z RANDOM 1998 autorstwa Raaba i Stegera analizuje to szczegółowo, pokazując, że wraz ze wzrostem $m$ prawdopodobieństwo gwałtownego przekroczenia wartości oczekiwanej $m/n$ gwałtownie spada. Z grubsza, ustawiając $r = m/n$ , pokazują, że prawdopodobieństwo zobaczenia więcej niż $r + \sqrt{r\log n}$ oznacza$o(1)$.

Ten artykuł ukazał się w 1998 roku i nie znalazłem nic nowszego. Czy istnieją nowe i jeszcze bardziej skoncentrowane wyniki w tym zakresie, czy też istnieją heurystyczne / formalne powody, by podejrzewać, że jest to najlepszy wynik? Powinienem dodać, że pokrewny artykuł na temat wariantu wielokrotnego wyboru, którego współautorem jest Angelika Steger w 2006 r., Również nie cytuje najnowszych prac.

Aktualizacja : W odpowiedzi na komentarz Petera pozwól mi wyjaśnić rzeczy, które chciałbym wiedzieć. Mam tutaj dwa cele.

1. Po pierwsze, muszę wiedzieć, które odniesienie do cytowania, i wydaje się, że jest to najnowsza praca nad tym.
2. Po drugie, prawdą jest, że wynik jest dość ciasny w zakresie r = 1. Interesuje mnie zakres m >> n, a konkretnie dziedzina, w której r może być pol log n, a nawet n ^ c. Próbuję podzielić ten wynik na lemat, który udowodniłem, a specyficzne ograniczenie r kontroluje inne części ogólnego algorytmu. Myślę (ale nie jestem pewien), że zakres r podany przez ten papier może być wystarczający, ale chciałem tylko upewnić się, że nie ma ściślejszego ograniczenia (to dałoby lepszy wynik).

Nie do końca pełna odpowiedź (ani przydatne odniesienie), ale raczej obszerny komentarz. Dla każdego danego bin prawdopodobieństwo posiadania dokładnie kulek w bin będzie podane przez p B = ($B$. Możemy użyć nierówności z powodu Sondow,((b+1)$p_B = \binom{m}{B} \left(\frac{1}{n}\right)^B \left(\frac{n-1}{n}\right)^{m-B}$, z wytworzeniempB<((R+1)R+$\binom{(b+1)a}{a}<\left(\frac{(b+1)^{b+1}}{b^b}\right)^a$, gdzier=$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}$. Zauważ, że ta granica jest dość ciasna, ponieważ a ( (b+1)$r=\frac{m}{B}-1$$\binom{(b+1)a}{a}>\frac{1}{4ab}\left(\frac{(b+1)^{b+1}}{b^b}\right)^a$.

Mamy więc . Teraz, ponieważ jesteś zainteresowany prawdopodobieństwem znalezienia B lub więcej piłek w koszu, możemy rozważyć p ≥ B = ∑ m b = B p b$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)}$. Rearranging the terms, we get

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

Note the summation above is merely a geometric series, so we can simplify this to give

$$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)}.$$ If we rewrite $\frac{(r+1)^{r+1}}{r^r (n-1)}$ terms using exponentials, we get $$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)}},$$ which then becomes $$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)}}.$$

Now, I take it you care about finding some $B$ such that $p_{\geq B} < \frac{C}{n}$ for some constant $C$, since this gives the total probability of any bin having $B$ or more balls as bounded from above by $C$. This criteria is satisfied by taking

$$\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},$$ which can be rewritten as $$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)}.$$

I'm not entirely sure how useful this comment will be to you (it's entirely possible I've made a mistake somewhere), but hopefully it can be of some use.