# Can everybody suggest a better upper bound?

1. Jul 15, 2011

### sabbagh80

Hi,
I have sent this question a couple of days ago, but it seems that its latex form had problem. So, I decide to send it again.

I will thank If somebody help me solving this problem.

Consider a random variable $k_1$ with the given pmf as:

$Pr[k_1=l]=\sum_{l_1+2l_2=l} \frac{N!}{(N-l_1-l_2)!l_1!l_2!}p_1^{l_1} p_2^{l_2} (1-(p_1+p_2))^{N-l_1-l_2}$

where $l_1,l_2 \in [0,1,...,l]$.

but we don't have $p_1$ and $p_2$ separately and we know just the value of $p_1+p_2$.

I want to find at least a good and tight upper bound for the above pmf.

For example; we can use the inequality of $p_1^{l_1} p_2^{l_2} \leq \frac{l_1!l_2!}{(l_1+l_2)!}(p_1+p_2)^{l_1+l_2}$, but it is not that much tight.

Can everybody suggest a better upper bound?

2. Jul 15, 2011

### Stephen Tashi

Do you get a sensible answer if you set $\theta = p_1 + p_2$ and solve the maximization problem:

Maximize $f(x) = x^{L_1}(1-x)^{L_2}$ with respect to $x$
subject to the constraint $0 < x < \theta$

by using calculus?

3. Jul 15, 2011

### SW VandeCarr

Set $$\theta=1, l_1 = 1, l_2=1$$

and maximize f(x) wrt x.

Last edited: Jul 15, 2011
4. Jul 16, 2011

### sabbagh80

If I reword the problem,
find the supreme (or at least one good) function$f(.)$ which for it we have $p_1^{l_1}p_2^{l_2}\leq f(p_1+p_2,l_1,l_2)$

Last edited: Jul 16, 2011
5. Jul 16, 2011

### SW VandeCarr

The function is maximal when $$p_1=0.5, p_2=0.5, l_1=1, l_2=1$$

That is, the left side of your expression cannot exceed 0.25 if the exponents are from the set of natural numbers (as you defined them) and the sum of the two probabilities are constrained to be less than or equal to one.

EDIT: Stephen Tashi already gave you the function to maximize in post 2, which you quoted above. I added some constraints so that the answer would make sense in terms of probabilities.

Last edited: Jul 16, 2011
6. Jul 17, 2011

### sabbagh80

Dear SW VandeCarr,
let me explain the problem in other view and also my answer.

Let $p_1, p_2$ be any two probability values with the constraint $p_1+p_2=k\leq 1$ where $k$ is constant. Also, suppose $l_1, l_2 \in N$ are two fixed numbers.
Then, by maximization, we have: $p_1^{l_1}p_2^{l_2}\leq (\frac{kl_1}{l_1+l_2})^{l_1}(\frac{kl_2}{l_1+l_2})^{l_2}.$
Now, it seems that finding a better upper bound which is in terms of $p_1+p_2$ is impossible. Is this conclusion right?

7. Jul 17, 2011

### SW VandeCarr

Clearly, on the left side of the inequality $$p_1^{l_1} p_2^{l_2}$$ for any positive integer values of the exponents greater than 1, the value of the expression decreases. If one or both of the exponents take a zero value then the left side of the expression becomes 0.5 or 1 which, while true, is trivial IMO in terms of maximizing the function;

$$f(x)=(x)^{l_1}(1-x)^{l_2}$$ $$0\leq x \leq 1$$

Note for the right side of your inequality, for values of k less than or equal to 1, the expression has a maximum value of 0.25 when the $l$ terms are equal to 1.

EDIT: I'm not sure you what you mean about the upper bound for $p_1 + p_2$. Assuming they refer to the same probability space, the upper bound is of course 1. That's defined by the laws of probability.

Last edited: Jul 17, 2011
8. Jul 17, 2011

### sabbagh80

Are you agree with the given upper bound for $l_1, l_2 \in N$ and $k \leq 1$?
I have to find the upper bound "in terms of $p_1 + p_2=k"$ not "for" $p_1 + p_2=k$
Also, about the probability space, except $p_1 + p_2$, we also have $p_0=1-p_1-p_2=1-k$.

Last edited: Jul 17, 2011
9. Jul 17, 2011

### sabbagh80

Even when we find the upper bound of the $p_1^{l_1}p_2^{l_2}$ as $(\frac{kl_1}{l_1+l_2})^{l_1}(\frac{kl_2}{l_1+l_2}) ^{l_2}$ with the constraint of $p_1+p_2=k \leq 1,$ but the main problem has not solved.
If I rephrase the main problem again, it is as follows;

$$f=max_{0\leq x \leq k} \sum_{l_1,l_2 \in A} \frac{N!}{(N-l_1-l_2)!l_1!l_2!} x^{l_1}(k-x)^{l_2}(1-k)^{N-l_1-l_2}$$
where for the sake of simplicity, $A$ is the set of which the integer values of $l_1, l_2$ are picked up.
If we want to maximize the above expression in greedy way, we can write
$$f<\sum_{l_1,l_2 \in A} \frac{N!}{(N-l_1-l_2)!l_1!l_2!} (\frac{k l_1}{l_1+l_2})^{l_1}(\frac{k l_2}{l_1+l_2})^{l_2}(1-k)^{N-l_1-l_2}.$$
But, it is clear that this bound is not that much acceptable.
Can everybody suggest a better upper bound?(the main question of this thread!)

Last edited: Jul 17, 2011
10. Jul 18, 2011

### bpet

Could you show how the pmf was derived, so maybe it is possible to derive bounds or an exact formula by another method?

11. Jul 20, 2011

### sabbagh80

We can say, it is a kind of tri-nomial distribution with a constraint of $p_1+p_2=k$ where $0<k<1$. And $Pr[k_1=l]$ is the summation of the above pmf over the constraint of $l_1+2l_2=l$. If you sum up over all the values of $l$, you can easily get unity, since it is the summation of a tri-nomial distribution.
Actually, the set $A$ is defined as: $A=\{l_1,l_2 \in \{0,1,...,N\}|l_1+2l_2=l \}$ and $l \in \{0,1,...,2N \}$.
I really need to improve the given upper bound which is derived in greedy way.

12. Jul 20, 2011

### bpet

Ok so $L=X_1+...+X_N$ where $P[X=1]=p_1$ and $P[X=2]=p_2$, in which case you'd also need $l_1+l_2\le N$ right?

13. Jul 20, 2011

### sabbagh80

yes, you are right. I had considered it in my mind, but, I forgot to mention it. So, we can modify the set as $A=\{l_1,l_2 \in \{0,1,...,N\}|l_1+2l_2=l, l_1+l_2\leq N \}$

Last edited: Jul 20, 2011
14. Jul 20, 2011

### bpet

Write $L_N=X_1+...+X_N$, so the p.g.f. with $p_1+p_2=q$ is
$$g(x;p_1,N) = (1-q+p_1x+(q-p_1)x^2)^N$$
and
$$P[L_N=n] = \tfrac{\partial^n}{\partial x^n}g|_{x=0}$$
so taking derivatives wrt $p_1$ and applying the Leibniz formula shows that the probability is maximized at either
$$P[L_{N-1}=n-1] = P[L_{N-1}=n-2]$$
or $p_1=0$ or $p_1=q$. Not sure how to solve the equation though.

15. Jul 21, 2011

### sabbagh80

Could you please define what you mean by $L_i$ and $X_j$? Sorry, but, I am confused by these two notations.

16. Aug 8, 2011

### Stephen Tashi

sabbagh80,

The usual algorithms for "geometric programming" find the extrema of polynomials with positive coefficients, but people have developed extensions of the algorithms that handle polynomials with coefficients of arbitrary signs. I haven't searched for an online reference to these algorithms, but I recall reading a hardcopy of a paper about them years ago. So if you are seeking numerical answers, I think the algorithms exist.