From: "Mauricio Fernández" <batsman.geo@...>
Date: 2004-03-07T20:51:50+09:00
Subject: Re: random range

On Sun, Mar 07, 2004 at 04:49:39PM +0900, Charles Comstock wrote:
> >
> >No Enumerable#size.  Try:
> >
> >module Enumerable
> >    ## Return a random element, or nil if empty.
> >    def rand
> >        i = 1
> >        ret = nil
> >        each do |el|
> >            if Kernel.rand(i) == 0
> >                ret = el
> >            end
> >            i += 1
> >        end
> >        return ret
> >    end
> >end
> >
> >
> 
> Umm I don't think that is a uniform distribution, not to mention the 

It *is* uniform...

> fact that you don't break out of the each if it succeeds.

... precisely because he doesn't break out of the each if it succeeds.

S(i): element i is taken in ret = el (i.e. Kernel.rand(i) == 0)
AND: intersection
PI: big PI (product)
N: number of elements in the Enumerable (if infinite, rand would never
return)

P(ret == el(i) at the end) = P(S(i) AND (for all N >= j > i NOT S(j)))
== { they're independent if we ignore the fact that this is a PRNG } ==
= P(S(i)) * P(for all j > i NOT (S(j))) == { S(j) and S(j+1) indep. } ==
= 1/i * PI(1-P(S(j)), j = i+1 .. N) = 
= 1/i * (1-1/(i+1)) * (1-1/(i+2)) * ... * (1-1/(N)) =
= 1/i * i/(i+1) * (i+1)/(i+2) * ... * (N-1)/N = 
= 1/i * i / N = 1 / N


-- 
Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

Netscape is not a newsreader, and probably never shall be.
	-- Tom Christiansen