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
