Método provabilístic

En matemàtiques, el método provabilístic és un procediment no constructiu, utilisat principalment en combinatòria i desenrollat per Paul Erdős, per a demostrar l'existència d'un tipo prescrit d'objecte matemàtic.^[1] Funciona provant que, si s'elegixen aleatoriamente objectes d'una classe específica, la provabilitat de que el resultat siga del tipo prescrit és estrictament major que zero. Encara que la demostració utilisa provabilitat, la conclusió final es determina en certea, sense possibilitat d'error.

Este método s'ha aplicat a atres àrees de les matemàtiques, com la teoria de números, l'àlgebra llineal i l'anàlisis real, aixina com en ciències de la computació (com per eixemple, en el grosseig aleatori) i en la teoria de l'informació.

Introducció

Si cap objecte d'una colecció posseïx una propietat determinada, la provabilitat de que un objecte elegit aleatoriamente posseïxca dita propietat és zero. Per lo tant, per mig de contraposició llògica, si la provabilitat de que un objecte aleatori elegit del conjunt posseïxca eixa propietat és distinta de zero, llavors algun objecte del conjunt deu posseir-la.

D'igual manera, demostrar que la provabilitat és (estrictament) menor que 1 pot utilisar-se per a demostrar l'existència d'un objecte que no satisfà les propietats prescrites.

Una atra forma d'utilisar el método provabilístic és calculant el valor esperat d'alguna variable aleatòria. Si es pot demostrar que la variable aleatòria pot prendre un valor menor que el valor esperat, açò demostra que la variable aleatòria també pot prendre un valor major que el valor esperat.

Alternativament, el método provabilístic també pot utilisar-se per a garantisar l'existència d'un element desijat en un espai mostral en un valor major o igual que el valor esperat calculat, ya que l'inexistència de dit element implicaria que tots els elements de l'espai mostral són menors que el valor esperat, lo que constituïx una contradicció.

Les ferramentes comunes utilisades en el método provabilístic inclouen la desigualtat de Márkov, les cotes de Chernoff^[2] i el lema local de Lovász.

Dos eixemples deguts a Erdös

Encara que atres matemàtics varen demostrar abans que Erdős teoremas per mig del método provabilístic (com per eixemple, el resultat de Szele de 1943 de que en teoria de grafos existixen tornejos que contenen un gran número de cicles hamiltonianos), moltes de les demostracions més conegudes que utilisen este método es deuen a Erdös. El primer eixemple a continuació descriu un resultat de 1947 que proporciona una demostració d'una cota inferior per al número de Ramsey $R (r, r)$ .

Primer eixemple

Suponga's que es té un grafo complet sobre $n$ vèrtiços. Es vol demostrar (per a valors suficientment chicotets de $n$ ) que és possible colorear les arestes del grafo en dos colors (per eixemple, roig i blau) de modo que no existixca un subgrafo complet sobre $r$ vèrtiços que siga monocromàtic (cada aresta coloreada del mateix color).

Per a això, es colorea el grafo aleatoriamente, cada aresta independentment en la provabilitat $1/2$ de ser roig i de $1/2$ de ser blau. Ara, es calcula el número esperat de subgrafos monocromàtics sobre $r$ vèrtiços de la següent manera:

Per a qualsevol conjunt $S_{r}$ de $r$ vèrtiços del grafo analisat, definixca's la variable $X (S_{r})$ com $1$ si totes les arestes entre els $r$ vèrtiços són del mateix color, i com $0$ en cas contrari. Note's que el número de subgrafos $r$ monocromàtics és la suma de $X (S_{r})$ sobre tots els $S_{r}$ subconjunts possibles. Per a qualsevol conjunt $S_{r}^{i}$ , el valor esperat de $X (S_{r}^{i})$ és simplement la provabilitat de que totes les arestes $C (r, 2)$ en $S_{r}^{i}$ siguen del mateix color:

E [X (S_{r}^{i})] = 2 \cdot 2^{- (\binom{r}{2})}

(el factor $2$ s'obté perque hi ha dos colors possibles).

Açò és vàlit per a qualsevol dels subconjunts $C (n, r)$ possibles que es pogueren haver elegit, és dir, $i$ va de $1$ a $C (n, r)$ . Aixina, la suma de $E [X (S_{r}^{i})]$ sobre tots els $S_{r}^{i}$ és:

\sum_{i = 1}^{C (n, r)} E [X (S_{r}^{i})] = (\binom{n}{r}) 2^{1 - (\binom{r}{2})} .

La suma de les expectatives és l'esperança de la suma (independentment de si les variables són independents), per lo que l'esperança de la suma (el número esperat de tots els subgrafos $r$ monocromàtics) és:

E [X (S_{r})] = (\binom{n}{r}) 2^{1 - (\binom{r}{2})} .

Considere's qué succeïx si este valor és menor que $1$ . Ya que el número esperat de $r$ subgrafos monocromàtics és estrictament menor que $1$ , existix una coloració que complix la condició de que el número de $r$ subgrafos monocromàtics siga estrictament menor que $1$ . El número de subgrafos $r$ monocromàtics en esta coloració aleatòria és un número entero no negatiu. Per lo tant, deu ser $0$ ( $0$ és l'únic sancer no negatiu menor que $1$ ). D'això es deduïx que si

E [X (S_{r})] = (\binom{n}{r}) 2^{1 - (\binom{r}{2})} < 1

(la qual cosa es complix, per eixemple, per a $n = 5$ i $r = 4$ ), deu existir una coloració en la que no hi haja $r$ subgrafos monocromàtics.

Segons el teorema de Ramsey, açò implica que $R (r, r)$ deu ser major que $n$ . En particular, $R (r, r)$ deu créixer a lo manco exponencialment en $r$ .

Una debilitat d'este argument és que és completament no constructiu. Si ben prova (per eixemple) que casi cap coloració del grafo complet en els vèrtiços de $(1.1) r$ conté cap $r$ subgrafo monocromàtic, no oferix un eixemple explícit de dita coloració. El problema de trobar dita coloració ha estat obert durant més de 50 anys.

Segon eixemple

Un artícul de Erdős de 1959 (vore la referència citada més avall) va abordar el següent problema en teoria de grafos: donats els sancers positius $g$ i $k$ , ¿existix un grafo $G$ que continga sol cicles en una llongitut d'a lo manco $g$ , tal que el número cromàtic de $G$ siga a lo manco $k$ ?

Es pot demostrar que dit grafo existix per a qualsevol $g$ i $k$ , i la demostració és prou senzilla. Siga $n$ molt gran i considere's un grafo aleatori $G$ en $n$ vèrtiços, a on cada aresta en $G$ existix en provabilitat $p = n 1/ g -1$ . Es demostra que, en provabilitat positiva, $G$ satisfà les dos propietats següents:

<o>Propietat 1:</o> $G$ conté com a màxim $n /2$ cicles de llongitut menor que $g$ .

Demostració: siga

X

el número de cicles de llongitut menor que

g

. El número de cicles de llongitut

i

en el grafo complet en vèrtiços

n

és

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

i cada u d'ells està present en

G

en provabilitat

p i

. Per lo tant, per la desigualtat de Márkov, es té que

\Pr (X > \frac{n}{2}) \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}} = g n^{- \frac{1}{g}} = o (1) .

Per lo tant, per a un

n

suficientment gran, la propietat 1 es complix en una provabilitat major que

1/2

.

<o>Propietat 2:</o> $G$ no conté cap conjunt independent de tamany $⌈ \frac{n}{2 k} ⌉$ .

Demostració: siga

I

el tamany del major conjunt independent en

G

. Clarament, es té que

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

quan

y = ⌈ \frac{n}{2 k} ⌉ .

Per lo tant, per a un

n

suficientment gran, la propietat 2 es complix en una provabilitat major que

1/2

.

Per a un $n$ suficientment gran, la provabilitat de que un grafo de la distribució tinga abdós propietats és positiva, ya que els events per a estes propietats no poden ser disjuntos (si ho anaren, les seues provabilitats sumarien més d'1).

Ací ve el truc: com $G$ té estes dos propietats, es pot eliminar com a màxim $n /2$ vèrtiços de $G$ per a obtindre un nou grafo $G'$ sobre $n^{'} \geq n / 2$ vèrtiços que continga sol cicles de llongitut a lo manco $g$ . Es pot vore que este nou grafo no té un conjunt independent de tamany $⌈ \frac{n^{'}}{k} ⌉$ . $G'$ solament es pot dividir en a lo manco $k$ conjunts independents i, per lo tant, té un número cromàtic a lo manco $k$ .

Este resultat dona una pista de per qué el càlcul del número cromàtic d'un grafo és tan difícil: inclús quan no existixen raons locals (com a cicles menuts) per a que un grafo requerixca molts colors, el número cromàtic pot ser arbitrariamente gran.

Vore també

Referències

↑ Noga Alon, Joel H. Spencer (2004). The Probabilistic Method, John Wiley & Sons, pp. 3 de 328. ISBN 9780471653981.
↑ G. V. Chernov (2004). Inference and Anticipation in Simultaneous Interpreting: A Probability-prediction Model, John Benjamins Publishing, pp. 266. ISBN 9789027216632.

Bibliografia

Alon, Noga; Spencer, Joel H. (2000). The probabilistic method (2ed). New York: Wiley-Interscience. ISBN 0-471-37046-0.
Erdős, P.. “Graph theory and probability”. Ca. J. Math. 11: 34–38. doi:10.4153/CJM-1959-003-9.
Erdős, P.. “Graph theory and probability, II”. Ca. J. Math. 13: 346–352. doi:10.4153/CJM-1961-029-9.
J. Matoušek, J. Vondrak. The Probabilistic Method. Lecture notes.
Alon, N and Krivelevich, M (2006). Extremal and Probabilistic Combinatorics
Elishakoff I., Probabilistic Methods in the Theory of Structures: Random Strength of Materials, Random Vibration, and Buckling, World Scientific, Singapore, ISBN 978-981-3149-84-7, 2017
Elishakoff I., Lin Y.K. and Zhu L.P., Probabilistic and Convex Modeling of Acoustically Excited Structures, Elsevier Science Publishers, Amsterdam, 1994, VIII + pp. 296; ISBN 0 444 81624 0

Referències

Este artícul conté una traducció derivada de «Método probabilístico» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[NAJHS-1] Noga Alon, Joel H. Spencer (2004). The Probabilistic Method, John Wiley & Sons, pp. 3 de 328. ISBN 9780471653981.

[GVC-2] G. V. Chernov (2004). Inference and Anticipation in Simultaneous Interpreting: A Probability-prediction Model, John Benjamins Publishing, pp. 266. ISBN 9789027216632.

[1]

[2]