Dies ist ein Ableger von diesem StackOverflow Frage .
Angenommen, Sie haben eine feste Anzahl k Ablagemöglichkeiten und Platz für zwei Theken. Sie erhalten n Elemente in zufälliger Reihenfolge (alle Permutationen der n Elemente sind gleich wahrscheinlich). Nach Erhalt jedes Gegenstands können Sie ihn entweder in einem der k (wobei einer der zuvor gespeicherten Werte verworfen wird), oder verwerfen Sie das Element. Sie können auch einen der beiden Zähler inkrementieren oder dekrementieren. Ein verworfenes Element kann nicht wiederhergestellt werden.
Die Fragen lauten
- Mit welcher Strategie lässt sich die Wahrscheinlichkeit maximieren, den exakten Median zu finden?
- Wie hoch ist diese Wahrscheinlichkeit?
Offensichtlich, wenn k > n/2 können wir den Median ermitteln. Im Allgemeinen scheint es, dass dieselbe Strategie, die Anzahl der verworfenen hohen Werte gleich der Anzahl der verworfenen niedrigen Werte zu halten, optimal sein sollte, aber ich bin mir nicht sicher, wie man das beweisen kann oder wie man die Wahrscheinlichkeit herausfindet, dass man den Median findet.
Von Interesse ist auch der Fall, dass wir nicht wissen n sondern kennen die Wahrscheinlichkeitsverteilung von n .
Editar: Gehen Sie zunächst davon aus, dass die Werte eindeutig sind (keine Duplikate). Wenn Sie jedoch auch den nicht eindeutigen Fall lösen können, wäre das beeindruckend.
