Método probabilístico - Probabilistic method

O método probabilístico é um método não construtivo , usado principalmente em combinatória e introduzido por Paul Erdős , para provar a existência de um tipo prescrito de objeto matemático. Ele funciona mostrando que, se alguém escolher aleatoriamente objetos de uma classe especificada, a probabilidade de que o resultado seja do tipo prescrito é estritamente maior do que zero. Embora a prova use probabilidade, a conclusão final é determinada com certeza , sem qualquer erro possível.

Este método agora foi aplicado a outras áreas da matemática , como teoria dos números , álgebra linear e análise real , bem como na ciência da computação (por exemplo, arredondamento aleatório ) e teoria da informação .

Introdução

Se cada objeto em uma coleção de objetos deixar de ter uma determinada propriedade, a probabilidade de que um objeto aleatório escolhido na coleção tenha essa propriedade é zero.

Da mesma forma, mostrar que a probabilidade é (estritamente) menor que 1 pode ser usado para provar a existência de um objeto que não satisfaz as propriedades prescritas.

Outra maneira de usar o método probabilístico é calcular o valor esperado de alguma variável aleatória . Se puder ser mostrado que a variável aleatória pode assumir um valor menor que o valor esperado, isso prova que a variável aleatória também pode assumir algum valor maior que o valor esperado.

Alternativamente, o método probabilístico também pode ser utilizado para garantir a existência de um elemento desejado em um espaço amostral com valor maior ou igual ao valor esperado calculado, uma vez que a inexistência de tal elemento implicaria em todos os elementos do o espaço amostral é menor do que o valor esperado, uma contradição.

As ferramentas comuns usadas no método probabilístico incluem a desigualdade de Markov , o limite de Chernoff e o lema local de Lovász .

Dois exemplos devido a Erdős

Embora outros antes dele tenham provado teoremas através do método probabilístico (por exemplo, o resultado de Szele em 1943 que existem torneios contendo um grande número de ciclos hamiltonianos ), muitas das provas mais conhecidas usando este método são devidas a Erdős. O primeiro exemplo que se segue descreve um tal resultado de 1947, que dá uma prova de um limite inferior para o número de Ramsey $R (r, r)$ .

Primeiro exemplo

Suponha que temos um gráfico completo em $n$ vértices. Queremos mostrar (para valores pequenos o suficiente de $n$ ) que é possível colorir as arestas do gráfico em duas cores (digamos vermelho e azul) de modo que não haja subgráfico completo em $r$ vértices que é monocromático (cada aresta colorida mesma cor).

Para fazer isso, colorimos o gráfico aleatoriamente. Pinte cada aresta independentemente com probabilidade $1/2$ de ser vermelha e $1/2$ de ser azul. Calculamos o número esperado de subgráficos monocromáticos em $r$ vértices da seguinte forma:

Para qualquer conjunto de vértices de nosso gráfico, defina a variável como $1$ se todas as arestas entre os vértices forem da mesma cor e $0$ caso contrário. Observe que o número de subgráficos monocromáticos é a soma de todos os subconjuntos possíveis . Para qualquer conjunto individual , o valor esperado de é simplesmente a probabilidade de que todas as arestas sejam da mesma cor: ${\ displaystyle S_ {r}}$ ${\ displaystyle r}$ ${\ displaystyle X (S_ {r})}$ ${\ displaystyle r}$ ${\ displaystyle r}$ ${\ displaystyle X (S_ {r})}$ ${\ displaystyle S_ {r}}$ ${\ displaystyle S_ {r} ^ {i}}$ ${\ displaystyle X (S_ {r} ^ {i})}$ ${\ displaystyle C (r, 2)}$ ${\ displaystyle S_ {r} ^ {i}}$

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

(o fator de $2$ vem porque há duas cores possíveis).

Isso é verdadeiro para qualquer um dos subconjuntos possíveis que poderíamos ter escolhido, ou seja, varia de $1$ a . Portanto, temos que a soma de tudo é ${\ displaystyle C (n, r)}$ ${\ displaystyle i}$ ${\ displaystyle C (n, r)}$ ${\ displaystyle E [X (S_ {r} ^ {i})]}$ ${\ displaystyle S_ {r} ^ {i}}$

{\ displaystyle \ sum _ {i = 1} ^ {C (n, r)} E [X (S_ {r} ^ {i})] = {n \ escolha r} 2 ^ {1- {r \ escolha 2}}.}

A soma das expectativas é a expectativa da soma ( independentemente de as variáveis serem independentes ), então a expectativa da soma (o número esperado de todos os subgrafos monocromáticos ) é ${\ displaystyle r}$

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

Considere o que acontece se esse valor for menor que $1$ . Uma vez que o número esperado de monocromáticas $r$ -subgraphs é estritamente menor que $1$ , ele deve ser que um específicas satisfaz coloração aleatória que o número de monocromáticas $r$ -subgraphs é estritamente inferior a $1$ . O número de subgrafos monocromáticos $r$ nesta coloração aleatória é um inteiro não negativo, portanto, deve ser $0$ ( $0$ é o único inteiro não negativo menor que $1$ ). Segue-se que se

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

(que é válido, por exemplo, para $n$ = 5 $er$ = 4), deve existir uma coloração na qual não haja $r$ -subgrafos monocromáticos .

Por definição do número de Ramsey , isso implica que $R (r, r)$ deve ser maior que $n$ . Em particular, $R (r, r)$ deve crescer pelo menos exponencialmente com $r$ .

Uma peculiaridade desse argumento é que ele é totalmente não construtivo . Mesmo que prove (por exemplo) que quase todas as cores do grafo completo em $(1.1) r$ vértices não contém nenhum subgrafo $r$ monocromático , não dá nenhum exemplo explícito de tal coloração. O problema de encontrar tal coloração está em aberto há mais de 50 anos.

Segundo exemplo

Uma 1959 papel de Erdős (ver referências citadas abaixo) apresentou o seguinte problema em teoria gráfico : dado inteiros positivos $g$ e $k$ , não existe um gráfico $G$ contendo apenas ciclos de comprimento, pelo menos, $g$ , de tal modo que o número cromático de $L$ é a pelo menos $k$ ?

Pode-se demonstrar que existe um tal gráfico para qualquer $g$ e $k$ , e a prova é razoavelmente simples. Seja $n$ muito grande e considere um grafo aleatório $G$ em $n$ vértices, onde toda aresta em $G$ existe com probabilidade $p = n 1 / g -1$ . Mostramos que, com probabilidade positiva, $G$ satisfaz as duas propriedades a seguir:

Propriedade 1.

G

contém no máximo

n / 2

ciclos de comprimento menor que

g

.

Prova. Seja $X$ o número de ciclos de comprimento menor que $g$ . O número de ciclos de comprimento $i$ no gráfico completo em $n$ vértices é

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

e cada um deles está presente em $G$ com probabilidade $p i$ . Portanto, pela desigualdade de Markov , temos

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

Assim, para

n

suficientemente grande , a propriedade 1 é válida com uma probabilidade de mais de

1/2

.

Propriedade 2.

G

não contém nenhum conjunto independente de tamanho .

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

Prova. Deixe que $Y$ seja o tamanho do maior conjunto independente em $L$ . Claramente, nós temos

{\ displaystyle \ Pr (Y \ geq y) \ leq {n \ escolher 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),}

quando

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

Assim, para

n

suficientemente grande , a propriedade 2 é válida com uma probabilidade de mais de

1/2

.

Para $n$ suficientemente grande , a probabilidade de que um gráfico da distribuição tenha ambas as propriedades é positiva, pois os eventos para essas propriedades não podem ser disjuntos (se fossem, suas probabilidades somariam mais de 1).

Aí vem o truque: como $G$ tem essas duas propriedades, podemos remover no máximo $n / 2$ vértices de $G$ para obter um novo grafo $G '$ em vértices que contém apenas ciclos de comprimento de pelo menos $g$ . Podemos ver que este novo gráfico não possui um conjunto independente de tamanho . $G '$ só pode ser particionado em pelo menos $k$ conjuntos independentes e, portanto, tem número cromático de pelo menos $k$ . ${\ displaystyle n '\ geq n / 2}$ ${\ displaystyle \ left \ lceil {\ frac {n '} {k}} \ right \ rceil}$

Este resultado dá uma dica de por que o cálculo do número cromático de um gráfico é tão difícil: mesmo quando não há razões locais (como pequenos ciclos) para um gráfico exigir muitas cores, o número cromático ainda pode ser arbitrariamente grande.

Veja também

Referências

Alon, Noga; Spencer, Joel H. (2000). O método probabilístico (2ed). Nova York: Wiley-Interscience. ISBN 0-471-37046-0 .
Erdős, P. (1959). "Teoria e probabilidade de grafos" . Lata. J. Math . 11 : 34–38. doi : 10.4153 / CJM-1959-003-9 . MR 0102081 .
Erdős, P. (1961). "Teoria e probabilidade de grafos, II" . Lata. J. Math . 13 : 346–352. CiteSeerX 10.1.1.210.6669 . doi : 10.4153 / CJM-1961-029-9 . MR 0120168 .
J. Matoušek , J. Vondrak. O Método Probabilístico . Notas da aula.
Alon, N e Krivelevich, M (2006). Combinatória Extrema e Probabilística
Elishakoff I., Probabilistic Methods in the Theory of Structures: Random Strength of Materials, Random Vibration, and Buckling, World Scientific, Singapura, ISBN 978-981-3149-84-7 , 2017
Elishakoff I., Lin YK e Zhu LP, Probabilistic and Convex Modeling of Acoustically Excited Structures, Elsevier Science Publishers, Amsterdam, 1994, VIII + pp. 296; ISBN 0 444 81624 0

Languages

In other projects