[MUSIQUE] Nous allons maintenant passer à la séance d'exercices 2, du cours 1, qui va consister à démontrer une formule dite du crible, ou d'inclusion-exclusion, qu'on appelle aussi parfois la formule de Poincaré, et qui est tout simplement une manière de calculer de façon exacte la probabilité de l'union d'un nombre fini d'événements. Voici la formule que nous allons étudier. On se donne, n événements aléatoires, et on va démontrer que la probabilité de l'union de ces événements a une formule exacte, qui est un peu compliquée mais qu'on va explorer ensemble. On peut l'écrire comme P1 moins P2 etc... plus, moins 1 puissance, n moins 1, fois Pn, ce qu'on peut écrire sous cette forme, cette somme, et les Pk qui apparaissent dans cette somme sont tout simplement la somme sur les intersections de ces événements, on les prend par paquets de k, on ordonne toutes les listes possibles de k événements et on prend l'intersection, ça donne ce Pk. C'est donc une formule un peu compliquée. on peut essayer de voir comment elle s'écrit plus explicitement. Comme la formule précédente, si je la réécris, c'est que la probabilité de l'union de ces, n événements, si on lit cette formule, on l'écrit de façon plus explicite, on obtient d'abord la somme de la probabilité des événements, ce qui évidemment est en général faux, puisque ils ne sont pas disjoints, donc l'idée consiste à, si on lit vraiment la formule, à supprimer les intersections deux à deux, donc on va retrancher la probabilité de l'intersection de Ai avec Aj, sur les paires ij ordonnées d'événements, et ensuite si on continue à lire cette formule pas à pas, on voit que on ajoute la probabilité de l'intersection des événements pris trois à trois, donc on obtient cette somme de probabilités d'intersections, etc. Et le dernier terme, si on lit la formule précédente, on voit que c'est, moins 1 puissance n plus 1, probabilités de l'intersection. Donc a priori ça a l'air compliqué mais on va voir comment comprendre cette formule. Tout simplement on va commencer par regarder des cas particuliers, avant de la démontrer. Vous constatez bien sûr que pour, n égale 1, la formule est triviale, On a juste un événement, la formule donne bien que la probabilité de A1 est égale à la probabilité de A1, donc on n'apprend rien. Le deuxième cas, quand on prend deux événements, c'est une formule que vous avez déjà rencontrée plusieurs fois, et qui est très facile à vérifier, par exemple en faisant un petit diagramme ; qui est que, si vous prenez deux événements, la probabilité de leur union c'est la somme des probabilités de ces événements, et il faut retrancher la probabilité de l'intersection. Alors on peut vérifier que la formule est correcte, puisque P1, si on regarde ce que c'est, c'est la somme sur un seul indice de P de Ai 1, et donc on a deux événements, ça fait bien P de A1 plus P de A2. Et P2, qui est le seul autre terme, c'est la somme sur les paires et à cause du fait qu'il n'y a qu'une seule paire, ça nous donne la probabilité de A1 inter A2, et il faut bien la retrancher ; donc on a bien la formule précédente dans le cas, n égale 2. Donc c'est assez simple. On peut aussi se faire une intuition avec trois événements. Je prends trois ensembles, A B et C, je ne note pas avec des indices, c'est plus simple de noter simplement comme ça. Et je fais ce petit diagramme. Ce que je n'ai pas précisé tout à l'heure c'est que la formule de Poincaré ou d'inclusion-exclusion, vous pouvez imaginer tout simplement que les événements sont de cardinalité finie, donc ça fait penser à des propriétés combinatoires, mais en fait cette formule est vraie aussi pour des événements beaucoup plus généraux, et donc on va utiliser plutôt l'interprétation en termes d'ensembles finis et de comptage, pour nous familiariser avec la formule dans le cas, n égale 3. Nous allons regarder le cas de trois événements, je vais prendre trois événements aléatoires, A B C, et je peux représenter sous forme de diagramme ce qu'il se passe. Donc vous avez ces trois événements qui a priori s'intersectent, et la première chose c'est, si vous dites que la probabilité de leur union c'est simplement la somme de leurs probabilités, donc si vous dites que le nombre d'éléments dans l'union c'est tout simplement la somme des éléments dans chacun des ensembles, évidemment c'est incorrect ; puisque quand vous faites la somme, PA plus PB plus PC, vous comptez en fait, si vous raisonnez en termes d'éléments, deux fois ce qui est dans la zone rouge, alors que vous avez bien compté une fois ce qui est dans la zone blanche, à l'intérieur des ensembles, et vous comptez trois fois la zone verte. Donc on a compté beaucoup trop de fois certains événements. Donc la première correction c'est tout simplement de soustraire la probabilité des intersections, deux à deux. Donc on obtient déjà quelque chose de plus correct, mais en faisant ça on a aussi compté trois fois, négativement, la surface verte, et comme au début on l'avait comptée trois fois et que là on l'a soustraite trois fois, puisque la zone verte est contenue dans chacune des intersection deux à deux, il faut tout simplement ajouter, à la fin, l'intersection des trois événements et ajouter cette probabilité. Et on obtient bien la formule dans le cas, n égale 3. Évidemment, si on veut raisonner dans le cas général, on ne va pas pouvoir s'en sortir de cette manière, on commence à sentir le mécanisme, et donc nous allons montrer cette formule par récurrence sur n. Nous allons donc établir la formule générale par récurrence. On suppose la formule vraie au rang n, et on veut la vérifier au rang, n plus 1. Nous avons déjà la récurrence qui est initiée, puisqu'on a vérifié le cas, n égale 1, et le cas le plus intéressant qui est le cas, n égale 2, et c'est ce cas, n égale 2, que nous allons utiliser puisqu'il est vrai pour toute paire d'événements aléatoires, on va utiliser le cas, n égale 2, pour des ensembles particuliers qui sont l'union de n événements Ai, et on met, A n plus 1, de côté, qui va constituer notre second événement. Donc j'applique la formule pour, n égale 2, qu'on a vérifiée et qui est juste. Et si je calcule ça, j'obtiens que la probabilité de l'union de ces, n plus 1, événements qui est donc la probabilité de l'union où je n'en prends que, n, que je prends avec l'événement, A n plus 1, si j'applique la formule pour, n égale 2, ça me donne simplement la somme des probabilités de ces deux événements, et il faut que je soustraie la probabilité de leur intersection. J'ai juste appliqué la formule dans le cas, n égale 2, pour ces deux événements particuliers. Je peux utiliser la distributivité de l'intersection par rapport à l'union. Donc j'écris juste une ligne de plus, qui va me servir dans un instant, je laisse les deux premiers termes comme ils sont et j'écris juste que la probabilité à la fin c'est l'union, de 1 jusqu'à n, de Ai inter A, n plus 1. Je fais l'union de ces événements, Ai inter A, n plus 1. et c'est la même chose que la ligne au-dessus, par distributivité. Maintenant, on applique l'hypothèse de récurrence. [AUDIO_VIDE] aux deux termes qui contiennent, qui sont des réunions. Et ce sont des réunions de, n ensembles. Donc allons-y. On utilise l'hypothèse de récurrence, on a supposé qu'au rang, n, c'était vrai. Donc la probabilité de l'union des, n événements, si je reprends la formule c'est la somme, de k égale 1 jusqu'à n, de moins 1, puissance k plus 1, et je somme sur la liste des événements que je prends par k, j'obtiens ça d'une part, [AUDIO_VIDE] et la probabilité de l'autre union, qui contient aussi, n événements, s'écrit comme la somme, de k égale 1 jusqu'à n, moins 1 puissance, k plus 1, somme sur les k [uplés ?] [AUDIO_VIDE] et là on a Ai 1 inter Ai 2 etc. inter Ai k, on a une intersection avec, n plus 1, en plus. On va tout simplement remplacer ces probabilités d'unions dans la formule précédente, qu'on avait appliquée à l'union des n premiers et derniers, et on obtient la chose suivante. Donc je ré écris tout, je récapitule. Quand je prends l'union de, n plus 1, événements, j'obtiens d'une part cette somme, qui est un peu pénible à écrire mais tout simplement j'ordonne la liste des k uplés événements, je regarde la probabilité de leur intersection, [AUDIO_VIDE] je n'oublie pas la probabilité de, n plus 1, et vient ensuite le, moins, k égale 1 jusqu'à n, moins 1, puissance k plus 1, qui est la même chose qu'avant, sauf que nous avons l'événement A, n plus 1. Donc l'idée consiste à re sommer, rebaptiser les indices et les décaler dans la dernière somme que j'ai écrite ; et, en fait, on constate que toute cette partie se réécrit, la somme qui va de 2 jusqu'à, n plus 1, moins 1, puissance k plus 1, la somme sur i1, i2 etc., jusqu'à ik moins 1, plus petit ou égal à n. Et ik, lui, est fixé, il vaut, n plus 1. Et donc, juste en rebaptisant mes indices, j'obtiens cette formule. Maintenant, si vous utilisez cette partie et ce qui précède, vous pouvez tout réécrire, et si vous vous souvenez de ce que nous avons écrit au début, en explicitant un peu plus la formule, on avait fait apparaître d'abord la somme des probabilités et ensuite retranché la probabilité des intersections, deux à deux, puis ajouté l'intersection des événements, trois à trois ; donc si je regarde juste la décomposition qui consiste à regarder la somme des probabilités plus tout le reste, on va retrouver exactement la bonne formule, puisque si vous réarrangez ce qui précède, on obtient bien la somme des probabilités des, n plus 1, événements plus ce qui reste, qui est cette somme avec des signes alternés, i1 plus petit que i2, ik plus petit ou égal à, n plus 1, inter Ai 2, inter Ai k. Ce qui est exactement l'expression qu'on voulait. [AUDIO_VIDE] Donc nous avons la formule que nous avions écrite au début et qui est assez compliquée, mais on va le voir, est très utile dans de nombreux problèmes qui mettent des combinatoires en jeu, et quand on veut vraiment calculer exactement la probabilité de l'union, et pas simplement avoir une borne en éliminant certains événements compliqués. Ceci achève la démonstration, qui est effectivement un peu abstraite de cette formule du crible, et nous allons voir dans la séance 3 comment l'appliquer à un problème qui se retrouve sous des tas de formes différentes, et que cette formule est extrêmement puissante.
