Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The following equation arises in the water-filling problem:

$\sum_{i=1}^{n} max \left\{ 0, \frac{1}{\nu} - \alpha_i \right\} = 1$

Assuming that all $\alpha_i$s are known, how does one solve for $\nu$?

share|cite|improve this question
up vote 0 down vote accepted

One possible method: arrange all $\alpha_i$'s into an increasing sequence:

$$\alpha_{(1)} \leq \alpha_{(2)} \leq \alpha_{(3)} \leq \ldots \leq \alpha_{(n)}$$

For now, introduce the variable $x=\frac{1}{\nu}$. Then, the problem can be restated as

$$\sum_{i=1}^n \max\{0,x-\alpha_{(i)}\} = 1$$

We are looking for an $m$ such that

$$m x - \sum_{i=1}^m \alpha_{(i)} = 1$$


$$ x = \frac{1+\sum_{i=1}^m \alpha_{(i)}}{m} $$

and we must also have that

$$ \frac{1+\sum_{i=1}^m \alpha_{(i)}}{m} \geq \alpha_{(j)} \; , \; \forall j \in \{1,\ldots,m\} $$


$$ \frac{1+\sum_{i=1}^m \alpha_{(i)}}{m} < \alpha_{(j)} \; , \; \forall j \in \{m+1,\ldots,n\} $$

This gives a method for finding the solution.

share|cite|improve this answer
Thank you. Works like a charm! – user1058 Feb 8 '11 at 10:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.