problème du scrutin

Imaginez huit bulletins tirés d'une urne : cinq portent A et trois portent B. Après chaque bulletin, on compare les deux totaux. Pour que A reste strictement en tête, le premier bulletin doit porter A et aucune égalité ne peut ensuite apparaître.

Le problème du scrutin demande la chance que cette avance ne disparaisse jamais lorsque l'ordre des bulletins est aléatoire. Il ne s'intéresse donc pas seulement au gagnant final : il suit l'écart tout au long du dépouillement.

Le problème du scrutin porte sur tous les ordres possibles d'un dépouillement à deux candidats. Le nombre p désigne les voix obtenues par A et le nombre q celles obtenues par B, avec p strictement supérieur à q. On suppose que les bulletins sont révélés un à un dans un ordre aléatoire, chaque ordre des p bulletins A et des q bulletins B étant équiprobable. L'événement cherché exige qu'après chaque bulletin le total de A soit strictement supérieur à celui de B.

Sous ces hypothèses, la probabilité vaut : $\frac{p-q}{p+q}\backslash frac\{p-q\}\{p+q\}$. Un ordre de dépouillement se représente aussi par un chemin sur un treillis : un bulletin A fait un pas dans une direction et un bulletin B dans l'autre. Rester strictement en tête revient à commencer par A puis à ne pas toucher la diagonale d'égalité. Parmi les chemins qui commencent par A, il y en a $\left(\genfrac{}{}{0px}{}{p+q-1}{q}\right)\backslash binom\{p+q-1\}\{q\}$. Pour chaque chemin qui rejoint ensuite la diagonale, on réfléchit sa portion allant du départ à son premier retour à l'égalité : cette bijection donne l'ensemble des chemins qui commencent par B, au nombre de $\left(\genfrac{}{}{0px}{}{p+q-1}{q-1}\right)\backslash binom\{p+q-1\}\{q-1\}$. La différence entre les deux familles vaut $\left(\genfrac{}{}{0px}{}{p+q-1}{q}\right)-\left(\genfrac{}{}{0px}{}{p+q-1}{q-1}\right)=\frac{p-q}{p+q}\left(\genfrac{}{}{0px}{}{p+q}{q}\right)\backslash binom\{p+q-1\}\{q\}-\backslash binom\{p+q-1\}\{q-1\}=\backslash frac\{p-q\}\{p+q\}\backslash binom\{p+q\}\{q\}$ chemins favorables ; divisée par les $\left(\genfrac{}{}{0px}{}{p+q}{q}\right)\backslash binom\{p+q\}\{q\}$ ordres possibles, elle explique le quotient annoncé.

William Allen Whitworth posa le problème en 1878 sous une forme légèrement différente. En 1887, Joseph Bertrand en donna une démonstration par récurrence, tandis que Désiré André proposa la démonstration par réflexion. Ce résultat relie ainsi probabilités, marches aléatoires et dénombrement de chemins.

Prenons cinq voix pour A et trois voix pour B. Les données sont p = 5, q = 3 et huit bulletins au total. Nous cherchons les ordres dans lesquels A possède plus de voix que B après chacun des huit bulletins.

1. Le nombre total d'ordres distincts est le nombre de choix des trois places occupées par B : $\left(\genfrac{}{}{0px}{}{8}{3}\right)=56\backslash binom\{8\}\{3\}=56$.

2. La formule du scrutin donne la probabilité cherchée : $\frac{p-q}{p+q}=\frac{5-3}{5+3}=\frac{1}{4}\backslash frac\{p-q\}\{p+q\}=\backslash frac\{5-3\}\{5+3\}=\backslash frac14$. La figure suit l'ordre favorable A, A, B, A, B, A, B, A : son chemin ne revient jamais sur la diagonale d'égalité.

3. Le nombre d'ordres favorables vaut donc 56 × 1/4 = 14.

4. Pour contrôler ce résultat, notons N(a, b) le nombre de chemins qui atteignent a voix pour A et b voix pour B sans égalité après le départ. Pour a > b, l'addition des deux arrivées possibles donne N(a, b) = N(a − 1, b) + N(a, b − 1), avec N(a, 0) = 1 et N(a, a) = 0. On obtient successivement N(2, 1) = 1, N(3, 1) = 2, N(3, 2) = 2, N(4, 1) = 3, N(4, 2) = 5, N(4, 3) = 5 et N(5, 1) = 4, puis N(5, 2) = 5 + 4 = 9. Ainsi, N(5, 3) = N(4, 3) + N(5, 2) = 5 + 9 = 14. On retrouve bien 14/56 = 1/4.

Pour calculer la probabilité directement, relevez les deux totaux finaux et vérifiez que p > q. Si l'ordre des bulletins est aléatoire et que l'avance doit rester stricte, la fraction (p − q)/(p + q) donne le résultat sans énumérer les dépouillements.

Pour contrôler un petit cas, tracez un chemin dont chaque pas code un bulletin. La diagonale représente une égalité ; un chemin favorable reste du côté où le total de A dépasse celui de B. Une récurrence sur les sommets est préférable si vous voulez compter les ordres un par un.

Pour modéliser une autre succession de gains et de pertes, la marche aléatoire fournit le cadre naturel. La formule du scrutin ne s'emploie telle quelle que lorsque les pas correspondent à deux types de bulletins, avec des ordres équiprobables et une avance strictement positive recherchée à chaque étape.

Victoire finale et avance permanente. Savoir que A termine avec cinq voix contre trois fixe le vainqueur, mais pas le trajet du score. L'ordre B, A, A, A, A, A, B, B conduit au même résultat final sans que A ait été en tête après le premier bulletin.

Probabilité conditionnelle et ordre aléatoire. Le problème fixe déjà les totaux p et q, puis rend aléatoire leur ordre de révélation. Un modèle où chaque voix serait tirée indépendamment avec une probabilité inconnue ne possède pas le même espace d'issues.

Égalité interdite. « Strictement en tête » signifie qu'un score de 1–1 après deux bulletins suffit à rendre l'ordre défavorable. Si les égalités intermédiaires sont autorisées, l'événement change et la formule (p − q)/(p + q) ne doit pas être appliquée sans adaptation.

Totaux à égalité. L'hypothèse p > q est indispensable. Au seuil p = q, A ne peut pas être strictement en tête à l'étape finale ; la probabilité de l'événement demandé est donc nulle.

Ordres non équiprobables. Le quotient classique suppose que chaque ordre comportant p bulletins A et q bulletins B a la même probabilité. Si certains ordres sont favorisés par le protocole, compter les chemins ne suffit plus ; il faut additionner leurs probabilités propres.

Plus de deux candidats. La formule compare exactement deux totaux. Avec trois candidats ou davantage, plusieurs frontières d'égalité interviennent ; le quotient (p − q)/(p + q) ne décrit plus à lui seul l'événement.

Principe de réflexion — Voir la bijection qui transforme les chemins touchant une frontière en chemins plus simples à compter.

dénombrement — Replacer le comptage des ordres de bulletins parmi les techniques générales de combinatoire.