average.py

1from fractions import Fraction2from collections import defaultdict3from itertools import product4from .bang import corners, code_to_filled5from .complexity import sensitivity_at67# AVERAGE-CASE COMPLEXITY OVER THE FAMILY - Q3, ANALYTIC VIA THE UNIFORM MEASURE89def point_sensitivity_law(dimension):10    from math import comb11    return {k: Fraction(comb(dimension, k), 2 ** dimension) for k in range(dimension + 1)}1213def expected_average_sensitivity(dimension):14    return Fraction(dimension, 2)1516def variance_average_sensitivity(dimension):17    return Fraction(dimension, 2 ** (dimension + 1))1819def average_sensitivity(filled, cells):20    D = len(cells[0])21    total = 022    for x in cells:23        total += sensitivity_at(filled, cells, x)24    return Fraction(total, 2 ** D)2526def exact_average_sensitivity_moments(dimension):27    cells = corners(dimension)28    total = 1 << (1 << dimension)29    s_sum = Fraction(0)30    s2_sum = Fraction(0)31    for code in range(total):32        filled = code_to_filled(code, cells)33        I = average_sensitivity(filled, cells)34        s_sum += I35        s2_sum += I * I36    mean = s_sum / total37    var = s2_sum / total - mean * mean38    return mean, var3940def exact_point_sensitivity_law(dimension):41    cells = corners(dimension)42    index = {c: i for i, c in enumerate(cells)}43    total = 1 << (1 << dimension)44    x0 = cells[0]45    neighbours = [tuple(x0[j] ^ (1 if j == a else 0) for j in range(dimension)) for a in range(dimension)]46    dist = defaultdict(int)47    for code in range(total):48        fx = (code >> index[x0]) & 149        s = sum(1 for nb in neighbours if ((code >> index[nb]) & 1) != fx)50        dist[s] += 151    return {k: Fraction(v, total) for k, v in dist.items()}5253def orbit_weighted_distribution(rows, measure, dimension):54    total = 1 << (1 << dimension)55    dist = defaultdict(Fraction)56    for row in rows:57        dist[row[measure]] += Fraction(row["orbit_size"], total)58    return dict(dist)