Sort 5 Discussions, By:
Please Login in order to post a comment
This was a bit tricky! I wasted some time trying to solve it in terms of probabilities when the simpler approach is to simply think about expected values. Remember, the expected wait time for an event is the reciprocal of its probability: if something has a 1/3 chance of occuring each second, you can expect to wait 3 seconds for it to happen. Sounds kind of obvious but maybe it will help someone.
Makes total sense, thanks, this clarified it.
This is known as the Coupon collector problem.
The fun part about this problem is realizing you HAVE to do it mathematically. I tried about 3 other standard methods before I realized I'd have to research the problem more.
It's actually very fun and rather easy. I recommend pencil and paper, try to get as far as possible and then go read about the Coupon Collectors problem. After that it's trivial.
this is really just math so sit down with pen and pencil
and figure it out.
In case you need some hints, consider this relation:
expectedTime cntPoped cntUnpoped =
(cntPoped / (cntPoped + cntUnpoped)) * (1 + expectedTime cntPoped cntUnpoped)
+ (cntUnpoped / (cntPoped + cntUnpoped)) * (1 + expectedTime (cntPoped + 1) (cntUnpoped - 1))
now of course this will not work as the recursion never stops - here comes the math (solve x = a*(1+x) + y for x and compare)
x = a*(1+x) + y
the rest should be really easy
What is x, y and a in your case ?
If we have 2 bubbles, why expected number of steps = 3? Minimum is 4:
Seems I don't understand the problem. Can somebody explain, please?
No more comments