Bourrage d'une urne.

[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 (je ne sais pas ce qu'est une martingale), mais je vais chercher.

[beagle]

bof, je suis émotif, pas sur de moi, alors je vois des fantomes, et j'efface mes messages.
Et puis après je pleure, je regrette, mais pourquoi j'ai effacé etc ...
Dure vie!
Bon, je fais un grand nombre de n tirages à deux objets a et b au départ,
j'aurai proba de
aaaaaaaaaaaaaahque des a+ 1 b
égale proba de
autant a que b
donc j'aurai autant de tirages qui auront complètement divergé vers a (mais le b de départ restera, non?)
que de tirages où je retrouverai autant de a que de b
et c'est du 1/(n+1)

bon je réefface cela dans 10 mn.

[acoustica]

bof, je suis émotif, pas sur de moi, alors je vois des fantomes, et j'efface mes messages.
Et puis après je pleure, je regrette, mais pourquoi j'ai effacé etc ...
Dure vie!
Bon, je fais un grand nombre de n tirages à deux objets a et b au départ,
j'aurai proba de
aaaaaaaaaaaaaahque des a+ 1 b
égale proba de
autant a que b
donc j'aurai autant de tirages qui auront complètement divergé vers a (mais le b de départ restera, non?)
que de tirages où je retrouverai autant de a que de b
et c'est du 1/(n+1)

bon je réefface cela dans 10 mn.

Snif, la vie est dure. =)
Justement, même si, en faisant un arbre à probabilités, on a ce que tu dis, on ne va pas naviguer aléatoirement dans cet arbre. On n'aura pas équiprobabilité de prendre telle ou telle orientation dans l'arbre à chaque tirage. C'est de là que vient le problème. :marteau:
Les probabilités changent à chaque étape. Avoir du 50-50 est assez improbable. D'après ce que j'ai compris, tu fais comme si on rajoutait une boule au hasard à chaque étape. Or, avoir équirépartition est très improbable, puisque dès qu'on a un décrochage, on s'enfonce dans l'inégalité. Le truc vraiment top, ce serait de faire un tracé des probabilités sur un logiciel, pour voir un peu comment ça oscille.

[Black Jack]

En partant d'un cas simple, déséquilibré volontairement au départ. (avec des boules de couleurs, mais c'est équivalent à des cartons numérotés).

Au départ : 2 boules rouges et 1 boule noire dans un sac.
A chaque tirage, on remet la boule tirée dans le sac avec en plus une boule de la même couleur que celle qui a été tirée ...

Au départ : le ratio Noires/rouges = 1/2

Après 1 tirage :
On a proba (2N,2R) = 1/3
et proba(1N,3R) = 2/3
Soit un ratio de Noires/rouges (compte tenu des proba) : N/R = (2*1/3 + 1*2/3)/(2*1/3 + 3*2/3) = 1/2

Après 2 tirages :
On a proba (3N,2R) = 1/6
proba(2N,3R) = 1/3
proba(1N,4R) = 1/2
Soit un ratio de Noires/rouges (compte tenu des proba) : N/R = (3*1/6 + 2*1/3 + 1*1/2)/(2*1/6 + 3*1/3 + 4*1/2) = 1/2

Après 3 tirages :
On a proba (4N,2R) = 1/10
proba(3N,3R) = 1/5
proba(2N,4R) = 3/10
proba(1N,5R) = 2/5
Soit un ratio de Noires/rouges (compte tenu des proba) : N/R = (4*1/10 + 3*1/5 + 2*3/10 + 1*2/5)/(2*1/10 + 3*1/5 + 4*3/10 + 5*2/5) = 1/2

Le ratio N/R (compte tenu des proba) reste le même (que celui du départ) quel que soit le nombre de tirages.

Evidemment, quelques "épreuves" individuelles peuvent donner des résultats très différents les unes des autres et très loin d'un ratio final de 1/2 (celui imposé au départ).
Cependant sur un "très grand nombre" d'épreuves, on devrait trouver que la moyenne du ratio entre les boules des 2 couleurs reste celui du départ.

Aux bêtises près.

:zen:

[beagle]

Snif, la vie est dure. =)
Justement, même si, en faisant un arbre à probabilités, on a ce que tu dis, on ne va pas naviguer aléatoirement dans cet arbre. On n'aura pas équiprobabilité de prendre telle ou telle orientation dans l'arbre à chaque tirage. C'est de là que vient le problème. :marteau:
Les probabilités changent à chaque étape. Avoir du 50-50 est assez improbable. D'après ce que j'ai compris, tu fais comme si on rajoutait une boule au hasard à chaque étape. Or, avoir équirépartition est très improbable, puisque dès qu'on a un décrochage, on s'enfonce dans l'inégalité. Le truc vraiment top, ce serait de faire un tracé des probabilités sur un logiciel, pour voir un peu comment ça oscille.

Bon, je ne dois pas comprendre l'exo,
il faut partir d'un déséquilibre initial?
Donc pourquoi ne pas démarrer de la situation aab alors?,
Parce que si on part de ab et qu'on va voir au bout de n tirages, je ne comprends pas où j'ai faux.
Tu pars d'un déséquilibre?
Bon, je fais ce truc en passant en bossant autre chose donc cela n'aide pas ma ptite tète!

[beagle]

tiens Black Jack m'a répondu:
"En partant d'un cas simple, déséquilibré volontairement au départ. (avec des boules de couleurs, mais c'est équivalent à des cartons numérotés).

Au départ : 2 boules rouges et 1 boule noire dans un sac."

[beagle]

"D'après ce que j'ai compris, tu fais comme si on rajoutait une boule au hasard à chaque étape. "

euh, non je rajoute une boule en proba,
si je suis à aaaab,
je rajoute a en 4/5 et b en 1/5

[Dlzlogic]

Bonjour,
J'ai fait une simulation, et la répartition des résultats est celle de la loi normale.
312;211
189;88
83;-18
12;-89
129;28
78;-23
63;-38
20;-81
15;-86
109;8
Etude de tirage aléatoire de boules
Nombre = 10 Moyenne = 101.000000 emq=92.67 ep=61.78
Classe 1 nb= 0 0.00% théorique 0.35%
Classe 2 nb= 1 10.00% théorique 2%
Classe 3 nb= 0 0.00% théorique 7%
Classe 4 nb= 1 10.00% théorique 16%
Classe 5 nb= 2 20.00% théorique 25%
Classe 6 nb= 3 30.00% théorique 25%
Classe 7 nb= 3 30.00% théorique 16%
Classe 8 nb= 0 0.00% théorique 7%
Classe 9 nb= 0 0.00% théorique 2%
Classe 10 nb= 0 0.00% théorique 0.35%

Il s'agit de 1000 tirages avec 10 cartes numérotées au départ.
Ceci rejoint et confirme l'explication de Black-Jack.

[acoustica]

En partant d'un cas simple, déséquilibré volontairement au départ. (avec des boules de couleurs, mais c'est équivalent à des cartons numérotés).

Au départ : 2 boules rouges et 1 boule noire dans un sac.
A chaque tirage, on remet la boule tirée dans le sac avec en plus une boule de la même couleur que celle qui a été tirée ...

Au départ : le ratio Noires/rouges = 1/2

Après 1 tirage :
On a proba (2N,2R) = 1/3
et proba(1N,3R) = 2/3
Soit un ratio de Noires/rouges (compte tenu des proba) : N/R = (2*1/3 + 1*2/3)/(2*1/3 + 3*2/3) = 1/2

Après 2 tirages :
On a proba (3N,2R) = 1/6
proba(2N,3R) = 1/3
proba(1N,4R) = 1/2
Soit un ratio de Noires/rouges (compte tenu des proba) : N/R = (3*1/6 + 2*1/3 + 1*1/2)/(2*1/6 + 3*1/3 + 4*1/2) = 1/2

Après 3 tirages :
On a proba (4N,2R) = 1/10
proba(3N,3R) = 1/5
proba(2N,4R) = 3/10
proba(1N,5R) = 2/5
Soit un ratio de Noires/rouges (compte tenu des proba) : N/R = (4*1/10 + 3*1/5 + 2*3/10 + 1*2/5)/(2*1/10 + 3*1/5 + 4*3/10 + 5*2/5) = 1/2

Le ratio N/R (compte tenu des proba) reste le même (que celui du départ) quel que soit le nombre de tirages.

Evidemment, quelques "épreuves" individuelles peuvent donner des résultats très différents les unes des autres et très loin d'un ratio final de 1/2 (celui imposé au départ).
Cependant sur un "très grand nombre" d'épreuves, on devrait trouver que la moyenne du ratio entre les boules des 2 couleurs reste celui du départ.

Aux bêtises près.

:zen:

Oui, mais au fond, là on fait un arbre à probabilité d'après ce que j'ai compris. Et on regarde, toujours avant de commencer l'épreuve, quelle est la probabilité d'avoir telle proportion de rouge et telle proportion de noires. Quand bien même à chaque noeud les probabilités sont différentes, il y a forcément un équilibrage puisque le jeu est symétrique en rouge et noir. Ici tu ne te focalises pas sur une trajectoire, mais sur l'ensemble des trajectoires. Il aurait été bizarre de trouver autre chose que 50-50. C'est comme si on déformait l'arbre à probas en pondérant par les probabilités, c'est-à-dire qu'au lieu de faire deux bifurcations à chaque noeud, on fait des doublons pour se retrouver avec des bifurcations équiprobables. Alors bien sûr, vu d'en haut, en appréhendant toutes les combinaisons possibles, on retrouve l'équiprobabilité. Mais ça ne nous renseigne pas sur les chemins séparément.

PS : je viens de réaliser que ce problème revient à réfléchir sur l'influence des sondages sur les votes. Ce serait un peu ça non ? =)

[Doraki]

En fait mon histoire avec log elle sert à rien. la suite (an/bn) est presque une martingale donc sa composée avec n'importe quelle fonction dérivable aussi.
En revanche, on devrait pouvoir choisir une fonction f (dérivable) telle que si Xn = f(an/bn), l'écart-type de X(n+1) - Xn soit équivalent à 1/n quand n tend vers l'infini, indépendemment de Xn.

Avec une variante du TCL on peut ptetre montrer que (an/bn) (et donc aussi (an/n)) converge presque sûrement, et que la variable aléatoire L = limite de la suite (an/n) est répartie uniformément dans [0;1] (lorsqu'on part de (1,1). si on part d'ailleurs, ce n'est plus une répartition uniforme)

Par exemple, si on regarde (X(n+sqrt(n)) - X(n)) * n^(3/4), c'est une variable aléatoire qui devrait converger en loi vers une gaussienne, donc que en sqrt(n) coups à partir de Xn, on peut espérer bouger de O(n^ -3/4) seulement. Et en sommant tout ça, on peut espérer bouger de seulement O(n^-1/4) à partir de Xn (donc plus on avance, plus il est probable qu'on soit coincé dans un petit intervalle)
et donc Xn devrait converger presque sûrement.

[Dlzlogic]

Les essais montrent que souvent le premier vers le 50è tirage, reste premier.
Il y a eu des cas où le premier a changé vers le 400è tirage. Mes essais se limitent à 1000 tirages.

PS un cas intéressant
Le 1 passe premier au rang 1
Le 8 passe premier au rang 6
Le 9 passe premier au rang 9
Le 1 passe premier au rang 23
liste au rang 100 : 31 1 8 6 6 22 1 12 19 4 prem=1
liste au rang 200 : 50 4 15 17 15 46 1 17 36 9 prem=1
liste au rang 300 : 74 8 22 24 18 70 1 30 51 12 prem=1
Le 6 passe premier au rang 356
liste au rang 400 : 93 13 31 27 25 96 1 38 70 16 prem=6
Le 1 passe premier au rang 417
liste au rang 500 : 125 17 35 37 28 119 1 43 86 19 prem=1
liste au rang 600 : 148 19 42 46 34 143 1 50 105 22 prem=1
liste au rang 700 : 173 21 50 55 38 173 1 57 118 24 prem=1
Le 6 passe premier au rang 701
Le 1 passe premier au rang 727
Le 6 passe premier au rang 741
Le 1 passe premier au rang 753
Le 6 passe premier au rang 765
liste au rang 800 : 198 23 59 61 39 202 1 63 135 29 prem=6
Le 1 passe premier au rang 857
Le 6 passe premier au rang 860
liste au rang 900 : 217 30 64 69 42 222 1 74 160 31 prem=6
liste au rang 1000 : 242 33 70 79 48 245 1 79 181 32 prem=6

[beagle]

C'est pas la question?
Ben c'est ma réponse!

Si on part de deux éléments, a et b,
au bout de n tirages,
toutes les combinaisons (il y en a n+1 en tout) de k fois le a et (n+2-k) fois le b sont en équiproba de 1/(n+1)
donc au bout d'une multitude de 998 tirages,
les séries avec 396 a et 604 b
seront aussi nombreuses que celles avec 999 a et 1 b
(à la réserve près de Dlzlogic qui retrouvera fort justement du gaussien dans l'uniforme de n tirages)

Si on part avec un déséquilibre de 2a et 1b
alors les probas des différentes combi divergent
le tout a +1 b sera à proba de 2/(n+2)
le tout b avec 2a sera à proba de 2/(n+1)(n+2)

Maintenant la réponse de départ est mieux appréhendée par la réponse de Black Jack, pour moi.
Mais c'est uniquement parce que je ne peux pas suivre les réponses de Doraki.Et ce n'est pas un reproche, juste mes limites.

[fatal_error]

slt Dlzlogic,
tes interventions sur les topics de probabilité ne sont pas la bienvenue. Aussi, je te demande de t'abstenir pour la suite de cette discussion.
merci,
fatal_error

[fatal_error]

J'essaie de revenir sur

Avec une variante du TCL on peut ptetre montrer que (an/bn) (et donc aussi (an/n)) converge presque sûrement, et que ...
et donc Xn devrait converger presque sûrement.

plus tard, jsens que ca va me prendre un peu de temps :marteau:

sinon, on peut chercher pour n fixé:
On a



avec
et quand n tend vers l'infini


voilà un graphe associé :


qui plotte
donc avec en abscisse c, et en ordonnée

cad que la partie la plus importante se situe lors d'un déséquilibre de a et b

[Doraki]

Si j'ai bien suivi, tu as plotté la distribution de Lim(an/bn) ?
Si on suppose que Lim(an/n) est uniforme dans [0;1], on peut en déduire son expression exacte.
enfin j'imagine que c'est ce que t'as fait.

Sinon, j'ai plotté 50 trajectoires de 10000 tirages.
En abscisse, n va de 0 à 10000, en ordonnée j'ai mis (An / n)

Donc An/n a bien l'air de converger (plutôt rapidement d'ailleurs) vers une valeur aléatoire uniforme dans [0;1] (ça devrait pas être trop dur à s'en convaincre puisqu'on sait que An/n est uniforme. Mais bon c'est encore un truc bizarre à démontrer proprement)

Aussi, on voit que les variations sont plus importantes pour An / n proche de 1/2.
Si j'avais composé par une fonction f pour uniformiser l'écart-type, on verrait un comportement plus uniforme.

[lapras]

J'ai pas lu tout mais c'est pas l'urne de polya classique ? Donc la proportion de 1 est une martingale et le nombre Xn de 1 suit une loi uniforme sur 1, ..., n ?

[acoustica]

Waw, super les graphiques ! J'arrivais pas à en faire un, je commençais à désespérer, mais en tout cas j'avais des résultats qui tendaient en faveur de la répartition uniforme. A vrai dire, après coup, ça semble assez intuitif (toujours plus facile après coup^^). Reste quand même à étudier tout ce dont vous parlez, les martingales et tout ça.

[acoustica]

Ce document est vraiment très bien fait !

http://www.apmep.asso.fr/IMG/pdf/LES_URNES_DE_POLYA_6.pdf

[antonyme]

Salut tous le monde, voici quelque simulations sur Wolfram Mathematica avec des urne de deux boules au départ :

1) Urne : {-1, 1} Graph : b-a en fonction de n avec a le nombre de -1 et b de 1, le numéro du tirage n allant de 0 à 100.
Le résultat varie beaucoup pour chaque simulation mais il est rarement proche de 0.



2) La même avec n allant de 0 à



3) Urne : {0,1} Graph : b/n en fonction de n pour n allant de 0 à 1000.
b/n quand b>a varie entre 0,6 et 0,9 environ (très rarement proche de 1/2).



4) La moyenne sur 100000 simulation du 3) qui donne des valeurs très proches des 3/4

[fatal_error]

Mais bon c'est encore un truc bizarre à démontrer proprement)

ouais ca se fait bien en fait
c<=a_n/n<d
nc<a_n<nd
P(c<a_n<d)=(c-d)+1/(n-1)(c-d)
et quand n tend vers linfini
P(c<a<d)=(c-d)
qui est l'expression d'une loi uniforme

edit: comme à l'accoutumée, j'ai encore écrit de la m.