06/12/2010
Urnes aléatoires, populations en équilibre et séries génératrices
Article déposé le 28 novembre 2010. Validation scientifique : Grégory Ginot (ENS Ulm) - Editeur : Eric Vandendriessche. Toute reproduction pour publication ou à des fins commerciales, de la totalité ou d'une partie de l'article, devra impérativement faire l'objet d'un accord préalable avec l'éditeur (ENS Ulm). Toute reproduction à des fins privées, ou strictement pédagogiques dans le cadre limité d'une formation, de la totalité ou d'une partie de l'article, est autorisée sous réserve de la mention explicite des références éditoriales de l'article. Urnes aléatoires, populations en équilibre et séries génératrices
Version [pdf] (284 ko, 15 pages)
Le but de cet article est de présenter un objet étudié en probabilités : les urnes aléatoires. Une urne aléatoire est une boite opaque, contentant des boules de deux couleurs, disons rouge et bleu. Sur la boite on a inscrit une règle d'évolution, sous la forme suivante : α, β, γ et δ sont des entiers fixés, et on suppose qu'avant le premier tirage, le nombre de boules de chaque couleur présentes dans la boite est connu. On cherche alors comment la composition de cette urne évoluera au fil des tirages. Le nombre de boules présentes dans l'urne après n tirages forme deux suites de variables aléatoires que l'on appelle une chaîne de Markov, c'est-à-dire que seule la valeur de la suite à l'instant n influe sur la loi de la (n+1)ième variable aléatoire. Insistons sur le fait que dans notre règle d'évolution, on a supposé que la boule tirée est remise dans l'urne. Un des intérêts des urnes aléatoires est qu'elles donnent des modèles, simples à comprendre et à utiliser, pour simuler des phénomènes divers, en physique, en biologie... On peut par exemple s'intéresser à l'évolution d'un gaz dans deux chambres reliées l'une à l'autre par un trou, pour savoir s'il est possible que tout le gaz rentre dans la première chambre. C'est dans ce but qu'Ehrenfest a introduit l'urne qui porte son nom, afin de démontrer certains paradoxes de la thermodynamique qui annonçait qu'une telle évolution était impossible, le gaz devant forcément s'équilibrer entre les deux chambres. L'urne évolue ainsi : lorsqu'on tire une boule d'une couleur, on la remplace par une boule de l'autre couleur. Le lien avec le modèle est le suivant. On suppose que l'écoulement dans les chambres se fait une molécule après l'autre. Les boules rouges représentent les molécules présentes dans la chambre de gauche, et les bleues celles de la chambre de droite. A chaque étape, une molécule au hasard parmi toutes les molécules présentes change de chambre. On retrouve bien le problème d'Ehrenfest. Nous pouvons également citer la modélisation d'évolutions de populations. Des modèles déterministes, comme la suite de Fibonacci, que nous expliciterons en Section 2.3. sont connus depuis bien longtemps. Les urnes aléatoires permettent d'obtenir d'autres types de modèles, aléatoires, comme l'urne de Pólya que nous présenterons en Section 3.2, qui permet par exemple de modéliser l'évolution d'une population dans laquelle deux versions d'un même gène coéxistent. Pour cette urne, les boules rouges représentent alors des individus possédant l'une des versions de ce gène, et les boules bleues ceux possédantl'autre version. La boule que l'on tire est alors considérée comme un descendant possédant l'une des deux versions du gène. On ajoute donc dans l'urne une boule de la même couleur que celle que nous avons piochée, et remise. Afin de calculer la probabilité pour qu'après n étapes, il y ait un certain nombre de boules rouges dans l'urne, nous aurons besoin d'une notion très utile en combinatoire, celle de série génératrice. L'idée est d'associer une fonction à une suite, de telle sorte que des égalités sur les quantités de la suite (comme des formules de récurrence) se transforment en équations fonctionnelles (équation différentielle, équation du second degré, etc.). On utilise alors des résultats d'analyse afin de déterminer cette fonction, pour ainsi remonter à la suite inconnue. D'une certaine manière, la série génératrice (la fonction associée) "retient" toute l'information contenue dans la suite, y compris pour les très grandes valeurs, alors qu'en combinatoire, la plupart des raisonnements se font à entier n fixé. Cette "connaissance" des grandes valeurs nous permet alors d'appliquer les relations connues à toute la suite à la fois, et donc d'obtenir une information supplémentaire. De plus les outils d'analyse permettent une écriture très simple de certaines relations compliquées. Nous commencerons par présenter les séries génératrices, que nous appliquerons tout d'abord au calcul de la fameuse suite de Fibonacci. Ensuite nous reviendrons aux urnes aléatoires en général, avant d'appliquer les résultats présentés au cas de l'urne de Pólya. Présentons maintenant ce qu'est une série génératrice. On a déjà expliqué qu'il s'agissait d'une fonction associée à une suite permettant notamment deux opérations : connaissant la fonction, on doit pouvoir retrouver la suite, et les relations connues sur les suites doivent pouvoir se traduire sur la fonction. Nous définissons la série génératrice associée à la suite (an)n∈ N comme : Cette fonction est bien définie pour z assez petit, pourvu que (an)n∈ N ne croisse pas trop vite. Par exemple, si an≤An pour tout n, la limite de (∑k=0nakzk)n∈ N existe pour tout ∣z∣<1A. Donc dans ce cas, la série génératrice est bien définie, et on peut calculer avec. Nous devons pour commencer vérifier que les séries génératrices caractérisent les suites auxquelles elles sont associées de manière non équivoque, c'est-à-dire que si deux séries génératrices sont égales, alors les suites associées le sont aussi. Prenons deux suites (an)n∈N et (bn)n∈ N. Si nous avons : Par conséquent, à chaque fonction est associée au plus une série génératrice, mais cette preuve nous donne davantage : connaissant une fonction qui est une série génératrice, nous pouvons calculer la suite de termes associée en utilisant la méthode précédente. Par exemple, pour f(z)=11+z2, nous avons : Nous pourrions bien sûr itérer ce processus pour obtenir pour tout entier n : Une autre propriété intéressante de ces séries est leur comportement intuitif vis-à-vis des opérations usuelles. Notamment, si l'on pose : Par conséquent, fʹ est la série génératrice associée à la suite ((n+1)an+1)n∈N, f+g est celle associée à (an+bn)n∈N, et fg à (∑k=0nakbn-k)n∈N. Intéressons-nous maintenant à la détermination de séries génératrices remarquables, qui nous permettrons de calculer par la suite les développements des fonctions que nous obtiendrons. Les séries génératrices que nous aurons à développer par la suite pourront être exprimées comme somme de fonctions plus simples de la forme z→1(1-z)i. Par conséquent nous allons déterminer quelles sont les suites associées à ces fonctions. Nous commençons par calculer le développement de z→11-z. Soit gn la fonction définie (pour ∣z∣<1) comme suit : Dès lors nous pouvons écrire, pour a,b,c∈ R : Nous allons généraliser un peu plus notre propos, et développer fp:z→1(1-z)p. Pour cela procédons par récurrence. On sait que pour p=1, tous les coefficients sont égaux à 1. Pour p=2, remarquons que f2=f1ʹ. Par conséquent, il suffit de dériver l'écriture de f1 en série génératrice pour obtenir : La suite de Fibonacci a été introduite au XIIIe siècle par Leonardo Fibonacci. Cette suite peut représenter, par exemple, l'évolution d'une population de lapins qui se reproduisent de la manière suivante. Un jeune couple de lapins met un mois à devenir adulte, et tout couple de lapins adultes donne naissance à un nouveau couple chaque mois. On note fn le nombre de couples de lapins présents au début du nième mois, et on suppose qu'au premier mois, on ne possède qu'un unique couple de jeunes lapins. Nous commençons par déterminer la formule de récurrence. Le nombre de couples de lapins naissant le (n+2)ième mois est égal au nombre de couples âgés de plus d'un mois présents. Or il y a fn+1-fn couples qui sont nés au (n+1)ième mois qui sont donc des jeunes qui ne se reproduisent pas. Chacun des fn couples âgés d'au moins un mois donne alors naissance à un nouveau couple. On a en définitive : Cette suite est très connue en raison de son lien avec le nombre d'or Φ=1+52. En particulier on remarque que le rapport fn+1fn tend vers Φ quand n tend vers l'infini, comme nous le montrerons ci-dessous. Soit ψ la série génératrice associée à la suite de Fibonacci, qui est définie par : Nous utilisons alors la relation de récurrence pour calculer explicitement ψ. En effet, en écrivant fn+2=fn+1+fn dans la formule précédente, nous obtenons : On vient d'appliquer à la série génératrice la relation de récurrence que nous connaissions pour la suite. Cela se traduit par une égalité fonctionnelle, particulièrement simple dans ce cas particulier, qui nous permet de déterminer ψ : Ce n'est malheureusement pas une forme que l'on sait facilement développer en série entière. Nous allons donc la décomposer en éléments simples. Commençons par déterminer les solutions de z2+z-1=0. On obtient ω1=5-12=1Φ et ω2=-1+52=-Φ, où on a posé Φ=1+52 le nombre d'or. On écrit alors : En utilisant les calculs du paragraphe précédent et en déterminant la série génératrice associée à ψ, nous obtenons alors pour fn : On en déduit une expression explicite pour la suite de Fibonacci ne nécessitant pas le calcul des n premiers termes pour donner fn+1. En particulier, on obtient bien, grâce à un petit calcul, que limn→+∞fn+1fn=Φ. Commençons par nous intéresser à une urne aléatoire générale. Rappelons que la règle est la suivante : si on a tiré une boule rouge, on ajoute α boules rouges et β bleues à l'urne, et si on a tiré une boule bleue, on en ajoute γ rouges et δ bleues. On note a0 et b0 le nombre (déterministe) de boules respectivement rouges et bleues présentent à l'instant 0, et an et bn le nombre (aléatoire) de boules de chaque couleur présentes dans l'urne après n étapes. Nous cherchons quelle est la probabilité pour une urne donnée d'arriver après n étapes à une configuration avec a boules rouges et b boules bleues. Pour cela nous avons besoin de déterminer le nombre d'"histoires" possibles pour l'urne conduisant à une configuration avec a boules rouges et b boules bleues en n étapes. Une "histoire" est donnée par la suite des boules tirées, chacune étant supposées distinctes. Par exemple, pour l'urne de Pólya partant d'une boule rouge et d'une boule bleue, il existe deux histoires menant à deux boules rouges et deux boules bleues après deux étapes : celle où on a d'abord tiré la boule rouge et celle où on a d'abord tiré la boule bleue. Il existe également deux histoires menant à trois boules rouges et une bleue selon la boule rouge tirée à la deuxième étape, l'"ancienne" ou la "nouvelle".
- Regarder sa couleur et la remettre dans l'urne.
- Si la boule est rouge, ajouter α boules rouges (α pouvant être négatif, dans ce cas on retirera des boules rouges) et β boules bleues.
- Si la boule est bleue, ajouter γ boules rouges et δ boules bleues (là encore, δ peut être positif ou négatif).
- Recommencer à la première étape
2. Série génératrice
2.1 Propriétés des séries génératrices
alors pour z=0 nous avons a0=b0. Soustrayons a0=b0, et divisons par z nous avons :
a1+a2z+a3z2+...=b1+b2z+b3z2+...
Ce qui nous permet de voir que a1=b1, en faisant tendre z vers 0. En réitérant le processus nous obtenons bien que les suites (an)n∈N et (bn)n∈N sont identiques.
a0=f(0)=1a1=limz→01z(f(z)-a0)=limz→0-z1+z2=0a2=limz→01z(-z1+z2-0)=limz→0-11+z2=-1a3=limz→01z(-11+z2+1)=limz→0z1+z2=0⋯
mais cette formule nous demande de calculer tous les termes jusqu'au rang n - 1 pour connaître le nième terme, alors que nous souhaiterions connaître une formule valable quel que soit l'entier n. Notons que (an)n∈N ne dépend que des valeurs de f pour z proche de 0. On pourra par conséquent toujours supposer que z est assez petit, et restreindre f à une fonction définie sur un voisinage de 0.
f(z)=a0+a1z+a2z2+... et g(z)=b0+b1z+b2z2+...,
on a alors (pour des z assez petits) :
fʹ(z)=a1+2a2z+3a3z2+...
f(z)+g(z)=(a0+b0)+(a1+b1)z+(a2+b2)z2+...
f(z)g(z)=(a0+a1z+a2z2+...)(b0+b1z+b2z2+...)=a0b0+(a1b0+a0b1)z+(a2b0+a1b1+a0b2)z2+⋯
2.2 Calcul des coefficients de fonctions "utiles"
On remarque que
zgn(z)-gn(z)=z+z2+...+zn+1-(1+z+...+zn)=zn+1-1.
Par conséquent gn(z)=zn+1-1z-1. En faisant tendre n vers +∞, nous obtenons alors :
limn→+∞gn(z)=11-z
Ce qui nous donne en définitive l'égalité suivante valable pour ∣z∣<1 :
1+z+z2+...=11-z
autrement dit, la suite associée à la fonction z↦11-z est la suite constante égale à 1.
donc par conséquent le nième coefficient associé à cette fonction s'écrira a(-b)ncn+1.
De manière générale, on remarque que fp+1=1pfpʹ. On obtient ainsi par récurrence que, pour tout n∈N :
fp(z)=1+(p1)z+(p+12)z2+(p+23)z3+...
Soit par conséquent, le nième coefficient associé à fp est égal à
(n+p-1n)=(n+p-1p-1).
Nous allons maintenant appliquer ces résultats une première fois à la suite de Fibonacci.
2.3 La suite de Fibonacci
2.3.1 Génération de la suite
Les conditions initiales sont données par f0=0 et f1=1.
2.3.2 Construction et calcul de la série génératrice
ψ(z)=f0+f1z+f2z2+...=f0+f1z+(f2z2+f3z3+f4z4+⋯)=z+((f0+f1)z2+(f1+f2)z3+(f2+f3)z4+⋯)=z+z2(f0+f1z+f2z2+...)+z(f0+f1z+f2z2+...)=z+zψ(z)+z2ψ(z).
En réduisant au même dénominateur il vient :
ψ(z)=-(a+b)z+(-aΦ+bΦ)z2+z-1=-zz2+z-1,
d'où on tire le système :
{a+b=1bΦ-aΦ=0
soit a=11+Φ2 et b=Φ21+Φ2.
fn=a1ω1n+1+b1ω2n+1=11+Φ2(Φn+1+(-1)n+1Φn-1)
3. Urne aléatoire
Les urnes aléatoires ont été introduites il y a plus de trois siècles, et les premiers résultats ont été démontrés par Jacob Bernouilli et Laplace [Flajolet, Dumas et Puyhaubert, 2006]. Par la suite de nombreuses urnes particulières ont été introduites pour modéliser certains problèmes, parmi lequelles les urnes d'Ehrenfest, Friedman ou encore Pólya sont certainement les plus connues. Nous allons maintenant utiliser les outils que nous venons de développer pour étudier l'urne de Pólya. Comme l'approche que nous avons choisi s'étend sans grandes difficultés à de très nombreux types d'urnes, nous nous placerons pour commencer dans un cadre général. Nous laissons à la curiosité du lecteur l'application des résultats obtenus ici à d'autres urnes aléatoires, comme l'urne d'Ehrenfest, ou bien d'autres [1].
3.1 Série génératrice associée à l'urne aléatoire
Figure I Arbre des "histoires" d'une urne de Pólya |
La figure I montre que pour l'urne de Pólya, après 2 étapes, chacune des compositions possibles est donnée par deux histoires. On remarquera que l'on distingue bien dans la deuxième étape le choix de la première boule rouge et celui de la deuxième dans la partie gauche du tableau, et de même dans la partie droite pour ce qui est des boules bleues. Toutes les histoires possibles de longueur n sont équiprobables. Par conséquent, si on note hn(a,b) le nombre d'histoires de longueur n menant à une urne composée de aboules rouges et b boules bleues et hn le nombre total d'histoires de longueur n, alors on a : Nous allons calculer hn(a,b) grâce à la notion de série génératrice. Comme la quantité hn(a,b) croit très vite quand n croit, nous allons utiliser une série génératrice exponentielle, associée à hn(a,b)n!, où n!=1×⋯×n, qui croira donc à un rythme bien plus acceptable. Il y a néanmoins un autre problème, nous avons trois quantités à retenir simultanément : le nombre de boules rouges, le nombre de boules bleues, et le nombre d'étapes que nous avons effectué. Néanmoins, après n étapes, l'urne ne peut être que dans un nombre fini d'états différents, par conséquent, la somme suivantea : Ceci nous permet donc d'introduire la série génératrice exponentielle associée à l'urne comme la fonction de trois variables x,y,z suivante : Comme nous l'avons vu précédemment, connaître cette fonction nous permet de remonter aux coefficients, en considérant tout d'abord (x,y) comme des paramètres de notre fonction de la variable z. Pour x=y=1, la fonction z↦H(1,1,z) est intéressante en elle-même. En effet, hn est la somme des hn(a,b) pour tous les couples (a,b) possibles (le nombre d'histoires de longueur n est bien égal à la somme sur tous les états possibles du nombre d'histoires de longueur n menant à un état donné). Par conséquent, comme H(1,1,z) est la somme de tous les termes hn(a,b)znn!, pour a,b,n entiers, en commençant par faire les sommes par rapport à a et b à entier n fixé, on obtient que H(1,1,z) s'écrit comme la somme des hnznn!. Autrement dit, nous venons de prouver que la fonction z↦H(1,1,z) est la série génératrice exponentielle associée à la suite (hn). Afin d'établir une égalité fonctionnelle pour H, il va nous falloir utiliser une représentation astucieuse de notre urne aléatoire, utilisant des équations aux dérivées partielles. Nous pouvons remarquer que dans la série génératrice précédente, une urne avec a boules rouges et b boules bleues est représentée par le monôme xayb. Or si on définit les fonctions suivantes : Lorsqu'on réalise un tirage de cette urne, on crée a histoires pour lesquelles on a tiré une boule rouge et b pour lesquelles c'est une boule bleue qui est tirée. Par conséquent, à une fonction uavb, on associe a fonctions ua+αvb+β et b fonctions ua+γvb+δ. Cela revient à appliquer l'opérateur aux dérivées partielles suivant à notre fonction : En effet on a D(uavb)=aua+αvb+β+bua+γvb+δ. Par conséquent l'évolution de l'urne est gouvernée par cet opérateur, que l'on associe à l'urne. On peut se servir de celui-ci pour réécrire la série génératrice associée à l'urne. La série génératrice que nous cherchons est obtenue en itérant la dérivation associée à l'urne. Supposons que nous commencions avec a0 boules rouges et b0 boules bleues. L'état est représenté par ua0vb0. Les états accessibles après une étape, (comptés avec le nombre de manières possibles pour arriver à chacun d'entre eux) sont représentés par D(ua0vb0). Après deux étapes, c'est D(D(ua0vb0))=D2(ua0vb0) qui code la somme des états accessibles, puis D3(ua0vb0) après trois étapes, etc... On peut alors réécrire la série génératrice en regroupant tous les termes associés à zn. Grâce à l'opérateur D, nous pouvons alors écrire : Ceci nous donne un moyen d'obtenir une équation fonctionnelle satisfaite par H. Pour cela, appliquons l'opérateur D à l'égalité ci-dessus. H vérifie par conséquent l'équation aux dérivées partielles suivante : Pour résoudre cette équation différentielle on va chercher un couple de fonctions (X(z),Y(z)) qui se comportent, lorsqu'on les dérive par rapport à z, de la même manière que u et v lorsqu'on leur applique D. Autrement dit on veut que, pour tout choix de (a,b)∈N, on ait : Or on sait que : Maintenant, si les équations différentielles suivantes sont vérifiées par un couple de fonctions (Xx,Yy) satisfaisant la condition initiale Xx(0)=x,Yy(0)=y, alors on a : Nous venons d'obtenir une méthode générale permettant de calculer les valeurs de hn(a,b). Grâce à cette formule, si on est capable de résoudre le système d'équations différentielles précédent pour une urne aléatoires, alors on est capable de calculer la probabilité d'arriver dans un état donné en un certain nombre d'étapes. Nous allons maintenant appliquer les résultats obtenus au cas de l'urne de Pólya. Rappelons que l'urne de Pólya permet d'étudier l'évolution d'une population de deux espèces. Elle a été introduite par Pólya [Pólya, 1930] et été étudiée maintes fois par la suite. [Tautu,1986] en donne un bref aperçu historique. L'urne est définie avec les quantités suivantes : α=1,β=0,γ=0 et δ=1, autrement dit, quand on tire une boule d'une couleur, on en ajoute une de la même couleur. Le système associé à l'urne est alors le suivant : En d'autres termes, au produit de deux séries génératrices de coefficients (an) et (bn) est associé la suite (a0bn+a1bn-1+⋯+anb0). Dans notre cas, la série entière de zHx,y(z)=H(x,y,z) (nous considérons de nouveau x et y comme des paramètres) possède les coefficients suivants : Ceci nous permet par conséquent de calculer le nombre d'histoires de longueur n menant à un état particulier de l'urne : Finalement, toutes les histoires étant équiprobables, si on note an le nombre de boules rouges présentes dans l'urne à l'instant n et bn le nombre de boules bleues présentes à cet instant, nous obtenons les probabilités suivantes, qui nous permettent de déterminer l'évolution de toute urne (on utilisera le fait que le nombre total de boules à l'instantn est connu, an+bn=a0+b0+n, par conséquent nous pouvons nous intéresser au seul nombre de boules rouges, celui de boules bleues s'en déduit) : Nous pouvons maintenant interpréter les résultats obtenus. Commençons par une observation. On remarque que si a0=b0=1, c'est-à-dire que l'on commence avec une boule rouge et une boule bleue dans l'urne, alors toutes les urnes possibles au temps n ont exactement la même probabilité d'apparaître. Mais cette propriété n'est pas vraie quel que soit le nombre de boules avec lequel nous débutons : par exemple, si nous étudions une urne dans laquelle il y a au départ deux boules de chaque couleur, soit a0=b0=2, nous obtenons grâce à un calcul rapide : Ainsi, dans ce cas, on voit clairement que tous les états possibles au temps n ne sont pas équiprobables. En particulier, une urne qui possède une moitié de boules rouges apparaît avec la probabilité 3(n+4)22(n+3)(n+2)(n+1) à l'étape n alors qu'une urne ne possédant que deux boules rouges à l'étape n n'apparaît qu'avec la probabilité6(n+3)(n+2).
est finie quel que soit l'entier n. C'est un polynôme en deux variables x et y. Si x et y sont maintenant pensés comme des paramètres, la connaissance de cette quantité (dépendant de n) pour tout couple (x,y) nous permettra de remonter au polynôme puis aux coefficients. Étudions donc la série génératrice exponentielle associée à ces quantités :Hx,y(z)=(∑a,bh0(a,b)xayb)+(∑a,bh1(a,b)xayb)z1+(∑a,bh2(a,b)xayb)z22+⋯.
3.1.1 Représentation d'une urne aléatoire par une dérivation
v:x,y↦y,
on a xayb=ua(x,y)vb(x,y). On dit alors que l'urne contenant a boules rouges et b boules bleues est codée par la fonction uavb.
3.1.2 Système différentiel associé à l'urne
D(H)(u,v,z)=∑n=0+∞Dn+1(uavb)znn!=∑n=0+∞Dn+1(uavb)∂zzn+1(n+1)!=∂z∑n=1+∞Dn(uavb)znn!=∂zH.
Donc en choisissant successivement a=1,b=0 et a=0,b=1, il vient que X et Y vérifient en particulier le couple d'équations différentielles suivant :
{X.=Xα+1YβY.=XγYδ+1
Or H(x,y,z)=∑n=0+∞Dn(ua0vb0)(x,y)znn!, donc on a :
H(x,y,z)=∑n=0+∞Dn(ua0vb0)(Xx(0),Yy(0))dfracznn!=∑n=0+∞∂z(Xxa0Yyb0)(0)znn!=(Xx(z)a0Yy(z)b0)
3.2 L'urne de Pólya
qui se résout immédiatement en Xx(t)=x1-xt,Yy(t)=y1-yt. On a alors :
H(x,y,z)=(x1-xz)a0(y1-yz)b0.
On peut alors développer H en séries entières pour calculer hn(a,b). Pour cela nous commencerons par rappeler que :
(x1-xz)a0=x+(a0a0-1)x2z+(a0+1a0-1)x3z2+⋯
On doit maintenant réaliser le produit des deux développements suivants pour obtenir le développement en séries génératrices de notre urne. Rappelons que :
(a0+a1z+a2z2+...)(b0+b1z+b2z2+...)=a0b0+(a1b0+a0b1)z+(a2b0+a1b1+a0b2)z2+⋯
Or rappelons que ces coefficients s'écrivent également (c.f. Section 3.1, la définition de H(x,y,z) :
1n!(hn(0,n+2)yn+2+hn(1,n+1)xyn+1+⋯+hn(n+1,1)xn+1y).
De plus, en se souvenant que la série génératrice exponentielle associée à cette suite est H(1,1,z)=1(1-z)a0+b0, on obtient l'égalité :
hnn!=(n+a0+b0-1a0+b0-1).
Figure II Distribution des probabilités d'apparition d'une urne après 30 tours en fonctions des conditions initiales |
Sur la figure II, nous avons représenté la probabilité de posséder a boules rouges pour une urne de Pólya ayant subi 30 étapes d'évolution, à partir de toutes les situations initiales possibles avec 10 boules, de 1 rouges et 9 bleues à 9 rouges et 1 bleues. Chacune de ces distributions de probabilités est "piquée" au voisinage de la proportion de boules qu'il contient. Autrement dit, une urne de Pólya favorise dans le futur les configurations qui possèdent un nombre moyen de boules voisin du sien. Ainsi une urne de Pólya commençant avec une proportion r de boules rouges parmi ses boules rend plus probable les compositions d'urnes pour lesquelles cette proportion est conservée. En particulier, si on commence avec 13 de boules rouges dans l'urne, on a de fortes chances que ce rapport soit conservé pour toujours. Ce phénomène s'accentue quand le nombre total de boules augmente, autrement dit, plus le nombre initial de boules est grand, plus il est difficile de modifier le ratio de boules rouges présentes dans l'urne. Or une urne aléatoire vérifie une propriété remarquable : si à un moment donné nous regardons dans l'urne le nombre de boules de chaque couleur et que nous replaçons ensuite le couvercle, et recommençons à faire évoluer cette urne, alors l'urne se comporte comme si on avait dès le début commencé avec la composition que nous venons de découvrir. Cette propriété s'appelle la propriété de Markov. L'urne évolue à partir du temps n exactement comme si on avait à l'instant intial commencé avec an boules rouges et bn boules bleues. Revenons à l'urne de Pólya. On vient de voir que si la composition initiale est de une boule rouge et une boule bleue, alors à un instant donné toutes les compositions de l'urne sont équiprobables. Mais alors le ratio de boules rouges dans l'urne est une variable aléatoire choisie uniformément au hasard. Or si on repart ensuite d'un instant donné, ce ratio aura tendance à se conserver ! Par conséquent, le ratio de boules rouges tend vers une constante, mais cette constante est aléatoire de loi uniforme. Autrement dit, si on trace le graphe représentant l'évolution du nombre de boules rouges présentes dans l'urne au cours du temps, on obtient pour chaque réalisation de l'expérience une courbe proche d'une droite linéaire, mais dont la pente est aléatoire, et varie de telle façon qu'à un temps donné, sa distribution sur l'axe des ordonnées varie selon une loi uniforme (à entier n fixé, les probabilités d'atteindre chacun des points (n,k) pour 1≤k≤n+1 sont égales). On a représenté sur la figure III l'évolution du nombre de boules rouges de 11 réalisations d'urnes de Pólya, entre les instants 0 et 500. On remarquera l'allure de droite de ces courbes, ainsi que leur caractère uniforme.
Figure III 11 réalisations d'urnes de Pólya au cours du temps, partant d'une boule rouge et d'une boule bleue |
L'urne de Pólya modélise donc une population autostable, pour laquelle tout équilibre à un instant donné tend à être conservé à l'infini, avec une probabilité d'autant plus grande que le nombre d'individus est grand, cet équilibre restant toutefois aléatoire. Nous pourrions préciser quelle est la probabilité, partant d'une situation donné, que ces populations s'éloigne de manière significative de leur équilibre, c'est ce dont s'occupe la théorie des grandes déviations. De nombreuses autres questions peuvent encore se poser sur le comportement à l'infini de telles urnes. On a vu dans cet article comment nous pouvions utiliser des séries génératrices pour calculer certaines quantités (suite récurrente d'ordre 2, comme la suite de Fibonacci, probabilité pour une variable aléatoire d'avoir une valeur donnée, nombres d'objets de taille n dans un ensemble...). Le nombre d'application possibles ne s'arrête certainement pas ici. Il y a encore de nombreux cas pour lesquels cette méthode se révèle l'une des plus aisée, comme pour le calcul des nombres de Catalan, qui comptent le nombre d'arbres planaires à n branches (ou bien le nombre de parenthèsages de longueur n). Dans ce cas la résolution de la relation de récurrence se transforme en la résolution d'une équation du second degré. Un autre exemple est le nombre tn de triplets d'entiers naturels de somme égale à n (pour celui-ci nous avons déjà fait tous les calculs dans la Section 2.2, il suffit de considérer le développement de z↦1(1-z)3 de deux manières distinctes), et encore bien d'autres. En ce qui concerne les urnes aléatoires en général, il est possible de s'intéresser de plus près au système différentiel que nous leur avons associé, comme dans l'article [Flagolet, Dumas et Puyhaubert 2006]. Ainsi il devient possible d'étudier le comportement à long terme de certaines classes d'urnes aléatoires. Dans ce cas, il apparait que les proportions de boules rouges et bleues peuvent se comporter de manière bien plus étrange que dans le cas de l'urne de Pólya.
Conclusion
Bibliographie
Philippe Flajolet, Philippe Dumas, and Vincent Puyhaubert (2006). "Some exactly solvable models of urn process theory", Proceedings of Fourth Colloquium on Mathematics and Computer Science, vol. AG, p. 59–118.
Norman L. Johnson and Samuel Kotz (1977). Urns models and their application, John Wiley & Sons, New York-London-Sydney.
Pierre-Simon Laplace (1819). Théorie analytique des probabilités, Oeuvres complètes, Tome 7, Réédition 1886
Georges Pólya (1930). "Sur quelques points de la théorie des probabilités", Annales de l'institut Henri Poincaré, tome1, n° 2, p. 117-161
P. Tautu (1986). Stochastic spatial processes in biology : A concise historical survey, Lecture Notes in Math., vol. 1212, Springer-Verlag, Berlin and New York.
19:32 Publié dans Urnes aléatoires, populations en équilibre | Lien permanent | Commentaires (0) | 
| 
del.icio.us | 
| 
Digg | 
Facebook
Les commentaires sont fermés.