Calcul d'une espérance

[MB]

Bonjour à tous,

En considérant l’expérience aléatoire qui consiste à déplacer un jeton sur les $N$ cases d'un plateau similaire à celui représenté ci-dessous (cas $N=12$), jusqu’à ce qu’il retombe sur sa position initiale, en effectuant à chaque étape un lancer de dé donnant le nombre de cases à parcourir, on note $X$ la variable aléatoire donnant le nombre d'étapes effectuées.

Code : Tout sélectionner

unitsize(1cm);

void draw_unitsquare(int x, int y, int n)
{
    filldraw(shift(x,y)*unitsquare,lightgray,mediumgray);
    label(format("$%i$",n),(x+1/2,y+1/2));
}

draw_unitsquare(0,0,0);
draw_unitsquare(0,1,1);
draw_unitsquare(0,2,2);
draw_unitsquare(0,3,3);
draw_unitsquare(1,3,4);
draw_unitsquare(2,3,5);
draw_unitsquare(3,3,6);
draw_unitsquare(3,2,7);
draw_unitsquare(3,1,8);
draw_unitsquare(3,0,9);
draw_unitsquare(2,0,10);
draw_unitsquare(1,0,11);

Une simulation me conduit à conjecturer que $E(X)=N$, mais serait-il possible de valider (ou d'invalider) cette conjecture ?

[guiguiche]

Salut

Ton résultat semble bon pour $N=2$ avec un dé à 6 faces (je n'ai pas essayé avec un autre nombre de faces). Mais, dans le cas général, c'est bien compliqué ton exo !
Pas d'idée car il traîne une part d'arithmétique (que je ne pratique plus depuis longtemps) dans le calcul.
Sinon, par réflexe :

1. Découper avec des variables $X_i$ égales au résultat au lancer numéro $i$.
2. Remarquer que : $\ds [X>n] = [X_1\not\equiv0(N)]\cap [X_1+X_2\not\equiv0(N)]\cap\dots\cap[X_1+X_2+\dots+X_n\not\equiv0(N)]$.
3. Utiliser $\ds\mathbb{E}(X)=\sum_{n=0}^{+\infty}{\mathbb{P}(X>n)}$.

[MB]

Salut,

Je ne l'ai pas précisé mais le problème concerne effectivement un dé à six faces, même si le nombre de faces semble sans influence sur l'espérance de $X$. Sinon, j'avais également tenté une approche similaire à la tienne, mais le problème de dénombrement m'a semblé assez complexe et je n'ai pas creusé.

Le résultat conjecturé étant on ne peut plus simple, je me dis qu'il y a possiblement une manière plus astucieuse de procéder, sans avoir à calculer $\mathbb{P}(X=n)$ ou $\mathbb{P}(X>n)$, ce qui semble un peu délicat.

[Edit] Pour revenir sur le nombre de faces du dé, je me dis que si on peut prouver que l'espérance ne dépend pas de ce nombre, alors on peut considérer un "dé à une face" qui donne $X=N$ et donc $E(X)=N$.

[MB]

Au cas où, voici le code Python utilisé pour la simulation.

Code : Tout sélectionner

import random

def D():
    return random.randint(1,6)

def X(m):
    s = D()
    n = 1
    while not s%m == 0:
        s = s+D()
        n = n+1
    return n

def échantillon_X(m,n):
    e = {}
    for k in range(n):
        x = X(m)
        e[x] = e.get(x,0)+1
    return e

m = 12
n = 100000
e = échantillon_X(m,n)
s = 0
for key in sorted(e.keys()):
    print ("{:<4} {:<6}".format(key,e[key]))
    s = s+key*e[key]
print('moyenne = {}'.format(s/n))

Et un exemple d'échantillon de X.

Code : Tout sélectionner

2    2846  
3    11407 
4    9567  
5    5851  
6    6390  
7    6575  
8    5224  
9    4803  
10   4378  
11   4133  
12   3624  
13   3283  
14   3049  
15   2740  
16   2537  
17   2203  
18   2055  
19   1825  
20   1634  
21   1467  
22   1413  
23   1249  
24   1153  
25   1020  
26   926   
27   798   
28   689   
29   699   
30   592   
31   562   
32   529   
33   473   
34   423   
35   346   
36   339   
37   301   
38   261   
39   259   
40   234   
41   222   
42   204   
43   167   
44   149   
45   134   
46   119   
47   109   
48   91    
49   87    
50   90    
51   77    
52   60    
53   52    
54   44    
55   51    
56   45    
57   41    
58   32    
59   37    
60   39    
61   29    
62   27    
63   22    
64   21    
65   14    
66   14    
67   19    
68   12    
69   17    
70   13    
71   6     
72   6     
73   5     
74   9     
75   6     
76   9     
77   7     
78   3     
79   5     
80   3     
81   4     
82   9     
83   4     
85   3     
86   1     
87   3     
88   2     
89   2     
90   4     
92   1     
93   2     
94   1     
96   4     
97   1     
100  1     
102  1     
112  1     
113  1     
120  1     
moyenne = 12.02417

[guiguiche]

J'utilise numpy (c'est ce que je dois enseigner !) :

Code : Tout sélectionner

import numpy as np ; import numpy.random as rd
m=10**4 ; f=6
for N in range(2,21) :
    X=np.zeros(m)
    for i in range(m) :
        T=0 ; T+=rd.randint(f)+1 ; X[i]+=1
        while (T%N)!=0 :
            T+=rd.randint(f)+1 ; X[i]+=1
    print(N,np.mean(X))

Code : Tout sélectionner

2 1.9822
3 3.0043
4 3.9991
5 5.0216
6 6.0324
7 7.0312
8 7.9896
9 8.9319
10 10.0173
11 10.8177
12 11.7963
13 12.9058
14 14.1138
15 15.1991
16 16.0744
17 17.0656
18 18.1138
19 19.0155
20 19.8659

[guiguiche]

Et avec 9 faces au dé :

Code : Tout sélectionner

2 1.993
3 2.9909
4 4.0403
5 5.0769
6 5.9949
7 6.9293
8 8.0188
9 9.1966
10 9.9182
11 11.0665
12 11.8959
13 13.1742
14 14.0256
15 14.9243
16 15.6856
17 17.0419
18 18.1596
19 18.7655
20 20.099

[MB]

J'ai donc l'impression que numpy mène à la même conjecture.
D'ailleurs ça marche également lorsque le nombre de cases parcourues à chaque étape correspond à la somme d'un dé à 6 faces et d'un dé à 9 faces.

Code : Tout sélectionner

import random

def D():
    return random.randint(1,6)+random.randint(1,9)

def X(m):
    s = D()
    n = 1
    while not s%m == 0:
        s = s+D()
        n = n+1
    return n

def échantillon_X(m,n):
    e = {}
    for k in range(n):
        x = X(m)
        e[x] = e.get(x,0)+1
    return e

m = 12
n = 100000
e = échantillon_X(m,n)
s = 0
for key in sorted(e.keys()):
    print ("{:<4} {:<6}".format(key,e[key]))
    s = s+key*e[key]
print('moyenne = {}'.format(s/n))

Voici un échantillon.

Code : Tout sélectionner

1    7555  
2    7262  
3    7396  
4    6491  
5    6041  
6    5470  
7    5197  
8    4803  
9    4224  
10   3869  
11   3569  
12   3199  
13   2860  
14   2727  
15   2537  
16   2163  
17   2060  
18   1930  
19   1720  
20   1664  
21   1474  
22   1266  
23   1254  
24   1137  
25   1031  
26   910   
27   864   
28   767   
29   691   
30   642   
31   621   
32   549   
33   519   
34   436   
35   429   
36   392   
37   349   
38   337   
39   320   
40   267   
41   246   
42   221   
43   228   
44   196   
45   187   
46   172   
47   137   
48   134   
49   112   
50   122   
51   95    
52   92    
53   78    
54   83    
55   69    
56   82    
57   55    
58   59    
59   55    
60   57    
61   41    
62   48    
63   37    
64   30    
65   25    
66   27    
67   29    
68   31    
69   31    
70   21    
71   15    
72   23    
73   22    
74   11    
75   14    
76   7     
77   7     
78   7     
79   7     
80   10    
81   8     
82   5     
83   6     
84   5     
85   4     
86   2     
87   4     
88   3     
89   5     
90   1     
91   6     
92   1     
93   2     
95   4     
96   1     
97   2     
98   2     
99   1     
100  4     
101  1     
103  2     
104  3     
106  2     
107  1     
108  1     
109  2     
110  1     
111  1     
114  1     
124  1     
128  1     
131  1     
136  1     
moyenne = 11.97737

Il doit bien y avoir un argument relativement simple permettant de justifier ça non ?

[guiguiche]

Dans le cas où $N=2$, on obtient que $X\hookrightarrow\mathcal{G}(1/2)$ qui a bien pour espérance 2 (avec 6 faces mais je pense que le même raisonnement convient pour un autre nombre de faces). Au delà, je n'ai pas vraiment insisté même si le début des tests pour $N=3$ m'amène à penser que $X\hookrightarrow\mathcal{G}(1/3)$.

Edit. D'ailleurs, je pense qu'il s'agit bien du temps d'attente d'un multiple de $N$ et les multiples de $N$ sont en proportion $1/N$ dans $\N$ ce qui donnerait le résultat immédiatement.

[MB]

J'avais aussi pensé à une loi géométrique, mais j'ai du mal à mettre en évidence les épreuves de Bernoulli associées, surtout dans le cas général.

[guiguiche]

Tu notes $Y_i$ la variable aléatoire qui prend la valeur 1 lorsque l'événement $[X_1+\dots+X_i\equiv0(N)]$ est réalisé et la valeur 0 sinon ($X_i$ étant égale au nombre fourni par le dé lors $i$-ème lancer). Effectivement, la question se pose quant à l'indépendance de la famille de variables aléatoires $(Y_i)_{i\geqslant1}$.

J'ai écrit trop vite hier soir, ce que j'ai dit est fonctionnel (ou pas) lorsque $N\leqslant f$ où $f$ est le nombre de faces du dé. L'événement $[X=1]$ est impossible lorsque $N>f$, donc pas de loi géométrique. Et des variables $Y_i$ pas vraiment indépendantes certainement. Donc une autre approche à considérer.

[MB]

Pour le cas où $N$ est supérieur au nombre de faces, j'envisageais de faire des paquets $k$ de $X_i$ de sorte que $kf \geqslant N$, mais bon je ne suis pas convaincu que ça mène à quelque chose d'intéressant.

[guiguiche]

Je pense qu'il ne faut pas fixer $k$ mais plutôt choisir des variables $Z_k$ de sorte que :
- $Z_1$ est le nombre de lancers pour atteindre ou dépasser $N$,
- $Z_2$ est le nombre de lancers supplémentaires pour atteindre ou dépasser $2N$,
- $Z_3$ est le nombre de lancers supplémentaires pour atteindre ou dépasser $3N$,
- etc.

Autrement dit :
$[Z_1=n_1] = [X_1+\dots+X_{n_1-1}<N] \cap [X_1+\dots+X_{n_1}\geqslant N]$ (avec la convention $X_0=0$ presque sûrement).
$[Z_1=n_1] \cap [Z_2=n_2]= [X_1+\dots+X_{n_1-1}<N] \cap [X_1+\dots+X_{n_1}\geqslant N] \cap [X_1+\dots+X_{n_1+n_2-1}<2N] \cap [X_1+\dots+X_{n_1+n_2}\geqslant 2N]$.
Je suis quasiment certain que les variables $Z_k$ sont indépendantes.
La difficulté est d'exprimer la variable aléatoire $X$ à partir de ces $Z_k$ et de calculer l'espérance des $Z_k$.

[MB]

Alors j'avais également initialement pensé à ce type de regroupement, sans parvenir à le formaliser. Mais en regardant ce que tu proposes, j'ai l'impression que les variables $Z_k$ risquent d'être assez compliquées à manipuler.

En fixant le $k$, je pensais à me ramener au cas où l'expérience consiste à lancer $k$ dés à chaque déplacement, ce qui ne semble d'ailleurs pas modifier l'espérance de $X$ (cf l'exemple avec la somme de deux dés). Mais bon ça ne m'avance à grand chose ...

J'en viens parfois à me demander si la conjecture est bien correcte.

[MB]

Je reviens sur cette question puisqu'on m'a suggéré ici une solution faisant appel à des résultats sur les chaînes de Markov. Après avoir lu quelques documents à ce propos, voici une solution qui me semble correcte dans le cas très général.

On considère une suite $(X_k)_{k \geqslant 1}$ de variables aléatoires indépendantes et identiquement distribuées, à valeurs dans $\{1,\cdots,K\}$ et telles que $\mathbb{P}(X_1 = 1) > 0$ puis on note $Y = (Y_n)_{n \geqslant 1}$ la chaîne de Markov homogène définie par l'égalité suivante.
$$Y_n = X_1+\cdots+X_n\;\mathrm{mod}\;N$$
En considérant $i$ et $j$ dans l'espace des états $E = \{ 0,\cdots,N-1 \}$, le coefficient $P(i,j)$ de la matrice de transition $P$ est donné par l'égalité suivante.
$$P(i,j) = \mathbb{P}(Y_{n+1}=j|Y_n=i)=\mathbb{P}(i+X_{n+1}\equiv j\;\mathrm{mod}\; N)=\mathbb{P}(X_{1}\equiv j-i\;\mathrm{mod}\; N)$$
Par définition de la matrice de transition, on a toujours $\sum_{j \in E} P(i,j) = 1$, mais on peut ici obtenir le même résultat en sommant sur $i$.
$$\sum_{i \in E} P(i,j) = \sum_{i \in E} \mathbb{P}(X_{1}\equiv j-i\;\mathrm{mod}\; N) = 1$$
La mesure de probabilité $\pi$ définie pour tout $i \in E$ par $\pi(i) = \frac{1}{N}$ est donc invariante puisque $\pi = \pi P$.

L'hypothèse $\mathbb{P}(X_1 = 1) > 0$ permet d'affirmer tous les états communiquent entre eux et donc que $Y$ est irréductible.

Une propriété générale affirme alors que toute chaîne de Markov irréductible sur un espace d'états fini admet une unique probabilité invariante $\pi$ telle que pour tout i $\in E$, $\pi_i = \frac{1}{m_i}$ où $m_i$ est l'espérance du premier retour en $i$.

On a alors $\frac{1}{m_0} = \frac{1}{N}$ et donc $m_0 = N$, ce qui prouve que l'espérance du premier retour en 0 est égale à $N$.

Le raisonnement n'est pas tout à fait semblable à celui proposé initialement, puisqu'il ne me semble pas nécessaire de montrer que la chaîne est apériodique. J'espère en tout cas qu'il n'y a pas d'erreur.

[guiguiche]

Je viens de consulter les livres que je possède sur la question (mais pas étudiés, ce n'était pas mon domaine) et cela semble concorder avec ce qui est décrit. La frustration, c'est que je ne peux pas en faire un exo pour mes étudiants.

[MB]

Moi non plus je n'avais jamais étudié les chaînes de Markov, mais ça le semble assez intéressant et il est peut être possible de redémontrer le théorème utilisé dans le cadre spécifique d'un exercice, ce qui ferait intervenir un peu d'algèbre linéaire.

[guiguiche]

J'ai fait en classe cette année (en révisions), l'existence d'un état stable (mais pas que c'est une loi de probabilité ni unicité dans le cas où la matrice de transition n'a pas de 0, difficile), autres vecteurs propres de sommes de composantes nulles, convergence vers un état stable dans un cas particulier diagonalisable. Ça prend déjà du temps. Mais j'y réfléchirais un jour pour le temps du premier retour.

[MB]

La théorie offre en tout cas une solution assez élégante au problème initial, dans un cas encore plus général puisqu'on suppose juste que la probabilité d'obtenir un 1 est non nulle.

Pour prendre en compte le cas où on lance plusieurs dès à chaque étape, on peut vraisemblablement supposer que la probabilité d'obtenir deux sommes premières entre elles. L'objectif étant simplement de garantir l'irréductibilité de la chaîne.

[JCL]

Bonjour,

Je suggère et détaille l'argument suivant, qui permet de se convaincre que l'espérance du temps de retour à la case initiale est bien égale à $N.$
Soit donc un plateau à $N$ cases et un dé à $k$ faces .
On est ainsi en présence d'une chaîne de Markov dont l'ensemble des états (positions du jeton) est $\mathcal E=\Z/N\Z$ et dont la matrice de transition $P$ est définie par:
$$P\in \mathcal M_N(\R), \:\:P =\dfrac 1k\displaystyle\sum _{s=1}^kJ^s \: \text{ où }\:\forall i,j \in[\![1;N]\!], \:J _{ij}=\begin{cases}1&\text{si }j-i\equiv 1 \mod N\\0&\text{sinon}\end{cases}.\:$$
Soit $ \pi =(1,1,\dots 1) \in \R^N.\quad $Alors $\:\:\pi J =\pi\quad \boxed{\pi P =\pi.\quad(\bigstar)}$
Pour $i,j\in \mathcal E,\:$ on note $T_{ij} $ le temps d'atteinte de l'état $j$ à partir de l'état initial $i$, et $M $ la matrice de $\mathcal M_N(\R) $ définie par $M_{ij} = \mathbb E(T_{ij}).$
$\forall i \in \mathcal E, \:\:M_{ii} =\mathbb E(T_{ii}) =\mathbb E (T)$ où $\mathbb E (T)$ est l'espérance cherchée.
$\forall n \in \N, \:\: X_n $ désigne la variable aléatoire indiquant la position du jeton à l'issue du $n$-ième lancer de dé.$\:(X_n\in\mathcal E.)$
En recourant à ce que l'on nomme parfois "l'analyse du premier pas", avec $\mathbb P(X_1=s\mid X_0=i) = P_{is},\:$ on obtient:
$$\forall i,j \in \mathcal E, \:\:\mathbb E(T_{ij})= \displaystyle\sum_{s\in \mathcal E}P_{is}\:\mathbb E(T_{ij}|X_1=s)= P_{ij} +\sum_{s\neq j}P_{is}\:\left(1+\mathbb E(T_{sj})\right), \quad M_{ij} =1+\left(\sum_{s\in \mathcal E} P_{is}M_{sj}\right)-P_{ij}M_{jj}, $$
ce qui, en notant $U$ la matrice de $\mathcal M_N(\R)$ dont tous les coefficients sont égaux à $1$, s'écrit:$\quad\boxed{ M =U +PM- \mathbb E(T)P.}$
et entraîne, en multipliant à gauche par $\pi, \quad\pi M\overset{(\bigstar)}=\pi U+ \pi M- \mathbb E(T)\pi,\quad N\pi =\mathbb E(T) \pi, \quad \boxed{ \mathbb E(T)=N.}$

[MB]

Bonjour et merci pour ce retour, qui donne effectivement le résultat de manière relativement élémentaire, en tout cas sans appel à des résultats concernant les chaînes de Markov.