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

 

[SW VandeCarr]

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

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.