{"id":8576,"date":"2015-11-30T23:37:55","date_gmt":"2015-11-30T22:37:55","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=8576"},"modified":"2015-12-02T08:56:20","modified_gmt":"2015-12-02T07:56:20","slug":"back-to-basics-polya-urns","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2015\/11\/30\/back-to-basics-polya-urns\/","title":{"rendered":"Back to basics - P\u00f3lya urns"},"content":{"rendered":"
\"Georges<\/a>
Georges P\u00f3lya (1887 - 1985)<\/figcaption><\/figure>\n

This post is devoted to P\u00f3lya urns<\/b>, probably the simplest stochastic model of reinforcement<\/b>. At time \\( {n=0} \\), we prepare an urn containing \\( {a>0} \\) azure<\/b> balls and \\( {b>0} \\) black<\/b> balls. To produce the configuration of the urn at time \\( {n=1} \\), we draw at random a ball in the urn, and then we replace this ball in the urn together with a new ball of the same color. We repeat this mechanism independently to produce the configuration of the urn at any time \\( {n\\in\\mathbb{N}} \\).<\/p>\n

Let \\( {M_n\\in[0,1]} \\) be the proportion of azure balls in the urn at time \\( {n\\in\\mathbb{N}} \\). At time \\( {n\\in\\mathbb{N}} \\), the urn contains \\( {a+b+n} \\) balls, and \\( {(a+b+n)M_n} \\) azure balls. Conditional on \\( {M_n} \\), an azure ball is added to the urn at time \\( {n+1} \\) with probability \\( {M_n} \\). Hence<\/p>\n

\\[ M_0=\\frac{a}{a+b} \\quad\\text{and}\\quad M_{n+1}=\\frac{(a+b+n)M_n+\\mathbf{1}_{\\{U_{n+1}\\leq M_n\\}}}{a+b+n+1} \\]<\/p>\n

where \\( {{(U_n)}_{n\\geq1}} \\) are iid uniform random variables on \\( {[0,1]} \\), and the event \\( {\\{U_{n+1}\\leq M_n\\}} \\) corresponds to add an azure ball. The stochastic recursive sequence \\( {{(M_n)}_{n\\geq0}} \\) is a non-homogeneous Markov chain<\/b> with state space \\( {[0,1]} \\), and also a martingale<\/b>.<\/p>\n

If we encode the result of the \\( {n} \\) drawing by a random variable \\( {X_n} \\) with values in \\( {\\{\\alpha,\\beta\\}} \\) where \\( {\\alpha} \\) and \\( {\\beta} \\) indicate respectively that the ball is azure or black. Let \\( {Y_n} \\) and \\( {Z_n} \\) be respectively the number of azure and black balls added to the urn after the first \\( {n} \\) drawing. At time \\( {n} \\), the urn contains<\/p>\n

\\[ a+Y_n+b+Z_n=a+b+n \\]<\/p>\n

balls, more precisely the number of azure balls is<\/p>\n

\\[ a+Y_n=a+\\sum_{k=1}^n\\mathbf{1}_{\\{X_k=\\alpha\\}}=(a+b+n)M_n \\]<\/p>\n

while the number of black balls is<\/p>\n

\\[ b+Z_n=b+\\sum_{k=1}^n\\mathbf{1}_{\\{X_k=\\beta\\}}. \\]<\/p>\n

We have \\( {Y_n+Z_n=n} \\). The sequence \\( {{(X_n,Y_n,Z_n)}_{n\\geq1}} \\) satisfies the stochastic recursion<\/p>\n

\\[ (X_{n+1},Y_{n+1},Z_{n+1}) = \\left\\{ \\begin{array}{rl} (\\alpha,Y_n+1,Z_n) & \\mbox{if } U_{n+1}\\leq\\frac{a+Y_n}{a+b+n},\\\\ (\\beta,Y_n,Z_n+1) & \\mbox{if } U_{n+1}>\\frac{a+Y_n}{a+b+n}, \\end{array} \\right. \\]<\/p>\n

with by convention \\( {Y_0=0} \\) and \\( {Z_0=0} \\) (the value of \\( {X_0} \\) is useless).<\/p>\n

Martingale.<\/b> The sequence \\( {{(M_n)}_{n\\geq0}} \\) is a martingale<\/b> taking its values in \\( {[0,1]} \\) for the filtration \\( {{(\\mathcal{F}_n)}_{n\\geq0}} \\) defined by \\( {\\mathcal{F}_n=\\sigma(U_1,\\ldots,U_n)} \\). Indeed \\( {M_n\\in L^1(\\mathcal{F}_n)} \\) and<\/p>\n

\\[ \\mathbb{E}(M_{n+1}\\,|\\,\\mathcal{F}_n) =\\mathbb{E}(M_{n+1}\\,|\\,M_n) =\\frac{(a+b+n)M_n+M_n}{a+b+n+1} =M_n. \\]<\/p>\n

In particular we have the following conservation law<\/b>: for all \\( {n\\in\\mathbb{N}} \\),<\/p>\n

\\[ \\mathbb{E}(M_n)=\\mathbb{E}(M_0)=\\frac{a}{a+b}. \\]<\/p>\n

It follows from martingale limit theorems (the martingale is uniformly bounded and thus uniformly integrable!) that there exists a random variable \\( {M_\\infty} \\) on \\( {[0,1]} \\) such that<\/p>\n

\\[ \\lim_{n\\rightarrow\\infty}M_n = M_\\infty \\]<\/p>\n

almost surely and in \\( {L^p} \\) for any \\( {p\\geq1} \\). In particular \\( {\\mathbb{E}(M_\\infty)=\\mathbb{E}(M_0)=\\frac{a}{a+b}} \\).<\/p>\n

Limiting distribution.<\/b> The random variable \\( {M_\\infty} \\) follows the Beta distribution<\/b> on \\( {[0,1]} \\) with parameter \\( {(a,b)} \\) and density<\/p>\n

\\[ u\\in[0,1]\\mapsto\\frac{u^{a-1}(1-u)^{b-1}}{\\mathrm{Beta}(a,b)} \\quad\\text{where}\\quad \\mathrm{Beta}(a,b):=\\int_0^1\\!p^{a-1}(1-p)^{b-1}\\,dp. \\]<\/p>\n

In particular if \\( {a=b=1} \\) then \\( {M_\\infty} \\) follows the uniform distribution on \\( {[0,1]} \\).<\/p>\n

To see it let us recall first of all that<\/p>\n

\\[ \\mathrm{Beta}(a,b) =\\frac{\\Gamma(a)\\Gamma(b)}{\\Gamma(a+b)} \\quad\\text{where}\\quad \\Gamma(x):=\\int_0^\\infty\\!t^{x-1}e^{-x}\\,dx. \\]<\/p>\n

For any \\( {c} \\) and \\( {k} \\) we set<\/p>\n

\\[ c^{(k)}=c(c+1)\\cdots(c+k-1)=\\frac{(c+k-1)!}{(c-1)!}=\\frac{\\Gamma(c+k)}{\\Gamma(c)}. \\]<\/p>\n

Now for any \\( {x_1,\\ldots,x_n} \\) in \\( {\\{0,1\\}} \\), we have, denoting \\( {k=x_1+\\cdots+x_n} \\),<\/p>\n

\\[ \\mathbb{P}(\\mathbf{1}_{\\{X_1=\\alpha\\}}=x_1,\\ldots,\\mathbf{1}_{\\{X_n=\\alpha\\}}=x_n) =\\frac{a^{(k)}b^{(n-k)}}{(a+b)^{(n)}}. \\]<\/p>\n

This probability is invariant by permutation of \\( {x_1,\\ldots,x_n} \\): this means that the distribution of the random vector \\( {(\\mathbf{1}_{\\{X_1=\\alpha\\}},\\ldots,\\mathbf{1}_{\\{X_n=\\alpha\\}})} \\) is exchangeable<\/b>. Hence the random variable<\/p>\n

\\[ Y_n=\\sum_{k=1}^n\\mathbf{1}_{\\{X_k=\\alpha\\}} \\]<\/p>\n

satisfies, for any \\( {k\\in\\{0,1,\\ldots,n\\}} \\),<\/p>\n

\\[ \\begin{array}{rcl} \\mathbb{P}(Y_n=k) &=&\\binom{n}{k}\\frac{a^{(k)}b^{(n-k)}}{(a+b)^{(n)}}\\\\ &=&\\binom{n}{k} \\frac{\\Gamma(a+k)\\Gamma(b+n-k)\\Gamma(a+b)}{\\Gamma(a)\\Gamma(b)\\Gamma(a+b+n)}\\\\ &=&\\binom{n}{k} \\frac{\\mathrm{Beta}(a+k,b+n-k)}{\\mathrm{Beta}(a,b)}\\\\ &=&\\int_0^1\\! \\binom{n}{k}p^{k}(1-p)^{n-k}\\frac{p^{a-1}(1-p)^{b-1}}{\\mathrm{Beta}(a,b)}\\,dp. \\end{array} \\]<\/p>\n

We say that \\( {Y_n} \\) follows the Beta-binomial distribution<\/b>, which is a a mixture of binomial laws of size \\( {n} \\) with a parameter \\( {p} \\) which follows the Beta distribution of parameter \\( {(a,b)} \\). We have \\( {M_n=(a+Y_n)\/(a+b+n)} \\) with \\( {Y_0=0} \\). When \\( {a=b=1} \\), then formula for the law of \\( {Y_n} \\) indicates that \\( {Y_n} \\) is uniform on \\( {\\{0,1,\\ldots,n\\}} \\), and thus \\( {M_n} \\) is uniform on \\( {\\{1\/(n+2),\\ldots,(n+1)\/(n+2)\\}} \\), which implies that \\( {M_\\infty} \\) is uniform on \\( {[0,1]} \\). In the general case, for any \\( {t\\in[0,1]} \\),<\/p>\n

\\[ \\begin{array}{rcl} \\mathbb{P}(M_\\infty\\leq t) &=&\\lim_{n\\rightarrow\\infty}\\mathbb{P}(Y_n\\leq(a+b+n)t-a)\\\\ &=&\\cdots =\\frac{1}{\\mathrm{Beta}(a,b)}\\int_0^t\\!u^{a-1}(1-u)^{b-1}\\,du. \\end{array} \\]<\/p>\n

The computation is based on the so-called Beta-binomial correspondence, which states that if \\( {U_1,\\ldots,U_n} \\) are iid and uniform on \\( {[0,1]} \\) and if \\( {U_{(1)}\\leq\\cdots\\leq U_{(n)}} \\) is their reordering, then for any \\( {k=1,\\ldots,n} \\) the random variable \\( {U_{(k)}} \\) follows the Beta distribution on \\( {[0,1]} \\) with parameter \\( {(k,n-k+1)} \\) and<\/p>\n

\\[ \\mathbb{P}(S_n\\geq k) =\\mathbb{P}(\\mathbf{1}_{\\{U_1\\leq p\\}}+\\cdots+\\mathbf{1}_{\\{U_n\\leq p\\}}\\geq k) =\\mathbb{P}(U_{(k)}\\leq p). \\]<\/p>\n

From discrete to continuous.<\/b> The results remain valid when \\( {a} \\) and \\( {b} \\) are positive reals. This motivates the usage of Beta and Gamma functions instead of factorials. In this case we may use an interval partition<\/b> instead of an urn.<\/p>\n

General urns and sampling schemes.<\/b> We generalized the reinforcement mechanism as follows: we fix an integer \\( {r\\geq-1} \\), and, at each drawing, we replace in the urn \\( {1+r} \\) balls of the drawn color.<\/p>\n