Intuitions

Je pense que pour une probabilité fixée, plus le nombre de sommets du graphe est important moins la proportion de sommets isolés est importante car chaque sommet a plus de voisins pour former des arêtes. Mais ici le probabilité est (c+log(n))/n, c’est une fonction decroissante de n ce qui viendrait contrebalancer ceci, de plus cette probabilité n’est pas très simple et donc j’ai du mal à imaginer ce que ça va donner.

Concernant la convergence vers la loi de poisson, cela ne m’etonne pas car la loi de poisson est souvent utilisée pour modéliser la survenue d’évènements rares (ici la probabilité p devient faible quand n est grand).

Je n’ai pas vraiment d’intutions sur la suite de l’exercice.

Question 1

On cherche l’espérance d’une variable aléatoire comptant le nombre de sommets isolés dans un graphe d’Erdös-Renyi G(n, p) avec n tends vers l’infini et p = (constance+log(n))/n. La fonction suivante crée un tel graphe et compte le nombre de sommets isolés.

set.seed(10);

nb_isoles<-function(n,c){
  p = (c+log(n))/n
  aretes = rbinom(n*n,1,p) # tirage aléatoire des arêtes suivant une loi de Bernoulli de paramètre p
  A = matrix(data = aretes, nrow = n) # création de la matrice d'incidence du grahpe correspondant
  X1 = matrix(data = rep(T,n), nrow=n) # ensemble des sommets du graphe
  X2 = ((A %*% X1) == 0) # ensemble des sommets isolés
  X2
  as.vector(X2)
  sum(X2) # retourne le nombre de sommets isolés du graphe
}

Pour trouver l’espérance, on répète un grand nombre de fois l’expérience et on prend une valeur moyenne. On prend une grande valeur pour n car n doit tendre vers l’infini (ici n=1000), on prend c=-3 pour avoir un résultat pas trop proche de 0 et on répète l’expérience 1000 fois pour avoir une mesure assez précise.

c = -3;
mean(mapply(nb_isoles,rep(1000,1000),rep(c,1000)))
## [1] 19.96

En moyenne, on trouve un nombre de sommets isolés proche de exp(3)=20.086. On a donc montré que E(points isolés de G(n,(c + log(n))/n)) —> e^(-c) quand n tends vers l’infini.

Démontrons le résultat précedent.

Un sommet est isolé si aucunes des (n-1) arêtes possibles avec les (n-1) autres sommets n’a été tirée. La probabilité qu’une arête ne soit pas tirée est 1-p = 1-(c+log(n))/n. Les tirages des arêtes sont indépendants donc la probabilité qu’un point soit isolé est (1-(c+log(n))/n)^(n-1). La variable aléatoire qui compte le nombre de points isolés suit une loi binomiale de paramètres n et (1-(c+log(n))/n)^(n-1), son espérance est n(1-(c+log(n))/n)^(n-1). En passant à la limite sachant que limite quand n tends vers l’infini de (1+a/n)^n = e(a) on obtient E(points isolés) = nexp(-c-log(n)) = nexp(-c)exp(-log(n)) = nexp(-c)*1/n = exp(-c). CQFD

Vérifions expérimentalement que le nombre Xn de sommets isolés du graphe G(n,(c+log(n))/n) converge en loi vers une loi de Poisson de paramètre e(-c). Pour ca faire on procède comme dans la partie précédente, on répète un grand nombre de fois l’expérience mais plutôt que de prendre la moyenne des résultats, on trace leur histogramme. Sur le graphique on superpose (en bleu) la fonction de densité d’une loi de poisson de paramètre exp(-c)

Xn = mapply(nb_isoles,rep(1000,1000),rep(-3,1000));
h <- hist(Xn, col ='red',freq = FALSE);
xfit<-seq(min(Xn),max(Xn),length=max(Xn)-min(Xn)+1) 
yfit<-dpois(xfit,lambda=exp(-c)) 
lines(xfit, yfit, col="blue", lwd=2)

On voit que l’histogramme est très proche de la courbe ce qui montre que Xn suit bien une loi de poisson de paramètre exp(-c);

Question 2

On veut vérifier expérimentalement que P(G(n,(c + log(n))/n) est connexe) = exp(-exp(-c)). Un graphe est connexe si l’ensemble des voisins de l’ensemble des sommets du graphe est l’ensemble des sommets du graphe. On modifie le programme de la partie 1 pour qu’il retourne si le graphe simulé est connexe.

est_connexe<-function(n,c){
  p = (c+log(n))/n
  aretes = rbinom(n*n,1,p) # tirage aléatoire des arêtes suivant une loi de Bernoulli de paramètre p
  A = matrix(data = aretes, nrow = n) # création de la matrice d'incidence du grahpe correspondant
  X1 = matrix(data = rep(T,n), nrow=n) # ensemble des sommets du graphe
  X2 = ((A %*% X1) != 0) # ensemble des voisins de X1
  X2
  as.vector(X2)
  sum(X2)==n # retourne le nombre de voisins de X1
}

On répète l’expérience un grand nombre de fois pour estimer la probabilié que le graphe soit connexe.

c = 1; # on choisit une constante qui donne une proabailité pas trop proche de 0 ou 1
sum(mapply(est_connexe,rep(1000,1000),rep(c,1000)))/1000
## [1] 0.722

On obtient une probabilité qui est proche de exp(-exp(-1)) = 0.692, on a donc montré expérimentalement que P(G(n,(c + log(n))/n) est connexe) = exp(-exp(-c)).

Un sommet d’un graphe d’Erdös-Renyi peut être connecté avec les n-1 autres sommets. La probabilité que chacune de ces arêtes existe est p=(c + log(n))/n. Les arêtes sont tirées idépendamment, donc le degré d’un sommet suit une loi binomiale de paramètres n-1 et p et son espérance est (n-1)p = (n-1)/n(c + log(n)) soit environ c+log(n) pour n grand.

La probabilité que le graphe soit connexe est exp(-exp(-c)), elle ne dépend pas de n est elle devient rapidement assez proche de 1 (plus de 0.95 pour c>=3). L’espérance du degré du graphe est logarithmique en n ce qui signifie que le degré du graphe augment bien moins rapidement que le nombre de sommets. Ainsi on peut obtenir un graphe qui a une fort probabilité d’etre connexe (en prenant c assez grand) mais dont le degré est faible en comparaison du nombre de sommets.