concentration forte pour la sélection par répartition aléatoire?

Question

L'algorithme simple, habituel pour trouver l'élément médian dans un tableau $ A $ de nombres $ n $ est:

• Exemple $ n ^ {3/4} éléments de $ de $ A $ avec remplacement dans $ B $
• Trier $ B $ et trouver le $ rang | B | \ pm \ sqrt {n} $ éléments $ l $ et $ r $ de $ B $
• Vérifiez que $ l $ et $ r $ sont sur les côtés opposés de la médiane de $ A $ et qu'il ya au plus $ C \ sqrt {n} $ éléments en $ A $ entre $ l $ et $ r $ pour une constante appropriée $ C> 0 $. Fail si cela ne se produit pas.
• Sinon, trouver la médiane en triant les éléments de $ A $ entre $ l $ et $ r $

Il est pas difficile de voir que cela va dans le temps linéaire et qu'il réussit avec une forte probabilité. (Tous les mauvais événements importants écarts loin de l'attente d'un binomiale.)

Un autre algorithme pour le même problème, ce qui est plus naturel d'enseigner aux étudiants qui ont vu est un peu rapide celui décrit ici: Sélection aléatoire

Il est également facile de voir que celui-ci a linéaire temps d'exécution prévu: dire qu'un « tour » est une séquence d'appels récursifs qui se termine lorsque l'on donne un 1 / 4-3 / 4 split, puis observer que la la durée prévue d'un tour est au plus 2. (Dans le premier tirage d'un tour, la probabilité d'obtenir une bonne répartition est 1/2, puis après en fait augmente, que l'algorithme a été décrit si la longueur ronde est dominée par une géométrique aléatoire variable.)

Alors maintenant la question:

  

Est-il possible de montrer que des pistes de sélection aléatoires dans le temps linéaire avec une forte probabilité?

Nous avons $ O (\ log n) $ tours et chaque tour a une longueur d'au moins $ k $ avec une probabilité d'au plus 2 $ ^ {- k + 1} $, donc une limite union donne que le temps d'exécution est de $ O (n \ log \ log n) $ avec une probabilité 1-1 $ / O (\ log n) $.

Ce genre est de peu satisfaisant, mais est-ce vraiment la vérité?

Answer 1

Il est pas vrai que l'algorithme fonctionne en temps linéaire avec une forte probabilité. En ne considérant que le premier tour, le temps de fonctionnement est au moins $ \ Theta (n) $ fois par G $ (1/2) $ La variable aléatoire. Soit $ p (n) \ longrightarrow 0 $ est la probabilité de défaillance autorisée. Depuis $ \ Pr [G (1/2) \ geq \ log_2 p (n) ^ {- 1}] = p (n) $, la durée est au moins $ \ Omega (n \ log_2 p (n) ^ {-1}) = \ omega (n) $.

(Il y a une tricherie en cause, puisque la longueur du premier tour n'est pas vraiment G (1/2) $. Une analyse plus minutieuse pourrait ou non valider cette réponse.)

Edit: Grubel Rosler prouvé que le nombre prévu de comparaisons divisé par $ n $ tend (dans un sens) à une distribution limite, ce qui est sans bornes. Voir par exemple le document de Grübel « l'algorithme de sélection de Hoare: une approche de la chaîne de Markov »., Qui fait référence à leur papier d'origine