Water-Filling Power Allocation

Problem

Allocate total_power across parallel channels with the given noise variances using water-filling. The optimal powers are p_i = max(0, level - n_i) where the water level is chosen so the powers sum to total_power. Find the level by bisection on [min(n), max(n) + total_power] for 200 iterations and return the power list.

Hint

Noisy channels sometimes receive zero power when the water level stays below their noise.

Test cases

case 1

in: [[1,1],2]

expected: [1,1]

case 2

in: [[1,3],4]

expected: [3,1]

case 3

in: [[1,3],1]

expected: [1,0]

case 4

in: [[2,2,2],3]

expected: [1,1,1]

case 5

in: [[0.5,1.5,4],3]

expected: [2,1,0]

Starter codePython

def water_filling(noise_vars, total_power):
    # Your code here
    pass

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