La fratrie

Dans le problème de la fratrie on fixe un ensemble {1, 2, 3, …, m − 1, m} d’emplacements d’un album, et on a un ensemble {1, 2, 3, …, n, …} de moments quand un certain ainé achète une vignette. Puisque l’ainé est devenu cupide, il ne donne plus ses doublons aux petits frères, mais colle les vignettes l’une sur l’autre jusqu’à ce que le dernier emplacement soit rempli (d’une seule vignette, évidemment). Supposons (sans trop restreindre la généralité) que ce dernier emplacement porte le numéro m. Notre espace de probabilité contient alors chaque surjection s : [n] → [m − 1] pour n = m − 1, m, m + 1, m + 2, … avec la probabilité (1/m)^{n}. Soit la variable aléatoire X_{i}^{(k)} égal à 1 si la vignette i arrive précisément k fois et égal à 0 sinon, et posons X^{(k)} := ∑_{i=1}^{m−1} X_{i}^{(k)}. Nous nous proposons de calculer le nombre moyen d’emplacement (parmi l’ensemble {1, 2, 3, …, m − 1}) où les vignettes s’entassent exactement jusqu’à la hauteur k quand l’album est rempli. En tant qu’amateurs des fonctions génératrices, ceci nous conduit à l’espérance mathématique

∑_{k=0}^{∞} 𝔼[X^{(k)}] · t^{k} = (m − 1) · ∑_{k=0}^{∞} 𝔼[X_{1}^{(k)}] · t^{k} = (m − 1) · (m − 2)! · ∑_{k=0}^{∞} 𝔼[X̃_{1}^{(k)}] · t^{k},

où la variable aléatoire X̃_{1}^{(k)} signifie que l’on restreint l’espace de probabilité en supposant que les vignettes 2, 3, …, m − 1 arrivent pour la première fois dans l’ordre naturel. Autrement dit, l’ainé commence par acheter i_{1} fois, i_{1} ≥ 0, la vignette 1, ce qui fournit, dans notre espérance mathématique, le poids t^{i_{1}} · (1/m)^{i_{1}}. Ensuite, il achète une première fois la vignette 2, dont le poids (i. e. la probabilité) vaut 1/m. Après cela, il achète i_{2} fois, i_{2} ≥ 0, une des vignettes 1 ou 2, contribuant le poids [(t/m) + (1/m)]^{i_{2}}. Ensuite, il achète une première fois la vignette 3, dont le poids vaut 1/m. Après cela, il achète i_{3} fois, i_{3} ≥ 0, une des vignettes 1, 2 ou 3, contribuant le poids [(t/m) + (1/m) + (1/m)]^{i_{3}}, et ainsi de suite. On obtient alors la formule

\begin{aligned}∑_{k=0}^{∞} 𝔼[X̃_{1}^{(k)}] · t^{k} & = ∑_{i_{1}=0}^{∞} ∑_{i_{2}=0}^{∞} … ∑_{i_{m−1}=0}^{∞}(\frac{t}{m})^{i_{1}} · \frac{1}{m}(\frac{t + 1}{m})^{i_{2}} · . . . · \frac{1}{m}(\frac{t + m − 2}{m})^{i_{m−1}} \\ & = \frac{1}{1 − t/m} · \frac{1}{m − 1 − t} · . . . · \frac{1}{2 − t}, \end{aligned}

dénombrant effectivement des surjections si et seulement si la vignette 1 est achetée au moins une fois, c’est-à-dire si et seulement si le facteur t apparaît au moins une fois. Une multiplication par (m − 1)! fournit notre résultat principal

∑_{k=0}^{∞} 𝔼[X^{(k)}] · t^{k} = \frac{1}{1 − t/m} · \frac{1}{1 − t/(m − 1)} · . . . · \frac{1}{1 − t/2},

dont seul le terme constant est faux, puisque 𝔼[X^{(0)}] = 0.