Can everybody suggest a better upper bound?

[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?

 

[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?

 

[SW VandeCarr]

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?

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

and maximize f(x) wrt x.

 

[sabbagh80]

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?

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

and maximize f(x) wrt x.

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

 

[SW VandeCarr]

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

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.

 

[sabbagh80]

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.

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?

 

[SW VandeCarr]

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?

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.

 

[sabbagh80]

Clearly, on the left side of the expression 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 expression, 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.

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.

 

[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!)

 

[bpet]

Hi,
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.

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

 

[sabbagh80]

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

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.

 

[bpet]

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.

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?

 

[sabbagh80]

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?

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 \}

 

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

 

[sabbagh80]

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.

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

 

[Stephen Tashi]

sabbagh80,

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}

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.