For The Love of Computing: How Do We Flip A Billion Coins in a Fair Way?

For The Love of Computing: How Do We Flip A Billion Coins in a Fair Way?

So let’s say we have one billion people who are in a competition. We have a single toss of the coin, and if you match it, you continue. If not it does not match, then you are out of the competition. How many tosses will it take to get a winner (on average)?

It think it would only take … 30 rounds (I asked someone early and they said one trillion!).

So from one billion people, we would have 30 tosses of the coin, and we would (on average) have a winner. Do you agree with me?

So how are we going to build a computer that is going to create one billion random numbers quickly. Well, in 2016, Xoroshiro128+ came along, and has sub-nano-second times for each random number generated. We could thus generate one billion random numbers in less than a second. But how do we just to a bit flip? Well we just mask of the least significant bit.

So let’s take two seed values, and generate the first 10 random values and the first 50 tosses:

import sys

val1=54253124354024L
val2=5395042653908L

def bin2chr(data):
	result = ''
	
	while data:
		char = data & 0xff
		result += chr(char)
		data >>= 8
	
	return result

class Xoroshiro128Plus(object):
	def __init__(self, seed):
		self.seed = seed
	
	@staticmethod
	def rotl(x, k):
		return ((x << k) & 0xffffffffffffffff) | (x >> 64 - k)
	
	def next(self):
		s0 = self.seed[0]
		s1 = self.seed[1]

		result = (s0 + s1) & 0xffffffffffffffff
		
		s1 ^= s0

		self.seed[0] = self.rotl(s0, 55) ^ s1 ^ ((s1 << 14) & 0xffffffffffffffff)
		self.seed[1] = self.rotl(s1, 36)
		
		return result

print "Seed 1:\t",val1
print "Seed 2:\t",val2
print

generator = Xoroshiro128Plus([val1, val2]) 
for i in range(4):
	val=generator.next()
	print hex(val),'\t',

print(repr(bin2chr(val)))

The run gives:

Seed 1:    54253124354024
Seed 2:    5395042653908

0 0x363febce56bcL         '\xbcV\xce\xeb?6'
1 0xb44a630c2a0b0f01L     '\x01\x0f\x0b*\x0ccJ\xb4'
2 0x35b971bef18473e6L     '\xe6s\x84\xf1\xbeq\xb95'
3 0x9497b673f320d89bL     '\x9b\xd8 \xf3s\xb6\x97\x94'
4 0xd07401ef48e22e0L     '\xe0"\x8e\xf4\x1e@\x07\r'
5 0xdcc0618d77a1ce2bL     '+\xce\xa1w\x8da\xc0\xdc'
6 0xd719917970062c09L     '\t,\x06py\x91\x19\xd7'
7 0xacd2ed2c5461b336L     '6\xb3aT,\xed\xd2\xac'
8 0xc619e5ac2efae9e7L     '\xe7\xe9\xfa.\xac\xe5\x19\xc6'
9 0x4bfbdf8610735319L     '\x19Ss\x10\x86\xdf\xfbK'

Coin flip (60)
H T H T H T T H T T T T T H T T H H H H H T T H T H T T T H T T T H T T H H H T H T H T H T T T H T T T H T H T H H T H
Heads:    26

Tails:    34

We can see we have 26 heads and 34 tails, which isn’t 50/50, but it will start to tend to a 50/50 split once we have enough tosses. Sample run here: