Bonjour,

Sur un poly sur la méthode probabiliste appliquée aux graphes, ils balancent un résultat sans justification que je n'arrive pas à démontrer.

On prend un graphe avec n sommets, et pour chaque doublet de points on met une arrête avec une proba 1/2.

On note X la variable aléatoire qui donne le degré d'un sommet.
Dans le poly ils disent qu'on a une variance de (1/4)(n-1) et une espérance de (1/2)(n-1).

Pour l'espérance c'est facile. Il y a n(n-1)/2 arrêtes possibles que l'on met avec proba de 1/2 mais chaque arrête augmente le degré total du graphe de 2 donc n(n-1)/2 on divise par n (on fait une moyenne) ça donne bien (1/2)(n-1).

Là c'est facile car on peut sommer sur chaque arrête.

Mais pour V(X) il faut savoir calculer E(X²) donc on peut plus sommer sur chaque arrête car le degré de chaque sommet intervient au carré.

J'ai essayé de sommer sur chaque sommet donc. Sauf que je me suis rendu compte que c'était faux:
J'ai commencé à écrire que pour chaque sommet la proba qu'il soit de degré k est (1/2)^(n-1)*(k parmi n-1) (loi binomiale).
Sauf que après je vais sommer, mais tout mon truc est faux car en faisant ça je compte des arrêtes en double. Quand je fais du sommet A vers le sommet B et inversement.

Du coup ça me saoule un peu qu'ils détaillent pas ce genre de trucs

Merci d'avance

Ben perso j'ai envie de me placer du point de vue d'un seul sommet, disons le premier et de regarder ses voisins, numérotés de $2$ à $n$. Pour chaque autre sommet, tu tires une pièce et si tu tires face, tu ajoutes l'arète correspondante. (Les arêtes entre les sommets $2$ à $n$ on s'en tape par on regarde le degré moyen d'un seul sommet.) Bref, avoir une arête de plus c'est une loi de Bernoulli de proba $\frac 12$ et le nombre total d'arêtes reliées au premier sommet, c'est une loi binomiale de paramètres $\frac 12, n-1$.

Les résultats tombent trivialement en lisant une table de la loi binomiale.

Oui donc E(X²) c'est bien somme de k=0 à n-1 de P(X = k) *k² le tout divisé par n? Avec P(X = k) =(1/2)^(n-1)*(k parmi n-1)?

J'ai du me tromper dans le calcul de la somme alors.

Le 30 avril 2017 à 11:54:21 Vistiche a écrit :
Oui donc E(X²) c'est bien somme de k=0 à n-1 de P(X = k) *k² le tout divisé par n? Avec P(X = k) =(1/2)^(n-1)*(k parmi n-1)?

J'ai du me tromper dans le calcul de la somme alors.

Non E(X^2) c'est juste la somme des k^2*P(X=n), y a pas de division par n.

Oui pardon la proba ça fait déjà la "moyenne"

Ah bah du coup ça marche. Mon calcul était faux à cause de ça

Merci