With high probability (original) (raw)
En mathématiques et plus particulièrement en théorie des probabilités, une suite d'évènements, indexée par les entiers naturels, se réalise avec grande probabilité si la probabilité que le n-ième évènement se réalise converge vers 1 à l'infini.
| Property | Value |
|---|---|
| dbo:abstract | En mathématiques et plus particulièrement en théorie des probabilités, une suite d'évènements, indexée par les entiers naturels, se réalise avec grande probabilité si la probabilité que le n-ième évènement se réalise converge vers 1 à l'infini. (fr) In mathematics, an event that occurs with high probability (often shortened to w.h.p. or WHP) is one whose probability depends on a certain number n and goes to 1 as n goes to infinity, i.e. the probability of the event occurring can be made as close to 1 as desired by making n big enough. (en) Асимптотически достоверное событие — событие, вероятность которого зависит от некоторого параметра и стремится к при стремящемся к бесконечности, то есть, вероятность данного события может быть сделана сколь угодно высокой путём увеличения . Про такое событие говорят, что оно происходит «с высокой вероятностью» (англ. with high probability, обычно сокращается до w.h.p.) или «асимптотически почти наверное» (asymptoticaly almost surely). Всякое почти достоверное событие (которое происходит с вероятностью ) асимпотически достоверно, обратное неверно. Используется в информатике при асимптотическом анализе вероятностных алгоритмов. Например, если некоторый алгоритм работает на графах с вершинами и вероятность того, что алгоритм выдаст правильный результат равна , то при достаточно большом количестве вершин в графе вероятность того, что алгоритм выдаст правильный ответ будет близка к , то есть, можно говорить, что «алгоритм корректен с высокой вероятностью». Некоторые алгоритмы, использующие понятие асимптотической достоверности: * тест Миллера — Рабина: вероятностный алгоритм для проверки того, является ли число простым или составным, если — составное, то алгоритм определит это с высокой вероятностью; * алгоритм Фрейвалдса: рандомизированный алгоритм для проверки матричного произведения, работает быстрее известных детерминированных алгоритмов с высокой вероятностью; * декартово дерево: рандомизированное бинарное дерево поиска, высота которого логарифмична с высокой вероятностью. В машинном обучении применяется схема вероятно приближённо корректного обучения, в котором конструируемая функция обладает низкой ошибкой обобщения с высокой вероятностью. Выделяется класс сложности BQP, состоящий из задач, для которых существуют полиномиальные квантовые алгоритмы, корректные с высокой вероятностью. (ru) |
| dbo:wikiPageExternalLink | http://dcg.ethz.ch/lectures/podc_allstars/lecture/chapter7.pdf |
| dbo:wikiPageID | 45454942 (xsd:integer) |
| dbo:wikiPageLength | 2966 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1038365234 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Probably_approximately_correct_learning dbc:Randomized_algorithms dbr:Almost_surely dbr:Mathematics dbr:Freivalds'_algorithm dbr:Gossip_protocol dbr:Communication_protocol dbr:Computer_science dbr:BQP dbc:Probability_theory dbr:Treap dbr:Distributed_computing dbr:Fusion_tree dbr:Miller–Rabin_primality_test dbr:Randomized_algorithm dbr:Online_codes dbr:Probabilistic_algorithm |
| dbp:wikiPageUsesTemplate | dbt:Cite_journal dbt:Cite_web dbt:Short_description dbt:Use_American_English dbt:Cs-stub |
| dct:subject | dbc:Randomized_algorithms dbc:Probability_theory |
| rdfs:comment | En mathématiques et plus particulièrement en théorie des probabilités, une suite d'évènements, indexée par les entiers naturels, se réalise avec grande probabilité si la probabilité que le n-ième évènement se réalise converge vers 1 à l'infini. (fr) In mathematics, an event that occurs with high probability (often shortened to w.h.p. or WHP) is one whose probability depends on a certain number n and goes to 1 as n goes to infinity, i.e. the probability of the event occurring can be made as close to 1 as desired by making n big enough. (en) Асимптотически достоверное событие — событие, вероятность которого зависит от некоторого параметра и стремится к при стремящемся к бесконечности, то есть, вероятность данного события может быть сделана сколь угодно высокой путём увеличения . Про такое событие говорят, что оно происходит «с высокой вероятностью» (англ. with high probability, обычно сокращается до w.h.p.) или «асимптотически почти наверное» (asymptoticaly almost surely). Всякое почти достоверное событие (которое происходит с вероятностью ) асимпотически достоверно, обратное неверно. (ru) |
| rdfs:label | Avec grande probabilité (fr) Асимптотически достоверное событие (ru) With high probability (en) |
| owl:sameAs | freebase:With high probability yago-res:With high probability wikidata:With high probability dbpedia-fa:With high probability dbpedia-fr:With high probability dbpedia-ru:With high probability https://global.dbpedia.org/id/setG |
| prov:wasDerivedFrom | wikipedia-en:With_high_probability?oldid=1038365234&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:With_high_probability |
| is dbo:wikiPageDisambiguates of | dbr:WHP |
| is dbo:wikiPageWikiLink of | dbr:Amplitude_amplification dbr:Bayesian-optimal_pricing dbr:Envy-free_item_allocation dbr:Online_fair_division dbr:Prior-free_mechanism dbr:Pseudorandom_graph dbr:Maximal_independent_set dbr:Freivalds'_algorithm dbr:Glossary_of_quantum_computing dbr:Component_(graph_theory) dbr:Maximin_share dbr:BQP dbr:Treap dbr:Karger's_algorithm dbr:Alon–Boppana_bound dbr:Error_function dbr:Balls_into_bins_problem dbr:Fair_division_among_groups dbr:Greedy_coloring dbr:Grover's_algorithm dbr:WHP dbr:Giant_component dbr:Online_codes dbr:Uniform_convergence_in_probability dbr:Set_balancing dbr:Quantum_phase_estimation_algorithm |
| is foaf:primaryTopic of | wikipedia-en:With_high_probability |