Bertrand's ballot theorem (original) (raw)
Bertranden bozketa ebazkizuna ebazkizun klasikoa da konbinatorian eta probabilitatean. Honela dio: bozketa bateko bi hautagaiek p eta q boto lortu badituzte hurrenez hurren, zenbatekoa da boto zenbaketan p boto lortu dituen hautagaia beti aurretik izateko Pp,q probabilitatea?. Adibidez, hautagaiek 10 boto eta 6 boto lortu badituzte hurrenez hurren, 10 boto lortu dituenak beti aurretik izateko probabilitatea hau da: Argi denez, probabilitatea 0 izango da, p denean. Bertranden bozketa ebazkizuna lehen aldiz Joseph Bertrand matematikari frantsesak asmatu eta ebatzi zuen 1887. urtean.
| Property | Value |
|---|---|
| dbo:abstract | في التركيبات، نص مسألة برتراند هو: "في إحدى الانتخابات، المرشح A استلم p تصويتاً، والمرشح B استلم q تصويتاً حيث p > q. عند عد عدد التصويتات للمرشحين ما احتمالية تجاوز A عدد تصويتات B دائماً خلال التعداد؟." الجواب هو أول من نشر النتيجة هو عام 1878، لكنها سُمِّيت نسبة ل الذي أعاد طرحها عام 1887م. كتب برتراند في ورقته الأصلية برهاناً مبني على الصيغة العامة لعدد المتتابعات الملائمة باستخدام علاقة تعاودية. وقد ذكر أنه من المحتمل لمثل هذه النتيجة البسيطة وجود طريقة إثبات أخرى أكثر مباشرة. هذه الطريقة أثبتها ، بناءً على ملاحظته أن المتتابعات غير الملائمة بالإمكان تقسيمها لقسمين، إحدى القسمين يكون فيه B هو من يستلم الصوت الأول، ويُثبت ذلك عن طريق التقابل. (ar) In combinatorics, Bertrand's ballot problem is the question: "In an election where candidate A receives p votes and candidate B receives q votes with p > q, what is the probability that A will be strictly ahead of B throughout the count?" The answer is The result was first published by W. A. Whitworth in 1878, but is named after Joseph Louis François Bertrand who rediscovered it in 1887. In Bertrand's original paper, he sketches a proof based on a general formula for the number of favourable sequences using a recursion relation. He remarks that it seems probable that such a simple result could be proved by a more direct method. Such a proof was given by Désiré André, based on the observation that the unfavourable sequences can be divided into two equally probable cases, one of which (the case where B receives the first vote) is easily computed; he proves the equality by an explicit bijection. A variation of his method is popularly known as André's reflection method, although André did not use any reflections. The Bertrand's ballot theorem is equivalent to the Cycle lemma. (en) Bertranden bozketa ebazkizuna ebazkizun klasikoa da konbinatorian eta probabilitatean. Honela dio: bozketa bateko bi hautagaiek p eta q boto lortu badituzte hurrenez hurren, zenbatekoa da boto zenbaketan p boto lortu dituen hautagaia beti aurretik izateko Pp,q probabilitatea?. Adibidez, hautagaiek 10 boto eta 6 boto lortu badituzte hurrenez hurren, 10 boto lortu dituenak beti aurretik izateko probabilitatea hau da: Argi denez, probabilitatea 0 izango da, p denean. Bertranden bozketa ebazkizuna lehen aldiz Joseph Bertrand matematikari frantsesak asmatu eta ebatzi zuen 1887. urtean. (eu) En probabilités, le problème du scrutin est une question concernant un scrutin à deux candidats où l'on connait le nombre de voix obtenues par le vainqueur et le nombre de voix obtenues par le perdant. On demande la probabilité que le vainqueur soit toujours strictement en tête lors du dépouillement. La réponse, qui constitue le théorème du scrutin, est simplement le rapport , mais la démonstration n'en est pas immédiate. Posant , la probabilité contraire, qu'il y ait au moins un moment avec autant de voix pour les deux candidats, valant , est donc proportionnelle à . Par exemple, cet évènement arrive plus d'une fois sur deux pour . (fr) Il teorema del ballottaggio prende il nome dal problema che originariamente si pone obiettivo di risolvere: Data un'elezione con voti validi e due soli candidati e che ricevono rispettivamente e , dove (e ), qual è la probabilità che, nello spoglio dei voti, risulti in ogni momento (a parte ovviamente che all'inizio) strettamente in vantaggio su ? Questa probabilità è , ovvero, espressa in percentuale, , dove e sono rispettivamente le percentuali di voti di e . (it) Em probabilidade, o Teorema da Eleição é um resultado clássico sobre passeios aleatórios que afirma: Em uma eleição com dois candidatos A e B com e votos respectivamente, se então a probabilidade de que durante a apuração da eleição o candidato A esteja sempre à frente é dada por . O resultado foi descoberto por A. De Moivre em 1708 ao estudar jogos de azar e redescoberto por Joseph Louis François Bertrand em 1887. (pt) В комбинаторике, Теорема Бертрана о выборах, названная в честь Жозефа Бертрана, который опубликовал её в 1887 году — утверждение, доказывающее ответ на вопрос «Какова вероятность того, что на выборах с участием двух кандидатов, в которых первый набрал p голосов, а второй набрал q < p, первый будет опережать второго в течение всего времени подсчета голосов?». Ответ на этот вопрос: . В своей публикации Бертран сделал наброски доказательства данной теоремы по индукции, и задался вопросом о том, может ли она быть доказана комбинаторными методами. Такое доказательство было предложено Д. Андре. (ru) 在组合数学中，伯特兰投票问题是指，在一场选举中候选人A得到了p张选票，而候选人得到了q张选票（p>q），那么在整个点票过程中A的票数都严格大于B的概率是多少。这个问题的答案是 这个结果首次由于1878年发布，但最终以在1887年重新发现这个问题的约瑟·伯特兰的名字命名。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/AndreReflection.svg?width=300 |
| dbo:wikiPageExternalLink | http://webspace.ship.edu/msrenault/ballotproblem/ http://www.dms.umontreal.ca/~addario/papers/btsurvey.pdf http://www.jehps.net/Decembre2006/Bru.pdf https://books.google.com/books%3Fid=kIKW18ENfUMC |
| dbo:wikiPageID | 1043036 (xsd:integer) |
| dbo:wikiPageLength | 16286 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116346371 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Election dbr:Binomial_coefficient dbc:Enumerative_combinatorics dbc:Probability_theorems dbr:Désiré_André dbc:Articles_containing_proofs dbr:Mathematical_induction dbr:László_Lovász dbr:Combinatorics dbr:Bruce_Reed_(mathematician) dbc:Theorems_in_combinatorics dbc:Probability_problems dbr:Probability dbc:Voting_theory dbr:Lattice_path dbr:Bijection dbr:Joseph_Louis_François_Bertrand dbr:Integer dbr:Optional_stopping_theorem dbr:Catalan_number dbr:Random_walk dbr:Martingale_(probability_theory) dbr:William_Allen_Whitworth dbr:Recursion_relation dbr:File:AndreReflection.svg |
| dbp:title | Ballot Problem (en) |
| dbp:urlname | BallotProblem (en) |
| dbp:wikiPageUsesTemplate | dbt:ISBN dbt:MathWorld dbt:More_footnotes_needed dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Enumerative_combinatorics dbc:Probability_theorems dbc:Articles_containing_proofs dbc:Theorems_in_combinatorics dbc:Probability_problems dbc:Voting_theory |
| rdf:type | yago:WikicatNamedProbabilityProblems yago:WikicatTheorems yago:WikicatTheoremsInCombinatorics yago:Abstraction100002137 yago:Attribute100024264 yago:Communication100033020 yago:Condition113920835 yago:Difficulty114408086 yago:Message106598915 yago:Problem114410605 yago:Proposition106750804 yago:State100024720 yago:Statement106722453 yago:Theorem106752293 yago:WikicatProbabilityTheorems |
| rdfs:comment | Bertranden bozketa ebazkizuna ebazkizun klasikoa da konbinatorian eta probabilitatean. Honela dio: bozketa bateko bi hautagaiek p eta q boto lortu badituzte hurrenez hurren, zenbatekoa da boto zenbaketan p boto lortu dituen hautagaia beti aurretik izateko Pp,q probabilitatea?. Adibidez, hautagaiek 10 boto eta 6 boto lortu badituzte hurrenez hurren, 10 boto lortu dituenak beti aurretik izateko probabilitatea hau da: Argi denez, probabilitatea 0 izango da, p denean. Bertranden bozketa ebazkizuna lehen aldiz Joseph Bertrand matematikari frantsesak asmatu eta ebatzi zuen 1887. urtean. (eu) Il teorema del ballottaggio prende il nome dal problema che originariamente si pone obiettivo di risolvere: Data un'elezione con voti validi e due soli candidati e che ricevono rispettivamente e , dove (e ), qual è la probabilità che, nello spoglio dei voti, risulti in ogni momento (a parte ovviamente che all'inizio) strettamente in vantaggio su ? Questa probabilità è , ovvero, espressa in percentuale, , dove e sono rispettivamente le percentuali di voti di e . (it) Em probabilidade, o Teorema da Eleição é um resultado clássico sobre passeios aleatórios que afirma: Em uma eleição com dois candidatos A e B com e votos respectivamente, se então a probabilidade de que durante a apuração da eleição o candidato A esteja sempre à frente é dada por . O resultado foi descoberto por A. De Moivre em 1708 ao estudar jogos de azar e redescoberto por Joseph Louis François Bertrand em 1887. (pt) В комбинаторике, Теорема Бертрана о выборах, названная в честь Жозефа Бертрана, который опубликовал её в 1887 году — утверждение, доказывающее ответ на вопрос «Какова вероятность того, что на выборах с участием двух кандидатов, в которых первый набрал p голосов, а второй набрал q < p, первый будет опережать второго в течение всего времени подсчета голосов?». Ответ на этот вопрос: . В своей публикации Бертран сделал наброски доказательства данной теоремы по индукции, и задался вопросом о том, может ли она быть доказана комбинаторными методами. Такое доказательство было предложено Д. Андре. (ru) 在组合数学中，伯特兰投票问题是指，在一场选举中候选人A得到了p张选票，而候选人得到了q张选票（p>q），那么在整个点票过程中A的票数都严格大于B的概率是多少。这个问题的答案是 这个结果首次由于1878年发布，但最终以在1887年重新发现这个问题的约瑟·伯特兰的名字命名。 (zh) في التركيبات، نص مسألة برتراند هو: "في إحدى الانتخابات، المرشح A استلم p تصويتاً، والمرشح B استلم q تصويتاً حيث p > q. عند عد عدد التصويتات للمرشحين ما احتمالية تجاوز A عدد تصويتات B دائماً خلال التعداد؟." الجواب هو أول من نشر النتيجة هو عام 1878، لكنها سُمِّيت نسبة ل الذي أعاد طرحها عام 1887م. (ar) In combinatorics, Bertrand's ballot problem is the question: "In an election where candidate A receives p votes and candidate B receives q votes with p > q, what is the probability that A will be strictly ahead of B throughout the count?" The answer is The result was first published by W. A. Whitworth in 1878, but is named after Joseph Louis François Bertrand who rediscovered it in 1887. (en) En probabilités, le problème du scrutin est une question concernant un scrutin à deux candidats où l'on connait le nombre de voix obtenues par le vainqueur et le nombre de voix obtenues par le perdant. On demande la probabilité que le vainqueur soit toujours strictement en tête lors du dépouillement. La réponse, qui constitue le théorème du scrutin, est simplement le rapport , mais la démonstration n'en est pas immédiate. (fr) |
| rdfs:label | نظرية تصويت برتراند (ar) Bertrand's ballot theorem (en) Bertranden bozketa ebazkizuna (eu) Problème du scrutin (fr) Teorema del ballottaggio (it) Teorema da Eleição (pt) Теорема Бертрана о выборах (ru) 伯特兰投票问题 (zh) |
| owl:sameAs | freebase:Bertrand's ballot theorem yago-res:Bertrand's ballot theorem wikidata:Bertrand's ballot theorem dbpedia-ar:Bertrand's ballot theorem dbpedia-eu:Bertrand's ballot theorem dbpedia-fa:Bertrand's ballot theorem dbpedia-fr:Bertrand's ballot theorem dbpedia-it:Bertrand's ballot theorem dbpedia-pt:Bertrand's ballot theorem dbpedia-ru:Bertrand's ballot theorem dbpedia-zh:Bertrand's ballot theorem https://global.dbpedia.org/id/28pHP |
| prov:wasDerivedFrom | wikipedia-en:Bertrand's_ballot_theorem?oldid=1116346371&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/AndreReflection.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Bertrand's_ballot_theorem |
| is dbo:wikiPageRedirects of | dbr:André's_reflection_method dbr:Bertrand's_Ballot_Theorem dbr:Cycle_Lemma dbr:Cycle_lemma dbr:Ballot_Problem dbr:Ballot_problem dbr:Ballot_theorem dbr:Ballot_theorems dbr:Ballot_theory dbr:Bertrand's_ballot_problem dbr:Bertrand_ballot_theorem dbr:Theory_of_ballots |
| is dbo:wikiPageWikiLink of | dbr:List_of_examples_of_Stigler's_law dbr:André's_reflection_method dbr:Bertrand's_Ballot_Theorem dbr:Joseph-Émile_Barbier dbr:Index_of_combinatorics_articles dbr:List_of_misnamed_theorems dbr:1878_in_science dbr:1887_in_science dbr:Dmitry_Mirimanoff dbr:Lobb_number dbr:Cycle_Lemma dbr:Cycle_lemma dbr:Catalan_number dbr:Catalog_of_articles_in_probability_theory dbr:List_of_statistics_articles dbr:List_of_theorems dbr:William_Allen_Whitworth dbr:Ballot_Problem dbr:Ballot_problem dbr:Ballot_theorem dbr:Ballot_theorems dbr:Ballot_theory dbr:Bertrand's_ballot_problem dbr:Bertrand_ballot_theorem dbr:Theory_of_ballots |
| is foaf:primaryTopic of | wikipedia-en:Bertrand's_ballot_theorem |
