Бертранс дауыс беру теоремасы - Bertrands ballot theorem - Wikipedia

Жылы комбинаторика, Бертранның дауыс беру мәселесі деген сұрақ: «Ан сайлау А кандидатын қайда қабылдайды б дауыстарды алады және В кандидаты алады q дауыс береді б > q, не ықтималдық А санақ бойынша В-дан едәуір озады ма? «Жауап:

${ displaystyle { frac {p-q} {p + q}}.}$

Нәтиже бірінші болып жарияланды Уитуорт 1878 жылы, бірақ есімімен аталады Джозеф Луи Франсуа Бертран кім оны 1887 жылы қайта ашты.^[1][2]

Бертранның түпнұсқалық мақаласында ол қолайлы дәйектіліктің жалпы формуласына негізделген дәлелдеу эскизін рекурсиялық қатынас. Оның айтуынша, мұндай қарапайым нәтижені тікелей әдіспен дәлелдеуге болатын сияқты. Мұндай дәлел келтірілген Désiré André,^[3] қолайсыз тізбектерді екі бірдей ықтимал жағдайға бөлуге болатынын бақылауға негізделген, олардың бірі (В бірінші дауысты алатын жағдай) оңай есептеледі; ол теңдікті айқын түрде дәлелдейді биекция. Оның әдісінің вариациясы танымал ретінде танымал Андренің рефлексия әдісі, дегенмен Андре ешқандай рефлексия қолданбаған.^[4]

Мысал

5 сайлаушы бар делік, оның ішінде 3 үміткерге дауыс береді A және кандидатқа 2 дауыс B (сондықтан б = 3 және q = 2). Дауыстарды берудің он мүмкіндігі бар:

• AAABB
• AABAB
• ABAAB
• BAAAB
• AABBA
• АБАБА
• БААБА
• АББАА
• БАБАА
• ББАА

Тапсырыс үшін AABAB, сайлауға қарай дауыстардың саны:

Әр бағанға арналған есеп A әрқашан үлкеннен үлкен B сондықтан A әрқашан алда келеді B. Тапсырыс үшін AABBA сайлауға қарай дауыстардың саны:

Осы тапсырыс үшін, B байланысты A төртінші дауыс беруден кейін, сондықтан A әрқашан қатаң түрде алда келе бермейді B10 ықтимал тапсырыстың ішінен A әрқашан алда B тек үшін AAABB және AABAB. Сондықтан ықтималдығы A әрқашан алда болады

${ displaystyle { frac {2} {10}} = { frac {1} {5}},}$

және бұл шынымен де тең ${ displaystyle { frac {3-2} {3 + 2}}}$ теорема болжағандай.

Эквивалентті мәселелер

Дауыстарды кездейсоқ санау бұйрығының қажетті қасиетке ие болу ықтималдығын есептеудің орнына, қолайлы санау тапсырыстарының санын есептеуге болады, содан кейін дауыстарды санауға болатын тәсілдердің жалпы санына бөлуге болады. (Бұл Бертран қолданған әдіс.) Жолдардың жалпы саны: биномдық коэффициент ${ displaystyle { tbinom {p + q} {p}}}$; Бертранның дәлелі көрсеткендей, дауыстарды санауға болатын қолайлы тапсырыстар саны ${ displaystyle { tbinom {p + q-1} {p-1}} - { tbinom {p + q-1} {p}}}$ (бірақ ол бұл санды нақты бермейді). Бөлінгеннен кейін бұл береді ${ displaystyle { tfrac {p} {p + q}} - { tfrac {q} {p + q}} = { tfrac {p-q} {p + q}}}$.

Тағы бір баламалы мәселе - санын есептеу кездейсоқ серуендер үстінде бүтін сандар тұрады n басынан бастап нүктесінде аяқталатын бірлік ұзындығының қадамдары м, бұл ешқашан теріс болмайды. Болжалды n және м бірдей теңдікке ие және n ≥ м ≥ 0, бұл сан

${ displaystyle { binom {n} { tfrac {n + m} {2}}} - { binom {n} {{ tfrac {n + m} {2}} + 1}} = { frac {m + 1} {{ tfrac {n + m} {2}} + 1}} { binom {n} { tfrac {n + m} {2}}}.}$

Қашан м = 0 және n тең, бұл береді Каталон нөмірі ${ displaystyle { frac {1} {{ tfrac {n} {2}} + 1}} { binom {n} { tfrac {n} {2}}}}$.

Рефлексия арқылы дәлелдеу

Дауыстарды санау кезінде А-дан В-дан едәуір озып кетуі үшін байланыстар болмайды. Бірінші дауысқа сәйкес санау ретін бөліп алыңыз. В-ға дауыс беруден басталатын кез-келген дәйектілік белгілі бір уақытта теңдікке жетуі керек, өйткені А соңында жеңіске жетеді. А-дан басталып, теңдікке жеткен кез-келген дәйектілік үшін, бірінші теңдік нүктесіне дейін дауыстарды көрсетіңіз (сондықтан кез-келген А В-ға айналады және керісінше) Б-дан басталатын ретті алу үшін, демек, барлық басталатын кезек А және галстукке жету В-дан басталатын бір-біріне сәйкес келеді, ал В-дан басталу ықтималдығы ${ displaystyle q / (p + q)}$, демек, А дауысты әрдайым басқарады

${ displaystyle = 1-}$ белгілі бір сәтте байланыстыратын реттіліктің ықтималдығы

${ displaystyle = 1-}$ белгілі бір уақытта байланған және А немесе В-дан басталатын реттіліктің ықтималдығы

${ displaystyle = 1-2 { frac {q} {p + q}} = { frac {p-q} {p + q}}}$

Индукция арқылы дәлелдеу

Дәлелдеудің тағы бір әдісі - математикалық индукция:

• Біз шартты босатамыз ${ displaystyle p> q}$ дейін ${ displaystyle p geq q}$. Теорема қашан дұрыс екендігі анық ${ displaystyle p = q}$, өйткені бұл жағдайда бірінші үміткер болмайды қатаң түрде барлық дауыстар есептелгеннен кейін (сондықтан ықтималдық 0-ге тең).
• Әрине, егер теорема дұрыс болса б > 0 және q = 0, ықтималдық 1 болғанда, бірінші кандидат барлық дауыстарды алатындығын ескере отырып; бұл қашан да дұрыс б = q > 0 біз жаңа көргендей.
• Мұны қашан да дұрыс деп есептеңіз б = а - 1 және q = б, және қашан б = а және q = б - 1, бірге а > б > 0. (Біз істі қараудың қажеті жоқ ${ displaystyle a = b}$ осында, өйткені біз бұған дейін оны жойдық.) Содан кейін істі қарастыру б = а және q = б, соңғы дауыс ықтималдықпен бірінші үміткерге есептеледі а/(а + б) немесе екіншісіне ықтималдықпен б/(а + б). Сонымен, санау кезінде бірінші болып саналудың алдын-ала есептелген дауысқа дейін (сондай-ақ соңғы дауыс беруден кейін) ықтималдығы:

${ displaystyle {a over (a + b)} {(a-1) -b over (a + b-1)} + {b over (a + b)} {a- (b-1) over (a + b-1)} = {ab over a + b}.}$

• Сонымен, бұл бәріне қатысты б және q бірге б > q > 0.

Ауыстыру арқылы дәлелдеу

Қарапайым дәлелдеме Дворетцкий мен Мотцкиннің әдемі Леммасына негізделген.^[5]Дауыс беру кезегін шақырыңыз басым егер дауыстарды санау кезінде А, В-дан қатаң алда болса. Лемма циклі кез келген дәйектілік деп санайды ${ displaystyle p}$ A және ${ displaystyle q}$ B, қайда ${ displaystyle p> q}$, дәл бар ${ displaystyle p-q}$ басым циклдық ауыстырулар. Мұны көру үшін берілген тізбегін орналастырыңыз ${ displaystyle p + q}$ A және B дөңгелектерде және көршілес АВ жұптарын тек бірнеше рет алып тастаңыз ${ displaystyle p-q}$ A қалды. Осы А-лардың әрқайсысы ешнәрсе жойылмағанға дейін басым циклдық ауыстырудың басталуы болды. Сонымен ${ displaystyle p-q}$ ішінен ${ displaystyle p + q}$ кез келген орналасудың циклдық ауыстырулары ${ displaystyle p}$ Дауыстар және ${ displaystyle q}$ B дауыстары басым.

Бертран мен Андренің дәлелдері

Бертран шешімді келесідей білдірді

${ displaystyle { frac {2m- mu} { mu}}}$

қайда ${ displaystyle mu = p + q}$ - сайлаушылардың жалпы саны және ${ displaystyle m = p}$ бұл бірінші кандидатқа сайлаушылар саны. Ол нәтиже формуладан туындайтынын айтады

${ displaystyle P_ {m + 1, mu +1} = P_ {m, mu} + P_ {m + 1, mu},}$

қайда ${ displaystyle P_ {m, mu}}$ - бұл қолайлы тізбектердің саны, бірақ «мұндай қарапайым нәтижені тура жолмен көрсетуге болатын сияқты». Шынында да, көп ұзамай Désiré André тікелей дәлелдеді. Оның көзқарасын қазіргі авторлар көбінесе қате түрде «шағылысу қағидасы» деп атайды, бірақ іс жүзінде ауыстыруды қолданады. Ол «қолайсыз» тізбектер (аралық теңдікке жететіндер) А-дан басталатын, В-дан басталатын бірдей тізбектер санынан тұратындығын көрсетеді. ${ displaystyle { tbinom {p + q-1} {q-1}}}$ мұндай тізбектер В, содан кейін ерікті тізбегі (q-1) B және б А. А-дан басталатын кез-келген қолайсыз тізбекті ерікті тізбекке айналдыруға болады (q-1) B және б A ережені бұзатын бірінші B-ді тауып (дауыстардың тең болып қалуына әкеліп соқтырады) және оны өшіріп, қалған бөліктердің ретін ауыстырады. Процесті кері айналдыру үшін (q-1) B және б А және соңынан бастап А санының қай жерде В санынан артық болатынын анықтап, бөліктердің ретін ауыстырып, олардың арасына В қойыңыз. Мысалы, қолайсыз реттілік AABBABAA ерікті ABAA дәйектілігіне сәйкес келедіAAB. Бұдан қолайлы тізбектер саны шығады б A және q B - бұл

${ displaystyle { binom {p + q} {q}} - 2 { binom {p + q-1} {q-1}} = { binom {p + q} {q}} { frac { pq} {p + q}}}$

және, осылайша, қажетті ықтималдық

${ displaystyle { frac {p-q} {p + q}}}$

күткендей.

Нұсқа: байланыстыруға рұқсат етілген

Бастапқы мәселе - бірінші кандидаттың дауыстарды санау кезінде әрдайым алда тұру ықтималдығын табу. Оның орнына екінші үміткердің ешқашан алда болмау ықтималдығын табу мәселесін қарастыруға болады (яғни байланыстарға рұқсат етіледі). Бұл жағдайда жауап табылады

${ displaystyle { frac {p + 1-q} {p + 1}}.}$

Нұсқалық есеп рефлексия әдісімен бастапқы есепке ұқсас түрде шешілуі мүмкін. Мүмкін болатын дауыс берудің саны ${ displaystyle { tbinom {p + q} {q}}}$. Егер екінші үміткер алда болатын болса, егер нашар тізбектер санын санауға болатын болса, онда «жақсы» қатарлардың санын азайту арқылы табуға болады және ықтималдықты есептеуге болады.

Дауыс беру ретін а ретінде көрсетіңіз торлы жол декарттық жазықтықта келесідей:

• Жолды (0, 0) -ден бастаңыз
• Әрбір бірінші үміткерге дауыс берілген сайын 1 бірлік оңға жылжиды.
• Екінші үміткерге дауыс түскен сайын 1 бірлікке жоғарылайды.

Әрбір осындай жол дауыс берудің бірегей реттілігіне сәйкес келеді және аяқталады (б, q). Сәйкес жол ешқашан диагональ сызығынан асып кетпесе, реттілік «жақсы» болады ж = х; эквивалентті түрде, сәйкес жол сызыққа тиген кезде реттілік «нашар» болады ж = х + 1.

«Жаман» жол (көк) және оның шағылысқан жолы (қызыл)

Әрбір «жаман» жол үшін P, жаңа жолды анықтаңыз PReflect бөлігін көрсету арқылы P бірінші нүктеге дейін ол сызықпен жанасады. P′ - (−1, 1) -ден (-ге) дейінгі жолб, q). Сол операция қайтадан түпнұсқаны қалпына келтіреді P. Бұл «жаман» жолдар мен (-1, 1) -ден (б, q). Бұл жолдардың саны ${ displaystyle { tbinom {p + q} {q-1}}}$ және бұл «жаман» тізбектердің саны. Бұл «жақсы» тізбектердің санын қалдырады

${ displaystyle { binom {p + q} {q}} - { binom {p + q} {q-1}} = { binom {p + q} {q}} { frac {p + 1 -q} {p + 1}}.}$

Бар болғандықтан ${ displaystyle { tbinom {p + q} {q}}}$ тұтастай алғанда, реттіліктің жақсы болу ықтималдығы ${ displaystyle { tfrac {p + 1-q} {p + 1}}}$.

Шындығында, бастапқы есеп пен вариант мәселесінің шешімдері оңай байланысты. А үміткерлері дауыстарды санау кезінде қатаң озып кетуі үшін, олар бірінші дауысты алуы керек, ал қалған дауыстар үшін (біріншісіне мән бермей) олар қатаң алда болуы керек немесе бүкіл санау кезінде байланған болуы керек. Демек, бастапқы мәселені шешу болып табылады

${ displaystyle { frac {p} {p + q}} { frac {p-1 + 1-q} {p-1 + 1}} = { frac {p-q} {p + q}}}$

талап етілгендей.

Керісінше, галстук галстукты галстук емес жағдайдан алуға болады. Назар аударыңыз нөмір p + 1 дауысы бар галстук емес тізбектердің саны A үшін p p, ал A үшін p + 1 дауысы бар галстук емес дауыс саны ${ displaystyle { tfrac {p + 1-q} {p + 1 + q}} { tbinom {p + 1 + q} {q}}}$, бұл алгебралық манипуляция арқылы ${ displaystyle { tfrac {p + 1-q} {p + 1}} { tbinom {p + q} {q}}}$, сондықтан бөлшек p үшін A дауысы берілген тізбектер ${ displaystyle { tfrac {p + 1-q} {p + 1}}}$.

Бұл мақалада жалпы тізімі бар сілтемелер, бірақ бұл негізінен тексерілмеген болып қалады, өйткені ол сәйкесінше жетіспейді кірістірілген дәйексөздер. Көмектесіңізші жақсарту осы мақала таныстыру дәлірек дәйексөздер. (Маусым 2012) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз)

Ескертулер

Әдебиеттер тізімі

• Дауыс беру теоремалары, ескі және жаңа, Л. Аддарио-Берри, Б.А. Қамыс, 2007 ж Комбинаториканың көкжиектері, Редакторлар Эрвин Джайри, Г. Катона, Дюла О. Х. Катона, Ласло Ловаш, Springer, 2008, ISBN  978-3-540-77199-9

Сыртқы сілтемелер

• Дауыс беру бюллетені (француз тіліндегі мақалалардың түпнұсқаларын және ағылшын тіліндегі аудармаларын қамтиды)
• Бернард Бру, Les leçons de calcul des probabilités de Joseph Bertrand, мәселенің тарихы (француз тілінде)
• Вайсштейн, Эрик В. «Дауыс беру бюллетені». MathWorld.