From: Mark Hubbart <discord@...>
Date: 2004-03-08T04:03:22+09:00
Subject: Re: random range


On Mar 7, 2004, at 3:51 AM, Mauricio Fern�ndez wrote:

> 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

or, for those who (like me) have no idea what the above means:

    >> 10000.times{b[a.rand]+=1}
   => 10000
    >> 10000.times{b[a.rand]+=1}
   => 10000
    >> b
   => [2055, 1959, 1934, 2002, 1983, 1931, 2005, 2050, 2057, 2024]

looks good to me!

--Mark


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