Se cammino attraverso la lista ed elimino ogni elemento fuori ordine che incontro, in media quanti elementi saranno lasciati?

Question

Ho un elenco uniformemente casuale a caso di lunghezza $ N $ . Cammino attraverso la lista element-by-element ed elimina un elemento se è fuori ordine (rispetto ai precedenti elementi in ordine dell'elenco). Quello che mi è lasciato è una lista più breve che è garantita per essere in ordine.

Esempio: gli elementi stellati di questo elenco saranno cancellati durante la passeggiata attraverso.

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

La mia domanda è: in media, quale sarà la lunghezza della lista rimanente? E c'è qualche forma semplice / ovvia della distribuzione di questo?

E come un follow-up: se ci ha usato questo per un algoritmo di ordinamento (chiamato Drop Sort), quale sarebbe il momento giusto? Essere chiari, l'algoritmo sarebbe qualcosa del genere: $$ \ textit {dropsort} (\ text {list})=text {merge} (\ text {list}, \ text {dropsort} (\ testo {list respinto} )) $$

Questa domanda è stata ispirata da questo R / PROGRAMMERMERMERHUMOR POST .

Answer 1

È possibile calcolare la media utilizzando la linearità delle aspettative.

Lasciare la variabile casuale $ x $ denota il numero di elementi che vengono mantenuti. Let $ x_i $ Sii un indicatore R.V. cioè 1 se la $ i $ l'elemento è mantenuto o 0 altrimenti. Quindi $ x= x_1 + \ Dots + x_n $ , quindi

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

Ora la classe $ I $ L'elemento è mantenuto se e solo se è il numero più grande tra il primo $ i $ elementi nell'elenco. Pertanto, $ \ PR [x_i= 1]=frac {1} {i} $ , quindi

$$ \ mathbb {e} [x]=frac {1} {1} + \ frac {1} {2} + \ Dots + \ frac {1} {n} \ circa \ log (n) + \ gamma $$

In altre parole, la lunghezza media della lista rimanente è $ o (\ log n) $ .

Non so cosa sia la distribuzione.

Come euristico, il tempo di esecuzione previsto del tipo di goccia soddisferà una ricorrenza come $ t (n) \ circa t (n- \ log (n)) + o ( n) $ , che corrisponde a $ o \ sinistra (\ frac {n ^ 2} {\ log n} \ destra) $ tempo. .