Immaginez un damier de n cases.
A chaque itération d'un algo, on tire une de ces case au hazard.
Une case peut etre tirée plusieurs fois.
Les tirages sont équiprobable.
Au bout de combien d'itérations je peut etre sûr, avec une marge d'erreur de x% que j'ai touché toutes les cases ???
Je n'ai pas trouvé d'equivalent a ce probleme dans les histoies d'urnes et de boules !
SVP aidez moi
Salut
Je pense que la probabilité de toucher toutes les cases apres m iterations est bien :
p=C(n,m)/n^m avec C la notation du nombre des combinaisons de n entre m.
donc le m cherché est tel que p superieur a 0.96.Selon ton n tu peux calculer m par maple ou matlab.
Salut!
Ca tend vers 1 quand m tend vers l'infini?Envoyé par science_82
A+
Moi je dirais 0, non?
Pour ceux qui voudrait verifier leurs formule, j'ai effectué un grand nombre de test et pour un damier de 25 case, la moyene du nombre de tirage a effectuer pour toucher toutes les cases est 94.
salut!
Bon je confirme la moyenne,en ayant testé sous matlab (après plus d'un an,c'est chaud,excusez l'optimisation pourrie,pas eu le courage de tout mettre sous forme matricielle...)
A copier-coller :
%Damier de 5 sur 5 (25 cases)
a=zeros(1,25); %damier "en ligne"
m=[]; %vecteur dont la coordonnée repr. nb itérations pour finir un damier
for i = 1:10000 % 10 000 damiers
iter=0;
while sum(a==0)>0 %tant que toutes les coordonnées de a sont différentes de 0
aa=zeros(1,25); %ligne pourrie(lol)
aa(ceil(25*rand))=1;
a=a+aa;
iter=iter+1;
end;
a=zeros(1,25);
m(i)=iter;
end;
moy=mean(m)
Par contre pour la proba , a priori je vois pas...
A+
Salut tout le monde
Je suis surpris que le sujet n'ait pas avancé pendant mon absence (hier)
J'y ai réfléchi un peu, et j'ai une solution d'ingénieur à vous proposer (tout du moins, un début de solution).
Supposons qu'au bout d'un certain nombre d'itérations i, on ait "touché" m cases.
La fois suivante, il y a alors m cases touchées, et (n-m) cases non touchées et on a: m/n chances de tomber sur une case déjà touchée, et 1-m/n de toucher une nouvelle case.
En regardant le nombre d'itérations comme une mesure de "temps" (discret), on s'aperçoit que la probabilité de toucher une nouvelle case ne dépend QUE du nombre de cases déjà touchées à l'"instant" précédent (et pas de l'instant lui-même).
Les tirages forment alors un processus stochastique (en gros, c'est une fonction du temps, où chaque "valeur" est la réalisation d'une variable aléatoire) d'un type très particulier, appelé processus de Markov (d'ordre 1).
L'intérêt de ces processus est qu'on peut les représenter facilement par l'intermédiaire d'une matrice, représentant les "transitions" possibles entre les "états" (ici, les états sont le nombre de cases déjà touchées, et les transitions, les probabilités de passer de m à l cases touchées).
Si on note qm l'état m (correspondant à m cases touchées), la transition s'exprime P(ql | qm), et vaut:
P(qm | qm) = m/n
P(qm+1 | qm) = 1-m/n = (n-m)/n
P(ql | qm) = 0 pour l != m et l != m+1
On a alors une matrice carrée (n+1)*(n+1), notée M. Pour des raisons de commodité, je considère les indices commençant à partir de 0.
On a donc: Mi,i = i/n et Mi+1,i = (n-i)/n.
La matrice a une propriété particulière, propre aux matrices représentant des processus de Markov: si V est un vecteur, alors M.V est tel que:
sum((M.V)i, i=0..n) = sum(Vi, i=0..n)
En particulier, si la somme des composantes de V vaut 1 (la composante i représente la probabilité de se trouver dans l'état qi à un instant donné), M.V représente la probabilité à l'instant suivant.
Quelques autres propriétés de la matrice M:
Si on connait le vecteur de probabilités à l'instant t=0, on peut en déduire le vecteur de probabilités à tout instant t:
* Vt = MtV0
* Vt = M.Vinf, c'est-à-dire que la distribution "stable" correspond au vecteur propre associé à la valeur propre 1 de M.
Dans le cas présent, il est évident (parce qu'on finit par toucher toutes les cases) que la distribution stable est le vecteur V=(0,0,...,0, 1), ce qu'on peut aussi voir en observant la dernière colonne de M.
Une autre façon de voir les choses est de dire que l'état qn est "absorbant". Une fois atteint, on n'en sort plus.
On connaît également la distribution à l'instant t=0: on n'a encore touché aucune case, donc on a:
V0 = (1, 0, ... , 0)
On trouve alors facilement que la probabilité d'avoir touché toutes les cases à un instant t est le coefficient An,0 de la matrice A = Mt. La difficulté est maintenant de calculer cette matrice
En regardant de plus près la matrice M, on voit qu'elle est triangulaire inférieure, et qu'en fait, il s'agit de la somme d'une matrice diagonale et d'une matrice "sous-diagonale" (M = D + S).
On peut en déduire son polynome caractéristique, qui est:
P(X) = prod((X-i/n), i=0..n). On en déduit facilement les valeurs propres, qui sont les i/n.
Je me suis arrêté là, n'ayant pas trouvé d'astuce pour calculer facilement la matrice Mt.
La mise sous forme de somme n'aide pas beaucoup, les matrices D et S ne commutant pas, on ne peut donc pas utiliser le formule du binôme de Newton.
Des valeurs propres de M, on peut déduire les vecteurs propres, et écrire une matrice de passage P, pour diagonaliser M.
On a alors M = P-1.D.P, et Mt = P-1.Dt.P
Le vecteur-colonne Pj de la matrice P est la solution du système:
M.Pj = j/n.Pj.
On en déduit que Pi,j = (-1)i-jCn-ji-j.
Je pense, mais je n'ai pas vérifié, que la matrice P-1 s'écrit avec les mêmes coefficients, mais tous positifs.
Reste à voir si on peut tirer quelque chose de là, pour exprimer Mt et répondre à la question, à moins qu'une autre "astuce" permette d'y arriver plus facilement.
Geoffrey
Salut.
Un petit complément d'information (mais pas de "solution complète"):
j'ai vérifié que les matrices P = ((-1)i-jCn-ji-j)i,j et Q = (Cn-ji-j)i,j sont bien inverses l'une de l'autre.
Par ailleurs, on a M = P.D.P-1 (rectification par rapport à mon message précédent), soit:
Mt = P.Dt.P-1.
Le développement, pour Mt(n,0) donne alors:
P(qn, t) = sum((-1)n-k(k/n)tCnk, k=0..n).
On retrouve évidemment que pour t < n, la probabilité est nulle, et pour t = n:
P(qn,n) = n!/nn.
Geoffrey
