It looks like the difference in our solutions is due to the fact that D. doesn't recognize that my generating function G is a rational function and so its doing an approximation. However, we can write out the generating function explicitly as a rational function and then compute its derivative and our solutions agree.
H=:+/ @: % @: >: @: i. E=:* (<: + H@:<:) _1 x: JR=: E 100r1 NB. John Randall's solution 10417.7 dif=: -/@,: NB. Polynomial difference ppr=: +//.@(*/) NB. Polynomial product pdi=: 1: }. ] * i.@# NB. Polynomial derivative N=: (!99x),~198$0 NB. Numerator polynomial D=: ppr/ (99#,:1 _99),(1r1,.<:@-@i. 99) NB. Denominator polynomial GR=: N&p. % D&p. NB. The rational generating function dGR=: ( (D ppr (pdi N)) dif N ppr (pdi D) )&p. % ( ppr~ D )&p. NB. The derivative ]JT=: ( * dGR ) 1r100 7263285850977246893522739697584168215280407r697203752297124771645338089353123035568 _1 x: JT 10417.7 JR -: JT 1 I think it should be possible to use D. and avoid working with polynomials directly but I don't really know anything about how D. works. Anyway, the generating function solution is not as short and quick as John Randall's, but it does give us a way to count other things. GR t. 197 NB. There are 0 ways to finish after less than 198 days 0 GR t. 198 NB. There are exactly !99 ways to finish after 198 days (any ordering of 99 prisoners each followed by the counter) 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000 %&(!99) GR t. 197 + i.10 NB. And so on... (divided by the !99 permutations of prisoners) 0 1 14751 1.09445e8 5.44568e11 2.04421e15 6.17495e18 1.56347e22 3.41285e25 6.55628e28 GR 1r100 NB. The probability they will eventually win 1 _1 x: GR 1r100 * 1-1r4000 NB. The probability they will eventually all win, given a daily chance of 1r4000 of someone in the group dying naturally (a reasonable rough estimate I think). 0.0762198 I think the moral here is if you actually find yourself in this situation to go with something closer to Skip's estimate of when you're probably good to assert the claim rather than waiting around for certainty. On Tue, Sep 11, 2012 at 1:04 PM, John Randall <[email protected] > wrote: > I get the expected value 10417.7 days for the 100-prisoner problem. > > The n-prisoner problem has expected value E n , where > > H=:+/ @: % @: >: @: i. > E=:* (<: + H@:<:) > > The time is a sum of two geometric random variables per newly selected > prisoner, summed over all (but one) prisoners. > > Best wishes, > > John > > Pierpaolo Bernardi wrote: > > On Tue, Sep 11, 2012 at 12:06 AM, 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. > > > > Running a simulation, without much thinking, I get around 10400 days. > > > > I'm eager to learn the proper way to compute this number, though. > > > > Cheers > > P. > > ---------------------------------------------------------------------- > > 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
