import numpy
import math

def ncr(n, r):
    return math.comb(n, r)

def getProb(u, p, epsilon):
    r = math.ceil((p + epsilon) * u)
    sum = 0
    for i in range(r, u + 1):
        sum += ncr(u, i) * p**i * (1 - p)**(u - i)
    return sum

def getProbUBHoeffding(u, p, epsilon):
    return numpy.exp(-2 * u * epsilon * epsilon)

def getProbUBKL(u, p, epsilon):
    kl = (p + epsilon) * numpy.log((p + epsilon) / p) + (1 - p - epsilon) * numpy.log((1 - p - epsilon) / (1 - p))
    return numpy.exp(-1 * u * kl)

u = 1000
p = 0.3
epsilon = 0.15

trueProb = getProb(u, p, epsilon)
hoeffUB = getProbUBHoeffding(u, p, epsilon)
klUB = getProbUBKL(u, p, epsilon)

print("true: " + str(trueProb))
print("hoeffding UB: " + str(hoeffUB))
print("kl UB: " + str(klUB))