Probabilità di trovare la mediana con spazio finito

Question

Questo è uno spin off di questo StackOverflow question.

Si supponga di disporre di un numero fisso k di posizioni di memoria e spazio per due contatori. Riceverai n articoli in ordine casuale (tutte le permutazioni degli articoli n sono ugualmente probabili). Dopo aver ricevuto ciascun articolo, è possibile memorizzarlo in una delle posizioni k (scartando uno dei valori precedentemente memorizzati) oppure eliminare l'elemento. È anche possibile incrementare o decrementare uno dei contatori. Qualsiasi oggetto scartato non può essere recuperato.

Le domande sono

1. Qual è la strategia che massimizza la probabilità di trovare la mediana esatta?
2. Che cos'è questa probabilità?

Ovviamente, se k> n/2, possiamo trovare la mediana. In generale sembra che la stessa strategia di tentare di mantenere il numero di valori alti scartati pari al numero di valori bassi scartati dovrebbe essere ottimale, ma non sono sicuro di come provarlo, né come capire la probabilità che esso trovi la mediana

Anche di interesse è il caso in cui non sappiamo n ma conosciamo la distribuzione di probabilità di n.

Modifica: Supponiamo per ora che i valori siano distinti (nessun duplicato.) Tuttavia, se è possibile risolvere anche il caso non distinto, sarebbe impressionante.

Answer 1

Munro e Paterson hanno studiato essenzialmente questo problema nel loro documento Selection and sorting with limited storage. Mostrano che il tuo algoritmo richiede k = Ω (√n) per avere successo con probabilità costante e che questo è asintoticamente ottimale facendo appello ai risultati di base sulle passeggiate casuali unidimensionali.

Se avessi voluto dimostrare l'ottimalità in assoluto, la prima cosa che vorrei provare sarebbe da considerare un algoritmo arbitrario A e poi paio la sua esecuzione con un algoritmo A' che, la prima volta un discosta dal vostro algoritmo, fa il tuo algoritmo farebbe invece e poi tenterà di seguire A il più vicino possibile.

Answer 2

Un'ipotesi selvaggia: scartare l'elemento più lontano dalla media dei valori attualmente memorizzati.

Il confronto con la mediana corrente non funziona se la distribuzione dei valori è multimodale e prima otteniamo i valori da una modalità non dominante.