Probabilistic method (original) (raw)

About DBpedia

Die probabilistische Methode ist ein nicht-konstruktives Beweisverfahren, das durch Paul Erdős geprägt wurde und vor allem in der Kombinatorik Anwendung findet. Die Methode beruht auf folgendem einfachen Prinzip: Um zu zeigen, dass es ein Objekt mit einer bestimmten Eigenschaft gibt, reicht es, eine Wahrscheinlichkeitsverteilung zu finden, sodass die Wahrscheinlichkeit, dass ein zufällig gewähltes Objekt die gewünschte Eigenschaft besitzt, positiv ist.

Property Value
dbo:abstract Die probabilistische Methode ist ein nicht-konstruktives Beweisverfahren, das durch Paul Erdős geprägt wurde und vor allem in der Kombinatorik Anwendung findet. Die Methode beruht auf folgendem einfachen Prinzip: Um zu zeigen, dass es ein Objekt mit einer bestimmten Eigenschaft gibt, reicht es, eine Wahrscheinlichkeitsverteilung zu finden, sodass die Wahrscheinlichkeit, dass ein zufällig gewähltes Objekt die gewünschte Eigenschaft besitzt, positiv ist. (de) La méthode probabiliste est une méthode non constructive, initialement utilisée en combinatoire et popularisée par Paul Erdős, pour démontrer l'existence d'un type donné d'objet mathématique. Cette méthode a été appliquée à d'autres domaines des mathématiques tels que la théorie des nombres, l'algèbre linéaire et l'analyse réelle. Son principe est de montrer que si l'on prend au hasard des objets d'une catégorie, la probabilité que le résultat soit d'un certain type est plus que zéro. Bien que la démonstration utilise la théorie des probabilités, la conclusion finale est déterminée de façon certaine. (fr) The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the probability that the result is of the prescribed kind is strictly greater than zero. Although the proof uses probability, the final conclusion is determined for certain, without any possible error. This method has now been applied to other areas of mathematics such as number theory, linear algebra, and real analysis, as well as in computer science (e.g. randomized rounding), and information theory. (en) Una dimostrazione probabilistica, o metodo probabilistico, è una tecnica di dimostrazione matematica non costruttiva dell'esistenza certa di un oggetto matematico tramite considerazioni probabilistiche. Il metodo è stato introdotto da Paul Erdős ed è applicato in combinatoria, teoria dei numeri, algebra lineare, analisi e in altre discipline applicate, come informatica o teoria dell'informazione. In generale, sfrutta il fatto che se tutti gli oggetti di un insieme non hanno una determinata proprietà, la probabilità che un oggetto scelto casualmente nell'insieme soddisfi quella proprietà è nulla. Se la probabilità è invece strettamente minore di uno, sicuramente almeno uno degli oggetti nell'insieme non soddisfa la proprietà. Considerando invece il valore atteso di una variabile aleatoria, se si dimostra che la variabile può assumere un valore inferiore al valore atteso allora deve assumere anche un valore maggiore rispetto ad esso. (it) Імовірнісний метод являє собою метод , що, в першу чергу, використовується у комбінаториці та винайдений Паулем Ердьошем, для доведення існування наперед визначеного виду математичних об'єктів. Він працює через демонстрацію того, що, якщо випадково обрати об'єкти з деякого класу, ймовірність того, що результат є визначеного вигляду, більше нуля. Хоча доведення використовує ймовірність, кінцевий висновок визначається напевно, без будь-якої похибки. Цей метод досі застосовується у різноманітних галузях математики таких, як теорія чисел, лінійна алгебра, та аналіз. (uk) Вероятностный метод — неконструктивный метод доказательства существования математического объекта с заданными свойствами. В основном используется в комбинаторике, но также и в теории чисел, линейной алгебре и математическом анализе, а также в информатике (например, метод вероятностного округления) и теории информации. Метод состоит в оценке вероятности того, что случайный объект из заданного класса удовлетворяет нужному условию.Если доказано, что эта вероятность положительна, то объект с нужными свойствами существует. Хотя доказательство использует вероятности, окончательный вывод делается определённо, без какой-либо неоднозначности. К распространённым инструментам, используемым в вероятностном методе, относятся неравенство Маркова, неравенство Чернова и локальная лемма Ловаса. (ru)
dbo:wikiPageExternalLink http://www.math.tau.ac.il/~nogaa/PDFS/epc7.pdf https://web.archive.org/web/20120205002452/http:/kam.mff.cuni.cz/~matousek/prob-ln-2pp.ps.gz https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/graph-theory-and-probability-ii/38F46DC839201178C2EEC2B14B1647BC%7Cciteseerx=10.1.1.210.6669 https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/graph-theory-and-probability/154EF813293BC7D0652C4CBCD9D18E84 https://ocw.mit.edu/courses/18-226-probabilistic-method-in-combinatorics-fall-2020/
dbo:wikiPageID 173525 (xsd:integer)
dbo:wikiPageLength 11746 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1112860522 (xsd:integer)
dbo:wikiPageWikiLink dbr:Method_of_conditional_probabilities dbr:Nonconstructive_proof dbr:Paul_Erdős dbr:Cycle_(graph_theory) dbc:Probabilistic_arguments dbr:Independent_set_(graph_theory) dbr:Interactive_proof_system dbr:Real_analysis dbr:Complete_graph dbr:Mathematics dbr:Chromatic_number dbr:Graph_coloring dbr:Probabilistic_proofs_of_non-probabilistic_theorems dbr:Linear_algebra dbr:Combinatorics dbr:Computer_science dbr:Tournament_(graph_theory) dbr:Las_Vegas_algorithm dbc:Combinatorics dbr:Expected_value dbr:Number_theory dbr:Graph_theory dbr:Probability dbr:Random_variable dbc:Mathematical_proofs dbr:Chernoff_bound dbr:Jiří_Matoušek_(mathematician) dbr:Information_theory dbr:Ramsey's_theorem dbr:Ramsey_number dbr:Markov's_inequality dbr:Exponential_growth dbr:Lovász_local_lemma dbr:Random_graph dbr:Randomized_rounding dbr:Statistical_independence dbr:Hamiltonian_cycle
dbp:wikiPageUsesTemplate dbt:= dbt:Cite_journal dbt:Efn dbt:ISBN dbt:Math dbt:Mvar dbt:Notelist dbt:Portal dbt:Short_description dbt:Isbn
dct:subject dbc:Probabilistic_arguments dbc:Combinatorics dbc:Mathematical_proofs
gold:hypernym dbr:Method
rdf:type dbo:Software yago:WikicatMathematicalProofs yago:Abstraction100002137 yago:Argument106648724 yago:Communication100033020 yago:Evidence106643408 yago:Indication106797169 yago:MathematicalProof106647864 yago:Proof106647614 yago:WikicatProbabilisticArguments
rdfs:comment Die probabilistische Methode ist ein nicht-konstruktives Beweisverfahren, das durch Paul Erdős geprägt wurde und vor allem in der Kombinatorik Anwendung findet. Die Methode beruht auf folgendem einfachen Prinzip: Um zu zeigen, dass es ein Objekt mit einer bestimmten Eigenschaft gibt, reicht es, eine Wahrscheinlichkeitsverteilung zu finden, sodass die Wahrscheinlichkeit, dass ein zufällig gewähltes Objekt die gewünschte Eigenschaft besitzt, positiv ist. (de) La méthode probabiliste est une méthode non constructive, initialement utilisée en combinatoire et popularisée par Paul Erdős, pour démontrer l'existence d'un type donné d'objet mathématique. Cette méthode a été appliquée à d'autres domaines des mathématiques tels que la théorie des nombres, l'algèbre linéaire et l'analyse réelle. Son principe est de montrer que si l'on prend au hasard des objets d'une catégorie, la probabilité que le résultat soit d'un certain type est plus que zéro. Bien que la démonstration utilise la théorie des probabilités, la conclusion finale est déterminée de façon certaine. (fr) Імовірнісний метод являє собою метод , що, в першу чергу, використовується у комбінаториці та винайдений Паулем Ердьошем, для доведення існування наперед визначеного виду математичних об'єктів. Він працює через демонстрацію того, що, якщо випадково обрати об'єкти з деякого класу, ймовірність того, що результат є визначеного вигляду, більше нуля. Хоча доведення використовує ймовірність, кінцевий висновок визначається напевно, без будь-якої похибки. Цей метод досі застосовується у різноманітних галузях математики таких, як теорія чисел, лінійна алгебра, та аналіз. (uk) The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the probability that the result is of the prescribed kind is strictly greater than zero. Although the proof uses probability, the final conclusion is determined for certain, without any possible error. (en) Una dimostrazione probabilistica, o metodo probabilistico, è una tecnica di dimostrazione matematica non costruttiva dell'esistenza certa di un oggetto matematico tramite considerazioni probabilistiche. Il metodo è stato introdotto da Paul Erdős ed è applicato in combinatoria, teoria dei numeri, algebra lineare, analisi e in altre discipline applicate, come informatica o teoria dell'informazione. (it) Вероятностный метод — неконструктивный метод доказательства существования математического объекта с заданными свойствами. В основном используется в комбинаторике, но также и в теории чисел, линейной алгебре и математическом анализе, а также в информатике (например, метод вероятностного округления) и теории информации. К распространённым инструментам, используемым в вероятностном методе, относятся неравенство Маркова, неравенство Чернова и локальная лемма Ловаса. (ru)
rdfs:label Probabilistische Methode (de) Méthode probabiliste (fr) Dimostrazione probabilistica (it) Probabilistic method (en) Вероятностный метод (ru) Імовірнісний метод (uk)
owl:sameAs freebase:Probabilistic method yago-res:Probabilistic method wikidata:Probabilistic method dbpedia-cy:Probabilistic method dbpedia-de:Probabilistic method dbpedia-fr:Probabilistic method dbpedia-it:Probabilistic method dbpedia-ru:Probabilistic method dbpedia-uk:Probabilistic method https://global.dbpedia.org/id/34bMW
prov:wasDerivedFrom wikipedia-en:Probabilistic_method?oldid=1112860522&ns=0
foaf:isPrimaryTopicOf wikipedia-en:Probabilistic_method
is dbo:wikiPageRedirects of dbr:Probabilistic_methods dbr:Erdős_magic dbr:Probabilistic_combinatorics dbr:Probabilistic_proof
is dbo:wikiPageWikiLink of dbr:Elementary_Number_Theory,_Group_Theory_and_Ramanujan_Graphs dbr:Method_of_conditional_probabilities dbr:Probabilistic_number_theory dbr:Barna_Saha dbr:Bella_Subbotovskaya dbr:Algorithmic_Lovász_local_lemma dbr:Paul_Erdős dbr:Incompressibility_method dbr:International_Journal_of_Uncertainty,_Fuzziness_and_Knowledge-Based_Systems dbr:List_of_mathematics-based_methods dbr:List_of_probabilistic_proofs_of_non-probabilistic_theorems dbr:Crossing_number_inequality dbr:Fuzzy_extractor dbr:Geoffrey_Grimmett dbr:Girth_(graph_theory) dbr:Monero dbr:Consideration_set dbr:Constructive_proof dbr:Erdős–Rényi_model dbr:Probabilistic_argument dbr:Probabilistic_methods dbr:Combinatorial_Games:_Tic-Tac-Toe_Theory dbr:Combinatorics dbr:Majority_function dbr:Maker-Breaker_game dbr:Bruce_Reed_(mathematician) dbr:Ahlswede–Daykin_inequality dbr:Tournament_(graph_theory) dbr:Joint_Committee_on_Structural_Safety dbr:Mirella_Lapata dbr:Erdős–Tetali_theorem dbr:Angular_resolution_(graph_drawing) dbr:Google_Brain dbr:Randomness_extractor dbr:Heilbronn_triangle_problem dbr:Binary_symmetric_channel dbr:Heuristic_argument dbr:Proofs_from_THE_BOOK dbr:Australian_Laureate_Fellowship dbr:Klaus_Roth dbr:Network_science dbr:Ramsey's_theorem dbr:Sequences_(book) dbr:Extractor_(mathematics) dbr:Extremal_graph_theory dbr:FKG_inequality dbr:Imaging_spectroscopy dbr:Lovász_local_lemma dbr:Gilbert–Varshamov_bound_for_linear_codes dbr:Outline_of_combinatorics dbr:Random_graph dbr:Randomized_rounding dbr:Erdős_magic dbr:Probabilistic_combinatorics dbr:Probabilistic_proof
is foaf:primaryTopic of wikipedia-en:Probabilistic_method