Le problème
Une élection comporte deux candidats, que l’on nommera \(A\) et \(B\). À l’issue de l’élection, le candidat \(A\) remporte l’élection en totalisant \(p\) votes, alors que le candidat \(B\) n’en compte qu’un nombre \(q\). Le candidat \(a\) est donc vainqueur… Mais était-il toujours en tête lors du dépouillement de ce vote ? C’est ce que l’on souhaite savoir : le problème du scrutin consiste à déterminer la probabilité que le candidat \(A\) se soit toujours trouvé en tête lors du dépouillement.
La réponse à cette question s’exprime assez simplement en fonction des quantités \(p\) et \(q\). En revanche, l’obtention de ce résultat fait intervenir une petite astuce combinatoire…
Ce problème a notamment été posé et résolu par Joseph Bertrand en 1887, puis par Désiré André la même année. La démonstration que nous présentons ici est toutefois celle publiée en 1922 par Aebly.
Les plus curieux pourront consulter les documents d’origine aux adresses suivantes :
- Pour la solution de Bertrand
- Pour celle donnée par Désiré André
- Enfin, la solution proposée par Aebly
Modélisation du problème
Modélisation probabiliste
L’urne qui rassemble les votes de l’élection comporte donc au total \(p+q\) bulletins : \(p\) en faveur du candidat \(A\) et \(q\) en faveur du candidat \(B\). On tire sans remise, mais de manière uniforme à chaque fois, l’ensemble des bulletins figurant dans l’urne : on peut alors construire un \(p+q\)-uplet de l’ensemble \(\{A,B\}\), la lettre \(A\) apparaissant exactement \(p\) fois.
On s’intéresse alors à la probabilité de l’événement \(E\) suivant :
Prenons un exemple où 7 bulletins figurent dans l’urne, dont 5 sont en faveur de \(A\)
- le tirage \(AAABABA\) réalise l’événement \(E\) : les états successifs du dépouillement sont \(A\), \(AA\), \(AAA\), \(AAAB\), \(AAABA\), \(AAABAB\) et \(AAABABA\). A chaque fois, il y a plus de bulletins dépouillés en faveur de A que de B.
- le tirage \(ABBAAAA\) ne réalise pas l’événement \(E\) : à la troisième étape, il y a plus de bulletins dépouillés en faveur de \(B\) qu’en faveur de \(A\).
Aspect géométrique
On munit le plan d’un repère \((O,\vec i, \vec j)\). On place alors un point à l’origine du repère, puis on applique des translations successives de ce point selon le bulletin tiré lors du dépouillement.
- On applique une translation de vecteur \(\vec h\begin{pmatrix} 1\\1\end{pmatrix}\) si le bulletin dépouillé est en faveur du candidat A (autrement dit, on se déplace d’un cran vers la droite et d’un cran vers le haut)
- On applique une translation de vecteur \(\vec b\begin{pmatrix} 1\\-1\end{pmatrix}\) si le bulletin dépouillé est en faveur du candidat B (autrement dit, on se déplace d’un cran vers la droite et d’un cran vers le bas)
Voici par exemple ce que donne le tirage \(AABABAA\), en traçant à chaque fois les segments intermédiaires.
Revenons alors au problème : puisqu’il y a \(p+q\) bulletins dans l’urne, il y aura alors \(p+q\) translations à appliquer. Parmi ces translations, \(p\) seront des translations de vecteur \(\vec h\) et \(q\) seront de vecteur \(\vec b\). Le vecteur ainsi obtenu a pour coordonnées
\[p \vec h + q \vec b \begin{pmatrix}p+q \\ p-q\end{pmatrix}\]
Le problème revient donc à dénombrer les chemins allant du point de coordonnées \((0\,;\,0)\) au point de coordonnées \((p+q\,;\,p-q)\) en utilisant uniquement les vecteurs \(\vec h\) et \(\vec b\), tout en restant au-dessus de l’axe des abscisses. Ce nombre sera alors divisé par le nombre total de chemins reliant ces deux points, sans condition, pour obtenir la probabilité recherchée dans ce problème.
Résolution
Nombre total de chemins
Commençons par le plus simple : on souhaite aller du point de coordonnées \((0\,;\,0)\) au point de coordonnées \((p+q\,;\,p-q)\) en utilisant uniquement les vecteurs \(\vec h\) et \(vec b\).
Parmi les \(p+q\) déplacements effectués, \(p\) doivent être des translations de vecteur \(\vec h\) : il suffit donc, pour construire un tel chemin, de choisir \(p\) déplacements parmi les \(p+q\) disponibles. Les déplacements ainsi choisis correspondront aux translations de vecteur \(\vec h\). Les autres, qui n’ont pas été choisi, correspondent quant à eux aux déplacements de vecteur \(\vec b\).
Le nombre de chemins dans cette situation est donc \(\dbinom{p+q}{p}\).
Nombre total de chemins restant au-dessus de l’axe des abscisses.
Comptons désormais les chemins qui restent au-dessus de l’axe des abscisses. Un tel chemin passe forcément par le point de coordonnées \((1\,;\,1)\) (sinon, il passerait sous l’axe des abscisses dès la première étape). Cela correspond au fait que le premier bulletin dépouillé doit forcément être en faveur du candidat A pour espérer que celui-ci reste en tête tout au long du dépouillement.
Nous allons procéder par complémentarité : nous compterons le nombre total de chemins allant de \((1\,;\,1)\) à \((p+q\,;\,p-q)\) et nous enlèverons le nombre de tels chemins qui coupent l’axe des abscisses.
En utilisant le même raisonnement que précédemment, on établit que le nombre de chemins allant du point de coordonnées \((1\,;\,1)\) au point de coordonnées \((p+q\,;\,p-q)\) vaut \(\dbinom{p+q-1}{p-1}\) : il reste en effet \(p-1\) déplacements vers le haut à effectuer parmi les \(p+q-1\) restants.
Reste alors à déterminer le nombres de chemins qui coupe l’axe des abscisses. Pour cela, on établit ce que l’on appelle une bijection entre deux ensembles :
- l’ensemble des chemins allant du point de coordonnées \((1\,;\,1)\) au point de coordonnées \((p+q\,;\,p-q)\) en coupant l’axe des abscisses
- l’ensemble des chemins allant du point de coordonnées \((1\,;\,-1)\) au point de coordonnées \((p+q\,;\,p-q)\)
A chaque élément du premier ensemble, on associe un et un seul élément du deuxième ensemble, et réciproquement. Ces deux ensembles auront donc alors le même nombre d’éléments.
Prenons donc un chemin du premier ensemble. De ce chemin, on conserve toute la partie qui suit la première intersection avec l’axe des abscisses. En revanche, on fait le symétrique de la partie avant ce point par rapport à l’axe des abscisses. De cette manière, le chemin que nous obtenons part du point de coordonnées \((-1\,;\,1)\). Cette construction peut par ailleurs se faire en sens inverse.
Les deux ensembles sont donc de même cardinaux. Or, les chemins du deuxième ensemble sont au nombre de \(\dbinom{p+q-1}{p}\) : il reste en effet \(p\) déplacements à effectuer sur les \(p+q-1\) restants.
Ainsi, le nombre de chemins allant du point de coordonnées \((1\,;\,1)\) au point de coordonnées \((p+q\,;\,p-q)\) vaut
\[\dbinom{p+q-1}{p-1}-\dbinom{p+q-1}{p} = \dfrac{(p+q-1)!}{(p-1)!q!}-\dfrac{(p+q-1)!}{p!(q-1)!} \]
En multipliant les numérateurs et dénominateurs de la première fraction par \(p\) et ceux de la seconde par \(q\), on a alors
\[\dbinom{p+q-1}{p-1}-\dbinom{p+q-1}{p}=\dfrac{p \times (p+q-1)!}{p \times (p-1)!q!}-\dfrac{q \times (p+q-1)!}{q \times p!(q-1)!} =
\dfrac{p \times (p+q-1)!}{p!q!}-\dfrac{q \times (p+q-1)!}{ p!q!} \]
Puis, en multipliant cette fois par \(p+q\), on obtient
\[\dbinom{p+q-1}{p-1}-\dbinom{p+q-1}{p}= \dfrac{(p-q) \times (p+q-1)!}{p!q!} \times \dfrac{p+q}{p+q} = \dfrac{p-q}{p+q} \times \dfrac{(p+q)!}{p!q!} = \dfrac{p-q}{p+q} \dbinom{p+q}{p}\]
Solution au problème
Il en vient alors que la probabilité que A soit toujours en tête lors du dépouillement vaut
\[\dfrac{\dfrac{p-q}{p+q} \dbinom{p+q}{p}}{\dbinom{p+q}{p}} = \dfrac{p-q}{p+q}\]
