py-aiger-coins 0.1.0

Library for creating circuits that encode discrete distributions.

py-aiger-coins

Library for creating circuits that encode discrete distributions. The name comes from the random bit model of drawing from discrete distributions using coin flips.

Install

To install this library run:

$ pip install py-aiger-coins

Usage

This tutorial assumes familiarity with py-aiger and py-aiger-bdd. py-aiger should automatically be installed with py-aiger-coins and py-aiger-bdd can be installed via:

$ pip install py-aiger-bdd

Biased Coins

We start by encoding a biased coin and computing its bias. The coin will be encoded as two circuits top and bot such that bias = #top / #bot, where # indicates model counting.

from fractions import Fraction

import aiger
import aiger_coins
from aiger_bdd import count

prob = Fraction(1, 3)
top, bot = aiger_coins.coin(prob)
top, bot = aiger_coins.coin((1, 3))  # or just use a tuple.

assert Fraction(count(top), count(bot)) == prob

Distributions on discrete sets

We now illustrate how to create a set of mutually exclusive coins that represent distribution over a finite set. Namely, coordinate i is 1 iff the ith element of the set is drawn. For example, a three sided dice can be encoded with:

circ, bot = aiger_coins.mutex_coins(
    {'x': (1, 6), 'y': (3, 6), 'z': (2, 6)}
)

Now to ask what the probability of drawing x or y is, one can simply feed it into a circuit that performs that test!

test = aiger.or_gate(['x', 'y']) | aiger.sink(['z'])
assert Fraction(count(circ >> test), count(bot)) == Fraction(2, 3)

Binomial Distributions

py-aiger-coins also supports encoding Binomial distributions. There are two options for encoding, 1-hot encoding which is a format similar to that in the discrete sets section and as an unsigned integers. The following snippet shows how the counts correspond to entries in Pascal's triangle.

x = binomial(6, use_1hot=False)
y = binomial(6, use_1hot=True)
for i, v in enumerate([1, 6, 15, 20, 15, 6, 1]):
    assert v == count(x == i)
    assert v == count(y == (1 << i))

Dividing by 2**n (64 in the example above) results in the probabilities of a Bionomial Distribution.