Ile niezależności jest potrzebne do oddzielnego łączenia?

13

Jeśli kulek zostanie rozmieszczonych losowo w koszach równomiernie, w najbardziej obciążonym pojemniku znajdują się kulki z dużym prawdopodobieństwem. W „The Power of Simple Tabulation Hashing” Pătraşcu i Thorup wspominają, że „Chernoff-Hoeffding ogranicza się do aplikacji o ograniczonej niezależności” ( lustro ) pokazuje, że to ograniczenie populacji najbardziej obciążonego pojemnika utrzymuje się również, jeśli kule są rozłożone niezależna funkcja skrótu.n O ( lg n / lg lg n ) Ω ( lg n / lg lg n )nnO(lgn/lglgn)Ω(lgn/lglgn)

W „Balls and Bins: Smaller Hash Families and Faster Evaluation” , Celis i in. zauważ, że nie wiadomo, czy istnieje rodzina funkcji skrótu gdzie

  1. Funkcje skrótu można przedstawić za pomocą bitów miejscaO(lgn)
  2. Funkcje mieszające może być oceniana w CzasO(1)
  3. Maksymalne obciążenie wynosi z dużym prawdopodobieństwem.O(lgn/lglgn)

Jeśli istnieje stała taka, że ​​jakakolwiek rodzina niezależna od wystarcza dla # 3, to wielomianowa konstrukcja rodzin niezależnych od spełniałaby # 1 i # 2.k kkkk

Co bound nie mamy dla najcięższego załadowanego kosza z -independent mieszaja?k

Korzystając z twierdzenia 4.III „Chernoff-Hoeffding bounds ...” i związania związanego, myślę, że mogę uzyskać granicę na wadze najbardziej obciążonego bata binO(n2/k)

Czy można to sprowadzić do przy użyciu innych technik?O(lgcn)

jbapple
źródło

Odpowiedzi: