Nombre moyen de records dans une permutation aléatoire

 Niveau exercicesPartager :
			        
Nombre moyen de records dans une permutation aléatoire
Posté par 
flight  08-02-26 à 20:22
Bonsoir , je vous propose l'exercice suivant ;

On considère les entiers 1, 2, …, n.

On mélange ces nombres au hasard pour obtenir une permutation aléatoire.

On appelle record une position k telle que la valeur à cette position soit plus grande que toutes celles qui la précèdent.

On note R le nombre total de records dans la permutation.

Question

Calculer l'espérance du nombre de records R.

Exemple

Pour la permutation

2, 4, 6, 1, 5, 7, 3

on lit de gauche à droite :

2 est un record (premier terme)

4 est un record (plus grand que 2)

6 est un record (plus grand que 4)

1 n'est pas un record

5 n'est pas un record

7 est un record (plus grand que 6)

3 n'est pas un record

Les positions records sont donc 1, 2, 3 et 6, et le nombre de records vaut R = 4.

Déterminez la valeur l'espérance  du nombre de records R lorsque la permutation est choisie uniformément au hasard parmi toutes les permutations possibles de {1, …, n}.
 Posté par 
dpire : Nombre moyen de records dans une permutation aléatoire  09-02-26 à 08:37
Bonjour,

 Cliquez pour afficher
Sans démonstration R=n/2
 Posté par 
candide2re : Nombre moyen de records dans une permutation aléatoire  09-02-26 à 09:54
Bonjour,

 Cliquez pour afficher
Soit Xp le variable aléatoire liée à la position p (avec 1 <= p <= n)

Xp = 1 si la position p est un record, sinon Xp = 0

Le nombre de records est 

P(Xp = 1) = 1/p

Exemple n = 3 --> E(R) = 1 + 1/2 + 1/3 = 11/6

et on vérifie avec tous les cas équiprobables possibles :

123... R = 3

132... R = 2

213... R = 2

231... R = 2

312... R = 1

321... R = 1

E(R) = 3 * 1/6 + 2 * 3/6 + 1 * 2/6 = 11/6
 Posté par 
verdurinre : Nombre moyen de records dans une permutation aléatoire  09-02-26 à 14:56
Bonjour,

 Cliquez pour afficher
en notant  le nombre moyen de records pour une permutation de longueur n et en posant  on a :

On doit pouvoir arranger cette expression.
 Posté par 
verdurinre : Nombre moyen de records dans une permutation aléatoire  09-02-26 à 15:04
Il y avait plus simple.

Bravo candide2.
 Posté par 
flightre : Nombre moyen de records dans une permutation aléatoire  09-02-26 à 20:36
Bonsoir bonne réponse de candide2 qui a utilisé une variable indicatrice Xp
 Posté par 
dpire : Nombre moyen de records dans une permutation aléatoire  10-02-26 à 09:25
Bonjour,

Comme dab ,j'étais hors sujet 

J'ai voulu voir ce que donnait  1,2,3,4,5,6,7,8

Il y a  40320 arrangements  soit 322560 chiffres dont 109593

sont des records  exemple :

36548712

en rouge les records successifs

3 6 5 4 8 7 1 2

en moyenne ,cela donne  2.717 .

A vérifier si la formule de candide2 vérifie ce résultat.
 Posté par 
jandri re : Nombre moyen de records dans une permutation aléatoire  10-02-26 à 11:08
Bonjour,

le résultat donné par candide2 pour l'espérance est juste mais sa démonstration est fausse.

En effet si  est définie par  quand  est un record et  sinon on a :

 et pas  (c'est évident pour  et ).

Une démonstration très courte :
 Cliquez pour afficher
L'ordre des entiers  étant choisi au hasard,  la probabilité que  soit le premier est égale à 
 Posté par 
dpire : Nombre moyen de records dans une permutation aléatoire  10-02-26 à 15:21
Pour mémoire,j'ai fait le tableau des r  de n=3 à n=8

    n                r

  2                  1.5

  3                  1.83

  4                   2.08

  5                   2.28

  6                   2.45

  7                   2.59

  8                   2.72

la formule est-elle vérifiée ?
 Posté par 
dpire : Nombre moyen de records dans une permutation aléatoire  10-02-26 à 16:07
Bien sûr,

pour n=8   -->1+1/2+1/3+1/4+1/5+1/6+1/7+1/8=2.71785714...

8 ! =5040 -->40320  arrangements s donc  322560 chiffres

dont  109584 seront records.
  Posté par 
jandri re : Nombre moyen de records dans une permutation aléatoire  10-02-26 à 21:38
Je m'aperçois (mieux vaut tard que jamais) que la démonstration de candide2 est exacte. J'ai lu un peu vite sa solution et j'ai cru que j'avais utilisé les mêmes variables  que lui.

En fait, comme il l'a écrit, candide2 a posé  si la position p est un record alors que pour moi  si la valeur p est un record. Par exemple pour la permutation (2,1,4,3) les positions records pour candide2 sont 1 et 3 alors que les valeurs records pour moi sont  2 et 4.

Nous n'avons pas les mêmes  donc pas les mêmes espérances pour ces , mais finalement nous trouvons bien la même espérance pour .