Jai regardé la conférence du MIT sur la liste de passage. Dans lensemble, je comprends le matériel, mais une chose. Quest-ce que « avec une probabilité élevée »? Je ne comprends vraiment pas du tout. Jai vu les notes de cours mais je ne les ai toujours pas compris.
Ils dit: « Lévénement $ E $ se produit avec une probabilité élevée (whp) si, pour tout $ \ alpha \ geq1 $, il existe un choix approprié de constantes pour lesquelles $ E $ se produit avec une probabilité dau moins $ 1 – O (1 / n ^ \ alpha) $ « .
Quelque chose de algorithmist.com na pas non plus aidé.
Quest-ce que $ \ alpha $ et quest-ce que $ 1 – O (1 / n ^ \ alpha) $? Ne pas comprendre cette chose me rend confus quant à lanalyse du pourquoi « Avec une probabilité élevée, chaque recherche dans une liste de sauts déléments $ n $ coûte $ O (\ lg n) $ ».
Commentaires
- Notez que les algorithmes aléatoires et probabilistes ne sont pas la même chose .
Réponse
Un événement se produit avec une probabilité élevée par rapport à un paramètre $ n $ sil se produit avec une probabilité $ p_n $ et $ \ lim_ {n \ to \ infty} p_n = 1 $. Habituellement, le paramètre $ n $ est clair du contexte. Dans ce cas, par exemple, il sagit probablement du nombre déléments de la liste.
La définition de « avec une forte probabilité » dans les notes de cours est encore plus précise, spécifiant à quelle vitesse $ p_n $ doit converger à $ 1 $: un événement se produit avec une probabilité élevée sil se produit avec une probabilité $ p_n \ geq C / n ^ \ alpha $ pour certains $ C, \ alpha > 0 $. Par exemple, si vous choisissez un nombre aléatoire parmi $ \ {0, \ ldots, n \} $, alors il est différent de zéro avec une probabilité élevée car la probabilité quil soit différent de zéro est de 1 à 1 $ / (n + 1) \ geq 1-1 / n $ (donc dans ce cas $ C = \ alpha = 1 $).
Commentaires
- Le critère de limite est également appelé " presque sûrement ". Jai vu " haute probabilité " utilisé principalement pour faire référence à des probabilités approchant un avec un taux exponentiel.
- Quand je voir " whp " il est généralement synonyme de " presque sûrement ", et quand je lutilise (sans le définir) cest toujours le sens auquel je me réfère. Mais plus généralement " whp " pourrait signifier soit approcher 1, approcher 1 polynomialement rapide, soit approcher 1 exponentiellement rapide. Si vous lutilisez dans lun des derniers sens, assurez-vous de le définir explicitement.
- Vraiment, vous ' appelez $ p_n = 1 – \ frac { 1} {\ log ^ * n} $ " avec une probabilité élevée "? 😉 Mais oui: pour être sûr, définissez ce que vous voulez dire dans votre contexte dans tous les cas.
- Quest-ce quune référence standard (par exemple des manuels) qui définit formellement WHP? Jai essayé décrire un article sur WHP dans wikipedia en.wikipedia.org/wiki/With_high_probability mais il a été suggéré de le supprimer car il ny a pas de sources, donc je suis recherche de sources ..
- Vous pouvez consulter les manuels de complexité et dalgorithmes standard. Mais même si vous trouvez une référence, cette ' nest que ce manuel particulier ' qui utilise le terme. Il est ' probablement de le définir explicitement comme une définition commune sans aucune " preuve ".