Problème du scrutin
En probabilités, le problème du scrutin est une question concernant un scrutin à deux candidats où l'on connait le nombre de voix obtenues par le vainqueur et le nombre de voix obtenues par le perdant.
On demande la probabilité que le vainqueur soit toujours strictement en tête lors du dépouillement. La réponse, qui constitue le théorème du scrutin, est simplement le rapport , mais la démonstration n'en est pas immédiate.
Posant , la probabilité contraire, qu'il y ait au moins un moment avec autant de voix pour les deux candidats, valant , est donc proportionnelle à . Par exemple, cet évènement arrive plus d'une fois sur deux pour .
Historique
[modifier | modifier le code]En 1878, William Allen Whitworth pose en exercice dans son livre "Choice and chance"[1] la question : "En combien d'ordres possibles peuvent être arrangées m unités positives et n unités négatives de sorte que la somme d'un nombre quelconque de termes ne soit jamais (strictement) négative ?" Ce qui constitue de fait le problème du scrutin au sens large que l'on verra ci-dessous.
Le problème a ensuite été posé et résolu par Joseph Bertrand en 1887[2] en utilisant une preuve par récurrence, une ingénieuse résolution directe étant peu après proposée par Désiré André[3]. En 1907, G. Dumas publie une démonstration identique dans le fond à celle d'André[4]. En 1922, J. Aebly publie une démonstration qui constitue aujourd'hui la méthode classique exposée ci-dessous[5]. Voir " Bernard Bru, Les leçons de calcul des probabilités de Joseph Bertrand, p 14-15" pour une discussion détaillée de l'historique.
Démonstration par le principe de réflexion (ou principe de symétrie)
[modifier | modifier le code]On associe au déroulement du dépouillement un chemin dans de la façon suivante : on part de et on ajoute pour un bulletin du vainqueur, et pour un bulletin du perdant.
Si le point de coordonnées est sur le chemin, représente le nombre de bulletins dépouillés, et la différence entre le nombre de voix obtenues par le vainqueur et celles obtenues par le vaincu. Le dernier le point est avec , .
Notre problème est de dénombrer les chemins allant de à , et se situant, à part , strictement au-dessus de l'axe des (dénommé "axe" dans la suite). Le premier segment d'un tel chemin joignant forcément à , il suffit de compter le nombre de chemins qui vont de à sans toucher ou traverser l'axe.
Or il est classique que le nombre de chemins qui vont dans ce réseau de à vaut (le chemin est entièrement déterminé par les déplacements vers le haut (ou les déplacements vers le bas), à choisir parmi les déplacements totaux).
Donc déjà, le nombre total de chemins qui vont de à vaut
La partie délicate est de déterminer le nombre de chemins de à qui touchent ou traversent l'axe.
On utilise ici le principe de réflexion pour montrer que ce nombre est le même que celui des chemins allant de à soit
Soit en effet un chemin qui va de à en touchant ou traversant l'axe. On note le premier point de contact avec l'axe. On note la portion de chemin qui va de à , et la portion de chemin qui va de à .On construit le chemin en réunissant le symétrique de par rapport à l'axe avec . est un chemin qui va de à , et on se convainc que la correspondance " donne " est bijective.
Le nombre de chemins allant de à sans passer par l'axe vaut donc que l'on montre facilement être égal à .
Le nombre de dépouillements possibles étant justement égal à la probabilité demandée vaut bien .
Indications pour la démonstration proposée par Désiré André[3]
[modifier | modifier le code]Désiré André calcule le nombre de chemins joignant à passant par l'axe. Ceux qui commencent par joindre à sont évidemment en nombre . Il montre que ceux qui commencent par joindre à sont aussi en nombre par une astucieuse bijection utilisant non une symétrie mais une transposition de deux parties du chemin. Il tombe donc sur le dénombrement qui vaut bien aussi .
Le principe de réflexion décrit ci-dessus n'est donc pas dû à Désiré André comme on le voit souvent écrit.
Démonstration par récurrence
[modifier | modifier le code]Notons le nombre de dépouillements où le vainqueur est toujours en tête ; il faut démontrer que . Or se décompose en dépouillements qui se terminent par un bulletin du vainqueur et dépouillements se terminant par un bulletin du perdant (à l'avant dernière ouverture d'enveloppe il y avait bulletins du perdant sortis). On a donc la relation , relation de Pascal vérifiée également par le deuxième membre de l'égalité voulue, composée de coefficients binomiaux. Il suffit donc de vérifier les initialisations.
Or valant 1 (le perdant n'a pas eu de bulletin), est bien égal à et valant 0 (personne ne peut être constamment en tête) est bien égal à , ce qui achève la récurrence. Cette démonstration est celle proposée par Bertrand, sans les justifications[2].
Voici le début du triangle formé par les nombres lu en lignes, pour :
n\p | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
1 | 1 | 1 | |||||||
2 | 0 | 1 | |||||||
3 | 1 | 1 | |||||||
4 | 0 | 2 | 1 | ||||||
5 | 2 | 3 | 1 | ||||||
6 | 0 | 5 | 4 | 1 | |||||
7 | 5 | 9 | 5 | 1 | |||||
8 | 0 | 14 | 14 | 6 | 1 | ||||
9 | 14 | 28 | 20 | 7 | 1 |
Sans les 0, il constitue la suite A008313 de l'OEIS.
Interprétation en termes de marche aléatoire
[modifier | modifier le code]Si on associe au déroulement du dépouillement un chemin dans de la façon suivante : on part de et on ajoute pour un bulletin du vainqueur, et pour un bulletin du perdant, on obtient cette fois une marche aléatoire isotrope de longueur aboutissant à l'entier .
Le calcul précédent donne donc le nombre de ces marches restant constamment : . Ceci permet le calcul du nombre de marches aléatoires de longueur ne revenant jamais en 0, comme fait dans cet article.
Problème du scrutin au sens large
[modifier | modifier le code]On demande maintenant la probabilité que le vainqueur soit toujours en tête lors du dépouillement, ou à égalité avec le perdant. La réponse est et on peut le démontrer en utilisant le résultat strict. En effet il s'agit de dénombrer les chemins allant de à en restant au dessus de l'axe au sens large. Mais si on ajoute à tous les points et on relie à ce chemin, on obtient un chemin allant de à restant strictement au dessus de l'axe ; le dénombrement cherché est donc , qui est bien égal à .
Cas important du cas de deux candidats ex æquo avec 2p bulletins.
[modifier | modifier le code]Il y a alors une chance sur qu'un candidat donné soit constamment en tête ou a égalité lors du dépouillement. Et notons que dans ce cas, le dénombrement des dépouillements ayant la propriété est le nombre de Catalan d'ordre : ; les dépouillements correspondants sont des mots de Dyck.
Problème du scrutin généralisé
[modifier | modifier le code]Dès 1887 Émile Barbier[6] propose la généralisation suivante : quelle est la probabilité que le vainqueur ait toujours lors du dépouillement un nombre de bulletins strictement supérieur à k fois le nombre de celui du perdant, où k est un entier vérifiant . Barbier donne sans démonstration la réponse .
Interprété en termes de chemin, on ajoute ici au lieu de pour chaque bulletin du perdant. Étonnamment, la méthode de la réflexion ne se généralise pas, mais c'est celle de Désiré André qui permet d’établir le résultat[7].
Notes et références
[modifier | modifier le code]- (en) Whitworth, William Allen, Choice and Chance, Cambridge Deighton, Bell, , p 279 exercice 235 (lire en ligne)
- Joseph Bertrand, « Solution d'un problème du calcul des probabilités », Comptes Rendus des Séances de l'Académie des Sciences. Paris, n° 105, , p. 369 (lire en ligne)
- Désiré André, « Solution directe du problème résolu par M. Bertrand », Comptes Rendus de l'Académie des Sciences, Paris, , p. 436-437 (lire en ligne)
- G. Dumas, « Sur le problème du scrutin », Nouvelles annales de mathématiques 4eme série, tome 7, , p. 546-549 (lire en ligne)
- J. Aebly, « Démonstration du problème du scrutin par des considérations géométriques », Enseignement mathématique, , p. 185 - 186 (lire en ligne)
- Emile Barbier, « Généralisation du problème résolu par M. J. Bertrand », Comptes Rendus de l'Académie des Sciences, Paris, , p. 407
- Marc Renault, « Lost (and Found) in Translation: Andŕe’s Actual Method and Its Application to the Generalized Ballot Problem », Amer. Math. Monthly 115 no. 4, , p. 358--363 (lire en ligne)
Voir aussi
[modifier | modifier le code]Liens externes
[modifier | modifier le code]"The ballot problem" par Marc Renault : liste exhaustive de références.