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.
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Je vous engage tous à chercher l'exo.
Merci.
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...
$$
E_{n+1}-E_n=25n+40.
$$
Où est la blague?
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...
Si cela peut aider:
Le problème de Kaplansky se trouve
dans le Mathematical Monthly de Mars 1946-Vol 53-n°3-p 158.
> 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.
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
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$.
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$.
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
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.
$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.
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
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,
Amicalement,
Marko
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
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
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
Marko
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
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à ?...)
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.$
Amicalement,
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$.)
Amicalement
Marko
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
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!
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.
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