wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> medium >> Back To Black
(Message started by: ThudanBlunder on Aug 24th, 2010, 3:02am)

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:
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.

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:
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.


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:
As I said, a lot of the second phase will be done before the first phase has finished.

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