<table cellspacing="0" cellpadding="0" border="0" ><tr><td valign="top" style="font: inherit;">Hi all,<br><br>Very nice analysis, Sebastian.<br><br>Thanks,<br><br>Michael<br><br>--- On <b>Sat, 1/30/10, Sebastian Fischer <i><sebf@informatik.uni-kiel.de></i></b> wrote:<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px;"><br>From: Sebastian Fischer <sebf@informatik.uni-kiel.de><br>Subject: Re: [Haskell-cafe] Strange random choice algorithm<br>To: "haskell-cafe Cafe" <haskell-cafe@haskell.org><br>Date: Saturday, January 30, 2010, 6:06 PM<br><br><div class="plainMail"><br>On Jan 30, 2010, at 8:59 PM, michael rice wrote:<br><br>> I'm not sure where I got this PICK function from, and don't understand why it's written as it is, so I wanted to test it for randomness. It seems random enough.<br><br>We can convince ourselves using reason instead of tests. An element is selected by the algorithm
if it is picked and no later element is picked afterwards. It doesn't matter which elements are picked before. The n-th element of the given list replaces the current selection with probability (1/n). Hence, the probability that the n-th element is selected in the end is (1/n)*(1-1/(n+1))*...*(1-1/m) if there are m elements. For example, if there are 9 elements, the probability of selecting the 7th is 1/7 * 7/8 * 8/9 which is 1/9 because the 7 and 8 are canceled out. This happens for all elements and, thus, every element is selected with probability 1/9.<br><br>Anyway,<br><br> pick xs = do n <- randomRIO (1,length xs)<br> return (xs!!(n-1))<br><br>would have been clearer.. It queries the random number generator only once but walks through the list twice.<br><br>Sebastian<br><br><br>--Underestimating the novelty of the future is a time-honored
tradition.<br>(D.G.)<br><br><br><br>_______________________________________________<br>Haskell-Cafe mailing list<br><a ymailto="mailto:Haskell-Cafe@haskell.org" href="/mc/compose?to=Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br></div></blockquote></td></tr></table><br>