Forte concentration pour la sélection via un partitionnement aléatoire?

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

• Echantillon des éléments de A , avec remplacement en $n^{3/4}$$A$$B$
• Triez et trouvez le rang | B | ± $B$ élémentsletrde$|B|\pm \sqrt{n}$$l$$r$$B$
• Vérifier que et r sont de part et d'autre de la médiane de A et qu'il y a au plus C $l$$r$$A$ éléments dansAentreletrpour une constante appropriéeC>0. Échouez si cela ne se produit pas.$C\sqrt{n}$$A$$l$$r$$C > 0$
• Sinon, trouvez la médiane en triant les éléments de entre l et $A$$l$$r$

Il n'est pas difficile de voir que cela fonctionne en temps linéaire et qu'il réussit avec une forte probabilité. (Tous les mauvais événements sont des écarts importants par rapport à l'attente d'un binôme.)

Un algorithme alternatif pour le même problème, qui est plus naturel à enseigner aux élèves qui ont vu un tri rapide, est celui décrit ici: Sélection aléatoire

Il est également facile de voir que celui-ci a un temps d'exécution prévu linéaire: disons qu'un "round" est une séquence d'appels récursifs qui se termine lorsque l'on donne un fractionnement 1 / 4-3 / 4, puis observez que la longueur attendue de un tour est au maximum de 2. (Dans le premier tirage d'un tour, la probabilité d'obtenir un bon fractionnement est de 1/2, puis augmente en fait, comme l'algorithme a été décrit de sorte que la longueur du tour est dominée par une variable aléatoire géométrique.)

Alors maintenant, la question:

Est-il possible de montrer que la sélection aléatoire s'exécute en temps linéaire avec une forte probabilité?

$O(\log n)$$k$$2^{-k+1}$$O(n\log\log n)$$1-1/O(\log n)$

C'est un peu insatisfaisant, mais est-ce vraiment la vérité?

$\Theta(n)$$G(1/2)$$p(n) \longrightarrow 0$$\Pr[G(1/2) \geq \log_2 p(n)^{-1}] = p(n)$$\Omega(n \log_2 p(n)^{-1}) = \omega(n)$

$G(1/2)$

$n$