Author |
Topic: Back To Black (Read 1369 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Back To Black
« on: Aug 24th, 2010, 3:02am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Back To Black
« Reply #1 on: Aug 24th, 2010, 3:14am » |
Quote Modify
|
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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Back To Black
« Reply #2 on: Aug 24th, 2010, 4:01am » |
Quote Modify
|
Yes, a thinly disguised Coupon Collector problem, where withdrawing a black ball is equivalent to collecting a coupon that we already have.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Back To Black
« Reply #3 on: Aug 24th, 2010, 4:31am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Back To Black
« Reply #4 on: Aug 24th, 2010, 5:54pm » |
Quote Modify
|
on Aug 24th, 2010, 4:31am, 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?
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Back To Black
« Reply #5 on: Aug 25th, 2010, 1:10am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Back To Black
« Reply #6 on: Aug 25th, 2010, 5:46am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Back To Black
« Reply #7 on: Aug 25th, 2010, 7:47am » |
Quote Modify
|
on Aug 24th, 2010, 4:31am, 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)?
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Back To Black
« Reply #8 on: Aug 25th, 2010, 7:53am » |
Quote Modify
|
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.)
|
| « Last Edit: Aug 25th, 2010, 7:54am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Back To Black
« Reply #9 on: Aug 25th, 2010, 8:59am » |
Quote Modify
|
on Aug 25th, 2010, 7:53am, 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.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print