Niveau Maths sup

Erdös et Renyi

Posté par
Rime24 25-09-24 à 16:12

Bonjour,

On fabrique un graphe sur n sommets en choisissant ses arêtes "au hasard". Plus précisément, on considère le graphe $G_{n,p}$ obtenu en choisissant chacune des $\bigl(\begin{smallmatrix}n \\ 2 \end{smallmatrix}\bigr)$ arêtes potentielles indépendamment avec probabilité p. Le but de ce problème est d'étudier la probabilité que $G_{n,p}$ soit connexe. On s'intéressera au cas où p est de la forme :

$p = p(n)=\frac{ln(n)}{n} +\frac{c}{n}$ où c est une constante fixée.

a) Soit $(X_i, 1\leq i \leq n)$ un n-uplet de variables aléatoires à valeurs dans {0,1} et soit $X= \sum_{i=1}^{n}{X_i}$ . Montrer que pour tout r tel que $r\geq 1 et 2r+1\leq n$ on a :

$\sum_{k=0}^{2r+1}{(-1)^kF^{(k)}} \leq P(X=0) \leq \sum_{k=0}^{2r}{(-1)^kF^{(k)}}$

où l'on a posé : $F^{(0)}=1$ et pour $k\geq 1$ :

$F^{(k)}= \sum_{j_1 <j_2<...<j_k}^{}{E[X_{j_1}X_{j_2}...X_{j_k}]}$

b) Que valent $E[X_i]$ et $E[X]$ ?

c) On suppose dorénavant c fixé. Montrer que la quantité $F^{(k)}$ , pour la variable X converge, lorsque n tend vers l'infini, vers $\frac{e^{-ck}}{k!}$ .

d)Montrer que $\lim_{n\rightarrow \infty} {P(X=0)=e^{-e^{-c}}}$

e) Calculer l'espérance du nombre de composantes connexes à 2 sommets, et constater que celle-ci tend vers zéro quand n tend vers l'infini.

f) Plus généralement, soit $C_t$ le nombre de composantes connexes à t sommets. Montrer que pour $2\leq t\leq \frac{n}{2}$ ,

$E[C_t] \leq \frac{1}{t!}\sum_{t-1\leq k\leq\bigl(\begin{smallmatrix}t \\ 2 \end{smallmatrix}\bigr)} {C_{k}^{\bigl(\begin{smallmatrix}t \\ 2 \end{smallmatrix}\bigr)}(\frac{p}{1-p})^k}$

En déduire que la probabilité que $G_{n,p}$ soit connexe tend, quand $n\rightarrow +\infty$ , vers $e^{-e^{-c}} \\$ . On admettra que $\sum_{2\leq t\leq \frac{n}{2}}^{}{E[C_t]}\rightarrow 0$ quand n tend vers l'infini.

g) Que peut-on déduire de la probabilité que $G_{n,p}$ soit connexe?

Merci d'avance!!

Ce topic

Imprimer
Réduire / Agrandir
Pour plus d'options, connectez vous !
Fiches de maths

probabilités en post-bac
1 fiches de mathématiques sur "probabilités" en post-bac disponibles.

Rechercher

Espace membre

Zone membre

Pas de compte ?
Je m'inscris

28 visiteurs

Changer d'île

Cours et Exercices de maths

Forum de maths

college

lycee

Outils de maths

Pages les plus populaires

Erdös et Renyi

Seuls les membres peuvent poster sur le forum !

Ce topic

Fiches de maths