[tpm] Golf Challenge for the November 2009 Meeting.

[Abram Hindle]

http://churchturing.org/x/golf-20091126.tar.gz
http://churchturing.org/x/golf-20091126/

The tar ball contains the golf testing framework (uses R) and the golf
challenge + our solutions first.pl and seneca.sh

Write a perl script to select 1 element from a stream of unknown length
uniformly randomly. The algorithm usually is read an element in, choose
a number between 0 and 1, if it is less than 1/n then keep that new
element, otherwise keep your old one. So first element is 1/1 to keep,
second element is 1/2 to keep, third element is 1/3 to keep. Via
induction you can work it out that this algorithm is uniformly random.

intuition:
n = 1
1/n = 1
100% chance of choosing 1

n = 2
step 1, a_1 is chosen
step 2, 1/2 chance a_2 is chosen
	1/2 chance a_2 is not chosen
		1/2 chance a_1 is chosen

n = 3
step 1, a_1 is chosen
step 2, 1/2 chance a_2 is chosen
	1/2 chance a_2 is not chosen
		1/2 chance a_1 is chosen
step 3, 1/3 chance a_3 is chosen
	2/3 chance a_3 not chosen
		1/2 chance a_1 1/2*2/3 = 1/3
		1/2 chance a_2 1/2*2/3 = 1/3

n = 4
step 1, a_1 is chosen
step 2, 1/2 chance a_2 is chosen
	1/2 chance a_2 is not chosen
		1/2 chance a_1 is chosen
step 3, 1/3 chance a_3 is chosen
	2/3 chance a_3 not chosen
		1/2 chance a_1 1/2*2/3 = 1/3
		1/2 chance a_2 1/2*2/3 = 1/3
step 4, 1/4 chance a_4 is chosen
	3/4 chance a_4 is not chosen
		1/3 chance a_0 1/3 * 3/4 = 1/4
		1/3 chance a_1 1/3 * 3/4 = 1/4
		1/3 chance a_2 1/3 * 3/4 = 1/4

Notice how the numerator and denominators cancel?
So now we say this p(a_x) = 1/n for all x in 1..n
Our base case was demonstrated above
p_n+1(a_n+1) = 1/(n+1)
p_n+1(a_{1..n}) = p_n(a_{1..n}) * n/n+1
p_n+1(a_{1..n}) = 1/n * n / n+1 = 1/n+1

We've shown via induction that p(a_x) = 1/n for all x in 1..n holds for
n and n+1.

[]

Therefore the chance the first element was chosen was
1/1 * 1/2 * 2/3 * 3/4 * ... * n-2/n-1 * n-1/n * n/n+1
We can cancel all of those numerators and denominators
we get 1/n


More information here:

http://kw.pm.org/wiki/index.cgi?GolfChallenge

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 260 bytes
Desc: OpenPGP digital signature
URL: <http://mail.pm.org/pipermail/toronto-pm/attachments/20091126/f5e06b75/attachment.bin>