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

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 $n$$n$$O(\lg n/\lg \lg n)$$\Omega(\lg n/\lg \lg n)$

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 miejsca$O(\lg n)$
2. Funkcje mieszające może być oceniana w Czas$O(1)$
3. Maksymalne obciążenie wynosi z dużym prawdopodobieństwem.$O(\lg n / \lg \lg n)$

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 $k$$k$$k$

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 bin$O(n^{2/k})$

Czy można to sprowadzić do przy użyciu innych technik?$O(\lg ^c n)$

Najwyraźniej nie. „Quicksort, Largest Bucket i Min-Wise Hashing with Limited Independence”, autor: Mathias Bæk Tejs Knudsen i Morten Stöckel pokazują „ niezależną od rodzinę funkcji, która implikuje rozmiar [najbardziej obciążonego pojemnika] ”.Ω ( n 1 / k$k$$\Omega(n^{1/k})$