Wenn ich durchläufe, und löschen Sie jedes Element, das ich qualperimentiere, wie viele Elemente übrig sind.

Question

Ich habe eine einheitlich zufällig zulässige Liste der Länge $ n $ . Ich gehe durch das Listenelement-by-element und lösche ein Element, falls er nicht mehr bestellt ist (im Vergleich zu den vorherigen Elementen der Liste der Liste). Ich bin noch eine kürzere Liste, die garantiert in Ordnung ist.

Beispiel: Die spielten Elemente dieser Liste würden während des Spaziergangs gelöscht.

[1, 4, 2 *, 3 *, 5, 7, 6 *] -> [1, 4, 5, 7]

Meine Frage ist: Im Durchschnitt, was ist die Länge der verbleibenden Liste? Und gibt es eine einfache / offensichtliche Form der Verteilung davon?

und als Follow-up: Wenn wir dies für einen Sortieralgorithmus (Sortiersalgorithmus (TROPT SORT SORT) verwendet haben), was wäre die Laufzeit? Um klar zu sein, wäre der Algorithmus so etwas: $$ \ textit {Dropsort} (\ Text {list})=textit {Merge} (\ Text {Restliste}, \ textit {dropsort} (\ Text {abgelehnter Liste}) )) $$

Diese Frage wurde von diesem inspiriert von diesem r / programmiererhumor post .

Answer 1

Sie können den Durchschnitt mit einer Linearität der Erwartung berechnen.

Lassen Sie die Zufallsvariable $ x $ die Anzahl der beibehaltenen Elemente bezeichnen. Lassen Sie $ x_i $ ein Indikator R.V. Das ist 1, wenn der $ I $ tiges Element beibehalten oder sonst 0 aufbewahrt wird. Dann $ x= x_1 + \ dots + x_n $ , so

$$ \ mathbb {e} [x]=mathbb {E} [x_1] + \ dots + \ mathbb {e} [x_n]=pr [x_1= 1] + \ dots + \ pr [x_n= 1]. $$

Jetzt ist der $ I $ tiges Element wird beibehalten, wenn und nur, wenn es die größte Zahl zwischen dem ersten $ i ist $ Elemente in der Liste. Daher $ \ PR [x_i= 1]=frac {1} {i} $ , so

$$ \ mathbb {E} [x]=frac {1} {1} + \ frac {1} {2} + \ dots + \ frac {1} {n} \ ca. \ log (n) + \ gamma $$

Mit anderen Worten, die durchschnittliche Länge der verbleibenden Liste ist $ O (\ log n) $ .

Ich weiß nicht, was die Verteilung ist.

als Heuristik, die erwartete Laufzeit der Drop-Sortierung würde ein Wiederauftreten von etwas wie $ t (n) \ ca. t (n- \ log (n)) + o ( n) $ , was dem $ o \ linke (\ frac {n ^ 2} {\ log n} \ rechts) $ Time.