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. 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
