S vysokou pravděpodobností - With high probability

v matematika, událost, která nastane s vysokou pravděpodobností (často zkráceno na w.h.p. nebo WHP) je ten, jehož pravděpodobnost závisí na určitém počtu n a jde do 1 jako n jde do nekonečna, tj. může být vytvořeno co nejblíže k 1 vytvořením n dost velký.

Aplikace

Termín WHP se používá zejména v počítačová věda, při analýze pravděpodobnostní algoritmy. Zvažte například určitý pravděpodobnostní algoritmus na grafu s n uzly. Pokud je pravděpodobnost, že algoritmus vrátí správnou odpověď, je , pak když je počet uzlů velmi velký, algoritmus je správný s pravděpodobností, která je velmi blízká 1. Tato skutečnost je krátce vyjádřena tím, že algoritmus je správný WHP.

Některé příklady, kde se tento výraz používá, jsou:

  • Miller – Rabinův test primality: pravděpodobnostní algoritmus pro testování, zda dané číslo n je primární nebo složený. Li n je složený, test detekuje n jako kompozitní WHP. Je malá šance, že máme smůlu a test si to bude myslet n je hlavní. Pravděpodobnost chyby však lze snížit na neurčito spuštěním testu mnohokrát s různými randomizacemi.
  • Freivaldsův algoritmus: randomizovaný algoritmus pro ověření násobení matic. Běží rychleji než deterministické algoritmy WHP.
  • Šlapat: randomizovaný binární vyhledávací strom. Jeho výška je logaritmická WHP. Fúzní strom je související datová struktura.
  • Online kódy: randomizované kódy, které uživateli umožňují obnovit původní zprávu WHP.
  • BQP: třída složitosti problémů, pro které existují polynomiálně-časové kvantové algoritmy, které jsou správné WHP.
  • Pravděpodobně přibližně správné učení: Proces pro strojové učení, ve kterém naučená funkce má nízkou chybu generalizace s chybou WHP.
  • Klebety: a komunikační protokol použito v distribuované systémy spolehlivě doručovat zprávy do celého klastru pomocí konstantního množství síťových prostředků v každém uzlu a zajištění jediného bodu selhání.

Viz také

Reference

  • Métivier, Y .; Robson, J. M .; Saheb-Djahromi, N .; Zemmari, A. (2010). Msgstr "Optimalizovaná bitová složitost náhodně distribuovaného algoritmu MIS". Distribuované výpočty. 23 (5–6): 331. doi:10.1007 / s00446-010-0121-5.
  • „Principy distribuovaného výpočtu (přednáška 7)“ (PDF). ETH Curych. Citováno 21. února 2015.