//img.uscri.be/pth/9079022eb5fd361c38ac868e30bb61751716325e
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Pólya Urns An analytic combinatorics approach

De
63 pages
Pólya Urns An analytic combinatorics approach Basile Morcrette Algorithms project, INRIA Rocquencourt. LIP6, UPMC CALIN Seminar 07/02/2012 1/35

  • urns models

  • balanced pólya

  • saddle-point method

  • urn models

  • combinatorics approach

  • approach boolean

  • b0 balls


Voir plus Voir moins
An
Pólya Urns analytic combinatorics approach
Basile Morcrette
Algorithms project, INRIA Rocquencourt. LIP6, UPMC
CALIN Seminar 07/02/2012
/153
Outline
1.
2.
3.
4.
5.
Urn model
An exact approach
boolean formulas
Singularity analysis
family ofk-trees
Saddle-point method
preferential growth models
Towards other urn models
unbalanced, with random entries
/253
I
I
an
urn
containing
1.
balls
rules for urn evolution
U
of
rn
two
som
colours
1 0
01
dels3/35
Balanced Pólya urns βαδγα, δZ γ, β,N
Balanced urn:α+β=γ+δ(deterministic total number of balls)
A given initial configuration(a0,b0):
a0balls(counted byx)
b0balls(counted byy)
Definition History of lengthn: a sequence ofnevolutions (nrules,ndrawings) n H(x,y,z) =XHn,a,bxaybzn! n,a,b Hn,a,b of histories of length: numbern, beginning in the configuration (a0,b0), and ending in(a,b)
4/35
Combinatorics of histories - Example 1001
We
consider
this
urn
with
(a0,
b0)
=
(1,
1).
H(x,y,
xy
z)
=
/553
Combinatorics of histories - Example 1001
We
consider
this
urn
with
(a0,
b0)
=
(1,
1).
H(x,y,
xy
z)
=
/553