Problème de répartition — Les-mathematiques.net The most powerful custom community solution in the world

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)

Réponses

  • Bonjour,

    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.
  • Merci à LOU16 pour cette belle démonstration que je ne connaissais pas. Je n'aurais pas pensé à numéroter les boules noires.

    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}$
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!