Кіріспе
Комбинаторикада Бертранның бюллетень мәселесі мынадай сұрақ: "А кандидат p дауыс алғанда және B кандидат q дауыс алғанда (p > q), дауыс санау барысында А кандидаты B кандидатынан әрқашан алда болады деген ықтималдық қандай?" Жауабы:
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. Bertrand's ballot theorem is related to the cycle lemma. They give similar formulas, but the cycle lemma considers circular shifts of a given ballot counting order rather than all permutations.
Бұл нәтиже алғаш рет 1878 жылы В. А. Уитворт жариялаған, бірақ оны 1887 жылы қайта ашқан Джозеф Луи Франсуа Бертранның есімімен аталады. Бертранның алғашқы мақаласында ол рекурсиялық қатынас қолданып, жақсы нәтижелердің жалпы формуласына негізделген дәлелдің жобасын ұсынады. Ол мұндай қарапайым нәтижені тікелей әдіспен дәлелдеу мүмкін екенін айтады. Мұндай дәлелді Дезире Андре берді, ол жағымсыз тізбектерді екі тең ықтималды жағдайға бөлуге болады деген байқауға негізделген, олардың бірі (B кандидаты бірінші дауысты алған жағдай) оңай есептеледі; ол теңдікті нақты биекция арқылы дәлелдейді. Оның әдісінің бір түрі Андренің бейнелеу әдісі деп белгілі, бірақ Андре ешқандай бейнелеуді қолданбаған. Бертранның бюллетень теоремасы цикл леммасымен байланысты. Олар ұқсас формулаларды ұсынады, бірақ цикл леммасы барлық мүмкіндіктердің орнына, берілген бюллетеньдерді санау ретінің дөңгелек ауысуын қарастырады.
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. Bertrand's ballot theorem is related to the cycle lemma. They give similar formulas, but the cycle lemma considers circular shifts of a given ballot counting order rather than all permutations.
Оңтайлы бұйрықтар
Кездейсоқ дауыс санау ретінің қажетті қасиетке ие болу ықтималдығын есептеудің орнына, қолайлы дауыс санау ретінің санын есептеуге болады, содан кейін дауыстар саналуының барлық мүмкін жолдарының санына бөлу керек. (Бұл Бертран қолданған әдіс.) Барлық мүмкін жолдардың саны – биномдық коэффициент; Бертранның дәлелі дауыстарды санауға қолайлы реттер санының (ол бұл санды тікелей көрсетпесе де) екенін көрсетеді. Ал бөлгеннен кейін нәтижесі шығады.
Кездейсоқ серуендеу
Тағы бір эквивалентті мәселе – бірлік ұзындығындағы n қадамнан тұратын бүтін сандар бойынша кездейсоқ жүрістер санын есептеу, бастапқы нүктеден басталып, m нүктесінде аяқталады, олар ешқашан теріс болмайды. n және m бірдей жұптылыққа ие болғандықтан және , бұл сан қашан және m жұп болса, Каталан санына тең. Осылайша, кездейсоқ жүріс ешқашан теріс болмай, t уақытында бастапқы нүктеге оралу ықтималдығы Стирлинг формуласы бойынша, қашан , бұл ықтималдық [n және m бірдей жұптылыққа ие екенін ескеріңіз: оңға қарайғы "оң" қозғалыстардың саны болсын, ал солға қарайғы "теріс" қозғалыстардың саны болсын. n және m саны болғандықтан, және олар бүтін сандар болғандықтан, бірдей жұптылыққа ие].
When and is even, this gives the Catalan number Thus the probability that a random walk is never negative and returns to origin at time is By Stirling's formula, when , this probability is
[Note that have the same parity as follows: let be the number of "positive" moves, i. e., to the right, and let be the number of "negative" moves, i. e., to the left. Since and , we have and Since and are integers, have the same parity]
Цикл леммасы бойынша дәлелдеу
Қарапайым дәлелдеу Дворецкий мен Мотцкиннің циклдік леммасына негізделген. Егер А дауыс санау барысында Б-ден әрдайым алда болса, онда дауыс беру тізбегін басым деп атаңыз. Циклдік лемма кез келген A және B тізбектерінің , , саны дәл басым циклдік ауысуларға ие екенін мәлімдейді. Мұны түсіну үшін, берілген A және B тізбектерін шеңберге орналастырып, тек A ғана қалғанша, AB жанындағы жұптарды қайталап алып тастаңыз. Осы A-ның әрқайсысы бірдеңе алынып тасталғанға дейін басым циклдік ауысудың бастамасы болды. Демек, кез келген A дауысы мен B дауысының барлық циклдік ауысуларының арасында басым ауысулар бар.
Мартингаль арқылы дәлелдеу
"Кері санау" стохастикалық процесін анықтайық, мұнда – дауыс берілгеннен кейін А үміткерінің B үміткерінен артықшылығы. Пайымдау: бұл мартингейл процесі. Берілген жағдайда, алғашқы дауыстардың арасында А үміткеріне дауыс берілген, ал B үміткеріне дауыс берілген. Олай болса, ықтималдығы бойынша , және соған ұқсас. Содан кейін анықтаңыз, тоқтату уақытын анықтаңыз, яғни, ең кішкентай , мұндай болмаса, онда А үміткерінің әрқашан жетекшілік ететін ықтималдығы, қалаулы тоқтату теоремасы бойынша, тең болады.
where is the lead of candidate A over B, after votes have come in. Claim: is a martingale process. Given , we know that , so of the first votes, were for candidate A, and were for candidate B. So, with probability , we have , and Similarly for the other one. Then compute to find Define the stopping time as either the minimum such that , or if there's no such Then the probability that candidate A leads all the time is just , which by the optional stopping theorem is