Des dés — Les-mathematiques.net The most powerful custom community solution in the world

Des dés

Bonjour,
Dans deux jours ce sera l'anniversaire de I. Kaplansky. En lisant un de ses
problèmes j'ai pensé à ceci:
On lance un dé $n$ fois. Chaque suite de $6$ consécutifs
de longueur $i$ fait gagner $6^{2+i}$ euros, $i>0$.
Ainsi pour $n=4$, on gagne $1512$ euros avec $6, 2, 6, 6.$
Calculer $E_n$ l'espérance de gain.

Réponses

  • Excellent ! Voilà qui me permet de commencer ma journée avec un bel éclat de rire !
    Je vous engage tous à chercher l'exo.

    Merci.
  • En traitant à la main les premières valeurs de $n$, j'ai trouvé : $E_1 = 36$, $E_2 = 96$, $E_3 = 181$ et $E_4 = 291$.
    Je ne suis pas allé plus loin car le nombre de cas à envisager commence à être un peu lourd. Cependant, après quelques essais numériques, j'ai remarqué qu'il s'agissait également des 4 premiers termes de la suite $\dfrac{1}{2}(25n^2+45n+2)$. Peut-être est-ce la formule générale...
  • Pour ma part, j'ai commencé par calculer $E_{n+1}-E_n$: c'est un polynôme de degré 1.
  • Moi aussi j'ai le droit de rire! Mais je trouve
    $$
    E_{n+1}-E_n=25n+40.
    $$
    Où est la blague?
  • Salut Lucas,

    Bon, ce n'est pas si drôle que ça, mais intuitivement, j'avais d'abord pensé que chaque terme apportait une contribution, qui formaient toutes ensembles un champ "presque" stationnaire, ce qui, avec le théorème ergodique, donnait une récompense proportionnelle à $n$. Le hic, c'est que le champ stationnaire qui approche la contribution de chaque terme, mettons $K.6^{L_n}$ où $L_n$ est le nombre de $6$ à gauche de $n$ n'est pas intégrable, d'où mon erreur, qui a postériori m'a bien fait rire.

    C'est d'ailleurs assez rigolo quand on y pense, car si on donnait une récompense
    $\rho^{n+2}$, avec $\rho<6$, ça marcherait et on aurait $E^{\rho}_n$ proportionnel à $n$. A l'inverse pour $\rho>6$, $E^{\rho}_n$ croit exponentiellement vite, il y a croissance exponentielle de $E^{\rho}_n$.

    Bon, maintenant, challenge (on revient à $\rho=6$): que dire du comportement de $G_n/n^2$ (en probas, déjà) ?
    Eh bien ça a l'air assez dur à étudier car les moments d'ordre supérieur à 1 du gain croissent exponentiellement vite avec $n$.
    Pour l'instant je sais que $E_n$ est p.s. un $o(n^{2+\epsilon})$.
    As tu mieux ?

    PS : dans mes souvenirs, je crois que j'ai $E_{n+1}-E_n=25n+35$, mais on n'est pas à une vache près...
  • Bonjour,

    Si cela peut aider:
    Le problème de Kaplansky se trouve
    dans le Mathematical Monthly de Mars 1946-Vol 53-n°3-p 158.
  • Ah ok aléa, j'ai cru un moment que la réponse était un calembour...

    > que dire du comportement de $ G_n/n^2$

    Oui, ça a l'air coton. J'ai quand même l'impression que les gains sont "trop bien calibrés" sur 6 pour que l'on arrive à contrôler cette limite.
  • Chers amis,

    voici ma solution. Soit $p_n(u) = \sum_{k=0}^n p_{n, k} u^k $ la fonction génératrice probabiliste ou le terme $p_{n, k}$ signifie la probabilité qu'on vient de voir une sequence de $6$ de longeur $k$ a la fin de $n$ essais.

    Alors on a $p_0(u) = 1$ et pour $n\ge 1$, $p_{n+1}(u) = \frac{1}{6} u p_n(u) + \frac{5}{6} p_n(1).$ Etant donné que $p_n(u)$ est une fonction génératrice probabiliste, on a $p_n(1) = 1$ et on trouve $p_{n+1}(u) = \frac{1}{6} u p_n(u) + \frac{5}{6}.$

    En utilisant la definition de l'espérance de gain, on a
    \[ E_n = 6^2
    \left( \frac{5}{6} \sum_{m=1}^{n-1} (p_m(6) - p_m(0) ) + p_n(6) - p_n(0) \right).\]

    Par la récurrence pour $p_n(u)$ on obtient immediatement que $p_n(0) = \frac{5}{6}$ quand $n\ge 1$. Ce qui plus est, $p_{n+1}(6) = p_n(6) + \frac{5}{6}$ ce qui donne $p_n(6) = 1 + n \frac{5}{6}.$ Avec ces valeurs, on a
    \[ E_n = 6^2
    \left( \frac{5}{6} \sum_{m=1}^{n-1} \left(1 + m \frac{5}{6} - \frac{5}{6} \right) +
    1 + n \frac{5}{6} - \frac{5}{6} \right).\]

    Il nous faut quelques simplifications pour conclure:
    \[ E_n = 6^2
    \left( \frac{25}{72} n^2 + \frac{5}{8} n + \frac{1}{36} \right) =
    \frac{25}{2} n^2 + \frac{45}{2} n + 1. \]

    Les premieres valeurs sont $36, 96, 181, 291, 426.$

    Vous trouverez en pièce jointe un fichier MAPLE pour verifier ces valeurs.

    Amicalement,

    Marko
  • Puisque l'heure semble venue de donner les solutions, voici la mienne.
    Marko, ta solution est très jolie, mais je ne suis pas sûr de bien comprendre comment tu obtiens ta première expression pour $E_n$.

    Amicalement,

    --

    \newcommand{\1}{1\hspace{-2.7mm}1}
    \newcommand{\E}{\ensuremath{\mathbb{E} }}
    On lance $n$ fois un dé à $M$ faces. Chaque séquence de $k$ ``M'' consécutifs rapporte $6^k$ points. On note $G_n$ le nombre de points marqués.
    Calculer $E_n=\E[G_n]$.

    On pose $L_n=\inf\{k\ge 0; X_{n-k}\ne M\}\wedge n$ (c'est le nombre de ``$M$'' consécutifs à droite du $n+1$ème terme.


    \begin{eqnarray*}
    G_{n+1}-G_n& =& (M^{L_n+1}-M^{L_n})\1_{\{X_{n+1}=M\}}\1_{\{L_n>0\}}+M\1_{\{X_{n+1}=M\}}\1_{\{L_n=0\}} \\
    & = & M^{L_n}(M-1)\1_{\{X_{n+1}=M\}}+\1_{\{X_{n+1}=M\}}\1_{\{L_n=0\}}
    \end{eqnarray*}
    Comme $L_n$ est indépendant de $X_{n+1}$, il vient
    $$\E[G_{n+1}-G_n] = \frac{M-1}{M}\E M^{L_n}+\frac{1}{M}\frac{M-1}M$$
    Or

    \begin{eqnarray*}
    \E[M^{L_n}] &=& (\frac1{M})^{n}M^n+ \sum_{k=0}^{n-1} (\frac1{M})^{k}(\frac{M-1}{M})M^k\\
    & = & 1+n\frac{M-1}{M}
    \end{eqnarray*}

    Soit $\E[G_{n+1}-G'_n] = (\frac{M-1}{M})^2n+(1+\frac1{M})\frac{M-1}{M}$.
    Si on pose $\alpha=\frac{M-1}{M}$, on a donc $E_{n+1}-E_n=2\alpha+(n-1)\alpha^2$.

    Cependant $E_1=1/M.M=1$, donc

    \begin{eqnarray*} E_n& =& 1+\sum_{k=1}^{n-1}u_{k+1}-u_k\\
    & =& 1 +\sum_{k=1}^{n-1} 2\alpha+(k-1)\alpha^2\\ & =& 1+2\alpha(n-1)+\frac{(n-1)(n-2)}2\alpha^2\\ & = & \frac1{2M^2}((M-1)^2n^2+(M-1)(M+3)n+2).
    \end{eqnarray*}

    Pour $M=2$, on trouve $E_n=\frac{n^2+5n+2}8$.
    Pour $M=6$, on trouve $E_n=\frac1{36}\frac{25n^2+45n+2}2$.
  • Merci pour les explications ( Aléa , Marko), elles m'ont permis de
    résoudre un autre problème.
    On dispose au départ d'un gain de $0$ point. On lance une pièce $n$ fois.
    Chaque $Pile$ augmente le gain de $1$ point, tandis que chaque
    $Face$ le divise par deux. Pour $n=2$, les gains possibles sont
    $0,1,\frac{1}{2},2$. Calculer l'espérance de gain $E_n$.
    Curieusement, il n'y a plus de polynômes en $n$ mais des
    puissances de $3$ et de $2$.
  • Chers lecteurs,

    ma première expression pour $E_n$ se obtient comme représentation de deux cas possibles. Premier, $\frac{5}{6} 6^2 ( p_m(6) - p_m(0))$ represente l'espérance de gain en allant du $m$-ieme essai au suivant. En moyen, on recoit la somme $6^2 (p_m(6) - p_m(0))$ avec une probabilité de $\frac{5}{6}$ (fin de suite de $6$ consécutifs). Deuxième, si la derniere valeur etait une $6$, alors on recoit, en moyen, la somme $6^2 (p_n(6) - p_n(0))$ avec une probabilité certaine (un). Il ne reste qu'a trouver la somme de ces contributions.

    Amicalement,

    Marko
  • Bonjour a tous,

    je vous presente la solution du deuxième probleme de Cidrolin. Soit $p_n(u) = \sum_{k=0}^n p_{n, k} u^k $ la fonction génératrice probabiliste ou le terme $p_{n, k}$ signifie la probabilité du gain $k$ avec $n$ essais. On a donc $p_0(u) = 1$ et

    \[ p_{n+1}(u) = \frac{1}{2} \, u \, p_n(u) + \frac{1}{2} \, p_n\left( u^\frac{1}{2} \right).\]

    Nous n'avons pas besoin d'une forme explicite de $p_n(u)$, etant donné que la valeur que nous cherchons est

    \[ E_n = \left. \frac{d}{du} p_n(u) \right|_{u=1} . \]

    On continue donc en dérivant la récurrence:

    \[ p'_{n+1}(u) = \frac{1}{2} \, p_n(u) + \frac{1}{2} \, u \, p'_n(u) +
    \frac{1}{2} \,
    p'_n\left( u^\frac{1}{2} \right) \, \frac{1}{2} \left( u^{-\frac{1}{2}} \right) .\]

    Rappellons la definition de $p_n(u)$: on a $p_n(1) = 1,$ ce qui donne

    \[ p'_{n+1}(1) = \frac{1}{2} + \frac{1}{2} \, p'_n(1) +
    \frac{1}{2} \, p'_n(1) \, \frac{1}{2} .\]

    On conclut que la recurrence pour $E_n$ est $\left(E_0 = 0\right)$:

    \[ E_{n+1} = \frac{3}{4} E_n + \frac{1}{2} \quad \mbox{d'ou} \quad E_n = 2 - 2 \left( \frac{3}{4} \right)^n .\]

    Les premiers valeurs sont $1/2,{\frac {7}{8}},{\frac {37}{32}},{\frac {175}{128}},{\frac {781}{512}},{\frac {3367}{2048}},{
    \frac {14197}{8192}},{\frac {58975}{32768}},{\frac {242461}{131072}},{\frac {989527}{524288}}.$

    Amicalement,

    Marko

    Vous trouverez en pièce jointe un fichier MAPLE pour verifier ces valeurs.
  • Heu, là c'est un peu le marteau-pilon et la mouche

    $G_{n+1}=(G_n+1)1_{P_{n+1}}+\frac{G_n}2 1_{F_{n+1}}$, on prend l'espérance et ça roule.

    Par contre, si tu arrives à préciser la concentration de $G_n$, c'est intéressant.
  • Greetings.

    Vous avez peut-être raison que c'est le marteau-pilon et la mouche, mais je crois que en lisant mon message avec attention, vous verrez que le calcul est pareil à celui que vous proposez.

    Par contre, le concept de "concentration" ne me dit rien, pouvez vous m'éclairer?

    Amicalement,
    Marko
  • Marko, j'ai bien lu ton message avec attention, mais je ne suis quand même pas tout à fait d'accord.

    Tu calcules la fonction génératrice (probabiliste), c'est à dire la fonction $p_n:u\mapsto \mathbb{E} [u^{G_n}]$. Cette fonction contient toute l'information sur la loi de $G_n$, en particulier l'espérance, puisque $ \mathbb{E}[G_n]=p'_n(1)$. Mais quand même, la preuve probabiliste que je propose est beaucoup plus courte, car elle fait une meilleure utilisation de l'indépendance que la preuve combinatorique:

    $G_{n+1}=(G_n+1)1_{P_{n+1}}+\frac{G_n}2 1_{F_{n+1}}$ donne
    $\mathbb{E}[G_{n+1}]=\mathbb{E}[G_n+1]\mathbb{E}[1_{P_{n+1}}]+\mathbb{E}[\frac{G_n}2]\mathbb{E}[ 1_{F_{n+1}}]$,
    soit $E_{n+1}=(E_{n}+1+E_n/2)/2$, ce qui donne la récurrence: tu avoueras que c'est plus court, ce qui est bien normal puisqu'on travaille directement avec l'objet qui contient exclusivement l'information qui nous intéresse.

    D'une certaine manière, on peut dire que le problème est trop simple pour que la puissance de la fonction génératrice soit utile (mais je reconnais que c'est très particulier, c'est lié au fait que $z\mapsto z+1$ et $z\mapsto z/2$ sont toutes deux affines).

    Tout cela étant dit, l'espérance c'est bien gentil, mais ça dit très peu de choses sur la variable. On aimerait controler sa concentration, ses fluctuations si tu préfères, donc au moins sa variance.
    Or la fonction génératrice donne accès aux moments (tout au moins en théorie), puisque, par exemple, $\mathbb{E} [G_n(G_n-1)]=p''_n(1)$. Saurait-on calculer $p''_n(1)$ ?

    Amicalement,
  • Merci pour vos explications, evidement ce que vous faites est plus court. C'est tres gentil de me donner l'opportunite de montrer la puissance de la fonction génératrice en calculant $p''_n(1)$. Je crois que oui, c'est faisable, je vais m'y mettre quand je rentre ce soir.

    Amicalement,

    Marko
  • Chers amis,

    je viens de rentrer et je me suis mis a calculer $p''_n(1).$ Il s'agit la d'un calcul tres simple: $p_n'(1)$ et $p''_n(1)$ c'est pareil.

    En calculant la dérivée de la recurrence que nous avons vue, on trouve

    \[ p''_{n+1}(u) = \frac{1}{2} p'_n(u) + \frac{1}{2} p'_n(u) + \frac{1}{2} u p''_n(u)
    + \frac{1}{4} p''_n\left( u^{\frac{1}{2}} \right) \frac{1}{2} u^{-\frac{1}{2}} u^{-\frac{1}{2}}
    - \frac{1}{8} p'_n\left( u^{\frac{1}{2}} \right) u^{-\frac{3}{2}} ,\]

    ce qui donne directement $\left( \mbox{avec} \quad F_n = p''_n(1) \right)$:

    \[ F_{n+1} = E_n + \frac{1}{2} F_n + \frac{1}{8} F_n - \frac{1}{8} E_n \quad \mbox{d'ou} \quad F_{n+1} = \frac{5}{8} F_n +
    \frac{7}{8} \left( 2 - 2 \left( \frac{3}{4} \right)^n \right).\]

    Cette recurrence est facile a resoudre (pas forcement a la main). Avec MAPLE, on trouve donc finalement:

    \[ F_n = \frac{14}{3}+{\frac {28}{3}}\, \left( \frac{5}{8} \right) ^{n}-14\, \left( \frac{3}{4} \right) ^{n}.\]

    Amicalement,

    Marko
  • Bonjour,

    C'est fini pour l'espérance, la variance. Une question me tire souci:
    le nombre de gains possibles ($4$ pour $n=2$; $7$ pour $n=3$ ) peut-il se
    trouver avec la fonction génératrice?

    Très cordialement
    Édouard
  • Bonjour,

    la vous êtes tombé sur quelque chose d'assez intéressant. J'ai calculée votre sequence (voir pièce jointe), ce que donne:

    \[ 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, \]

    Je ne vois pas comment on peut la trouver avec la fonction génératrice, mais la OEIS la connait.

    Il s'agit de $f_{n+3}-1}$, avec $f_n$ les nombres de Fibonacci!

    OEIS: A00071: f(n+3)-1

    On trouve donc la recurrence suivante: $ g_{n+1} = g_n + g_{n-1} + 1.$

    Quelqu'un nous offrira-t-il une preuve? La difficulté semble être qu'on peut arriver au même gain par des chemins differents dans l'arbre des possibilités.

    Amicalement,

    Marko
  • La première version de mon dernier message ne s'affiche pas bien, mais ca semble marcher maintenant.

    Marko
  • Bonjour a tous,

    est-ce que l'hypothèse suivante nous peut être utile? Soit $q(v)$ le niveau de la première apparition de la valeur $v$. Alors on a :
    \[ q(v) =
    \begin{cases}
    0 & \text{if $v=0$,} \\
    1 & \text{if $v=1$,} \\
    1 + q(v-1) & \text{if $v>1$,} \\
    2 + q(2v-1) & \text{if $v<1$ and $v>\frac{1}{2}$} \\
    1 + q(2v) & \text{if $v\le\frac{1}{2}$.}
    \end{cases} \]
    Soit $P_n$ l'ensemble des valeurs sur le niveau $n$. On aurait
    \[\begin{align}
    a_n = \left|\{ v \in P_n, \, v>1 \}\right| &=& f_{n+2}-2 \\
    b_n = \left|\{ v \in P_n, \, v\le1, v>\frac{1}{2} \}\right| &=& f_{n-1} \\
    c_n = \left| \{ v \in P_n, \, v\le\frac{1}{2} \}\right| &=& f_n+1
    \end{align} \]
    pour $n\ge 2.$
    Est-ce que ca sert a quelque chose?
    Amicalement,
    Marko
  • Une piste possible, c'est d'essayer de caractériser l'écriture en base 2 des résultats qu'on peut atteindre en $n$ coups.

    Dans ce genre de trucs, Fibonacci arrive facilement, par exemple si on cherche les mots de longueur $n$ qui n'ont pas deux "1" consécutifs.

    Ca semble être une question pour les habitués des olympiades...

    (JB, es-tu là ?...)
  • Greetings, alea,

    pouvez-vous m'aider? Il me semble qu'en appliquant l'hypothese sur $q(v)$ a $a_n$, $b_n$ et $c_n$ on devrait arriver a $a_n + b_n + c_n = f_{n+3}-1$ facilement. Il resterait alors de prouver l'hypothese. J'ai etudie l'écriture en base 2 des résultats, mais sans y pouvoir discerner une structure.

    Amicalement,

    Marko

    PS: En piece jointe, comment calculer $q(v)$ et $P_n.$
  • Heu... je n'ai pas la réponse...J'ai juste donné une piste qui me semblait raisonnable, mais je ne suis pas assez intelligent pour trouver vite, et pas assez motivé pour y passer du temps en ce moment (disons que j'ai d'autres problèmes de maths à chercher qui me nourissent...)

    Amicalement,
  • Bonjour,

    j'ecris ce message pour vous dire que oui, l'hypothèse tient bon et on peut calculer $a_n$, $b_n$ et $c_n$ en l'appliquant. En utilisant les definitions de $a_n$, $b_n$ et $c_n$, on tombe sur le systeme suivant:

    \[\begin{align}
    a_{n+1} & = & a_n + b_n + c_n -1 \\
    b_{n+1} & = & b_{n-1} + c_{n-1} - 1 \\
    c_{n+1} & = & b_n + c_n.
    \end{align} \]

    Le reste est un calcul simple. D'abord on a $b_n = c_{n+1} - c_n$, ce qui donne $a_{n+1} = a_n + c_{n+1} -1$ et $c_{n+2} = c_{n+1} + c_n - 1.$ Avec $c_1=1$ et $c_2 = 2$ on a donc immediatement $c_n = f_n + 1.$ Cela donne $b_n = f_ {n+1} + 1 - f_n - 1 = f_{n-1}.$ Finalement on a $a_{n+1} = a_n + f_{n-1} + f_n + 1 - 1 = a_n + f_{n+1} = a_1 + \sum_{k=2}^{n+1} f_k.$ Avec $a_1 = 0$, on trouve $a_n = f_{n+2} - 2.$

    C'est donc gagné, presque! J'ai du mal à croire qu'il ne se trouverait personne sur le forum qui nous prouverait l'hypothèse. (La formule pour la première apparition $q(v)$ d'une valeur $v$.) :D

    Amicalement

    Marko
  • Bonjour a tous,

    juste un petit exercice si vous voulez vérifier que vous maîtrisez $q(v)$. Montrer que
    \[ \left| \{ v \in P_n, \, v\le\frac{1}{2^k} \}\right| &=& f_{n-k+1} + 1 \]
    pour $n>k, k\ge 1.$

    Amicalement,

    Marko
  • Chers amis,

    c'est avec un grand plaisir que je vous presente une formule pour $q(v)$, $0 \le v < 1.$ (La zone difficile.)

    Ce qui plus est, alea avait raison! :)-D

    Soit $v = 0.b_1b_2b_3 \ldots b_m$. (La valeur $v$ écrite en base 2.)
    Alors $q(v) = \sum_{k=1}^m (1 + [b_k=1]) = m + \sum_{k=1}^m b_k.$

    Je la trouve assez jolie, cette formule! :D

    On va voir qu'est-ce que ca donne pour $a_n + b_n + c_n.$

    Amicalement,

    Marko

    En piece jointe, vérification de la formule.
  • Chers amis,

    me voici de nouveau avec une autre preuve de que $|q^{-1}(n)| = f_{n+3} -1.$ Nous avons vu que $q(v) = m + \sum_{k=1}^m b_k$ pour $0\le v < 1.$ En admettant l'hypothese, on trouve que
    \[ q(v) = \lfloor v \rfloor + m + \sum_{k=1}^m b_k.\]

    Par dénombrement direct, on a
    \[ \left| q^{-1}(n) \cap [0, 1) \right| = \sum_{m\ge \frac{n}{2}}^n \binom{m}{n-m}
    = f_{n+1}.\]

    Pour une valeur de $n$ quelconque, ll ne reste plus qu'à sommer les contributions pour $\lfloor v \rfloor = n, \, \lfloor v \rfloor = n-1, \, \lfloor v \rfloor = n-2, \, \ldots \lfloor v \rfloor = 0$, ce qui donne
    \[ \sum_{\lfloor v \rfloor = 0}^{\lfloor v \rfloor = n} f_{n - \lfloor v \rfloor + 1} =
    \sum_{k=0}^n f_{k+1} = f_{n+3} - 1, \quad \mbox{QED}.\]

    J’attends toujours avec une grande curiosité que quelqu'un nous présente une preuve de l'hypothese (en haut de la page).

    Amicalement,

    Marko
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!