Jordan
I think 1e6 is much too high. The problem seems to be equivalent to drawing
from a bag of 100 uniquely-numbered balls (0-99) with replacement. Then the
question is: how many draws on average does it take to see every number?
A quick modelling of this process:
$~.?100$100 NB. how many unique balls in 100 random draws, with
replacement ?
65
$~.?100$100 NB. Try a couple more times.
63
$~.?100$100
62
$~.?300$100 NB. Try 300 draws with replacement.
94
$~.?300$100
99
$~.?300$100
92
$~.?500$100 NB. Try 500 draws with replacement.
98
$~.?500$100
100
$~.?500$100
97
$~.?500$100
100
$~.?700$100 NB. Try 700 draws with replacement.
100
$~.?700$100
100
$~.?700$100
100
So it looks like making somewhere around 500 random draws on average, will
let the drawer see all 100 numbers. So it will typically be a couple of
years before the prisoners can be sure of their fate.
Skip
On Mon, Sep 10, 2012 at 10:32 PM, Jordan Tirrell <[email protected]>wrote:
> I got an expected number of rounds around 1e6. It seems a bit high but I
> think it might be right. So if they want to be 100% they'll die of natural
> causes while waiting.
>
> I wasn't on the forums 5 years ago but its certainly a good problem.
>
>
>
> On Mon, Sep 10, 2012 at 6:06 PM, Roger Hui <[email protected]
> >wrote:
>
> > V. good.
> >
> > A related question for the 100 Prisoners problem, is the expected
> > number of rounds before the prisoners go free, if each prisoner has
> > the same chance of being picked in each round.
> >
> > Did you solve the 88 Hats problem when it was posed here 5 years ago?
> >
>
--
Skip Cave
Cave Consulting LLC
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
