On Tue, Sep 11, 2012 at 6:31 PM, Jordan Tirrell <[email protected]> wrote:
> So after looking back at my computation, I noticed that I had forgotten a
> final step: dividing by 100. Now it looks like we're all in the 1e4
> ballpark.
>
> My computation is pretty short to write, but it will be hard to understand
> if you aren't familiar with generating functions.
>
> G=: (1+i.99)&(*/@:((**:)%(1-99*])*1-*))
> (*(G D. 1)) %100
> 10423.2
>
> Pierpaolo's estimate is incredibly close to my computation.
8^)
Here's what I get with my simulation (alas, not written in J):
> (test 100 ; number of prisoners
10000 ; number of experiments
)
10418.0462 ; average number of days
7222.0 ; minimum number of days occurred
14522.0 ; maximum = = = =
Cheers
P.
>
>
>
>
>
> On Tue, Sep 11, 2012 at 12:09 PM, Roger Hui <[email protected]>wrote:
>
>> 100 Prisoners Simulation: Assume without loss of generality that prisoner
>> 0 is the designated "counter". A "round" is a group of selections (one per
>> day) with prisoner 0 as the fret. Thus:
>>
>> part=: (0&= <;._2 ]) @ (?@$&100)
>> t=: part 1e6
>> $t
>> 10224
>> #&> t
>> 65 81 113 2 128 396 100 31 136 328 50 3 4 57 75 146 0 56 73 213 24 ...
>>
>> So part n does simulation on n days partitioned into rounds.
>>
>> If the first prisoner of round k has not turned on a light before, then
>> that's a good round; if he has, then remove from round k all the prisoners
>> that have turned on a light before, and repeat. This computation can be
>> coded as follows:
>>
>> f=: 3 : 0
>> whilst. -.*./(}.i.100) e. k{.m do.
>> m=. {.&>y
>> k=. ((0=m)+.~:m) i. 0
>> y=. (<(>k{y)-.k{.m) k}y
>> end.
>> k
>> )
>>
>> k , k+#;k{.t [ k=: f t=: part 1e6
>> 102 11453
>>
>> So in this simulation, 102 rounds totalling 11453 days are required. Again:
>>
>> k , k+#;k{.t [ k=: f t=: part 1e6
>> 105 10977
>> k , k+#;k{.t [ k=: f t=: part 1e6
>> 109 9949
>> k , k+#;k{.t [ k=: f t=: part 1e6
>> 100 9200
>> k , k+#;k{.t [ k=: f t=: part 1e6
>> 105 11130
>> k , k+#;k{.t [ k=: f t=: part 1e6
>> 99 9274
>>
>> Looks like less than 1e6 days. (Hmm, the last one looks rather suspicious,
>> so there may be a bug in my logic and/or coding :-)
>>
>>
>>
>> On Tue, Sep 11, 2012 at 8:03 AM, Roger Hui <[email protected]
>> >wrote:
>>
>> > You need the random draw to pick a prisoner who hasn't been, and then for
>> > the random draw to pick the designated "counter" prisoner.
>> >
>> >
>> >
>> > On Tue, Sep 11, 2012 at 7:52 AM, Skip Cave <[email protected]
>> >wrote:
>> >
>> >> 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
>> >>
>> >
>> >
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
