Mediana di distribuzione con vincolo di memoria

Question

attività

Voglio Avvicinamento della mediana di una determinata distribuzione $ d $ che posso campionare da.

Un semplice algoritmo per questo, utilizzando $ N $ campioni, è:

samples = [D.sample() for i in range(n)] # generate n samples from D
sort(samples)
return samples[n/2]

.

Tuttavia, sto cercando un algoritmo che richiede meno di $ o (n) $ spazio .

Idee

Ho esaminato questi algoritmi:

.
• mediana di mediane : ha bisogno di $ o (n) $ spazio, quindi non funziona per me.
• mediano randomizzato : Sembra Questo potrebbe essere facilmente generalizzato a un algoritmo che utilizza $ o (n ^ {3/4}) $ spazio.

Ci sono altri algoritmi che utilizzano meno di $ o (n) $ spazio che potrebbe risolvere il mio problema? In particolare, stavo pensando che ci sia un algoritmo che usa $ o (m) $ spazio generando lotti di campioni da di taglia $ m $ ...

Dettagli

.
• Idealmente, sto cercando un riferimento ad un algoritmo che include anche l'analisi (probabilità di successo, runtime previsto, ecc.).
• In realtà, ho bisogno di un algoritmo per stimare $ d $ 's $ p $ -th percentole Per un dato $ P $ , ma sperando che la maggior parte degli algoritmi di ricerca mediana può essere generalizzata in questo.
• Vorrei ottenere la stessa accuratezza del semplice algoritmo mostrato sopra. Un modo per raggiungere questo obiettivo è utilizzando un algoritmo la cui distribuzione di output è la stessa dell'algoritmo di esempio (ma forse il nuovo algoritmo potrebbe fallire in rari casi)

Answer 1

Sicuro, puoi sicuramente ottenere questo utilizzando un po 'più di tempo di esecuzione. Ecco un approccio concettualmente semplice, che potrebbe non essere ottimale, ma ti farà iniziare ed è probabilmente abbastanza buono:

Utilizzare la ricerca binaria per trovare una mediana approssimativa $ m $ . Come fai a sapere che il candidato $ m $ è troppo grande o troppo piccolo? Esempio di $ n '$ volte dalla distribuzione, conta quante volte i campioni sono $ \ ge m $ e confrontare il conteggio di $ n '/ 2 $ . Questo può essere fatto con $ o (1) $ spazio.

Quindi la domanda chiave diventa: come scegliere $ n '$ , per controllare la probabilità di errore? Un approccio semplice è scegliere $ n '$ per essere sufficientemente più grande di $ N $ che la probabilità di Errore in ciascuna iterazione della ricerca binaria è $ T $ più piccolo della probabilità di errore quando si utilizza $ N $ Campioni, dove $ T $ è il numero di iterazioni della ricerca binaria necessaria per ottenere la precisione desiderata. Quindi, un legato all'Unione garantisce che ciò soddisferà le tue condizioni di precisione.

Sfortunatamente, la tua condizione di accuratezza è un po 'difficile da lavorare, quando non sappiamo nulla della distribuzione dei dati, poiché la precisione della mediana del campione può essere arbitrariamente male. Ad esempio, considera una distribuzione che uscirà $ 0 $ con probabilità $ (1- \ Epsilon) / 2 $ e $ 100 $ con probabilità $ (1+ \ epsilon) / 2 $ . Quindi la mediana campione è ugualmente probabile che sia 0 o 100, mentre la mediana di distribuzione è 100, Quindi l'errore medio della mediana del campione è di circa 50 (a meno che tu non si disegna $ \ gg 1 / \ epsilon ^ 2 $ campioni). Questa è una distribuzione particolarmente cattiva, e sarà difficile da lavorare. Ma se presumi che la distribuzione sia approssimativamente gaussiana (ad esempio) con deviazione standard $ \ sigma $ , quindi l'errore del campione mediano, con $ N $ campioni, è approssimativamente $ 1,25 \ Sigma / \ sqrt {n} $ . Pertanto, l'algoritmo sopra riportato può essere utilizzato dove impostiamo $ t \ circa \ lg (\ sqrt {n} /1.25) $ e abbiamo impostato $ n '\ circa NT ^ 2 $ .

Questo è un approccio semplice. Probabilmente puoi fare meglio. Ti potrebbe piacere guardare gli algoritmi di streaming per il calcolo della mediana, mentre affrontano il problema con cui stai lavorando: dato un numero illimitato di campioni dalla distribuzione, ma solo una quantità limitata di spazio, qual è la migliore stima che possiamo ottenere la mediana? Ad esempio, qui è un semplice algoritmo: il primo strato richiede ripetutamente tre campioni e uscirà la mediana di quei tre; Il secondo strato richiede ripetutamente tre numeri dal primo strato e produce la mediana di questi tre; e così via. Dopo il numero logaritmicamente di strati, ottieni un'approssimazione ragionevole alla mediana. C'è un'intera letteratura su questo argomento, e dovresti essere in grado di trovare molto di più.