Bälle zufällig, unabhängig über N Kisten verteilt

Question

Aufgabe:

Zeige: Sei N = 2^k mit k ∈ ℕ. Falls N log(N) Bälle zufällig, unabhängig über N Kisten verteilt werden, ist die erwartete maximale Zahl von Bällen in einer Kiste O(log(N)) 

Problem/Ansatz:

(Mit log(N) ist der Log zur Basis 2 gemeint, also log₂(N))

Ich tue mir leider extrem schwer mit dieser Aufgabe. Wenn ich es richtig verstehe, geht es in die Richtung der Kombinatorik (Kombinationen). Also ziehen ohne Zurücklegen. Dafür eignet sich der Binomial Koeffizient, wenn ich mich nicht irre. Damit berechne ich die verschiedenen Möglichkeiten, überhaupt die Bälle entsprechend auf N Kisten zu verteilen. (Richtig bis hier hin?).

Für mein Verständnis habe ich das mal für k=1,2,3,4,5 durchgespielt. Dafür gilt:

k = 1 -> N = 2, also 2 Kisten und 2 Bälle -> 3 Möglichkeiten

k = 2 -> N = 4, also 4 Kisten und 8 Bälle -> 165 Möglichkeiten

k = 3 -> N = 8, also 8 Kisten und 24 Bälle -> 2629575 Möglichkeiten

k = 4 -> N = 16, also 16 Kisten und 64 Bälle -> ..

k = 5 -> N = 32, also 32 Kisten und 160 Bälle -> ..

usw.

Jetzt hab ich mir versucht das ganze in einem Baumdiagram vorzustellen und für k = 1 war das ja noch kein Problem. Aber das hat mir nicht weitergeholfen.

Jetzt stehe ich allerdings auf dem Schlauch. Es handelt sich ja um die erwartete maximale Zahl von Bällen in einer Kiste, also der Erwartungswert und wie der Übergang zu O(log(N)) ist. Über Tipps/Anregungen/Lösungsansätzen oder Verständnis-Unterstützungen würde ich mich freuen.

Answer 1

Die Zufallsvariable X ist binomialverteilt mit einer Wahrscheinlichkeit von p. Bei n Versuchen hat X die höchste Wahrscheinlichkeit bei p(X = E(X)) mit E(X) = n*p.

Im konkreten Fall entspricht die erwartete maximale Zahl von Bällen in einer Kiste somit n*p.

Wegen p=1/N und n = N*log(N) also bei log(N) Bällen.

Wegen N = 2^k folgt log₂(N) = k € N, somit ist das Ergebnis log(N) sogar exakt, und die Notation O(log(N)) überflüssig.