Jacob Fugal wrote:
Woah woah woah. You're not using the technique that was advocated.
What Hans and Jason were referring to is flip *all* the coins. If the
full result is outside the range, reflip *all* the coins. In your
implementation, you only reflip the most recent coin when the result
is out of bounds. There's a big difference.
Exactly. Allow me to quote myself: "Or do you mean a way without a
computer? In that case grab lg(N) people and have them each flip a coin,
repeat if you get a number bigger than N. Expected number of trials is
between 1 and 2."
From a practical standpoint, the probability of having to reflip more
than a few times depends on the number of people in the room. If you
have (2^N)+1 people in the room, your chances of having to reflip are
the worst at 0.5 - 1/2^(N+1). For most N, this is pretty close to 50%
and you may have to reflip several times to get a valid winner. On the
other hand, if you have (2^N)-1 people in the room, your chances of
having to reflip are very low, in which case this technique works very
well.
Which actually translates to an expected value of 2 flips before you get
a usable number.
I wrote a little empirical proof to go along with your theory. Here's
what it looks like:
$ ./flips.rb 17
0: ***********************************************************
1: ***********************************************************
2: ***********************************************************
3: ***********************************************************
4: **********************************************************
5: ***********************************************************
6: ***********************************************************
7: ***********************************************************
8: ***********************************************************
9: ***********************************************************
10: **********************************************************
11: ***********************************************************
12: ***********************************************************
13: ***********************************************************
14: ***********************************************************
15: ***********************************************************
16: **********************************************************
Average reflips per prize: 0.880561
Script is attached.
--
Hans Fugal ; http://hans.fugal.net
There's nothing remarkable about it. All one has to do is hit the
right keys at the right time and the instrument plays itself.
-- Johann Sebastian Bach
#!/usr/bin/ruby
def log2(n)
Math.log(n) / Math.log(2)
end
def flip(n)
# rather than simulate log2(n) coin flips, let's agree that flipping log2(n)
# fair coins to represent a binary number gives us a uniformly distributed
# random number between 0 and m-1, where m is the smallest power of 2 greater
# than or equal to n.
#
# The überparanoid can implement individual coin flips here
m = 2**(log2(n).ceil)
rand(m)
end
# Repetitions
Z = 1000000
if ARGV.empty?
puts "Give me n, fool."
exit 1
end
n = ARGV.shift.to_i
hist = Array.new(n, 0)
reflips_tot = 0
Z.times do |i|
reflips = -1
begin
x = flip(n)
reflips += 1
end until x < n
reflips_tot += reflips
hist[x] += 1
end
hist.each_with_index {|x,i|
h = 60.0 / hist.max
puts "%3d: %s" % [i, "*" * (x*h)]
}
puts "Average reflips per prize: #{reflips_tot.to_f / Z}"
/*
PLUG: http://plug.org, #utah on irc.freenode.net
Unsubscribe: http://plug.org/mailman/options/plug
Don't fear the penguin.
*/
