README.md

Copied from https://calaganne.blogspot.com/2018/11/consensus-by-avalanche.html by Hasan Karahan

Example run

$ ./avalanche.py --population=100000 --max-sample=10 --max-round=13

# {"population": 100000, "max_sample": 10, "max_round": 13}
4.988699999999999801e-01 4.966800000000000104e-01 4.984000000000000097e-01 5.022699999999999942e-01 5.014100000000000223e-01 5.012299999999999534e-01 5.022900000000000142e-01 5.009400000000000519e-01 5.020000000000000018e-01 5.022199999999999998e-01
4.988299999999999956e-01 4.967199999999999949e-01 4.961999999999999744e-01 5.048200000000000465e-01 5.040599999999999525e-01 5.027399999999999647e-01 5.079200000000000381e-01 5.044100000000000250e-01 5.049900000000000500e-01 5.068599999999999772e-01
5.008399999999999519e-01 4.946300000000000141e-01 4.975700000000000123e-01 5.091999999999999860e-01 5.078399999999999581e-01 5.056699999999999529e-01 5.165199999999999791e-01 5.125600000000000156e-01 5.125399999999999956e-01 5.180099999999999705e-01
5.001700000000000035e-01 4.928899999999999948e-01 4.971099999999999963e-01 5.179200000000000470e-01 5.152900000000000258e-01 5.101200000000000179e-01 5.370099999999999874e-01 5.320200000000000484e-01 5.312400000000000455e-01 5.497100000000000319e-01
4.999100000000000210e-01 4.890999999999999792e-01 4.946800000000000086e-01 5.317199999999999704e-01 5.306300000000000461e-01 5.204100000000000392e-01 5.826999999999999957e-01 5.774500000000000188e-01 5.754700000000000371e-01 6.302799999999999514e-01
5.019000000000000128e-01 4.824499999999999900e-01 4.934000000000000052e-01 5.604200000000000292e-01 5.594000000000000083e-01 5.454499999999999904e-01 6.734200000000000186e-01 6.862800000000000011e-01 6.799100000000000144e-01 8.149999999999999467e-01
5.020700000000000163e-01 4.750900000000000123e-01 4.914999999999999925e-01 6.127299999999999969e-01 6.083399999999999919e-01 5.992399999999999949e-01 8.385000000000000231e-01 8.855800000000000338e-01 8.746000000000000441e-01 9.923300000000000454e-01
4.981400000000000272e-01 4.623099999999999987e-01 4.866599999999999815e-01 7.039199999999999902e-01 6.959999999999999520e-01 7.061199999999999699e-01 9.845000000000000417e-01 9.983600000000000252e-01 9.976399999999999713e-01 1.000000000000000000e+00
5.013100000000000334e-01 4.423199999999999910e-01 4.833500000000000019e-01 8.430499999999999661e-01 8.304599999999999760e-01 8.831599999999999451e-01 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00
5.021499999999999853e-01 4.149599999999999955e-01 4.769399999999999751e-01 9.706099999999999728e-01 9.632399999999999851e-01 9.950499999999999901e-01 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00
5.045800000000000285e-01 3.738000000000000211e-01 4.657899999999999818e-01 9.998099999999999765e-01 9.995000000000000551e-01 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00
5.050700000000000189e-01 3.149700000000000277e-01 4.497700000000000031e-01 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00
5.029900000000000482e-01 2.368300000000000127e-01 4.264899999999999802e-01 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00 1.000000000000000000e+00

avalanche.py

#!/usr/bin/env python

from typing import Dict

from numpy.random import choice
from numpy.random import randint

from numpy import array
from numpy import maximum
from numpy import round
from numpy import zeros

from matplotlib import pyplot as pp

import argparse
import json
import numpy
import sys

def avalanche(
    population_size: int, max_sample: int, max_round: int
) -> array:

    """
    Simulates for the provided number of `max_round`, the given
    `population_size` and `max_sample` the *avalanche* process,
    where we keep the `population_size` fixed, but consider all
    sample sizes from `1` until `max_sample` (inclusive);  then
    return a matrix (array) `m` for each round and sample size.

    While technically it is not required to use the matrix `m`,
    and rely *only* on the array `p`  (to successfully simulate
    the avalanche process), it is used for book-keeping helping
    later-on to generate plots of the entire process.
    """

    m = zeros(shape=(max_round, max_sample))
    for s in range(max_sample):

        p = population(size=population_size)
        for r in range(max_round):

            m[r, s] = p.sum() / population_size
            p = resample(p, s + 1)

    return m

def population(size: int) -> array:

    """
    Returns a uniformly sampled population for the given `size`
    where a value of `0` represents *yellow* and a value of `1`
    *red* cards.
    """

    return randint(0, 2, size=size)

def resample(p: array, size: int) -> array:

    """
    Make a random choice of a sample `size` (from a given array
    `p`) for *each* element within the array `p`. Then for each
    sample calculate, if the majority of the sample indicates a
    *red* (i.e. `1`) or a *yellow* (i.e. `0`) card. However, if
    there is *no* majority (i.e. a tie) within the sample, then
    do nothing.

    Note that the returned array has the same size as the array
    `p`: It represents a state update of `p`, where elements of
    the array have switched their "opinion" with respect to the
    majority they have sampled.
    """

    ps = choice(p, size=(size, p.size)).sum(axis=0)
    eq, gt = ps == size / 2.0, ps > size / 2.0

    return p * eq + gt

if __name__ == '__main__':

    parser = argparse.ArgumentParser(
        description='Produces the Avalanche Matrix '
                    '[rounds x max.sample-size]')

    parser.add_argument('-p', '--population',
        type=int, help='population size '
        '(default: %(default)s)', default=100000)
    parser.add_argument('-r', '--max-round',
        type=int, help='maximum number of rounds '
        '(default: %(default)s)', default=13)
    parser.add_argument('-s', '--max-sample',
        type=int, help='maximum sample size '
        '(default: %(default)s)', default=10)

    args = parser.parse_args()

    m = avalanche(
        args.population, args.max_sample, args.max_round)
    numpy.savetxt(
        sys.stdout, m, header=json.dumps(vars(args)))