Pólya urna modell

Inom statistik är en Pólya urn modell (även känd som en Pólya urn scheme eller helt enkelt som Pólya's urn ), uppkallad efter George Pólya , en typ av statistisk modell som används som en idealiserad mental träningsram , som förenar många behandlingar.

I en urnmodell representeras föremål av verkligt intresse (som atomer, människor, bilar, etc.) som färgade kulor i en urna eller annan behållare. I den grundläggande Pólya urnmodellen innehåller urnan x vita och y svarta kulor; en kula dras slumpmässigt från urnan och dess färg observeras; den returneras sedan i urnan, och ytterligare en kula av samma färg läggs till urnan, och urvalsprocessen upprepas. Frågor av intresse är utvecklingen av urnpopulationen och sekvensen av färger på de utdragna kulorna.

Detta ger urnan en självförstärkande egenskap som ibland uttrycks som att de rika blir rikare .

Observera att Pólya-urnmodellen i någon mening är "motsatsen" till modellen för provtagning utan ersättning , där varje gång ett visst värde observeras är det mindre sannolikt att det observeras igen, medan i en Pólya-urnmodell, en observerad värdet är mer sannolikt att observeras igen. I båda dessa modeller har mäthandlingen en effekt på resultatet av framtida mätningar. (Som jämförelse, vid provtagning med utbyte har observation av ett visst värde ingen effekt på hur sannolikt det är att observera det värdet igen.) I en Pólya urnmodell har successiva mäthandlingar över tid mindre och mindre effekt på framtida mätningar, medan vid provtagning utan ersättning är det motsatta: Efter ett visst antal mätningar av ett visst värde kommer det värdet aldrig att ses igen.

En av anledningarna till intresset för just denna ganska utarbetade urnmodell (dvs med duplicering och sedan byte av varje dragen kula) är att den ger ett exempel där antalet (inledningsvis x svarta och y vita) bollar i urnan inte är dold, vilket kan approximera den korrekta uppdateringen av subjektiva sannolikheter som är lämpliga för ett annat fall där det ursprungliga urninnehållet döljs medan ordinarie provtagning med utbyte utförs (utan Pólya-kuldupliceringen). På grund av det enkla "sampling med ersättning"-schemat i detta andra fall är urninnehållet nu statiskt , men denna större enkelhet kompenseras av antagandet att urninnehållet nu är okänt för en observatör. En Bayesiansk analys av observatörens osäkerhet om urnans initiala innehåll kan göras genom att använda ett särskilt val av (konjugerad) tidigare distribution. Anta mer specifikt att en observatör vet att urnan bara innehåller identiska kulor, var och en färgad antingen svart eller vit, men han vet inte det absoluta antalet närvarande kulor eller andelen som är av varje färg. Antag att han har tidigare uppfattningar om dessa okända: för honom är sannolikhetsfördelningen av urninnehållet väl approximerad av någon tidigare fördelning för det totala antalet bollar i urnan, och en betafördelning med parametrar (x,y ) för initial andel av dessa som är svarta, denna andel anses (för honom) vara ungefär oberoende av det totala antalet. Sedan har processen med utfall av en följd av dragningar från urnan (med utbyte men utan duplicering) ungefär samma sannolikhetslag som ovanstående Pólya-schema där det faktiska urninnehållet inte var dolt för honom. Approximationsfelet här relaterar till det faktum att en urna som innehåller ett känt ändligt antal m kulor naturligtvis inte kan ha en exakt beta-fördelad okänd andel svarta kulor, eftersom domänen av möjliga värden för den andelen är begränsad till att vara multiplar av $1/m$ , snarare än att ha full frihet att anta vilket värde som helst i det kontinuerliga enhetsintervallet, precis som en exakt betafördelad proportion. Denna lite informella redogörelse ges av motivationsskäl och kan göras mer matematiskt exakt.

Denna grundläggande Pólya urnmodell har berikats och generaliserats på många sätt.

Utdelningar relaterade till Pólya-urnan

beta-binomial distribution : Fördelningen av antalet lyckade dragningar (försök), t.ex. antal extraheringar av vit boll, givet $n$ drag från en Pólya urna.
Beta-negativ binomialfördelning : Fördelningen av antalet vita kulor som observeras tills ett fast antal svarta kulor observeras.
Dirichlet-multinomialfördelning (även känd som den multivariata Pólya-fördelningen ): Fördelningen över antalet kulor av varje färg, givet ${\displaystyle n},$ hämtas från en Pólya-urna där det finns $k$ olika färger istället för bara två.
Dirichlet negativ multinomial distribution : Fördelningen över antalet kulor av varje färg tills ett fast antal stoppande färgade kulor observeras.
martingaler , beta-binomialfördelningen och betafördelningen : Låt w och b vara antalet vita och svarta kulor initialt i urnan, och $w+n_{w}$ antalet vita kulor för närvarande i urnan efter n drag. Sedan sekvensen av värden ${\frac {w+n_{w}}{w+b+n}}$ för $n=1,2,3,\dots$ är en normaliserad version av Beta-binomialfördelningen . Det är en martingal och konvergerar till betafördelningen när n → ∞.
Dirichlet-process , kinesisk restaurangprocess , Hoppe-urna : Föreställ dig ett modifierat Pólya-urnschema enligt följande. Vi börjar med en urna med $\alpha$ svarta kulor. När du drar en boll från urnan, om vi ritar en svart boll, sätt tillbaka bollen tillsammans med en ny boll av en ny icke-svart färg som genereras slumpmässigt från en enhetlig fördelning över en oändlig uppsättning tillgängliga färger, och överväga den nygenererade färg för att vara "värdet" av dragningen. Annars sätt tillbaka bollen tillsammans med en annan boll av samma färg, som för standard Pólya urnschema. Färgerna i en oändlig sekvens av ritningar från detta modifierade Pólya urnschema följer en kinesisk restaurangprocess . Om vi istället för att generera en ny färg drar ett slumpmässigt värde från en given basfördelning och använder det värdet för att märka bollen, följer etiketterna för en oändlig sekvens av ritningar en Dirichlet-process .
Moran-modell : En urnmodell som används för att modellera genetisk drift i teoretisk populationsgenetik . Detta är mycket likt Pólya-urnmodellen förutom att, förutom att lägga till en ny kula av samma färg, tas en slumpmässigt dragen kula bort från urnan. Antalet kulor i urnan förblir alltså konstant. Fortsatt provtagning leder sedan slutligen till en urna med alla kulor av en färg, sannolikheten för att varje färg är andelen av den färgen i den ursprungliga urnan. Det finns varianter av Moran-modellen som insisterar på att bollen som tas bort från urnan är en annan boll än den som ursprungligen provades i det steget, och varianter som tar bort en boll direkt efter att den nya bollen placerats i urnan, så att den nya bollen är en av bollarna som kan tas bort. Detta gör en liten skillnad i hur lång tid det tar att nå det tillstånd där alla bollar har samma färg. Moran-processen modellerar genetisk drift i en population med överlappande generationer.

Matematisk härledning

Anta att vi har en urna som innehåller $\gamma$ vita kulor och $\alpha$ svarta kulor. Varje gång vi väljer en slumpmässig boll från urnan, registrera dess färg och återför bollen till urnan med en annan boll av samma färg. Varje gång vi drar en ny kula från urnan definierar vi en slumpvariabel som heter $X_{i}$ för kulans färg. $X_{i}=1$ om kulans färg är svart och $X_{i}=0$ annars. Ju fler slumpvariabler före $X_{i}$ som är en, desto mer sannolikt kommer $X_{i}$ också att vara en, eftersom fler svarta kulor har lagts till i urnan. Därför är dessa variabler inte oberoende av varandra, men som visas nedan är de utbytbara.

Antag att $n$ bollar plockas från urnan, och av dessa är $n$ bollar $k$ bollar svarta och $nk$ är vita. Första gången är antalet kulor i urnan ${\displaystyle \gamma +\alpha } ,$ andra gången är det $\gamma +\alpha +1$ och så vidare. Så under i $\displaystyle i}$ -:e gången kommer antalet bollar att vara $\gamma +\alpha +i-1$ . Antag nu att vi har sett alla svarta kulor före de vita kulorna, sannolikheten för denna händelse är helt enkelt: ${\frac {\alpha }{\gamma +\alpha }}\times {\frac {\alpha +1}{\gamma +\alpha +1}}\times \cdots \times {\frac {\alpha +k-1}{\gamma +\alpha +k-1 }}\times {\frac {\gamma }{\gamma +\alpha +k}}\times {\frac {\gamma +1}{\gamma +\alpha +k+1}}\cdots {\frac { \gamma +nk-1}{\gamma +\alpha +n-1}}$

Nu måste vi bevisa att om ordningen på svarta och vita bollar ändras godtyckligt, kommer det inte att ske någon förändring i den slutliga sannolikheten. Som vi kan se på raden ovan kommer bråkens nämnare inte att ändras genom att ändra ordningen för att observera kulorna, ${\displaystyle i}:$ e nämnaren kommer alltid att vara $\gamma +\alpha +i-1$ , eftersom detta är antalet bollar i urnan vid den omgången.

Om vi ser $j$ -th svart kula i omgången $t$ , kommer sannolikheten $X_{t}=1$ att vara lika med ${\displaystyle {\frac {\alpha +j-1}{\gamma +\alpha +t-1}}} , dvs täljaren blir$ lika med $\alpha + j-1$ . Med ett liknande argument kan vi även beräkna sannolikheten för vita bollar. Därför kommer den slutliga sannolikheten att vara lika med följande uttryck:

{\begin{aligned}p(X_{1}=x_{1},X_{2}=x_{2},...,X_{n}=x_{n})&={\frac {\prod _{i=1}^{k}\left(\alpha +i-1\right)\times \prod _{i=1}^{nk}\left(\gamma +i-1\right )}{\prod _{i=1}^{n}\left(\gamma +\alpha +i-1\right)}}\\&={\frac {\left(\alpha +k-1\ höger)!\ gånger \vänster(\gamma +nk-1\höger)!\ gånger \vänster(\alpha +\gamma -1\höger)!}{\vänster(\alpha -1\höger)!\ gånger \ left(\gamma -1\right)!\left(\alpha +\gamma +n-1\right)!}}\end{aligned}}

Denna sannolikhet är inte relaterad till ordningen för att se svarta och vita bollar och beror bara på det totala antalet vita bollar och det totala antalet svarta bollar.

Enligt De Finettis sats måste det finnas en unik tidigarefördelning så att den gemensamma fördelningen av att observera sekvensen är en Bayesiansk blandning av Bernoullis sannolikheter. Det kan visas att denna tidigare fördelning är en betafördelning med parametrarna $\beta \left(\cdot ;\,\alpha ,\,\gamma \right)$ . I De Finettis sats, om $\pi (\cdot )$ med $\beta \left(\cdot ;\,\alpha ,\,\gamma \right)$ får vi föregående ekvation:

{\begin{aligned}p(X_{1}=x_{1},X_{2}=x_{2},...,X_{n}=x_{n})&=\int \ theta ^{\left({\summa _{i=1}^{n}x_{i}}\right)}\times \left(1-\theta \right)^{\left(n-{\summa _{i=1}^{n}x_{i}}\right)}\,\beta \left(\theta ;\alpha ,\,\gamma \right)d\left(\theta \right)\\ &=\int \theta ^{\left({\sum _{i=1}^{n}x_{i}}\right)}\times \left(1-\theta \right)^{\left( n-{\summa _{i=1}^{n}x_{i}}\right)}\,{\dfrac {(\alpha +\gamma -1)!}{(\alpha -1)!\ ,(\gamma -1)!}}\theta ^{\alpha -1}(1-\theta )^{\gamma -1}d\left(\theta \right)\\&=\int \theta ^ {\left({\alpha -1+\sum _{i=1}^{n}x_{i}}\right)}\times \left(1-\theta \right)^{\left(n+\ gamma -1-{\sum _{i=1}^{n}x_{i}}\right)}\,{\dfrac {(\alpha +\gamma -1)!}{(\alpha -1) !\,(\gamma -1)!}}d\left(\theta \right)\\&=\int \theta ^{\left({\alpha +k-1}\right)}\times \left (1-\theta \right)^{\left(nk-1+\gamma \right)}\,{\dfrac {(\alpha +\gamma -1)!}{(\alpha -1)!\, (\gamma -1)!}}d\left(\theta \right)\\&={\dfrac {(\alpha +\gamma -1)!}{(\alpha -1)!\,(\gamma -1)!}}\int \theta ^{\left({\alpha +k-1}\right)}\times \left(1-\theta \right)^{\left(n-k+\gamma - 1\höger)}\,d\left(\theta \right)\\&={\dfrac {(\alpha +\gamma -1)!}{(\alpha -1)!\,(\gamma -1 )!}}{\dfrac {\Gamma (\gamma +nk)\Gamma (\alpha +k)}{\Gamma (\alpha +\gamma +n)}}\\&={\dfrac {\left( \alpha +k-1\höger)!\ gånger \vänster(\gamma +nk-1\höger)!\ gånger \vänster(\alpha +\gamma -1\höger)!}{\vänster(\alpha -1 \right)!\times \left(\gamma -1\right)!\left(\alpha +\gamma +n-1\right)!}}\end{aligned}}

I denna ekvation $k=\sum _{i=1}^{n}x_{i}$ .

Se även

Vidare läsning

F. Alajaji och T. Fuja, "A Communication Channel Modeled on Contagion," IEEE Transactions on Information Theory, Vol. 40, s. 2035–2041, november 1994.
A. Banerjee, P. Burlina och F. Alajaji, "Image Segmentation and Labeling Using the Pólya Urn Model," IEEE Transactions on Image Processing, Vol. 8, nr 9, s. 1243–1253, september 1999.

Bibliografi

NL Johnson och S.Kotz, (1977) "Urnmodeller och deras tillämpning." John Wiley.
Hosam Mahmoud, (2008) "Pólya Urn Models." Chapman och Hall/CRC. ISBN 978-1420059830 .