Вероятностная комбинаторика, слу­чай­ные под­ста­но­вки

Привет, Вы узнаете о том , что такое вероятностная комбинаторика, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое вероятностная комбинаторика, слу­чай­ные под­ста­но­вки, подстановки в комбинаторика , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

вероятностная комбинаторика , раз­дел дис­крет­ной ма­те­ма­ти­ки, в ко­то­ром ме­то­ды тео­рии ве­ро­ят­но­стей при­ме­ня­ют­ся для изу­че­ния ком­би­на­тор­ных объ­ек­тов. В вероятностной комбинаторики рас­смат­ри­ва­ют­ся так­же пе­ре­чис­ли­тель­ные за­да­чи ком­би­на­то­ри­ки и во­про­сы су­ще­ст­во­ва­ния ком­би­на­тор­ных объ­ек­тов с за­дан­ны­ми ха­рак­те­ри­сти­ка­ми.

Этот раздел отвечает на вопросы вида: какова вероятность присутствия определенного свойства для случайного дискретного объекта, такого как случайный граф? Например, каково среднее число треугольников в случайном графе? Вероятностные методы также используются для определения существования комбинаторных объектов с определенными заданными свойствами (для которых явные примеры может быть трудно найти), просто наблюдая, что вероятность случайного выбора объекта с этими свойствами больше 0. Этот подход (часто называемый вероятностным методом) доказал свою высокую эффективность в приложениях экстремальной комбинаторики и теории графов. Тесно связанной областью является изучение конечных цепей Маркова, особенно на комбинаторных объектах. Здесь снова используются вероятностные инструменты для оценки времени смешивания.

Часто ассоциируемая с Палом Эрдешем, который сделал новаторскую работу по этому предмету, вероятностная комбинаторика традиционно рассматривалась как набор инструментов для изучения задач в других частях комбинаторики. Однако с ростом приложений для анализа алгоритмов в информатике, а также классической теории вероятностей, аддитивной теории чисел и вероятностной теории чисел, эта область в последнее время выросла и стала самостоятельной областью комбинаторики.

При ис­поль­зо­ва­нии ве­ро­ят­но­ст­ных ме­то­дов для ре­ше­ния пе­ре­чис­ли­тель­ных за­дач ком­би­на­то­ри­ки на ко­неч­ном мно­же­ст­ве ком­би­на­тор­ных объ­ек­тов за­да­ет­ся ве­ро­ят­но­ст­ное рас­пре­де­ле­ние и ис­сле­ду­ют­ся рас­пре­де­ле­ния ха­рак­те­ри­стик слу­чай­но­го ком­би­на­тор­но­го объ­ек­та из это­го мно­же­ст­ва. Ес­ли за­дан­ное рас­пре­де­ле­ние яв­ля­ет­ся рав­но­мер­ным, то ве­ро­ят­ность то­го, что не­ко­то­рая ха­рак­те­ри­сти­ка слу­чай­но­го объ­ек­та при­ня­ла ка­кое-то зна­че­ние, есть от­но­ше­ние чис­ла объ­ек­тов, об­ла­даю­щих этим зна­че­ни­ем ха­рак­те­ри­сти­ки, к об­ще­му чис­лу объ­ек­тов в мно­же­ст­ве, так что, ес­ли об­щее чис­ло объ­ек­тов из­вест­но, за­да­ча на­хо­ж­де­ния ве­ро­ят­но­сти и пе­ре­чис­ли­тель­ная за­да­ча на­хо­ж­де­ния чис­ла объ­ек­тов с за­дан­ным зна­че­ни­ем ха­рак­те­ри­сти­ки эк­ви­ва­лент­ны.

Пер­вые ша­ги вероятностной комбинаторики свя­за­ны с раз­ви­ти­ем в сер. 17 в. эле­мен­тар­ной тео­рии ве­ро­ят­но­стей, ко­гда ком­би­на­тор­ные ме­то­ды ис­поль­зо­ва­лись для под­сче­та разл. ве­ро­ят­но­стей в азарт­ных иг­рах. Пер­вые ре­зуль­та­ты ис­сле­до­ва­ний в вероятностной комбинаторики с ис­поль­зо­ва­ни­ем совр. ме­то­дов тео­рии ве­ро­ят­но­стей поя­ви­лись в ра­бо­тах В. Л. Гон­ча­ро­ва 1942–44, в ко­то­рых по­лу­че­ны осн. ре­зуль­та­ты о пре­дель­ном по­ве­де­нии слу­чай­ных ве­ли­чин, свя­зан­ных с цик­ло­вой струк­ту­рой слу­чай­ных под­ста­но­вок при воз­рас­та­нии их сте­пе­ней. Слу­чай­ная под­ста­нов­ка в комбинаторике сте­пе­ни n – это под­ста­нов­ка, вы­би­рае­мая с рав­ны­ми ве­ро­ят­но­стя­ми из мно­же­ст­ва всех под­ста­но­вок сте­пе­ни n. С ис­поль­зо­ва­ни­ем хо­ро­шо раз­ви­тых в тео­рии ве­ро­ят­но­стей ме­то­дов до­ка­за­тель­ст­ва пре­дель­ных тео­рем (ме­то­да про­из­во­дя­щих функ­ций, ме­то­да ха­рак­те­ри­сти­че­ских функ­ций, а так­же ме­то­да мо­мен­тов) Гон­ча­ро­вым бы­ло до­ка­за­но, что чис­ло цик­лов дли­ны r в слу­чай­ной под­ста­нов­ке сте­пе­ни n име­ет в пре­де­ле при n→∞ рас­пре­де­ле­ние Пу­ас­со­на с па­ра­мет­ром 1/r, рас­пре­де­ление об­ще­го чис­ла цик­лов сбли­жа­ет­ся с нор­маль­ным рас­пре­де­ле­ни­ем с па­ра­мет­ра­ми (lnn,lnn ), най­де­но пре­дель­ное рас­пре­де­ле­ние макс. Об этом говорит сайт https://intellect.icu . дли­ны цик­ла слу­чай­ной под­ста­нов­ки. Впо­след­ст­вии эти ре­зуль­та­ты во мно­гом слу­жи­ли об­раз­цом для изу­че­ния разл. клас­сов слу­чай­ных ком­би­на­тор­ных объ­ек­тов, в т. ч. слу­чай­ных раз­ме­ще­ний, слу­чай­ных раз­бие­ний це­лых чи­сел на це­ло­чис­лен­ные сла­гае­мые, разл. клас­сов слу­чай­ных гра­фов (слу­чай­ных ото­бра­же­ний, ле­сов, де­ревь­ев), слу­чай­ных мат­риц, сис­тем слу­чай­ных урав­не­ний, слу­чай­ных ав­то­ма­тов, слу­чай­ных ал­го­рит­мов.

При изу­че­нии слу­чай­ных гра­фов венг. ма­те­ма­ти­ка­ми П. Эр­де­шем и А. Ре­ньи был об­на­ру­жен (1960) не­ожи­дан­ный эф­фект, ко­то­рый по ана­ло­гии с по­доб­ным эф­фек­том в по­ве­де­нии сис­тем час­тиц в ста­ти­стич. фи­зи­ке трак­ту­ет­ся как фа­зо­вый пе­ре­ход. Пусть 𝒢n,T – слу­чай­ный граф с n вер­ши­на­ми, ко­то­рый по­лу­ча­ет­ся в ре­зуль­та­те раз­ме­ще­ния T ре­бер, каж­дое из ко­то­рых не­за­ви­си­мо от раз­ме­ще­ния ос­таль­ных ре­бер за­ни­ма­ет лю­бое из n(n−1)/2 воз­мож­ных мест с рав­ны­ми ве­ро­ят­но­стя­ми. Пусть 2T/n→λ при n,T→∞ . Ес­ли λ<1, точ­нее, ес­ли ( 1–2T/n)3n→∞, то граф 𝒢n,T с ве­ро­ят­но­стью, стре­мя­щей­ся к еди­ни­це, со­сто­ит из связ­ных ком­по­нент, ко­то­рые яв­ля­ют­ся ли­бо де­ревь­я­ми, ли­бо ком­по­нен­та­ми, со­дер­жа­щи­ми ров­но один цикл. При пе­ре­хо­де па­ра­мет­ром 2T/n зна­чения 1, точ­нее, в об­лас­ти, где при n,T→∞ па­ра­метр (1–2T/n)3 стре­мит­ся к к.-л. по­сто­ян­ной c, по­яв­ля­ет­ся т. н. ги­гант­ская ком­по­нен­та, чис­ло вер­шин в ко­то­рой асим­пто­ти­че­ски нор­маль­но с ма­те­ма­тич. ожи­да­ни­ем α(c)n, при этом с убы­ва­ни­ем па­ра­мет­ра c па­ра­метр α(c) воз­рас­та­ет. При (1–2T/n)3n→–∞ граф 𝒢n,T с веро­ят­но­стью, стре­мя­щей­ся к еди­ни­це, со­сто­ит из ги­гант­ской ком­по­нен­ты, де­ревь­ев и ком­по­нент с од­ним цик­лом. Та­кое по­ве­де­ние слу­чай­но­го гра­фа при пе­ре­хо­де па­ра­мет­ром 2T/n зна­че­ния 1 мож­но ин­тер­пре­ти­ро­вать как фа­зо­вый пе­ре­ход или, дру­ги­ми сло­ва­ми, как на­ли­чие по­ро­го­во­го эф­фек­та в по­ве­де­нии слу­чай­но­го гра­фа. Позд­нее по­ро­го­вый эф­фект был об­на­ру­жен в по­ве­де­нии еще бо­лее про­стых слу­чай­ных ком­би­на­тор­ных объ­ек­тов та­ких, как слу­чай­ные ле­са из кор­не­вых и не­кор­не­вых де­ревь­ев.

Ве­ро­ят­но­ст­ный под­ход ис­поль­зу­ет­ся и для до­ка­за­тель­ст­ва су­ще­ст­во­ва­ния ком­би­на­тор­ных объ­ек­тов без при­вле­че­ния кон­ст­рук­тив­ных по­строе­ний. Про­стей­ший ва­ри­ант это­го под­хо­да ос­но­ван на том, что ес­ли ма­те­ма­тич. ожи­да­ние це­ло­чис­лен­ной не­от­ри­ца­тель­ной слу­чай­ной ве­ли­чи­ны по­ло­жи­тель­но, то эта слу­чай­ная ве­ли­чи­на не рав­на то­ж­де­ст­вен­но ну­лю. Один из при­ме­ров при­ме­не­ния ве­ро­ят­но­ст­но­го под­хо­да со­сто­ит в сле­дую­щем.

Пусть 𝒢n(p) – слу­чай­ный граф с n вер­ши­на­ми, в ко­то­ром ка­ж­дая па­ра вер­шин не­за­ви­си­мо от ос­таль­ных со­еди­не­на реб­ром с ве­ро­ят­но­стью p (с ве­ро­ят­но­стью q та­ко­го реб­ра нет, p+q=1). В гра­фе

, до­пол­ни­тель­ном к гра­фу 𝒢_n(p), па­ра вер­шин со­еди­не­на реб­ром то­гда и толь­ко то­гда, ко­гда та­ко­го реб­ра нет в 𝒢n(p) . Пусть vn(p,k) и – чис­ла пол­ных под­гра­фов с k вер­ши­на­ми в со­от­вет­ст­вен­но.

Для ма­те­ма­тическихожи­да­ний спра­вед­ли­вы ра­вен­ст­ва

Ес­ли число , где

– би­но­ми­аль­ные ко­эф­фи­ци­ен­ты,

[a] – це­лая часть чис­ла a, то и при n→∞.

След­ст­ви­ем этих со­от­но­шений яв­ля­ет­ся то, что для ка­ж­до­го фик­си­ро­ван­но­го p,0 n су­ще­ст­ву­ет граф Gn(p) c n вер­ши­на­ми, не со­дер­жащий пол­но­го под­гра­фа с бо­лее чем 2ln⁡n/ln⁡(1/p) вер­ши­на­ми, до­пол­нитель­ный граф G¯n(p) ко­то­ро­го не со­дер­жит пол­но­го под­гра­фа с бо­лее чем ln⁡n/ln⁡(1/q) вер­ши­на­ми.

Зна­чи­тель­ное вни­ма­ние в вероятностной комбинаторики уде­ляет­ся ге­не­ра­ции по­сле­до­ва­тель­но­стей слу­чай­ных чи­сел, ге­не­ра­ции слу­чай­ных ком­би­на­тор­ных объ­ек­тов та­ких, как слу­чай­ные под­ста­нов­ки, а так­же ве­ро­ят­ност­но­му ана­ли­зу ал­го­рит­мов и по­строе­нию ве­ро­ят­но­ст­ных ал­го­рит­мов, вклю­чаю­щих в се­бя датчи­ки слу­чай­ных чи­сел.

Вау!! 😲 Ты еще не читал? Это зря!

• Комбинаторная оптимизация
• Теория вероятностей
• перестановки , сочетания , размещения в комбинаторике

Исследование, описанное в статье про вероятностная комбинаторика, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое вероятностная комбинаторика, слу­чай­ные под­ста­но­вки, подстановки в комбинаторика и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.

Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.