Médiane de la distribution avec contrainte de mémoire

Question

Tâche

Je veux approximatir de la médiane d'une distribution donnée $ d $ que je peux échantillonner de.

Un simple algorithme pour cela, en utilisant N $ N $ échantillons, est:

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

Cependant, je cherche un algorithme que nécessite moins que $ O (n) $ espace

.

.

Idées

J'ai examiné ces algorithmes:

• Médiane des médianes : a besoin $ o (n) $ espace, donc cela ne fonctionne pas pour moi.
• médiane randomisée : il semble que Cela pourrait être facilement généralisé à un algorithme qui utilise $ o (n ^ {3/4}) $ espace.

y a-t-il d'autres algorithmes qui utilisent moins de $ O (n) $ espace qui pourrait résoudre mon problème? En particulier, je pensais qu'il y avait peut-être un algorithme qui utilise $ o (m) $ en générant des lots d'échantillons de $ D $ de taille $ m $ ...

Détails

• Idéalement, je cherche une référence à un algorithme qui inclut également une analyse (probabilité de succès, runtime attendue, etc.).
• En fait, j'ai besoin d'un algorithme pour estimer $ d $ 's $ p $ -ème centile Pour un $ P $ , mais j'espère que la plupart des algorithmes de recherche médiane peuvent être généralisés à cela.
• Je voudrais obtenir la même précision que l'algorithme simple présenté ci-dessus. Une façon d'y parvenir consiste à utiliser un algorithme dont la distribution de sortie est la même que l'algorithme d'échantillon (mais peut-être que le nouvel algorithme peut échouer dans de rares cas)

Answer 1

Bien sûr, vous pouvez certainement y parvenir en utilisant un peu plus de temps d'exécution. Voici une approche conceptuellement simple, qui pourrait ne pas être optimale, mais vous fera commencer et sera probablement assez bonne:

Utilisez une recherche binaire pour trouver une médiane approximative $ M $ . Comment savez-vous si le candidat $ m $ est trop grand ou trop petit? Échantillon $ N '$ TEMPS DE LA DISTRIBUTION, COMPTE combien de fois les échantillons sont $ \ GE M $ et comparez ce nombre à $ n '/ 2 $ . Cela peut être fait avec $ o (1) $ espace.

Puis la question clé devient: comment choisissons-nous $ n '$ , pour contrôler la probabilité d'erreur? Une approche simple est de choisir $ n '$ suffisamment plus gros que $ n $ que la probabilité de L'erreur dans chaque itération de la recherche binaire est $ t $ plus petit que la probabilité d'erreur lors de l'utilisation $ n $ échantillons, où $ t $ est le nombre d'itérations de la recherche binaire nécessaire pour atteindre la précision souhaitée. Ensuite, un syndicat est tenté de s'assurer que cela répondra à vos conditions de précision.

Malheureusement, votre condition de précision est un peu difficile à travailler, lorsque nous ne savons rien de la répartition des données, car la précision de l'échantillon médiane peut être arbitrairement mauvaise. Par exemple, envisagez une distribution qui génère 0 $ avec probabilité $ (1- \ epsilon) / 2 $ et 100 $ avec probabilité $ (1+ \ epsilon) / 2 $ . Ensuite, l'échantillon médiane est à peu près probable d'être 0 ou 100, tandis que la médiane de la distribution est de 100, Donc, l'erreur moyenne de l'échantillon médiane est d'environ 50 (sauf si vous dessinez $ \ gg 1 / \ epsilon ^ 2 $ échantillons). C'est une distribution particulièrement méchante et il sera difficile de travailler avec. Mais si vous supposez que la distribution est approximativement gaussien (disons) avec écart type $ \ sigma $ , puis l'erreur de la médiane de l'échantillon, avec $ N $ échantillons est grossièrement $ 1.25 \ sigma / \ sqrt {n} $ . Ainsi, l'algorithme ci-dessus peut être utilisé là où nous définissons $ t \ environ \ lg (\ sqrt {n} /1.25) $ et nous définissons $ n '\ environ NT ^ 2 $ .

C'est une approche simple. Vous pouvez probablement faire mieux. Vous voudrez peut-être rechercher des algorithmes en streaming pour calculer la médiane, car ils abordent le problème avec lequel vous travaillez: donné un nombre illimité d'échantillons de la distribution, mais seulement une quantité limitée d'espace, quelle est la meilleure estimation que nous puissions obtenir pour la médiane? Par exemple, voici un algorithme simple: la première couche prend à plusieurs reprises trois échantillons et génère la médiane de ces trois; La deuxième couche prend à plusieurs reprises trois nombres de la première couche et génère la médiane de ces trois; etc. Après logarithmiquement nombre de couches, vous obtenez une approximation raisonnable à la médiane. Il y a une littérature entière sur ce sujet et vous devriez être capable de trouver beaucoup plus.