Crossover from Capacity

Problem

Invert the k-ary symmetric channel capacity formula to find the error probability producing a target capacity in bits. Capacity falls monotonically from log2(k) at p = 0 to 0 at p = (k-1)/k, so bisection applies. Return 0.0 when target >= log2(k) and (k-1)/k when target <= 0.

Hint

Bisect on the interval [0, (k-1)/k], always keeping the side whose capacity bracket contains the target.

Test cases

case 1

in: [2,0.5]

expected: 0.11002786443835949

case 2

in: [2,0.9]

expected: 0.012986862055517776

case 3

in: [4,1]

expected: 0.18928962491523177

case 4

in: [2,1]

expected: 0

case 5

in: [2,0]

expected: 0.5

case 6

in: [3,1]

expected: 0.10385734171378519

Starter codePython

import math
def crossover_from_capacity(k, target):
    # Your code here
    pass

6 test cases · run your code against them in the editor