Skip to content

Instantly share code, notes, and snippets.

@YuvalFilmus YuvalFilmus/uniform.py
Last active Jul 26, 2018

Embed
What would you like to do?
Generating uniform random bits for iid binary source
class bitstream:
def __init__(self, emit):
self.emit = emit
self.bits = []
self.daughters = [None, None]
def daughter(self, num):
if self.daughters[num] is None:
self.daughters[num] = bitstream(self.emit)
return self.daughters[num]
def send(self, bit):
self.bits.append(bit)
if len(self.bits) < 2:
return
a, b = self.bits[0], self.bits[1]
self.bits = []
if a == b:
self.daughter(0).send(a)
self.daughter(1).send(0)
else:
self.emit(a)
self.daughter(1).send(1)
import random
def test(p, n, seed = None):
output = []
random.seed(seed)
bs = bitstream(lambda x: output.append(x))
for _ in xrange(n):
bs.send(int(random.random() < p))
return output
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.