Bonjour,

Je lisais pour un projet le cours suivant : https://economics.mit.edu/files/4622 sur les graphes d'Erdos-Renyi.
Mais le problème c'est que je n'arrive pas à comprendre la dernière slide...
Si vous connaissez déjà les résultats sur ces graphes, il suffit de lire des deux dernières slides pour comprendre mon problème. Sinon, c'est un diaporama de 19 pages et c'est plutôt rapide à lire.

Ce que je ne comprend pas, c'est déjà comment exprimer la variable aléatoire "size of epidemic as a fraction of the society" ; et ensuite d'où viennent les inégalités/égalités.

Voilà, avec un peu de chance quelqu'un pourra m'expliquer ici Je vous remercie par avance !

La variable aléatoire c'est la taille de la composante connexe à laquelle appartient le nœud initialement infecté, divisée par n.
J'ai juste parcouru vite fait et je connais pas vraiment le sujet, mais le blabla avant ne donne pas des infos sur cette variable aléatoire ?

Merci pour ta réponse.
Oui un peu, mais justement je n'arrive pas à faire le lien. Je peux pas trop tout résumer, mais les résultats sont pages 4, 14 et 16 si j'en oublie pas.

Je trouve ce cours assez peu clair et je crois qu'il y a beaucoup d'abus de notation.

En gros d'après ce que j'ai compris t'as 3 comportements possibles.

Si p = p(n) est trop petit par rapport à n, plus précisément inférieur à 1/n, alors avec proba qui tend vers 1, le graphe n'est pas connexe, et ses composantes sont "petites", de taille O(log(n)). C'est l'idée du théorème page 14.

Si p = p(n) est assez grand, de l'ordre de log(n)/n ou supérieur, alors, avec proba qui tend vers 1, le graphe est connexe. C'est l'idée du théorème page 4.

Dans le cas intermédiaire, il se forme une unique "composante géante" : il existe un q > 0 tel qu'asymptotiquement, la composante géante contient qn noeuds. Et les autres composantes sont petites (O(log(n))). La valeur de q est obtenue en trouvant le point fixe d'une certaine fonction (page 17).

Les 3 cas considérés dans la dernière slide correspondent à ces 3 comportements. Tu peux prendre pi = 0 ça ne change absolument rien, c'est juste qu'au lieu de considérer n noeuds on en considère (1 - pi)n...

Les cas 1 et 3 sont assez clairs (à part qu'on passe de la proba à l'espérance)...

Pour le 2ème cas je vois à peu près d'où sortent les termes mais pas de façon rigoureuse. La taille de l'épidémie c'est la taille de la composante connexe dans laquelle se trouve l'infecté initial. Soit il se trouve dans la composante géante qui est de taille qn, ce qui arrive avec proba q, soit dans une autre composante, ce qui arrive avec proba 1-q. Donc l'espérance de la taille de l'épidémie c'est à peu près q*(q*n) + (1-q)*log(n) puisque les autres composantes sont de taille O(log(n)).
Par contre pour la valeur de q je comprends pas trop d'où ça sort, mais la réponse se trouve certainement page 16.

Merci beaucoup, c'est un peu plus clair.
(Et merci d'avoir pris le temps de te pencher sur le sujet).

Quand tu dis "c'est clair", c'est pas trop clair pour moi (surtout le passage à l'espérance qui n'est pas du tout détaillé, on sait même pas la loi de la variable aléatoire a priori... mais d'après ce que j'ai compris, il s'agit de gros abus de notations ?)
Comment pourrais-je exprimer ces résultats plus rigoureusement ? Dire plutôt "on peut s'attendre à..." serait plus correct non ?

Ou alors passer par une tout autre méthode ? J'ai besoin d'estimer numériquement cette probabilité (mais si ce n'est pas possible, je peux très bien le faire par simulation informatique) pour la comparer avec la réalité.

Oui quand je dis c'est clair c'est juste le lien avec le reste qui l'est.

Mais pour l'esperance ça se montre de façon rigoureuse. Par contre il me semble bien que l'égalité n'est vraie qu'asymptotiquement...

D'accord merci !

J'ai essayé sans succès de montrer de façon rigoureuse le résultat :

Si on note S la variable aléatoire donnant la taille de la composante connexe, alors S/n est la variable aléatoire considérée (en oubliant le (1-\pi) un moment). En notant k_n = a log(n) (dans le cas lambda < 1)
J'ai donc :

(Avec alpha une constante positive, j'ai démontré ce résultat, que P(|Cmax| >= alogn) = O(n^{-alpha}))
Mais j'arrive pas à faire mieux ...