Problème du scrutin

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.

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

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

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

Or il est classique que le nombre de chemins qui vont dans ce réseau de ${\displaystyle \left(a,b\right)}$ à ${\displaystyle \left(a+c,b+d\right)}$ vaut ${\displaystyle \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 ${\displaystyle {\frac {c+d}{2}}}$ déplacements vers le haut (ou les ${\displaystyle {\frac {c-d}{2}}}$ déplacements vers le bas), à choisir parmi les ${\displaystyle c}$ déplacements totaux).

Donc déjà, le nombre total de chemins qui vont de ${\displaystyle \left(1,1\right)}$ à ${\displaystyle \left(p+q,p-q\right)}$ vaut ${\displaystyle \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 ${\displaystyle (1,1)}$ à ${\displaystyle (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 ${\displaystyle (1,-1)}$ à ${\displaystyle (p+q,p-q),}$ soit ${\displaystyle \left({\begin{array}{c}p+q-1\\p\end{array}}\right).}$

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

Le nombre de chemins allant de ${\displaystyle \left(0,0\right)}$ à ${\displaystyle \left(p+q,p\right)}$ sans passer par l'axe vaut donc ${\displaystyle \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 à ${\displaystyle {\dfrac {p-q}{p+q}}\left({\begin{array}{c}p+q\\p\end{array}}\right)}$.

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

Désiré André calcule le nombre de chemins joignant ${\displaystyle \left(0,0\right)}$ à ${\displaystyle \left(p+q,p-q\right)}$ passant par l'axe. Ceux qui commencent par joindre ${\displaystyle \left(0,0\right)}$ à ${\displaystyle \left(1,1\right)}$sont évidemment en nombre ${\displaystyle \left({\begin{array}{c}p+q-1\\q-1\end{array}}\right)}$. Il montre que ceux qui commencent par joindre ${\displaystyle \left(0,0\right)}$ à ${\displaystyle \left(-1,1\right)}$ sont aussi en nombre ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle {\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.

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

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

Sans les 0, il constitue la suite A008313 de l'OEIS.

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

Le calcul précédent donne donc le nombre de ces marches restant constamment ${\displaystyle >0}$ : ${\displaystyle {\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 ${\displaystyle n}$ ne revenant jamais en 0, comme fait dans cet article.

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

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

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

• Le triangle de Catalan

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