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

17

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(logn) . 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+rlogn oznaczao(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).
Suresh Venkat
źródło
3
Nauczyłem się nazwy „problem obłożenia” z tagu, więc dziękuję za przesłanie pytania edukacyjnego. :)
Tsuyoshi Ito
7
Patrząc na artykuł Raaba i Stegera, ciężko mi zrozumieć, jakie dalsze wyniki chciałbyś osiągnąć w tym kierunku. Czy jest jakieś pytanie, na które musisz znać odpowiedź? Jeśli tak, powinieneś o to zapytać tutaj lub na MathOverflow. W szczególności, jeśli , Raab i Steger dają ścisłe ograniczenie r + r=m/n gdzie2jest poprawną stałą. r+2rlogn2
Peter Shor,
@Peter Zredaguję pytanie: to ważny punkt.
Suresh Venkat

Odpowiedzi:

8

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(n1n)mB, z wytworzeniempB<((R+1)R+1((b+1)aa)<((b+1)b+1bb)a, gdzier=mpB<((r+1)r+1rr)B(1n)B(n1n)mB. Zauważ, że ta granica jest dość ciasna, ponieważ a ( (b+1)ar=mB1((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)Brlnrmlnn+(mB)ln(n1)BpB=b=Bmpb<b=Bmeb(r+1)ln(r+1)brlnrmlnn+(mb)ln(n1). Rearranging the terms, we get

pB<emlnnn1×eB(r+1)ln(r+1)BrlnrBln(n1)b=0mBeb(r+1)ln(r+1)brlnrbln(n1).

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

pB<emlnnn1×eB(r+1)ln(r+1)BrlnrBln(n1)×1((r+1)r+1rr(n1))mB+11((r+1)r+1rr(n1)).
If we rewrite (r+1)r+1rr(n1) terms using exponentials, we get
pB<emlnnn1×eB(r+1)ln(r+1)BrlnrBln(n1)×1(e(r+1)ln(r+1)rlnrln(n1))mB+11e(r+1)ln(r+1)rlnrln(n1),
which then becomes
pB<emlnnn1×(eB((r+1)ln(r+1)rlnrln(n1))e(m+1)((r+1)ln(r+1)rlnrln(n1)))1e(r+1)ln(r+1)rlnrln(n1).

Now, I take it you care about finding some B such that pB<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

emlnnn1×(eB((r+1)ln(r+1)rlnrln(n1))e(m+1)((r+1)ln(r+1)rlnrln(n1)))1e(r+1)ln(r+1)rlnrln(n1)=Cn,
which can be rewritten as
B=ln(Cnemlnnn1(1e(r+1)ln(r+1)rlnrln(n1))+e(m+1)((r+1)ln(r+1)rlnrln(n1)))(r+1)ln(r+1)rlnrln(n1).

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.

Joe Fitzsimons
źródło
1
this is pretty awesome. thanks for the outline.
Suresh Venkat
@Suresh: Glad it's useful.
Joe Fitzsimons