Dovadă probabilistică

O dovadă probabilistică , sau o metodă probabilistică , este o tehnică de dovadă matematică non-constructivă a existenței certe a unui obiect matematic prin considerații probabiliste.

Metoda a fost introdusă de Paul Erdős și este aplicată în combinatorică , teoria numerelor , algebra liniară , analiză și în alte discipline aplicate, precum informatica sau teoria informației .

În general, profită de faptul că dacă toate obiectele dintr-un set nu au o anumită proprietate, probabilitatea ca un obiect ales aleatoriu din set să satisfacă acea proprietate este zero. Dacă probabilitatea este strict mai mică decât una, cu siguranță cel puțin unul dintre obiectele din set nu satisface proprietatea. Luând în considerare în schimb valoarea așteptată a unei variabile aleatorii , dacă se arată că variabila poate asuma o valoare mai mică decât valoarea așteptată, atunci trebuie să își asume și o valoare mai mare decât ea.

Exemple de Erdős

Mai multe dintre cele mai cunoscute rezultate obținute cu aplicarea metodei probabilistice au fost obținute de Erdős, chiar dacă unii matematicieni au folosit deja tehnici similare anterior (de exemplu, dovada lui Szele din 1943 a existenței turneelor care conțin un număr mare de cicluri hamiltoniene ).

Primul exemplu

Având un grafic complet cu $n$ ${\ displaystyle n}$ $n$ vârfuri, vrem să dovedim că pentru valorile de $n$ ${\ displaystyle n}$ $n$ suficient de mic este posibil să colorați arcurile graficului cu două culori (de exemplu roșu și albastru) astfel încât să nu existe niciun subgraf complet cu $r$ ${\ displaystyle r}$ $r$ vârfurile sunt monocromatice.

Pentru a face acest lucru, culoarea se arcuiește aleatoriu, cu probabilitatea ^_1/2 să fie roșu sau albastru. Valoarea așteptată a subgrafelor monocromatice este calculată cu $r$ ${\ displaystyle r}$ $r$ vârfuri:

Pentru fiecare set $S.$ ${\ displaystyle S}$ $S.$ din $r$ ${\ displaystyle r}$ $r$ vârfurile grafului, variabila este definită $X(S)$ ${\ displaystyle X (S)}$ ${\ displaystyle X (S)}$ care ia valoarea 1 dacă toate arcele din S sunt de aceeași culoare, 0 altfel. Numărul de grafice monocromatice este dat de sumă $\sum _{S}X(S)$ ${\ displaystyle \ sum _ {S} X (S)}$ ${\ displaystyle \ sum _ {S} X (S)}$ pentru fiecare posibil subgraf. Pentru fiecare $S.$ ${\ displaystyle S}$ $S.$ , valoarea așteptată a $X(S)$ ${\ displaystyle X (S)}$ ${\ displaystyle X (S)}$ este probabilitatea ca toate ${r \choose 2}$ ${\ displaystyle {r \ choose 2}}$ ${\ displaystyle {r \ choose 2}}$ arcuri în $S.$ ${\ displaystyle S}$ $S.$ sunt de aceeași culoare

2\cdot 2^{-{r \choose 2}}

{\ displaystyle 2 \ cdot 2 ^ {- {r \ choose 2}}}

{\ displaystyle 2 \ cdot 2 ^ {- {r \ choose 2}}}

(factorul 2 depinde de faptul că există două culori posibile).

Acest lucru este valabil pentru fiecare subset posibil, deci suma din $S.$ ${\ displaystyle S}$ $S.$ a valorilor așteptate $E[X(S)]$ ${\ displaystyle E [X (S)]}$ ${\ displaystyle E [X (S)]}$ Și

{n \choose r}2^{1-{r \choose 2}}.

{\ displaystyle {n \ choose r} 2 ^ {1- {r \ choose 2}}.}

{\ displaystyle {n \ choose r} 2 ^ {1- {r \ choose 2}}.}

Pentru independența variabilelor aleatorii, valoarea așteptată este liniară în raport cu suma, deci valoarea așteptată a sumei (care este valoarea așteptată a graficelor monocromatice cu $r$ ${\ displaystyle r}$ $r$ vârfuri) este

{n \choose r}2^{1-{r \choose 2}}.

{\ displaystyle {n \ choose r} 2 ^ {1- {r \ choose 2}}.}

{\ displaystyle {n \ choose r} 2 ^ {1- {r \ choose 2}}.}

Dacă această valoare ar fi mai mică de 1, deoarece numărul de subgrafe monocromatice trebuie să fie întreg, cel puțin o culoare ar trebui să ia o valoare mai mică decât valoarea așteptată. Singurul număr întreg care îndeplinește această condiție este 0, deci dacă

{n \choose r}<2^{{r \choose 2}-1},

{\ displaystyle {n \ choose r} <2 ^ {{r \ choose 2} -1},}

{\ displaystyle {n \ choose r} <2 ^ {{r \ choose 2} -1},}

(care deține, de exemplu, pentru $n=5$ ${\ displaystyle n = 5}$ ${\ displaystyle n = 5}$ Și $r=4$ ${\ displaystyle r = 4}$ ${\ displaystyle r = 4}$ ) apoi o anumită colorare îndeplinește criteriul cerut. ^[1]

Prin definiția numărului Ramsey , acest lucru înseamnă că $R(r,r)>n$ ${\ displaystyle R (r, r)> n}$ ${\ displaystyle R (r, r)> n}$ , în special $R(r,r)$ ${\ displaystyle R (r, r)}$ ${\ displaystyle R (r, r)}$ crește cel puțin exponențial în ceea ce privește $r$ ${\ displaystyle r}$ $r$ .

O particularitate a acestei demonstrații este că este total non-constructivă , iar problema construirii unei astfel de colorări a rămas deschisă de peste 50 de ani.

Al doilea exemplu

O lucrare din 1959 a lui Erdős a rezolvat următoarea problemă a teoriei graficelor: date două numere întregi pozitive $g$ ${\ displaystyle g}$ $g$ Și $k$ ${\ displaystyle k}$ $k$ , există un grafic $G.$ ${\ displaystyle G}$ $G.$ care conține doar bucle de cel puțin lungime $g$ ${\ displaystyle g}$ $g$ astfel încât numărul cromatic al $G.$ ${\ displaystyle G}$ $G.$ fii măcar $k$ ${\ displaystyle k}$ $k$ ?

Se arată că există un astfel de grafic pentru fiecare $g$ ${\ displaystyle g}$ $g$ Și $k$ ${\ displaystyle k}$ $k$ . Este $n$ ${\ displaystyle n}$ $n$ un număr suficient de mare și ia în considerare un grafic aleatoriu $G.$ ${\ displaystyle G}$ $G.$ cu $n$ ${\ displaystyle n}$ $n$ vârfuri, unde fiecare arc $G.$ ${\ displaystyle G}$ $G.$ probabil că există $p=n^{{\frac {1}{g}}-1}$ ${\ displaystyle p = n ^ {{\ frac {1} {g}} - 1}}$ ${\ displaystyle p = n ^ {{\ frac {1} {g}} - 1}}$ . Se afișează următoarele proprietăți:

Proprietatea 1.

G.

{\ displaystyle G}

G.

conține cel mult

{\frac {n}{2}}

{\ displaystyle {\ frac {n} {2}}}

{\ displaystyle {\ frac {n} {2}}}

cicluri mai mici de

g

{\ displaystyle g}

g

.

Demonstrație. Este $X$ ${\ displaystyle X}$ $X$ numărul de bucle mai mic de $g$ ${\ displaystyle g}$ $g$ . Numărul de bucle în lungime $the$ ${\ displaystyle i}$ $the$ în graficul complet al $n$ ${\ displaystyle n}$ $n$ vârfurile este

{\frac {n!}{2\cdot i\cdot (n-i)!}}\leq {\frac {n^{i}}{2}}

{\ displaystyle {\ frac {n!} {2 \ cdot i \ cdot (ni)!}} \ leq {\ frac {n ^ {i}} {2}}}

{\ displaystyle {\ frac {n!} {2 \ cdot i \ cdot (n-i)!}} \ leq {\ frac {n ^ {i}} {2}}}

și fiecare dintre ei este prezent în $G.$ ${\ displaystyle G}$ $G.$ cu probabilitate $p^{i}$ ${\ displaystyle p ^ {i}}$ ${\ displaystyle p ^ {i}}$ . Pentru inegalitatea Markov pe care o avem

\Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}E[X]\leq {\frac {1}{n}}\sum _{i=3}^{g-1}p^{i}n^{i}={\frac {1}{n}}\sum _{i=3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}n^{\frac {g-1}{g}}\leq gn^{-{\frac {1}{g}}}=o(1).

{\ displaystyle \ Pr \ left (X> {\ tfrac {n} {2}} \ right) \ leq {\ frac {2} {n}} E [X] \ leq {\ frac {1} {n} } \ sum _ {i = 3} ^ {g-1} p ^ {i} n ^ {i} = {\ frac {1} {n}} \ sum _ {i = 3} ^ {g-1} n ^ {\ frac {i} {g}} \ leq {\ frac {g} {n}} n ^ {\ frac {g-1} {g}} \ leq gn ^ {- {\ frac {1} {g}}} = o (1).}

{\ displaystyle \ Pr \ left (X> {\ tfrac {n} {2}} \ right) \ leq {\ frac {2} {n}} E [X] \ leq {\ frac {1} {n} } \ sum _ {i = 3} ^ {g-1} p ^ {i} n ^ {i} = {\ frac {1} {n}} \ sum _ {i = 3} ^ {g-1} n ^ {\ frac {i} {g}} \ leq {\ frac {g} {n}} n ^ {\ frac {g-1} {g}} \ leq gn ^ {- {\ frac {1} {g}}} = o (1).}

Proprietatea 2.

G.

{\ displaystyle G}

G.

nu conțineseturi independente de dimensiuni

\lceil {\tfrac {n}{2k}}\rceil

{\ displaystyle \ lceil {\ tfrac {n} {2k}} \ rceil}

{\ displaystyle \ lceil {\ tfrac {n} {2k}} \ rceil}

.

Demonstrație. Este $Da$ ${\ displaystyle Y}$ $Da$ dimensiunea celui mai mare set independent din $G.$ ${\ displaystyle G}$ $G.$ . Da, da

\Pr(Y\geq y)\leq {n \choose y}(1-p)^{\frac {y(y-1)}{2}}\leq n^{y}e^{-{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln n-p)}=o(1),

{\ displaystyle \ Pr (Y \ geq y) \ leq {n \ choose y} (1-p) ^ {\ frac {y (y-1)} {2}} \ leq n ^ {y} e ^ { - {\ frac {py (y-1)} {2}}} = e ^ {- {\ frac {y} {2}} \ cdot (py-2 \ ln np)} = o (1),}

{\ displaystyle \ Pr (Y \ geq y) \ leq {n \ choose y} (1-p) ^ {\ frac {y (y-1)} {2}} \ leq n ^ {y} e ^ { - {\ frac {py (y-1)} {2}}} = e ^ {- {\ frac {y} {2}} \ cdot (py-2 \ ln np)} = o (1),}

cand

y=\left\lceil {\frac {n}{2k}}\right\rceil .

{\ displaystyle y = \ left \ lceil {\ frac {n} {2k}} \ right \ rceil.}

{\ displaystyle y = \ left \ lceil {\ frac {n} {2k}} \ right \ rceil.}

Atâta timp cât $G.$ ${\ displaystyle G}$ $G.$ se bucură de aceste două proprietăți, pot fi eliminate cel mult ${\frac {n}{2}}$ ${\ displaystyle {\ frac {n} {2}}}$ ${\ displaystyle {\ frac {n} {2}}}$ vârfuri din $G.$ ${\ displaystyle G}$ $G.$ obținerea unui nou grafic ${G.}^{'}$ ${\ displaystyle G '}$ ${\ displaystyle G '}$ cu $n'\geq n/2$ ${\ displaystyle n '\ geq n / 2}$ ${\ displaystyle n '\ geq n / 2}$ vârfuri care conțin doar bucle de cel puțin lungime $g$ ${\ displaystyle g}$ $g$ . Se observă că acest nou grafic nu are seturi independente de dimensiuni $\lceil {\frac {n'}{k}}\rceil$ ${\ displaystyle \ lceil {\ frac {n '} {k}} \ rceil}$ ${\ displaystyle \ lceil {\ frac {n '} {k}} \ rceil}$ . ${G.}^{'}$ ${\ displaystyle G '}$ ${\ displaystyle G '}$ poate fi partiționat cel puțin în cel puțin $k$ ${\ displaystyle k}$ $k$ seturi independente și, prin urmare, are un număr cromatic egal cu cel puțin $k$ ${\ displaystyle k}$ $k$ .

Acest rezultat arată de ce calculul numărului cromatic al unui grafic este atât de dificil: chiar dacă nu există caracteristici locale (cum ar fi cicluri mici) care necesită un număr mare de culori, numărul cromatic poate fi în mod arbitrar mare.

Notă

^ Același fapt poate fi dovedit fără a utiliza probabilitatea, folosind un argument de numărare:
- Numărul total de subgrafe r este ${n \choose r}$ ${\ displaystyle {n \ alege r}}$ ${n \ alegeți r}$ .
- Fiecare r -subgraf are ${r \choose 2}$ ${\ displaystyle {r \ choose 2}}$ ${\ displaystyle {r \ choose 2}}$ arcuri și, prin urmare, pot fi colorate în $2^{r \choose 2}$ ${\ displaystyle 2 ^ {r \ alege 2}}$ ${\ displaystyle 2 ^ {r \ alege 2}}$ căi diferite.
- Dintre aceste culori, doar 2 sunt monocromatice (cele cu toate vârfurile roșii sau albastre).
- Astfel, numărul total de culori monocromatice pentru toate subgrafele este cel mult $2{n \choose r}$ ${\ displaystyle 2 {n \ alegeți r}}$ ${\ displaystyle 2 {n \ alegeți r}}$ .
- Astfel, dacă $2^{r \choose 2}>2{n \choose r}$ ${\ displaystyle 2 ^ {r \ alege 2}> 2 {n \ alege r}}$ ${\ displaystyle 2 ^ {r \ alege 2}> 2 {n \ alege r}}$ , trebuie să existe cel puțin o colorare non-monocromatică pentru fiecare subgraf.

Bibliografie

Alon, Noga; Spencer, Joel H. (2000). Metoda probabilistică (2ed). New York: Wiley-Interscience. ISBN 0-471-37046-0 .
Erdős, P., Teoria și probabilitatea graficelor ( PDF ), în Canad. J. Math. , vol. 11, n. 0, 1959, pp. 34–38, DOI : 10.4153 / CJM-1959-003-9 , MR 0102081 . Adus la 24 iulie 2016 (arhivat din original la 18 iulie 2011) .
Erdős, P., Teoria grafică și probabilitatea, II ( PDF ), în Canad. J. Math. , vol. 13, n. 0, 1961, pp. 346–352, DOI : 10.4153 / CJM-1961-029-9 , MR 0120168 . Adus la 24 iulie 2016 (arhivat din original la 18 iulie 2011) .
J. Matoušek , J. Vondrak. Metoda probabilistică . Note de curs.
Alon, N și Krivelevich, M (2006). Combinatorie extremă și probabilistică

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Același fapt poate fi dovedit fără a utiliza probabilitatea, folosind un argument de numărare:
Numărul total de subgrafe r este ${n \choose r}$ ${\ displaystyle {n \ alege r}}$ ${n \ alegeți r}$ .
Fiecare r -subgraf are ${r \choose 2}$ ${\ displaystyle {r \ choose 2}}$ ${\ displaystyle {r \ choose 2}}$ arcuri și, prin urmare, pot fi colorate în $2^{r \choose 2}$ ${\ displaystyle 2 ^ {r \ alege 2}}$ ${\ displaystyle 2 ^ {r \ alege 2}}$ căi diferite.
Dintre aceste culori, doar 2 sunt monocromatice (cele cu toate vârfurile roșii sau albastre).
Astfel, numărul total de culori monocromatice pentru toate subgrafele este cel mult $2{n \choose r}$ ${\ displaystyle 2 {n \ alegeți r}}$ ${\ displaystyle 2 {n \ alegeți r}}$ .
Astfel, dacă $2^{r \choose 2}>2{n \choose r}$ ${\ displaystyle 2 ^ {r \ alege 2}> 2 {n \ alege r}}$ ${\ displaystyle 2 ^ {r \ alege 2}> 2 {n \ alege r}}$ , trebuie să existe cel puțin o colorare non-monocromatică pentru fiecare subgraf.

[2] Numărul total de subgrafe r este ${n \choose r}$ ${\ displaystyle {n \ alege r}}$ ${n \ alegeți r}$ .

[3] Fiecare r -subgraf are ${r \choose 2}$ ${\ displaystyle {r \ choose 2}}$ ${\ displaystyle {r \ choose 2}}$ arcuri și, prin urmare, pot fi colorate în $2^{r \choose 2}$ ${\ displaystyle 2 ^ {r \ alege 2}}$ ${\ displaystyle 2 ^ {r \ alege 2}}$ căi diferite.

[4] Dintre aceste culori, doar 2 sunt monocromatice (cele cu toate vârfurile roșii sau albastre).

[5] Astfel, numărul total de culori monocromatice pentru toate subgrafele este cel mult $2{n \choose r}$ ${\ displaystyle 2 {n \ alegeți r}}$ ${\ displaystyle 2 {n \ alegeți r}}$ .

[6] Astfel, dacă $2^{r \choose 2}>2{n \choose r}$ ${\ displaystyle 2 ^ {r \ alege 2}> 2 {n \ alege r}}$ ${\ displaystyle 2 ^ {r \ alege 2}> 2 {n \ alege r}}$ , trebuie să existe cel puțin o colorare non-monocromatică pentru fiecare subgraf.

[1]