Bourrage d'une urne.

[acoustica]

Bonsoir,

J'me posais une question de probabilités, et j'espère que cette question en inspirera certains. :zen:

Le jeu se joue avec ainsi : une urne dans laquelle on a placé N papiers numérotés de 1 à N. Par exemple, disons N=10, ça fait les papiers 1, 2, 3... 10.
On pioche un papier, disons le 3. On le remet dans l'urne et on rajoute un papier numéro 3. On a donc maintenant deux papiers au numéro 3 dans l'urne. Et on recommence une infinité de fois.
A première vue, on pourrait penser qu'en l'infini, on aura toujours une proportion de 1 sur 10 de piocher chaque numéro. Cependant, je me demandais si au contraire, le simple fait de briser la symétrie au début , ou plus tard, oriente le jeu et ferait qu'en l'infini, on se retrouverait avec une probabilité de 1 pour l'un des numéros, c'est-à-dire qu'à partir d'un moment, on aurait un décrochage des probabilités, du fait des fluctuations d'échantillonnage, qui diminuerait de plus en plus les probabilités des numéros qui n'ont pas eu la chance d'être tirés au début. On aurait ainsi un bourrage de l'urne par quatre ou cinq numéros, puis deux, puis finalement, l'un d'entre eux domine les autres. Ou, si on le formule autrement, un équilibre instable des probabilités, qui se retrouvera au bout d'un certain temps brisé par les fluctuations d'échantillonnages, qui feront tendre le jeu en la faveur de l'un des dix numéros.

Les probabilités étant une mine de paradoxes, celui-ci m'a semblé intéressant (je sens qu'il va m'empêcher de dormir celui-là) :zen: . Bonne soirée !

NB : comme le souligne Doraki, il vaut mieux commencer par N=2, c'est l'orientation qu'a prit le fil jusqu'ici.

[antonyme]

Salut!
Je suis d'accord avec toi mais à mon avis la probabilité ce définit en fonction de ce que l'on sait. Ainsi la probabilité de tirer 3 au n-éme tirage quand n tend vers l'infini reste 1/10 tant que l'on ne connais pas les tirages précédant.

Maintenant à mon avis on peut dire que la probabilité de tirer deux fois de suite le même nombre aux n-éme et n+1 -éme tirage tend vers l'infini quand n tend vers l'infini. Mais ça reste à prouver et là, c'est pas du gâteau :look2: (moi non plus je ne vais pas dormir de la nuit à cause de toi :langue: )

[acoustica]

Salut!
Je suis d'accord avec toi mais à mon avis la probabilité ce définit en fonction de ce que l'on sait. Ainsi la probabilité de tirer 3 au n-éme tirage quand n tend vers l'infini reste 1/10 tant que l'on ne connais pas les tirages précédant.

Maintenant à mon avis on peut dire que la probabilité de tirer deux fois de suite le même nombre aux n-éme et n+1 -éme tirage tend vers l'infini quand n tend vers l'infini. Mais ça reste à prouver et là, c'est pas du gâteau :look2: (moi non plus je ne vais pas dormir de la nuit à cause de toi :langue: )

Oui mais justement, on connait tous les étages précédents, c'est bien ça le problème. Tant qu'on n'a pas commencé le jeu, là oui la probabilité pour que ce soit tel ou tel numéro qui domine reste le même. Mais dès le premier tirage, cette probabilité n'est plus la même. Si on commence par tirer le 3, on aura plus de chances de se stabiliser vers le trois. Au deuxième coup si on tire le 7, ça change encore.... :we: La question est donc : est-ce qu'au bout d'un moment l'équilibre est fatalement brisé ?

[Doraki]

On peut simplifier le problème en considérant que 2 papiers au début.

Mon intuition dit que la proportion du nombre de papiers de chaque numéro converge presque sûrement.
Je suis curieux de connaitre la loi de cette limite.

Si on prend 2 papiers et qu'on regarde la variable Xn = log (nombre de 1 / nombre de 2), la suite Xn ressemble à une marche aléatoire équilibrée où les pas sont de plus en plus petits.
Avec de la chance la loi de Xn tend vers une gaussienne centrée en 0, et donc la loi de la limite devrait probablement faire pareil.

[acoustica]

On peut simplifier le problème en considérant que 2 papiers au début.

Mon intuition dit que la proportion du nombre de papiers de chaque numéro converge presque sûrement.
Je suis curieux de connaitre la loi de cette limite.

Si on prend 2 papiers et qu'on regarde la variable Xn = log (nombre de 1 / nombre de 2), la suite Xn ressemble à une marche aléatoire équilibrée où les pas sont de plus en plus petits.
Avec de la chance la loi de Xn tend vers une gaussienne centrée en 0, et donc la loi de la limite devrait probablement faire pareil.

Je ne connais pas cette loi en log, mais mon vieil ami le gros livre de statistiques est justement à porté de main. :we: De quelle loi parles-tu ? Je vais me plonger là-dedans, il faudrait potasser quels chapitres ? En fait je ne vois pas d'où vient le log... et je ne vois pas où je pourrais avoir des informations. Les lois usuelles ne conviennent pas, puisqu'on a toujours plus de papiers.

Moi aussi je suis super curieux^^

[Doraki]

Je ne connais pas cette loi en log, mais mon vieil ami le gros livre de statistiques est justement à porté de main. :we: De quelle loi parles-tu ? Je vais me plonger là-dedans, il faudrait potasser quels chapitres ? En fait je ne vois pas d'où vient le log...

Moi aussi je suis super curieux^^

ben j'ai un peu dit tout ça au hasard.
Là après une petite simulation, il semblerait que la loi de (nombre de 1 après N coups) est uniforme dans {1...N+1} (et donc si on admet que la proportion converge presque surement, alors la loi de la limite est uniforme dans [0;1]).

Pour le log, ça vient du fait que si tu as n=p+q et que tu as p numéros 1 et q numéros 2 dans ta boite,
tu vas passer de Xn = log(p/q) à X(n+1) = log((p+1)/q) = Xn + log (1+1/p) ~= Xn + 1/p avec probabilité p/(p+q) ;
et à X(n+1) = log(p/(q+1)) ~= Xn - 1/q avec probabilité q/(p+q).
Donc l'espérance de X(n+1) sachant Xn vaut environ Xn + p/p(p+q) - q/q(p+q) = Xn.
J'ai pris ma fonction de sorte que ça ressemble le plus possible à une martingale.

J'ai déjà vu des gens parler de ce genre de "presque-martingales", il y a sûrement des trucs dessus.

[acoustica]

ben j'ai un peu dit tout ça au hasard.
Là après une petite simulation, il semblerait que la loi de (nombre de 1 après N coups) est uniforme dans {1...N+1} (et donc si on admet que la proportion converge presque surement, alors la loi de la limite est uniforme dans [0;1]).

D'acc. Ca voudrait donc dire qu'on retrouve bien la proportion de 1/N alors ?
Je vais faire un programme moi aussi pour voir.

[acoustica]

Difficile de trancher entre une loi uniforme et une convergence 1-0...


import random
L=[0,1]
for k in range(10000000):
L.append(L[random.randrange(0,len(L))])

i=0
j=0
for k in L:
if k==0:
i+=1
else:
j+=1
print(i,j)




donne :

8 864 445-1 135 557

Mais alors, à convergence très lente. J'ose pas aller au delà de dix millions, j'ai pitié pour mon ordi... Mais ce qui est drôle, c'est que la majorité des autres tests que j'ai fais avant avec des échantillons plus petits donnaient une répartition de type 7/8 - 1/8. A mon avis, au bout d'un moment, l'un des deux prend le dessus et on tend vers une proportion bien particulière entre les deux, qui n'est ni 1/2 - 1/2, ni 1-0.

On peut aussi stocker les proportions dans des listes. L'idéal serait de tracer sur Maple la suite des proportions ainsi obtenues, mais perso je ne sais pas comment faire.

[fatal_error]

salut,

si jme trompe po...
pour lurne biboule:

On peut representer un espece quadrillage. Lorigine contient (1,1), et un point destination (a,b) ou a est le nombre de boules de type A et B de type b.
Le but cest de trouver tous les chemins de (1,1) a (a,b)

pour ca on remarque qu'on a un nombre de deplacement n=(a-1)+(b-1)
p(a,b) represente la proba de se retrouver en avec a boules et b boules
on remarque que le denominateur augmente dune boule a chaque fois, on a un truc style
p(a,b)=(a+b-1)!*[numerateur]

le numerateur est une somme de chemins probabilises
on se deplace de (a-1) unites et (b-1) unites cad
p(a,b)=C(n,a-1)(a-1)!(n-(a-1))!/(n+1)!=1/(n+1)=1/(a+b-1)

[beagle]

Quand on le fait avec deux nombres-objets,
on trouve distribution uniforme après n tirages
toutes les combis sont à égalité à 1/(n+1).

Si à 2 pas de gagnants, je dirais pas de gagnants non plus si k nombres.

[acoustica]

salut,

si jme trompe po...
pour lurne biboule:

On peut representer un espece quadrillage. Lorigine contient (1,1), et un point destination (a,b) ou a est le nombre de boules de type A et B de type b.
Le but cest de trouver tous les chemins de (1,1) a (a,b)

pour ca on remarque qu'on a un nombre de deplacement n=(a-1)+(b-1)
p(a,b) represente la proba de se retrouver en avec a boules et b boules
on remarque que le denominateur augmente dune boule a chaque fois, on a un truc style
p(a,b)=(a+b-1)!*[numerateur]

le numerateur est une somme de chemins probabilises
on se deplace de (a-1) unites et (b-1) unites cad
p(a,b)=C(n,a-1)(a-1)!(n-(a-1))!/(n+1)!=1/(n+1)=1/(a+b-1)

Je ne comprends pas où tu veux en venir, dans la démarche. Je comprends cette méthode des quadrillages, je comprends ton calcul, mais j'aurais fais autrement. Pour avoir les chemins de (1,1) à (a,b), j'aurais dis "il y a a+b-2" boules en tout, a-1 boules A, b-1 boules B. Ca fait a-1 boules A parmi n, CAD C(n,a-1)". Mais toi tu itères, et c'est là que je ne te suis plus. Pourquoi fixes-tu un but à atteindre, pour ensuite étudier tous les chemins possibles ? Comment ensuite agglomérer tous les buts possibles (parce que c'est ça qu'on cherche si je ne dis pas de bêtises) ?


Pour visualiser le problème, je me suis dis qu'on pouvait l'imaginer comme ça : deux cuves (de capacité infinie héhé) remplies par deux robinets. Au début, les cuves sont remplies du même volume par deux robinets de même débit, mais soumis à des fluctuations autour de leur "espérance de débit". Quand une cuve prend l'avantage sur l'autre, le débit grossit pour la grosse cuve, et diminue pour la petite cuve, comme si la grosse cuve piquait du débit à la petite. Ainsi, on remplit toujours plus vite la plus grosse cuve au détriment de la petite.
Tout le problème vient des fluctuations autour de l'espérance. La question est de savoir si la vitesse de croissance de la grosse cuve est suffisamment faible devant l'espérance, au bout d'un grand nombre de fois", d'avoir un remplissage de la petite cuve qui rattrape celle de la grosse. Ou si on revient aux boules : l'urne se remplit toujours plus de boules noires, mais la question est de savoir si cette croissance est suffisamment faible pour qu'on puisse espérer à coup sûr, et ce au bout d'un nombre de fois éventuellement très grand, un tirage miraculeux qui permette de rééquilibrer les jeux.
Je pense que le problème est incomplet : on pourrait imaginer que si on pioche une boule noire, on doit la remettre, avec en plus une demi-boule noire. Ou un tiers, ou deux, ou quinze, ou un dixième, suivant le choix qu'on fait. Il doit y avoir une fraction limite en dessous de laquelle le jeu diverge, oscille sans cesse, avec toujours rattrapage des boules en faible nombre sur les autres, si bien que le jeu ne se stabilise jamais ; et au dessus de cette fraction limite, convergence en faveur d'une des deux boules.

[beagle]

pour deux objets, si on monte dans l'arbre des probas,
on voit que distribution uniforme non?

enfin après 4 tirages, il y autant de chances pour:
aaaaab
bbbbba
que
aaabbb

pas regardé les autres ...

[acoustica]

pour deux objets, si on monte dans l'arbre des probas,
on voit que distribution uniforme non?

Justement je ne crois pas : plus on a d'un certain type de boule, plus on bourre l'urne, et moins on a de chance de tirer l'autre. C'est un jeu qui donne toujours plus de chances au vainqueur d'écraser le perdant. :bad:

[beagle]

scusez dérangement

[Doraki]

C'est facile de montrer par récurrence que P(avoir la composition (a,b) après a+b-2 coups) = 1/(a+b-1) :
P(a,b) = P(a-1,b) * (a-1)/(a+b-1) + P(a,b-1) * (b-1)/(a+b-1) = (1/(a+b-2))*((a+b-2)/(a+b-1)) = 1/(a+b-1)

[acoustica]

pour deux objets, si on monte dans l'arbre des probas,
on voit que distribution uniforme non?

enfin après 4 tirages, il y autant de chances pour:
aaaaab
bbbbba
que
aaabbb

pas regardé les autres ...

Non, il n'y a pas autant de chances justement. Dès que a prend l'avantage sur b, il a plus de chances d'être tiré au tour suivant. Les jeux ne sont pas équitables, mais ils peuvent être rééquilibrés si les fluctuations le veulent bien. La question est de savoir s'il y a une proportion limite en dessous de laquelle on peut dire que les jeux sont faits. Bien sûr, on peut dire "oui, mais on peut toujours se rattraper avec beaucoup de chances". C'est une question de vitesse : quel phénomène est le plus rapide : la croissance du vainqueur, ou les fluctuations en faveur du perdant ?

[acoustica]

C'est facile de montrer par récurrence que P(avoir la composition (a,b) après a+b-2 coups) = 1/(a+b-1) :
P(a,b) = P(a-1,b) * (a-1)/(a+b-1) + P(a,b-1) * (b-1)/(a+b-1) = (1/(a+b-2))*((a+b-2)/(a+b-1)) = 1/(a+b-1)

OK, je comprends mieux ce qu'a fait fatal error. En même temps, ça ne nous avance à rien. Ca veut juste dire que pour des nombres très grands, on a très peu de chances d'avoir une combinaison désignée à l'avance. On s'en doutait un peu...

[beagle]

scusez du dérangement, je vais me réveiller!

[acoustica]

scusez du dérangement, je vais me réveiller!

Mais euh, t'as effacé ton message^^.

[acoustica]

ben j'ai un peu dit tout ça au hasard.
Là après une petite simulation, il semblerait que la loi de (nombre de 1 après N coups) est uniforme dans {1...N+1} (et donc si on admet que la proportion converge presque surement, alors la loi de la limite est uniforme dans [0;1]).

Pour le log, ça vient du fait que si tu as n=p+q et que tu as p numéros 1 et q numéros 2 dans ta boite,
tu vas passer de Xn = log(p/q) à X(n+1) = log((p+1)/q) = Xn + log (1+1/p) ~= Xn + 1/p avec probabilité p/(p+q) ;
et à X(n+1) = log(p/(q+1)) ~= Xn - 1/q avec probabilité q/(p+q).
Donc l'espérance de X(n+1) sachant Xn vaut environ Xn + p/p(p+q) - q/q(p+q) = Xn.
J'ai pris ma fonction de sorte que ça ressemble le plus possible à une martingale.

J'ai déjà vu des gens parler de ce genre de "presque-martingales", il y a sûrement des trucs dessus.

J'avais pas vu que tu avais complété ton message, merci pour les infos ! Je ne comprends pas pour l'instant, mais je vais chercher. =)