Chernoff bound (original) (raw)
In der Wahrscheinlichkeitstheorie beschreibt der Begriff Chernoff-Ungleichung eine obere Schranke für die Wahrscheinlichkeit, dass eine Sequenz unabhängiger Zufallsvariablen von ihrer erwarteten Anzahl an Erfolgen abweicht. Die Ungleichung wurde nach Herman Chernoff benannt, geht jedoch auf Herman Rubin zurück. Die Chernoff-Ungleichung ist ein vielseitiges und vielfach verwendetes Hilfsmittel bei der Analyse von randomisierten Algorithmen in der Informatik.
| Property | Value |
|---|---|
| dbo:abstract | In der Wahrscheinlichkeitstheorie beschreibt der Begriff Chernoff-Ungleichung eine obere Schranke für die Wahrscheinlichkeit, dass eine Sequenz unabhängiger Zufallsvariablen von ihrer erwarteten Anzahl an Erfolgen abweicht. Die Ungleichung wurde nach Herman Chernoff benannt, geht jedoch auf Herman Rubin zurück. Die Chernoff-Ungleichung ist ein vielseitiges und vielfach verwendetes Hilfsmittel bei der Analyse von randomisierten Algorithmen in der Informatik. (de) In probability theory, the Chernoff bound gives exponentially decreasing bounds on tail distributions of sums of independent random variables. Despite being named after Herman Chernoff, the author of the paper it first appeared in, the result is due to Herman Rubin. It is a sharper bound than the known first- or second-moment-based tail bounds such as Markov's inequality or Chebyshev's inequality, which only yield power-law bounds on tail decay. However, the Chernoff bound requires that the variates be independent – a condition that neither Markov's inequality nor Chebyshev's inequality require, although Chebyshev's inequality does require the variates to be pairwise independent. It is related to the (historically prior) Bernstein inequalities and to Hoeffding's inequality. (en) En la teoría de probabilidad, las Cotas de Chernoff fueron nombradas luego de su presentación por Herman Chernoff y, gracias a Herman Rubin, se dieron cotas exponencialmente decrecientes para las distribuciones de sumas de variables aleatorias independientes. Son una cota más fina que las conocidas cotas basadas en el primer y segundo momento tales como la inecuación de Markov o la inecuación de Chebyshev, las cuales solo obtienen cotas de nivel exponencial cuando la distribución decrece. Sin embargo, las cotas de Chernoff requieren que las variables sean independientes - una condición que ni las inecuaciones de Markov ni de Chebyshev requieren. Están relacionadas con las (antecesoras históricas) inecuaciones de Bernstein, y a la inecuación de Hoeffding. (es) En théorie des probabilités, l'inégalité de Chernoff permet de majorer la queue d'une loi de probabilité, c'est-à-dire qu'elle donne une valeur maximale de la probabilité qu'une variable aléatoire dépasse une valeur fixée. On parle également de borne de Chernoff. Elle est nommée ainsi en l'honneur du mathématicien Herman Chernoff. Elle est comparable à l'inégalité de Markov mais donne une borne exponentielle. (fr) Nierówność Chernoffa dostarcza silnych oszacowań prawdopodobieństwa, że suma jednakowych niezależnych zmiennych losowych przekracza pewną liczbę rzeczywistą. (pl) Оценка Чернова даёт экспоненциально убывающие оценки вероятности больших отклонений сумм независимых случайных величин.Эти оценки являются более точными, чем оценки, полученные с использованием первых или вторых моментов, такие как неравенство Маркова или неравенство Чебышёва, которые дают лишь степенной закон убывания.Вместе с тем оценка Чернова требует, чтобы случайные величины были независимы в совокупности — условие, которое ни неравенство Маркова, ни неравенство Чебышёва не требуют, хотя неравенство Чебышёва требует попарную независимость случайных величин. Оценка Чернова имеет отношение к и неравенству Хёфдинга, которые ей исторически предшествуют. (ru) Нерівність Чернова — ймовірнісна нерівність, що визначає експоненційне спадання ймовірності великих відхилень суми деяких однаково розподілених незалежних випадкових величин від математичного сподівання цієї суми. Нерівність вперше була доведена американським математиком Германом Черновим для величин з розподілом Бернуллі. Згодом було одержано багато узагальнень та посилень нерівності, які теж часто називають нерівностями Чернова (uk) |
| dbo:wikiPageID | 741759 (xsd:integer) |
| dbo:wikiPageLength | 25117 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1119845299 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Probably_approximately_correct_learning dbr:Bennett's_inequality dbr:Bernoulli_distribution dbr:Andreas_Winter dbr:Annals_of_Mathematical_Statistics dbr:Annals_of_Probability dbr:Approximation_error dbr:Doob_martingale dbr:Information_Processing_Letters dbr:List_of_logarithmic_identities dbr:Entropic_value_at_risk dbr:Gamma_distribution dbr:Concentration_inequality dbr:Convex_function dbr:Bernstein_inequalities_(probability_theory) dbr:Computational_learning_theory dbr:Matrix_Chernoff_bound dbr:Wassily_Hoeffding dbr:Cumulative_distribution_function dbr:Network_congestion dbr:Probability_theory dbr:Herman_Chernoff dbr:Cramér's_theorem_(large_deviations) dbr:Chebyshev's_inequality dbr:Hoeffding's_inequality dbr:Hoeffding's_lemma dbc:Probabilistic_inequalities dbr:Pigeonhole_principle dbr:I.i.d. dbr:Kullback–Leibler_divergence dbr:Randomized_algorithm dbr:Sergei_Bernstein dbr:Markov's_inequality dbr:Moment-generating_function dbr:Routing dbr:Rudolf_Ahlswede dbr:Sub-Gaussian_distribution dbr:Set_balancing dbr:Statistical_independence dbr:Packet_(information_technology) dbr:Bernoulli_random_variable dbr:Moment_generating_function dbr:Sparse_graph |
| dbp:wikiPageUsesTemplate | dbt:!! dbt:= dbt:Citation_needed dbt:Cite_journal dbt:Main dbt:Math dbt:Mvar dbt:NumBlk dbt:Reflist dbt:Sfrac dbt:Short_description dbt:EquationRef dbt:EquationNote |
| dcterms:subject | dbc:Probabilistic_inequalities |
| rdf:type | yago:WikicatMathematicalTheorems yago:Abstraction100002137 yago:Attribute100024264 yago:Communication100033020 yago:Difference104748836 yago:Inequality104752221 yago:Message106598915 yago:Proposition106750804 yago:Quality104723816 yago:WikicatInequalities yago:Statement106722453 yago:Theorem106752293 yago:WikicatProbabilisticInequalities |
| rdfs:comment | In der Wahrscheinlichkeitstheorie beschreibt der Begriff Chernoff-Ungleichung eine obere Schranke für die Wahrscheinlichkeit, dass eine Sequenz unabhängiger Zufallsvariablen von ihrer erwarteten Anzahl an Erfolgen abweicht. Die Ungleichung wurde nach Herman Chernoff benannt, geht jedoch auf Herman Rubin zurück. Die Chernoff-Ungleichung ist ein vielseitiges und vielfach verwendetes Hilfsmittel bei der Analyse von randomisierten Algorithmen in der Informatik. (de) En théorie des probabilités, l'inégalité de Chernoff permet de majorer la queue d'une loi de probabilité, c'est-à-dire qu'elle donne une valeur maximale de la probabilité qu'une variable aléatoire dépasse une valeur fixée. On parle également de borne de Chernoff. Elle est nommée ainsi en l'honneur du mathématicien Herman Chernoff. Elle est comparable à l'inégalité de Markov mais donne une borne exponentielle. (fr) Nierówność Chernoffa dostarcza silnych oszacowań prawdopodobieństwa, że suma jednakowych niezależnych zmiennych losowych przekracza pewną liczbę rzeczywistą. (pl) Нерівність Чернова — ймовірнісна нерівність, що визначає експоненційне спадання ймовірності великих відхилень суми деяких однаково розподілених незалежних випадкових величин від математичного сподівання цієї суми. Нерівність вперше була доведена американським математиком Германом Черновим для величин з розподілом Бернуллі. Згодом було одержано багато узагальнень та посилень нерівності, які теж часто називають нерівностями Чернова (uk) In probability theory, the Chernoff bound gives exponentially decreasing bounds on tail distributions of sums of independent random variables. Despite being named after Herman Chernoff, the author of the paper it first appeared in, the result is due to Herman Rubin. It is a sharper bound than the known first- or second-moment-based tail bounds such as Markov's inequality or Chebyshev's inequality, which only yield power-law bounds on tail decay. However, the Chernoff bound requires that the variates be independent – a condition that neither Markov's inequality nor Chebyshev's inequality require, although Chebyshev's inequality does require the variates to be pairwise independent. (en) En la teoría de probabilidad, las Cotas de Chernoff fueron nombradas luego de su presentación por Herman Chernoff y, gracias a Herman Rubin, se dieron cotas exponencialmente decrecientes para las distribuciones de sumas de variables aleatorias independientes. Son una cota más fina que las conocidas cotas basadas en el primer y segundo momento tales como la inecuación de Markov o la inecuación de Chebyshev, las cuales solo obtienen cotas de nivel exponencial cuando la distribución decrece. Sin embargo, las cotas de Chernoff requieren que las variables sean independientes - una condición que ni las inecuaciones de Markov ni de Chebyshev requieren. (es) Оценка Чернова даёт экспоненциально убывающие оценки вероятности больших отклонений сумм независимых случайных величин.Эти оценки являются более точными, чем оценки, полученные с использованием первых или вторых моментов, такие как неравенство Маркова или неравенство Чебышёва, которые дают лишь степенной закон убывания.Вместе с тем оценка Чернова требует, чтобы случайные величины были независимы в совокупности — условие, которое ни неравенство Маркова, ни неравенство Чебышёва не требуют, хотя неравенство Чебышёва требует попарную независимость случайных величин. (ru) |
| rdfs:label | Chernoff-Ungleichung (de) Cotas de Chernoff (es) Chernoff bound (en) Inégalité de Chernoff (fr) Nierówność Chernoffa (pl) Оценка Чернова (ru) Нерівність Чернова (uk) |
| owl:sameAs | freebase:Chernoff bound yago-res:Chernoff bound wikidata:Chernoff bound dbpedia-de:Chernoff bound dbpedia-es:Chernoff bound dbpedia-fa:Chernoff bound dbpedia-fr:Chernoff bound dbpedia-he:Chernoff bound dbpedia-hu:Chernoff bound dbpedia-pl:Chernoff bound dbpedia-ru:Chernoff bound dbpedia-th:Chernoff bound dbpedia-uk:Chernoff bound dbpedia-vi:Chernoff bound https://global.dbpedia.org/id/9FcM |
| prov:wasDerivedFrom | wikipedia-en:Chernoff_bound?oldid=1119845299&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Chernoff_bound |
| is dbo:knownFor of | dbr:Herman_Chernoff |
| is dbo:wikiPageDisambiguates of | dbr:Chernoff |
| is dbo:wikiPageRedirects of | dbr:Chernoff's_inequality dbr:Chernoff_bounds dbr:Chernoff_inequality dbr:Matrix_chernoff_bound dbr:Bernstein-Chernoff_inequality |
| is dbo:wikiPageWikiLink of | dbr:Probabilistic_method dbr:Quicksort dbr:List_of_analyses_of_categorical_data dbr:List_of_examples_of_Stigler's_law dbr:Bhattacharyya_distance dbr:List_of_probability_topics dbr:Chi-squared_distribution dbr:Q-function dbr:Equitable_coloring dbr:Andrew_M._Gleason dbr:Bernstein_inequalities_(probability_theory) dbr:Chernoff dbr:Chernoff's_inequality dbr:Matrix_Chernoff_bound dbr:McDiarmid's_inequality dbr:P/poly dbr:BPP_(complexity) dbr:BQP dbr:Hadamard_test_(quantum_computation) dbr:K-independent_hashing dbr:Linear_probing dbr:List_of_Brown_University_alumni dbr:Samplesort dbr:Expander_graph dbr:PP_(complexity) dbr:Herman_Chernoff dbr:Binary_symmetric_channel dbr:Binomial_distribution dbr:Hoeffding's_inequality dbr:Azuma's_inequality dbr:Poisson_distribution dbr:PostBQP dbr:MinHash dbr:Catalog_of_articles_in_probability_theory dbr:Moment-generating_function dbr:Quantum_circuit dbr:List_of_statistics_articles dbr:Random_matrix dbr:Set_balancing dbr:Chernoff_bounds dbr:Chernoff_inequality dbr:Matrix_chernoff_bound dbr:Bernstein-Chernoff_inequality |
| is foaf:primaryTopic of | wikipedia-en:Chernoff_bound |