Soient N le nombre de boules dans le sac, K le nombre de tirages successifs à réaliser et M le nombre moyen de tirages.

En raisonnant pour K=2, 3 ou 4, je me suis rendu compte que M ne dépend pas de N mais seulement de K. Seule condition évidente: N>=K.

On se place dans le cas N=K; chercher M revient à trouver le nombre moyen de fois pour tirer dans l'ordre de 1 à N les N jetons du sac.

* Tirage de 1: on y arrive en moyenne après K fois,
* Tirage de 1 puis 2: on y arrive en moyenne après K*(K-1) fois,
* ...
* Tirage de 1 à x dans l'ordre: on y arrive en moyenne après K!/(K-x)! fois,
* ...
* Tirage de 1 à K dans l'ordre: on y arrive en moyenne après K!/(K-K)!=K! fois.

M est la somme de toutes les tentatives soit:

M=Somme(x=1 à x=K)de(K!/(K-x)!)

Pour K=10, on a: M=Somme(x=1 à x=10)de(10!/(10-x)!) soit

M = 9 864 100.

Quelques M pour les 6 premières valeurs de K:
M=1 pour K=1
M=4 pour K=2
M=15 pour K=3
M=64 pour K=4
M=325 pour K=5
M=1 956 pour K=6.

Sans en être vraiment certain, j'aurais dit:
1+1)2+1)3+1)4+1)5+1)6+1)7+1)8+1)9+1)10 soit près de 10 millions.

En fait c'est facile à comprendre: Pour une combinaison de 10 nombres, il y a une chance sur 10! pour qu'elle soit dans le bon ordre. Cependant, il ne faut pas oublier qu'on remise tout à chaque fois, alors il faut corriger cette expression.
Quand on a réussi à obtenir k nombres dans l'ordre, il existe k+1 combis de k+1 nombres dont les k nombres sont dans l'ordre: le nombre supplémentaire a k+1 positions dans la combi de k nombres. C'est pourquoi quand on ajoute 1 nombre à une combi réussie de k nombres, on devra le faire k+1 fois.

Cependant, en passant par les intégrales, je ne retrouve pas ce résultat, je ne sais pas pourquoi. D'où mon scepticisme.

Mon raisonnement s'est basé sur 2 concepts:
1-) le nombre moyen pour réussir un événement de probabilité p est 1/p
2-) pour tirer par ordre de 1 à K dans l'ordre croisant, il faut avoir tiré :
* 1 (p=1/K donc K tentatives en moyenne),
* 1 puis 2 (K jeton, pour tirer 1, p_1=1/K. Il reste K-1 jetons, pour tirer 2, p_2=1/(K-1) ==> p=p_1*p_2==1/(K*(K-1)) donc K*(K-1) tentatives en moyenne),
...
ainsi de suite jusqu'à avoir le tirage complet.

La somme se justifie par le fait qu'on ne peut pas atteindre une étape supérieure sans avoir réussi les étapes antérieures. Le nombre moyen de tirage pour atteindre la dernière étape (1 à K) est la somme de toutes les tentatives y compris celles pour la réussite des étapes antérieures.

Justification du fait que M est indépendant de N (nombre de jetons dans le sac.

Pour tirer 2 nombre x et y tels que y>x dans un sac à N jetons, on a N-1 possibilités. La probabilité p de ce tirage est la somme des probabilités de toutes possibilités:
* possibilité 1: x=1. p_x=1/N et p_y=(N-1)/(N-1) car y peut prendre toutes les valeurs sauf 1.
p_1=p_x*p_y=(1/N)*((N-1)/(N-1))

* possibilité 2: x=2. p_x=1/N et p_y=(N-2)/(N-1); y prend toutes les valeurs sauf 1 et 2.
p_2=p_x*p_y=(1/N)*((N-2)/(N-1))

* ...

* possibilité m: x=m. p_x=1/N et p_y=(N-m)/(N-1); y prend toutes les valeurs > à m or il reste N-1 jetons dans le sac.
p_2=p_x*p_y=(1/N)*((N-m)/(N-1))=(1/(N*(N-1))*(N-m)

* ...

* possibilité N-1: n=N-1. p_x=1/N et p_y=1/(N-1); y peut prendre seulement la valeur N.
p_N-1=p_x*p_y=(1/N)*(1/(N-1))

p=somme des p_m; m allant de 1 à N-1=(1/(N*(N-1))*[somme des N - somme des m] (il y a N sommé N-1 fois et somme de 1 à N-1)

p=(1/(N*(N-1))*[N*(N-1)-N*(N-1)/2] =(1/(N*(N-1))*N*(N-1)*[1-1/2]=1/2 d'où l'indépendance de p. CQFD

Il y a sûrement un moyen plus rapidement

Bonsoir,
Le résultat ne dépend pas du nombre N de jetons dans le sac (≥10).
Si on appelle m le nombre moyens de jetons tirés dans les séries de 10 qui échouent, le nombre moyen de jetons tirés sera :

N + m * (N! - 1)

m calculé par ordinateur, en passant en revue les permutations de N éléments

m = 9864090/3628799

On obtient le nombre moyen de jetons tirés : 9864100

titoufred #11 a écrit:

Saurais-tu justifier ta première phrase sur l'indépendance.

Quand on compare les jetons tirés, seul compte l'ordre de leurs numéros. Qu'ils soient numérotés de 1 à 10, ou de 10 nombres différents choisis parmi 1000 ou 1000000, cela ne change rien.

Saurais-tu calculer simplement la réponse sans avoir à faire un programme qui passe en revue toutes les possibilités ?

Non, je n'ai pas trouvé…

Voici un programme en python qui fait le calcul :

#!/usr/bin/env python

import sys
from itertools import permutations

N=int(sys.argv[1])
n=0
for jetons in permutations(range(N)) :
   j0=-1
   for j in jetons :
      n+=1
      if j<j0 : break
      j0=j

print("N=%d Resul=%d"%(N,n))

à lancer ainsi (du moins sous Linux)

./le_script.py 10

Correction : Orthographe

Ah ! au fait j'allais oublier: et pour optimiser tout ça ? J'ai déja une solution avec moins de 9000 jetons: on prend les n°1 à 9 + 1 jeton. On peut sans doute faire beaucoup mieux, mais pour l'instant je n'ai pas la solution....

J'ai laissé entendre qu'avec une stratégie simple, il était possible d'obtenir la suite ordonnée avec 4500 tirages environ en moyenne. Pouvez vous dire mieux ?