Problème de répartition
Je vous propose le problème suivant que je vais présenter sous la forme d'un jeu dépendant de deux entiers k et n avec 0 < k < n. (On pourra prendre k = 1 dans un premier temps).
Dans une urne est placé des boules blanches et des boules noires pour un total de n boules.
On tire successivement toutes les boules.
Après avoir pioché k boules blanches, chaque boule noire piochée rapporte 1 point.
Quel doit être la répartition des boules blanches et noires dans cette urne pour en moyenne maximiser nos points ?
(On pourra se contenter d'un développement asymptotique de la répartition des boules en fonction de n pour k fixé en l'absence d'expression simple du résultat)
Dans une urne est placé des boules blanches et des boules noires pour un total de n boules.
On tire successivement toutes les boules.
Après avoir pioché k boules blanches, chaque boule noire piochée rapporte 1 point.
Quel doit être la répartition des boules blanches et noires dans cette urne pour en moyenne maximiser nos points ?
(On pourra se contenter d'un développement asymptotique de la répartition des boules en fonction de n pour k fixé en l'absence d'expression simple du résultat)
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Si simple est l'expression de l'espérance cherchée qu'il n'y a rien d'asymptotique dans ce qui suit:
Soit $p$ le nombre de boules blanches présentes dans l'urne et soit $X$ le nombre de boules noires qui, lors du tirage, apparaissent après l'extraction de la $k-\text{ième}$ boule blanche. $\:(1\leqslant k \leqslant p \leqslant n).\:$ Alors:$$ \mathbb E(X) = \dfrac {(n-p)(p+1-k)}{p+1}$$
et il est dès lors facile de déterminer le maximum de $\mathbb E(X) $ pour $p$ variant dans $[k;n]\:\:$.(étude des variations d'une fonction rationnelle.)
Voici quelques explications:
Pour $i \in [\![1;n-p]\!], \: N_i \:$ est la boule noire numéro $i$ et $\:X_i$ désigne la variable aléatoire définie par: $$\: X_i = \left\{\begin{array}{cl} 1& \text{si au moins}\: k\:\text{boules blanches sont tirées avant}\; N_i \\
0 &\text{sinon} \end{array}\right.$$
Alors: $\:\mathbb E(X)= \displaystyle \sum _{i=1}^{n-p}\mathbb E(X_i)= (n-p) \mathbb E(X_1) .\quad$ Il reste donc à évaluer $\mathbb E(X_1)$.
Soit $Y$ le nombre de boules blanches qui, dans le tirage, précèdent $N_1$.
Il est ici intéressant de remarquer que $\boxed{Y\:\text{ est uniformément distribuée dans}\: [\![0;p]\!].}\qquad$ Ainsi:$$\: \mathbb E(X_1) = \Pr[Y\geqslant k] = \dfrac {p+1-k}{p+1} \:\square$$
$\Omega := \mathfrak S_n\:\:(\text {ensemble des permutations de}\:[\![1;n]\!])$ est muni de la probabilité uniforme.$\quad \#\Omega = n! \:.$
$E_k$ est l'évènement: " La boule $N_1$ est, dans le tirage, précédée par exactement $k$ boules blanches".
Alors $\#E_k =\displaystyle \binom n{p+1}\times p! \times (n-p-1)!\:.\qquad \Pr (E_k) =\dfrac {\#E_k}{\#\Omega}= \dfrac 1{p+1}.$
$\bullet \:\displaystyle \binom n{p+1}$ est le nombre de façons de choisir l'ensemble des rangs du tirage dévolus aux boules blanches et à $N_1$.
$\bullet \:p!$ est le nombre de façons de classer ces boules au sein de cet ensemble en plaçant $N_1$ en $(k+1)$-ième position.
$\bullet \:(n-p-1)! $ est le nombre de façons de classer les boules noires restantes parmi les $(n-p-1)$ rangs disponibles.
Cette méthode permet aussi de calculer l'espérance de $Z_k$, rang de tirage de la $k$-ième boule blanche (pour $1\leq k\leq p$) puisque $Z_k$ est reliée à $X$ (nombre de boules noires tirées après la $k$-ième boule blanche) par $Z_k=k+(n-p-X)$.
On obtient $\mathbb E(Z_k) = \dfrac {k(n+1)}{p+1}$. Je savais montrer cette formule d'une autre façon que je précise ci-dessous.
On pose $Z_0=0\; ,\; Z_{p+1}=n+1$ puis $T_k=Z_k-Z_{k-1}$ pour $1\leq k\leq p+1$.
L'application qui à une valeur prise par $(Z_1,\dots,Z_p)$ associe une valeur prise par $(T_1,\dots,T_{p+1})$ est une bijection de l'ensemble des parties à $p$ éléments de $[[1,n]]$ vers l'ensemble des $\{t_1,\dots,t_{p+1}\}\in (\N^*)^{p+1}$ tels que $\sum t_k=n+1$.
L'équiprobabilité sur les parties à $p$ éléments de $[[1,n]]$ est donc équivalente à l'équiprobabilité sur l'ensemble des $(t_1,\dots,t_{p+1})\in (\N^*)^{p+1}$ tels que $\sum t_k=n+1$.
Les variables $T_k$ pour $1\leq k\leq p+1$ ont donc la même loi, donc la même espérance qui est égale à $\dfrac{n+1}{p+1}$ puisque la somme des $T_k$ est égale à $n+1$. Par suite $\mathbb E(Z_k)=\mathbb E(T_1)+\dots+\mathbb E(T_k)=\dfrac{k(n+1)}{p+1}$