Thanks, Dan. I hadn't checked the Wikipedia page when I posted the link. A better reference is Levin, Peres, and Wilmer's book "Markov Chains and Mixing Times", starting on page 25 (or see page 41 of the PDF: http://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf). Jim On Sun, Sep 20, 2015 at 2:09 PM, Dan Asimov <dasimov@earthlink.net> wrote:
I just skimmed an online paper that appears to describe the Polya urn model, as follows:
Start with an urn containing r red balls and g green balls.
At the nth stage, n = 1,2,3,..., pick a ball from the urn at random.
Then put the ball back in the urn and *add* to the urn one more ball of the same color.
It's surprising but easy to check that at each stage, the probability of picking a red or green ball is r/(r+g) or g/(r+g), respectively — the same as on the first stage.
Hence, the probabilities for the outcome (ball color) at the (n+1)st stage are independent of anything that occurred at previous stages. This is the defining property of a "martingale", and so the Polya urn model is a martingale.
—Dan
On Sep 20, 2015, at 9:13 AM, Dan Asimov <dasimov@earthlink.net> wrote:
Would anyone please be so kind as to say what the Polya urn model is?
(Not Jim, because he obviously doesn't want to bother.)
—Dan
On Sep 20, 2015, at 4:35 AM, James Propp <jamespropp@gmail.com> wrote:
Does anyone have a pointer to the cute way of seeing that the Polya urn model gives rise to the uniform distribution at the nth level, by contriving a uniformly random permutation of 1,2,...,n whose first (or last) element corresponds to the number of white-vs.-black balls at the end?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun