Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I came across this issue while trying to combine multiple probability distributions into a single distribution which approximates them all simultaneously. This boils down to maximizing this expression $$ S = \sum_i \frac{N_i p_i^i}{\sum_j N_j p_i^j} $$ in terms of the unknowns $N_1, \dots, N_t$, $p_1, \dots, p_t$. Here $p_i \in [0,1]$ and $N_i \geq 0$ for all $i$.

It is easy to see that $S \leq t$ (because the denominator term $\sum_j N_j p_i^j \leq N_i p_i^i$. Are there any tighter bounds available?

Thanks for the help

share|improve this question
    
I assume all the $p_i$ are positive and at least one of the $N_i$ is positive to make all the denominators positive? –  Noah Stein Dec 1 '11 at 14:58

2 Answers 2

up vote 1 down vote accepted

$t$ is in fact a tight bound. It's slightly tricky because the objective is not defined at what should be the optimal solution (due to zeros in numerators and denominators). What you want is first $p_1 \to 0+$ (making the first term $ \to N_1 p_1/(N_1 p_1) = 1$, then $N_1 \to 0+$ making the second term $\to N_2 p_2^2/(N_2 p_2^2 + \ldots)$, then $p_2 \to 0+$ making the second term $\to 1$, then $N_2 \to 0+$ etc.

share|improve this answer

This problem admits a very simple solution by partial derivation. You can consider this a function of $N_i$ and $p_i$ and, considering that you are summing all positive terms, all you need to do is maximize the expression

$$S_i=\frac{N_ip_i^i}{\sum_jN_jp_i^j}$$

so that

$$\frac{\partial S_i}{\partial p_\alpha}=0$$

and

$$\frac{\partial S_i}{\partial N_\alpha}=0.$$

You should not have too much difficulties to see that the solution is given by $p_\alpha=\alpha/t$ and $N_1=N_2=\ldots=N_t=constant$, that we call N. So, you get finally the expression

$$S\le S_M$$

being

$$S_M=\sum_i\frac{\frac{i^i}{t^i}}{\sum_j\frac{i^j}{t^j}}$$

that should be evaluated in a closed form.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.