[math-fun] Polya urn model
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? Jim Propp
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?
See https://en.m.wikipedia.org/wiki/P%C3%B3lya_urn_model Sorry about neglecting to include the link. Jim On Sunday, September 20, 2015, 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 <javascript:;>> 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 <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
That article is useless. —Dan
On Sep 20, 2015, at 10:30 AM, James Propp <jamespropp@gmail.com> wrote:
See
https://en.m.wikipedia.org/wiki/P%C3%B3lya_urn_model
Sorry about neglecting to include the link.
Jim
On Sunday, September 20, 2015, 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 <javascript:;>> 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?
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?
Please update the wiki page---at the very least, a link to that paper. On Sun, Sep 20, 2015 at 11:09 AM, 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
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
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
I seem to fail to understand: The chances clearly change depending on what happened. E.g., with initially g=1 and r=1, after the first draw we have w.l.o.g. g=2 and r=1 and chances are certainly not fifty-fifty anymore! In other words, in your formulas "r/(r+g) or g/(r+g)" the g and r do change (as far as I understand). Best regards, jj * Dan Asimov <dasimov@earthlink.net> [Sep 27. 2015 08:50]:
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
The probabilities in question means the probabilities *at the start* that the Nth choice will be R or G. (Not the probabilities of picking G or R at the Nth stage *given* some previous sequence of picks on stages 1 through N-1.) —Dan
On Sep 27, 2015, at 10:10 AM, Joerg Arndt <arndt@jjj.de> wrote:
I seem to fail to understand: The chances clearly change depending on what happened. E.g., with initially g=1 and r=1, after the first draw we have w.l.o.g. g=2 and r=1 and chances are certainly not fifty-fifty anymore!
In other words, in your formulas "r/(r+g) or g/(r+g)" the g and r do change (as far as I understand).
Best regards, jj
* Dan Asimov <dasimov@earthlink.net> [Sep 27. 2015 08:50]:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Dan Asimov -
Dan Asimov -
James Propp -
Joerg Arndt -
Mike Stay