From: Ezra Zygmuntowicz <ezra@...>
Date: 2005-07-17T02:39:48+09:00
Subject: Re: [QUIZ] Sampling (#39)

--Apple-Mail-4--653025233
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	delsp=yes;
	format=flowed


> <snip>
>> 999999621
>>
> 999999800
>
>> 999999877
>>
> 1000000000
>
> See? One number per 200-numbers interval. Every time[1]. This hints at
> a wrong implementation.
>
> I caught this because I had the same idea first :)
>
> [1]
>
> Unless I'm mistaken, in the 5e6-from-1e9 sampling, the probability
> that a sampling contains exactly one number from a given 200-numbers
> interval is 200.0*(1/200)*(199.0/200)**199 = 0.3688. The probability
> that this happens for 20 such 200-numbers intervals is
> 0.3688**20 = 2.1e-09.
>
Yep you caught me Olaf ;-) It looks like quite a few people stumbled  
upon this 'pseudo' random sampling technique. I'm working on a true  
implementation of this but so far it take __much__ longer than my  
naive impl. Looking at the rules though.. I'm not certain that my  
fast technique is illegal. I guess we will wait until tomorrow and  
let the quiz master decide ;-)

-Ezra Zygmuntowicz
WebMaster
Yakima Herald-Republic Newspaper
ezra@yakima-herald.com
509-577-7732


--Apple-Mail-4--653025233--