Considere um grafo com n vértices numerados de 1 a n e suponha que, entre cada um dos n 2 pares de vértices distintos, uma borda esteja presente com probabilidade p. O grau do vértice i, designado como D i , corresponde ao número de bordas que tem o vértice i como um de seus vértices.

(a) Qual é a distribuição de D i ?

(b) Determine p ( D i , D j )   , a correlação entre D i e D j .

Passo 1

Salve galera estudiosa, tudo certin??

Vamos para mais um problema de Probabilidade.

Afinal, o que são grafos?

É uma estrutura composta por um conjunto de pontos (vértices) e um conjunto de bordas que ligam esses pontos (arestas). Num grafo, entre dois vértices quaisquer pode haver ou não uma aresta e o grau de um vértice é definido como o número de arestas presentes naquele vértice. Como nas figuras abaixo:

a) Nosso primeiro questionamento é de certo modo muito intuitivo, vejamos:

Em um grafo com n vértices, dado um vértice i pode haver nele uma aresta com qualquer um dos demais n-1 vértices restantes de modo independente e com a mesma probabilidade p, temos que. Essa é uma característica própria da função binomial.

Podemos concluir que então:

D i ~ B i n o m i a l ( n - 1 , p )

Passo 2

b) Vamos definir as variáveis aleatórias V i k   que irá indicar se existe uma aresta entre o vértice i e o vértice k e V j k que irá indicar, da mesma forma, se há aresta entre os vértices j e k. Então:

D i =   ∑ k = 1 n - 1 V i k       e       D j =   ∑ k = 1 n - 1 V j k  

Analisando a covariância entre D i e D j , temos, por definição que:

C o v D i ,   D j = C o v   ∑ k = 1 n - 1 V i k , ∑ k = 1 n - 1 V j k =   ∑ k = 1 n - 1 V a r ( V i k ) + 2 ∑ k = 1 n - 1 ∑ l = 1 n - 1 C o v V i k ,   V j l =

Por propriedade de covariância, temos que C o v V i k ,   V j l = 0 já que as variáveis são independentes.

E por se tratar de uma distribuição binomial temos que: V a r ( V i k ) = p ( 1 - p )

Logo, C o v D i ,   D j = p ( 1 - p )

Finalmente, a correlação entre as variáveis é dada por:

r =   C o v D i ,   D j V a r D i

Onde, na distribuição binomial V a r D i = ( n - 1 ) . p . ( 1 - p )   , assim:

r =   p ( 1 - p ) ( n - 1 ) . p . ( 1 - p )

Simplificando:

r =   1 n - 1

Resposta

a) Distribuição Binomial ( n - 1 , p )

b) Correlação: r =   1 n - 1