# Bound on expression from probability distributions

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

-
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

$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.

-

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.

-