Exercice 106

1.(a) Un chemin est déterminé par son point de départ et la suite de ses pas $\varepsilon_{i} = s_{i+1} - s_{i} \in \{-1, 1\}$, et il arrive en $s_{\ell}$ si et seulement si $\varepsilon_{0} + \cdots + \varepsilon_{\ell - 1} = s_{\ell} - s_{0}$. Si $u$ pas valent $1$ et $\ell - u$ valent $-1$, cette condition s'écrit $u - (\ell - u) = s_{\ell} - s_{0}$, soit $u = \frac{\ell + s_{\ell} - s_{0}}{2}$. Un chemin correspond donc à la partie de $\llbracket 0\,,\ell - 1 \rrbracket$ formée des indices des pas montants, de cardinal $u$, et le théorème 2 donne $$\boxed{\text{nombre de chemins de } (0, s_{0}) \text{ à } (\ell, s_{\ell}) = \binom{\ell}{u}, \qquad u = \frac{\ell + s_{\ell} - s_{0}}{2}}$$ si $\ell + s_{\ell} - s_{0}$ est pair et $|s_{\ell} - s_{0}| \leqslant \ell$, et $0$ sinon : il faut que $u$ soit un entier de $\llbracket 0\,,\ell \rrbracket$.

1.(b) Un lemme des valeurs intermédiaires. Un chemin qui va d'un entier strictement positif à un entier négatif s'annule : si $i_{0}$ est le plus petit indice tel que $s_{i_{0}} \leqslant 0$, alors $i_{0} \geqslant 1$, $s_{i_{0} - 1} \geqslant 1$, et $s_{i_{0}} \geqslant s_{i_{0} - 1} - 1 \geqslant 0$, donc $s_{i_{0}} = 0$.

Soit $\mathcal{T}$ l'ensemble des chemins de $(0, s_{0})$ à $(\ell, s_{\ell})$ qui touchent l'axe, et $\mathcal{T}'$ l'ensemble des chemins de $(0, s_{0})$ à $(\ell, -s_{\ell})$. Pour un chemin $s$ qui touche l'axe, on note $\tau(s)$ le premier indice où il s'annule, et l'on définit le chemin réfléchi $$\Phi(s) = \big(s_{0}, \dots, s_{\tau}, -s_{\tau+1}, \dots, -s_{\ell}\big), \qquad \tau = \tau(s).$$ C'est bien un chemin : les pas avant l'indice $\tau$ sont conservés, ceux qui suivent l'indice $\tau + 1$ sont changés de signe, et, puisque $s_{\tau} = 0$, $$|-s_{\tau+1} - s_{\tau}| = |s_{\tau+1}| = |s_{\tau+1} - s_{\tau}| = 1.$$ Si $s \in \mathcal{T}$, alors $\Phi(s) \in \mathcal{T}'$. Réciproquement, un chemin de $\mathcal{T}'$ va de $s_{0} > 0$ à $-s_{\ell} < 0$ : il touche l'axe par le lemme, et la même construction l'envoie dans $\mathcal{T}$. Les deux chemins $s$ et $\Phi(s)$ coïncident jusqu'à l'indice $\tau(s)$, donc ont le même premier zéro, et réfléchir deux fois après ce zéro redonne le chemin initial : $\Phi$ réalise une bijection de $\mathcal{T}$ sur $\mathcal{T}'$, d'où $$\boxed{|\mathcal{T}| = |\mathcal{T}'| = \text{nombre de chemins de } (0, s_{0}) \text{ à } (\ell, -s_{\ell})}$$

Le chemin en bleu part de $(0, 2)$, touche l'axe pour la première fois au point rouge, d'abscisse $\tau = 2$, et arrive en $(10, 2)$ ; sa partie située après $\tau$, réfléchie par rapport à l'axe, donne le chemin en pointillés ocre, qui arrive en $(10, -2)$.

2. Les $2n$ boules sont discernables, et l'univers des ordres de sortie, muni de la probabilité uniforme, a $(2n)!$ éléments. On ne retient que la suite des couleurs : chaque suite de $n$ « blanc » et $n$ « noir » provient de $n!\,n!$ ordres (lemme des bergers), donc la suite des couleurs suit la loi uniforme sur les $\binom{2n}{n}$ suites possibles. On lui associe le chemin $s_{i} =$ (blanches sorties) $-$ (noires sorties) après $i$ tirages, de $(0, 0)$ à $(2n, 0)$ ; c'est une bijection entre suites de couleurs et chemins.

L'événement étudié est « $s_{i} \geqslant 0$ pour tout $i$ ». En décalant d'une unité vers le haut, il correspond aux chemins de $(0, 1)$ à $(2n, 1)$ qui ne touchent pas l'axe. Par la question 1, ils sont au nombre de $$\binom{2n}{n} - \binom{2n}{n - 1},$$ le second terme comptant les chemins de $(0, 1)$ à $(2n, -1)$, pour lesquels $u = n - 1$. Comme $$\binom{2n}{n - 1} = \frac{(2n)!}{(n - 1)!\,(n + 1)!} = \frac{n}{n + 1}\binom{2n}{n},$$ la probabilité vaut $$\boxed{1 - \frac{n}{n + 1} = \frac{1}{n + 1}}$$ Le nombre de suites favorables, $\frac{1}{n + 1}\binom{2n}{n}$, est le nombre de Catalan de l'exercice 21, obtenu ici par la réflexion plutôt que par le lemme cyclique. Le résultat a été contrôlé par énumération pour $n \leqslant 7$ ✓.

3. Comme à la question 2, l'ordre de dépouillement fournit une suite uniforme parmi les $\binom{1\,000}{400}$ suites de $600$ voix $A$ et $400$ voix $B$, et le chemin $s_{i} =$ (voix de $A$) $-$ (voix de $B$) va de $(0, 0)$ à $(1\,000, 200)$. Décalé d'une unité, il doit aller de $(0, 1)$ à $(1\,000, 201)$ sans toucher l'axe. Les chemins qui le touchent correspondent à ceux de $(0, 1)$ à $(1\,000, -201)$, pour lesquels $u = \frac{1\,000 - 201 - 1}{2} = 399$. La probabilité vaut $$1 - \frac{\dbinom{1\,000}{399}}{\dbinom{1\,000}{400}} = 1 - \frac{400}{601}, \qquad \boxed{\text{soit } \frac{201}{601} \approx 0{,}334}$$ Plus généralement, pour $a \geqslant b$ voix, on trouve $\frac{a - b + 1}{a + 1}$. Bien que $A$ l'emporte avec $60\,\%$ des voix, il n'est resté en tête, au sens large, tout au long du dépouillement qu'avec une probabilité d'environ un tiers. La version stricte, « $A$ toujours strictement en tête », se traite de même : la première voix doit être pour $A$, puis le chemin va de $(1, 1)$ à $(1\,000, 200)$ sans toucher l'axe, et l'on trouve $$\frac{\dbinom{999}{599} - \dbinom{999}{399}}{\dbinom{1\,000}{400}} = \frac{600}{1\,000} - \frac{400}{1\,000} = \frac{a - b}{a + b} = \frac{1}{5},$$ ce que confirme un calcul par programmation dynamique ✓.

4. On code un client qui paie avec un billet de $5$ euros par un pas $+1$ et un client qui paie avec un billet de $10$ euros par un pas $-1$ : après le passage des $i$ premiers clients, la caisse contient $r + s_{i}$ billets de $5$ euros, où $s$ est le chemin de $(0, 0)$ à $(100, 10)$ associé à la file. Un client qui paie avec $10$ euros peut être servi si et seulement s'il reste au moins un billet de $5$ euros avant son passage, c'est-à-dire si $r + s_{i} \geqslant 0$ après. On peut donc servir toute la file si et seulement si $r + s_{i} \geqslant 0$ pour tout $i$, c'est-à-dire si le chemin $(r + 1 + s_{i})_{i}$, de $(0, r + 1)$ à $(100, r + 11)$, ne touche pas l'axe. Comme à la question 2, la file fournit une suite uniforme parmi les $\binom{100}{45}$ suites possibles.

Si $r \geqslant 45$, on peut toujours servir tout le monde, puisque $s_{i} \geqslant -45$. Si $0 \leqslant r \leqslant 44$, les chemins qui touchent l'axe correspondent à ceux de $(0, r + 1)$ à $(100, -r - 11)$, pour lesquels $$u = \frac{100 - (r + 11) - (r + 1)}{2} = 44 - r.$$ La probabilité de servir toute la file vaut $$\boxed{P(r) = 1 - \frac{\dbinom{100}{44 - r}}{\dbinom{100}{45}} \quad (0 \leqslant r \leqslant 44), \qquad P(r) = 1 \quad (r \geqslant 45)}$$ Pour $r = 0$, on retrouve $1 - \frac{45}{56} = \frac{11}{56}$, valeur du scrutin avec $a = 55$ et $b = 45$. Le programme suivant cherche le plus petit $r$ convenable.

from math import comb

def P(r):
    # probabilite de servir toute la file avec r billets de 5 euros
    if r >= 45:
        return 1.0
    return 1 - comb(100, 44 - r) / comb(100, 45)

r = 0
while P(r) < 0.95:
    r += 1
print(r, P(r), P(r - 1))

Il affiche $r = 8$, avec $P(8) \approx 0{,}968$ et $P(7) \approx 0{,}944$ : $$\boxed{r = 8}$$ La formule a été confirmée, pour tout $r \in \llbracket 0\,,46 \rrbracket$, par un calcul direct par programmation dynamique ✓. Huit billets de $5$ euros suffisent dans $95\,\%$ des cas, alors que le pire cas, où les $45$ billets de $10$ euros arrivent en tête, en demanderait $45$.

À retenir. La réflexion remplace une condition difficile à compter, « ne jamais passer sous un niveau », par un simple changement de point d'arrivée. Toute la difficulté est de bien coder le problème : choisir le pas, placer le niveau interdit, et décaler le chemin pour que ce niveau devienne l'axe.

Les quatre derniers exercices sont des problèmes en autonomie ; chacun commence par l'idée directrice.