Powszechnie wiadomo, że jeśli wrzucisz n piłek do n pojemników, najprawdopodobniej w najbardziej załadowanym pojemniku będą znajdować się kulki . Ogólnie można zapytać o piłek w pojemnikach. Artykuł z RANDOM 1998 autorstwa Raaba i Stegera analizuje to szczegółowo, pokazując, że wraz ze wzrostem prawdopodobieństwo gwałtownego przekroczenia wartości oczekiwanej gwałtownie spada. Z grubsza, ustawiając , pokazują, że prawdopodobieństwo zobaczenia więcej niż oznacza.
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.
- Po pierwsze, muszę wiedzieć, które odniesienie do cytowania, i wydaje się, że jest to najnowsza praca nad tym.
- 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).
źródło
Odpowiedzi:
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 = ( mB . Możemy użyć nierówności z powodu Sondow,((b+1)apB=(mB)(1n)B(n−1n)m−B , z wytworzeniempB<((R+1)R+1((b+1)aa)<((b+1)b+1bb)a , gdzier=mpB<((r+1)r+1rr)B(1n)B(n−1n)m−B . Zauważ, że ta granica jest dość ciasna, ponieważ a ( (b+1)ar=mB−1 ((b+1)aa)>14ab((b+1)b+1bb)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 <pB<eB(r+1)ln(r+1)−Brlnr−mlnn+(m−B)ln(n−1) B p≥B=∑mb=Bpb<∑mb=Beb(r+1)ln(r+1)−brlnr−mlnn+(m−b)ln(n−1) . Rearranging the terms, we get
Note the summation above is merely a geometric series, so we can simplify this to give
Now, I take it you care about finding someB such that p≥B<Cn 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
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.
źródło