Des dés

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

Merci.

Pour ma part, j'ai commencé par calculer $E_{n+1}-E_n$: c'est un polynôme de degré 1.

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...

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.

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$.

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

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.

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,

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,

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

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

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.$

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$.)

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!

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.