Nous soussignés Rossi Ombeline et Eudes Robin déclarons sur l’honneur que ce rapport est le fruit d’un travail personnel, en binôme, que nous n’avons ni contrefait, ni falsifié, ni copié tout ou partie de l’œuvre d’autrui afin de la faire passer pour nôtre. Toutes les sources d’information utilisées et les citations d’auteur ont été mentionnées conformément aux usages en vigueur. Nous sommes conscient(e)s que le fait de ne pas citer une source ou de ne pas la citer clairement et complètement est constitutif de plagiat, que le plagiat est considéré comme une faute grave au sein de l’Université, pouvant être sévèrement sanctionnée par la loi.

Nous avons d’abord compris l’énoncé de la façon qui suit : chaque processus ne “pioche” qu’une seule fois une probabilité : soit il tombe sur \(p_0\) ou \(p_1\) et ne crée pas de fils, soit il en crée \(k-1\) pour une probabilité de \(p_k\). Toutefois, cela impliquait que les processus ne finissent jamais (on considère que la probabilité \(p_0\) indique un processus terminant). Il serait alors plus logique d’estimer que tant qu’un processus n’est pas terminé, il “repioche”" une probabilité et peut donc produire des fils tant qu’il n’a pas pioché \(p_0\). Nous avons uniquement utilisé la seconde interprétation pour répondre aux problèmes et quesions, qui nous semblait plus cohérente, bien que plus complexe - dans le pire des cas, aucune des interprétations n’était bonne…

Problème 1 :

À quelle condition sur la distribution de probabilité p le nombre total de processus n’explose pas ?

Lors de notre première étude de ce problème, nous avions estimé qu’il fallait que la distribution de probabilité se comporte ainsi :

\(\displaystyle {\lim_{k \rightarrow +\infty }}p_k = 0\)

Pour k tendant vers l’infini, \(p_k\) doit tendre vers 0. Ainsi, plus k est grand, plus \(p_k\) est petite, assurant ainsi un nombre de processus qui n’explosera pas.

En répondant au second problème, nous avons toutefois trouvé une inégalité que la distribution de probabilités se doit de respecter. Nous rajoutons donc une partie “Problème 1 et 2”.

Problème 1&2 :

Considérons m, le plus grand indice des probabilités de p. Si le processus sélectionne \(p_0\), il ne produit qu’un seul processus : lui-même. S’il sélectionne \(p_1\), il produira le nombre moyen de processus vu qu’il continue à s’exécuter et peut donc encore avoir des fils. S’il sélectionne \(p_k\), il produira k fois le nombre moyen de processus : ses \(k-1\) fils ainsi que lui continuent de s’exécuter.

\(nbmoyproc = 1*p_0 + nbmoyproc*p_1 + 2*nbmoyproc*p_2 + ... + m*nbmoyproc*p_m\)

\(nbmoyproc = p_0 + \sum\limits_{i=1}^{m}{i * nbmoyproc * p_i}\)

\(1 = \frac{p_0}{nbmoyproc} + \sum\limits_{i=1}^{m}{i * p_i}\)

\(\frac{p_0}{nbmoyproc} = 1 - \sum\limits_{i=1}^{m}{i * p_i}\)

\(nbmoyproc = \frac{p_0}{1 - \sum\limits_{i=1}^{m}{i * p_i}}\)

Cette équation donne un résultat positif et juste uniquement quand le nombre des processus créés est fini (quand il n’explose pas). Cela arrive uniquement quand : \(\sum\limits_{i=1}^{m}{i * p_i} < 1\) . Nous répondons donc de manière plus précise au premier problème avec cette inéquation, tout en répondant à la première partie du second problème.

Problème 2 :

Si le nombre de processus créés est fini (pas d’explosion), caractériser en fonction de p l’ensemble des processus générés : nombre moyen de processus générés, longueur moyenne de la plus longue chaîne de création.

Le nombre de processus générés a donc été déterminé ci dessus. Voyons maintenant la longueur moyenne de la plus longue chaine de création. Si le processus tire \(p_0\), il ne crée pas de fils et donc donne un maillon unique de taille 1. S’il tire \(p_1\), il pourra ensuite donner une chaine de la longueur moyenne puisqu’il peut encore avoir des fils. S’il tire \(p_k\), il pourra donner une chaine de la longueur moyenne + 1, peu importe son nombre de fils. On observe donc que ce système de création de processus crée un arbre (soit les processus tirent \(p_0\) et deviennent des feuilles, soit ils tirent \(p_1\) et on ne peut encore déterminer leur statut, soit ils tirent \(p_k\) et sont des noeuds qui peuvent encore donner des fils). On calcule la longueur de la chaine de processus la plus longue de la même manière qu’on calcule la hauteur d’un arbre. Ici, nous avons déterminé alors qu’un processus sans fils respecte la convention qui veut qu’une feuille soit de taille 1.

\(lgmoy = 1*p_0 + lgmoy*p_1 + \sum\limits_{i=2}^{m}{(1+lgmoy) * p_i}\)

\(lgmoy = \sum\limits_{i=0}^{m}{p_i} - p_1 + lgmoy*p_1 + \sum\limits_{i=2}^{m}{lgmoy * p_i}\)

\(lgmoy = 1 - p_1 + \sum\limits_{i=1}^{m}{lgmoy * p_i}\)

\(1 = \frac{1 - p_1}{lgmoy} + \sum\limits_{i=1}^{m}{p_i}\)

\(1 = \frac{1 - p_1}{lgmoy} + (1 - p_0)\)

\(p_0 = \frac{1 - p_1}{lgmoy}\)

\(lgmoy = \frac{1 - p_1}{p_0}\)

Question 2.1 .

set.seed(42)

gen <- function(p=0.5,law=c("bernouilli","binomiale","geometrique","poisson")){
  nb_proc_current =1;
  nb_proc_cree=0;
  while(nb_proc_current!=0){
    tmp = nb_proc_current;
    nb_proc_current=0;
    
    i=0;
    while(i<tmp){ 
        if(law=="bernouilli"){
          
          if(rbinom(1,1,p)==1){
            nb_proc_current = nb_proc_current +2;
            nb_proc_cree= nb_proc_cree +2;
            }
          
        }else if(law=="binomiale"){
         
          val = rbinom(1,13,p); # 13 fils max
          nb_proc_current = nb_proc_current + val;
          nb_proc_cree = nb_proc_cree + val;
          #nb_proc_cree;
        
        }else if(law=="geometrique"){
        
          val = rgeom(1,p);
          nb_proc_current = nb_proc_current + val;
          nb_proc_cree = nb_proc_cree + val;
        
        }else if(law=="poisson"){
          val = rpois(1,p); # p -> lambda ici...
          nb_proc_current = nb_proc_current + val;
          nb_proc_cree = nb_proc_cree + val;
        }
      i=i+1;
    }
  }
  nb_proc_cree;
}

Notre fonction nous retourne donc le nombre de processus créé. Regardons le corportement sur 500 simulations, suivant différentes lois.

Loi de Bernouilli ( p = 0.5 ):

save<-c();
i=0;
while(i<500){
save[i]<-gen(0.5,"bernouilli");
i=i+1;
}

mean(save);
## [1] 509.9
max(save);
## [1] 157932

Loi de Binomiale ( n = 13 , p = 0.07 ):

save<-c();
i=0;
while(i<500){
save[i]<-gen(0.07,"binomiale");
i=i+1;
}

mean(save);
## [1] 9.876
max(save);
## [1] 818

Loi de Géométrique ( p = 0.5 ):

save<-c();
i=0;
while(i<500){
save[i]<-gen(0.5,"geometrique");
i=i+1;
}

mean(save);
## [1] 390.7
max(save);
## [1] 140891

Loi de Poisson ( lambda = 0.9):

save<-c();
i=0;
while(i<500){
save[i]<-gen(0.9,"poisson");
i=i+1;
}

mean(save);
## [1] 9.156
max(save);
## [1] 500

Après ces premières simulations, on peut observer que les systèmes ont tendance à être très rapidement instables, le nombre de processus explosant. De façon générale, soit on a très peu de processus créé, voir aucun, soit le nombre explose très vite. Ainsi, la moyenne ici est à prendre avec des “pincettes”. On peut observer les valeurs maximum, qui peuvent donc exploser rapidement.

Question 2.2

Si \(p_0\) et \(p_1\) sont très élevées, on a un arbre très court, avec très peu de feuilles. Si \(p_2\) est très élevé, on a un arbre très long, mais avec peu de feuilles. Plus k et \(p_k\) sont grands, plus on obtient un arbre avec de nombreuses feuilles et très grand.