|
||
Title: Back To Black Post by ThudanBlunder on Aug 24th, 2010, 3:02am A bag initially contains n red balls. Balls are repeatedly withdraw and replaced. If the chosen ball is red we replace it with a black ball, and if it is black we return it to the bag. What is the expected number of withdrawals with replacement before all the balls in the bag are black? |
||
Title: Re: Back To Black Post by towr on Aug 24th, 2010, 3:14am [hide]AN(0) = 0 AN(R) = 1 + (N-R)/N*AN(R) + R/N AN(R-1) = N/R + AN(R-1) = Sum R=1..N N/R = N*H(N)[/hide] |
||
Title: Re: Back To Black Post by ThudanBlunder on Aug 24th, 2010, 4:01am [hide]Yes, a thinly disguised [/hide]Coupon Collector (http://demonstrations.wolfram.com/CouponCollectorProblem)[hide] problem, where withdrawing a black ball is equivalent to collecting a coupon that we already have.[/hide] |
||
Title: Re: Back To Black Post by towr on Aug 24th, 2010, 4:31am I've been thinking about if you went from red to green and then black (or even more steps in between), but it doesn't seem to yield a similarly nice answer. |
||
Title: Re: Back To Black Post by ThudanBlunder on Aug 24th, 2010, 5:54pm on 08/24/10 at 04:31:22, towr wrote:
If we replace withdrawn red balls only with the required colour (first green, then black), the mean and variance are just double the previous answer, right? |
||
Title: Re: Back To Black Post by towr on Aug 25th, 2010, 1:10am Perhaps I didn't explain it well. I meant that if you pick a red ball you replace it with green, if you pick a green ball replace it with black, if you pick a black ball simply place it back. So it's not converting all reds to green first in one stage, and then converting all greens to black in a second stage. Getting rid of the reds will take equally long as before, but in the meantime many greens will also already be converted to black, so getting from no-reds to all-black takes much less time. |
||
Title: Re: Back To Black Post by rmsgrey on Aug 25th, 2010, 5:46am I expect research has been done on extending the collector problem to collecting multiple full sets - for example, in the cardgame Magic: the Gathering, a "playset" of a given expansion consists of 4 copies of each card (because there are multiple rarities of card, and the more common rarities are decidedly not independently distributed in the random packs, it's probably sufficient to collect a playset of the rarest rarity and assume that there's a negligible chance of missing anything more common) which would be equivalent to using 5 colours - red, green, white, blue and black would seem to be thematically appropriate. |
||
Title: Re: Back To Black Post by ThudanBlunder on Aug 25th, 2010, 7:47am on 08/24/10 at 04:31:22, towr wrote:
Isn't it = 2*(Expected number for collecting 2 sets of coupons)? |
||
Title: Re: Back To Black Post by towr on Aug 25th, 2010, 7:53am No it's not. As I said, a lot of the second phase will be done before the first phase has finished. N single double 1 1.0 2.0 2 3.0 5.5 3 5.5 9.63888888889 4 8.33333333333 14.1886574074 5 11.4166666667 19.0413606481 6 14.7 24.1338691975 7 18.15 29.4247410361 8 21.7428571429 34.8846868232 9 25.4607142857 40.4919121909 10 29.2896825397 46.2295706394 Around 165, the ratio of double to single is around 1.38. So it costs just 38% more time. (At that point recursion depth is exceeded, and I can't be bothered to write an efficient table based version at the moment.) |
||
Title: Re: Back To Black Post by ThudanBlunder on Aug 25th, 2010, 8:59am on 08/25/10 at 07:53:47, towr wrote:
Believe it or not, my two previous suggestions were (meant to be) different. |
||
Title: Re: Back To Black Post by towr on Aug 25th, 2010, 9:42am It's equivalent to collecting two identical sets of N coupons (at the same time). (So no need to double the expected number of coupons.) I don't see how that gets me any further, though. Though there is a bit about this extension of the problem at http://en.wikipedia.org/wiki/Coupon_collector%27s_problem#Extensions_and_generalizations [edit] http://www.jstor.org/stable/2308930 I think the maths on this is a bit out of my league.. [/edit] |
||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |