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 $p$ de voix obtenues par le vainqueur et le nombre $q$ 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 ${\dfrac {p-q}{p+q}}$ , mais la démonstration n'en est pas immédiate.

Posant $n=p+q$, la probabilité contraire, qu'il y ait au moins un moment avec autant de voix pour les deux candidats, valant $2q \over n$, est donc proportionnelle à $q$ . Par exemple, cet évènement arrive plus d'une fois sur deux pour ${n \over 4}<q<{n \over 2}$.

Historique

En 1878, William Allen Whitworth pose en exercice dans son livre "Choice and chance" 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 en utilisant une preuve par récurrence, une ingénieuse résolution directe étant peu après proposée par Désiré André. En 1907, G. Dumas publie une démonstration identique dans le fond à celle d'André. En 1922, J. Aebly publie une démonstration qui constitue aujourd'hui la méthode classique exposée ci-dessous. 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)

On associe au déroulement du dépouillement un chemin dans $\mathbb {Z} ^{2}$ de la façon suivante : on part de $(0,0)$ et on ajoute $(1,1)$ pour un bulletin du vainqueur, et $(1,-1)$ pour un bulletin du perdant.

Si le point de coordonnées $(x,y)$ est sur le chemin, $x$ représente le nombre de bulletins dépouillés, et $y$ la différence entre le nombre de voix obtenues par le vainqueur et celles obtenues par le vaincu. Le dernier le point est $(n,k)$ avec $n=p+q$, $k=p-q$.

Notre problème est de dénombrer les chemins allant de $(0,0)$ à $(n,k)$, et se situant, à part $(0,0)$, strictement au-dessus de l'axe des $x$ (dénommé "axe" dans la suite). Le premier segment d'un tel chemin joignant forcément $(0,0)$ à $(1,1)$, il suffit de compter le nombre de chemins qui vont de $(1,1)$ à $(n,k)$ sans toucher ou traverser l'axe.

Or il est classique que le nombre de chemins qui vont dans ce réseau de $\left(a,b\right)$ à $\left(a+c,b+d\right)$ vaut $\left({\begin{array}{c}c\\{\frac {c+d}{2}}\end{array}}\right)=\left({\begin{array}{c}c\\{\frac {c-d}{2}}\end{array}}\right)$(le chemin est entièrement déterminé par les ${\frac {c+d}{2}}$ déplacements vers le haut (ou les ${\frac {c-d}{2}}$ déplacements vers le bas), à choisir parmi les $c$ déplacements totaux).

Donc déjà, le nombre total de chemins qui vont de $\left(1,1\right)$ à $\left(p+q,p-q\right)$ vaut $\left({\begin{array}{c}p+q-1\\p-1\end{array}}\right).$

La partie délicate est de déterminer le nombre de chemins de $(1,1)$ à $(p+q,p-q)$ 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 $(1,-1)$ à $(p+q,p-q),$ soit $\left({\begin{array}{c}p+q-1\\p\end{array}}\right).$

Soit en effet $C$ un chemin qui va de $(1,1)$ à $(p+q,p-q)$ en touchant ou traversant l'axe. On note $M$ le premier point de contact avec l'axe. On note $C_{1}$ la portion de chemin qui va de $(1,1)$ à $M$, et $C_{2}$ la portion de chemin qui va de $M$ à $(p+q,p-q)$.On construit le chemin $C^{\prime }$ en réunissant le symétrique $C_{1}^{\prime }$ de $C_{1}$ par rapport à l'axe avec $C_{2}$. $C^{\prime }$ est un chemin qui va de $(1,-1)$ à $(p+q,p-q)$, et on se convainc que la correspondance "$C$ donne $C^{\prime }$" est bijective.

Le nombre de chemins allant de $\left(0,0\right)$ à $\left(p+q,p\right)$ sans passer par l'axe vaut donc $\left({\begin{array}{c}p+q-1\\p-1\end{array}}\right)-\left({\begin{array}{c}p+q-1\\p\end{array}}\right)$ que l'on montre facilement être égal à ${\dfrac {p-q}{p+q}}\left({\begin{array}{c}p+q\\p\end{array}}\right)$.

Le nombre de dépouillements possibles étant justement égal à $\left({\begin{array}{c}p+q\\p\end{array}}\right),$ la probabilité demandée vaut bien ${\dfrac {p-q}{p+q}}$.

Indications pour la démonstration proposée par Désiré André

Désiré André calcule le nombre de chemins joignant $\left(0,0\right)$ à $\left(p+q,p-q\right)$ passant par l'axe. Ceux qui commencent par joindre $\left(0,0\right)$ à $\left(1,1\right)$sont évidemment en nombre $\left({\begin{array}{c}p+q-1\\q-1\end{array}}\right)$. Il montre que ceux qui commencent par joindre $\left(0,0\right)$ à $\left(-1,1\right)$ sont aussi en nombre $\left({\begin{array}{c}p+q-1\\q-1\end{array}}\right)$ par une astucieuse bijection utilisant non une symétrie mais une transposition de deux parties du chemin. Il tombe donc sur le dénombrement $\left({\begin{array}{c}p+q\\p\end{array}}\right)-2\left({\begin{array}{c}p+q-1\\q-1\end{array}}\right)$ qui vaut bien aussi ${\dfrac {p-q}{p+q}}\left({\begin{array}{c}p+q\\p\end{array}}\right)$.

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

Notons $D(n,p)$ le nombre de dépouillements où le vainqueur est toujours en tête ; il faut démontrer que $D(n,p)=\left({\begin{array}{c}n-1\\p-1\end{array}}\right)-\left({\begin{array}{c}n-1\\p\end{array}}\right)$. Or $D(n,p)$ se décompose en $D(n-1,p-1)$ dépouillements qui se terminent par un bulletin du vainqueur et $D(n-1,p)$ dépouillements se terminant par un bulletin du perdant (à l'avant dernière ouverture d'enveloppe il y avait $q-1$ bulletins du perdant sortis). On a donc la relation $D(n,p)=D(n-1,p)+D(n-1,p-1)$, 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 $D(n,n)$ valant 1 (le perdant n'a pas eu de bulletin), est bien égal à $\left({\begin{array}{c}n-1\\n-1\end{array}}\right)-\left({\begin{array}{c}n-1\\n\end{array}}\right)$ et $D(2p,p)$ valant 0 (personne ne peut être constamment en tête) est bien égal à $\left({\begin{array}{c}2p-1\\p-1\end{array}}\right)-\left({\begin{array}{c}2p-1\\p\end{array}}\right)$, ce qui achève la récurrence. Cette démonstration est celle proposée par Bertrand, sans les justifications.

Voici le début du triangle formé par les nombres $D(n,p)$ lu en lignes, pour $n/2\leqslant p\leqslant n$:

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

Si on associe au déroulement du dépouillement un chemin dans $\mathbb {Z}$ de la façon suivante : on part de $0$ et on ajoute $1$ pour un bulletin du vainqueur, et $-1$ pour un bulletin du perdant, on obtient cette fois une marche aléatoire isotrope de longueur $n$ aboutissant à l'entier $k$.

Le calcul précédent donne donc le nombre de ces marches restant constamment $>0$ : ${\dfrac {k}{n}}\left({\begin{array}{c}n\\{{n+k} \over 2}\end{array}}\right)$. Ceci permet le calcul du nombre de marches aléatoires de longueur $n$ ne revenant jamais en 0, comme fait dans cet article.

Problème du scrutin au sens large

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 ${\dfrac {p-q+1}{p+1}}$ et on peut le démontrer en utilisant le résultat strict. En effet il s'agit de dénombrer les chemins allant de $(0,0)$ à $(p+q,p-q)$ en restant au dessus de l'axe au sens large. Mais si on ajoute $(1,1)$ à tous les points et on relie $(0,0)$ à ce chemin, on obtient un chemin allant de $(0,0)$ à $(p+q+1,p+1)$ restant strictement au dessus de l'axe ; le dénombrement cherché est donc ${\dfrac {p+1-q}{p+1+q}}\left({\begin{array}{c}p+1+q\\p+1\end{array}}\right)$, qui est bien égal à ${\dfrac {p-q+1}{p+1}}\left({\begin{array}{c}p+q\\p\end{array}}\right)$.

Cas important du cas de deux candidats ex æquo avec 2p bulletins.

Il y a alors une chance sur $p+1$ 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 $p$ : ${\dfrac {1}{p+1}}\left({\begin{array}{c}2p\\p\end{array}}\right)$ ; les dépouillements correspondants sont des mots de Dyck.

Problème du scrutin généralisé

Dès 1887 Émile Barbier 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 $\geqslant 1$ vérifiant $p>kq$ . Barbier donne sans démonstration la réponse ${\dfrac {p-kq}{p+q}}$.

Interprété en termes de chemin, on ajoute ici $(1,-k)$ au lieu de $(1,-1)$ 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.

Voir aussi

• Le triangle de Catalan

Liens externes

"The ballot problem" par Marc Renault : liste exhaustive de références.