1
$\begingroup$

Let $$ f(k,n,p) = {n \choose k}p^k(1-p)^{n-k} $$ be the binomial probability mass function. I want to maximize a function of binomial pmf's with respect to $n$: \begin{align*} g(n) \equiv &\left(1-\sum_{T=0}^{L}\sum_{t=0}^T f(t,n,p_A) \cdot f(T-t,N-n,p_B) \right)\\ \cdot &\left( \sum_{T=0}^{U}\sum_{t=0}^T f(t,n,p_A) \cdot f(T-t,N-n,p_B) \right) \end{align*} for fixed $L,U,N,\in \mathbb{Z}^+,\ p_A,p_B \in [0,1]$. In the case of a single binomial pmf, $f(n,k,p)$ is unimodal with respect to $n$ so one can find $n^* \equiv \operatorname{argmax} f(k,n,p)$ by finding $n$ such that: $$ f(k,n,p) \geq f(k,n+1,p)\qquad \text{and}\qquad f(k,n,p)\geq f(k,n-1,p) $$ which yields $$ \frac{k}{p} \geq n\geq \frac{k}{p}-1; $$ i.e., $f(k,n,p)$ for fixed $k,p$ is maximized by $$ n^* = \text{floor}\left(\frac{k}{p}\right). $$ Having tested empirically, I think $g(n)$ is also unimodal with respect to $n$, but haven't been able to prove it. Additionally, I have not been able to solve the analogous inequalities: $$ g(n) \geq g(n+1)\qquad g(n)\geq g(n-1) $$ (neither by hand nor using Mathematica).

Any suggestions for how to maximize $g(n)?$ I'd prefer to avoid differentiating if possible: I think a solution which only deals with integer values is more likely to provide illuminating intuition for the problem I'm working on, and gamma functions are well-defined on values that aren't admitted by my problem. That being said, if it's the only way to do this, so be it.

Edit for clarification: I am primarily interested in the case $L < U \leq N$.

$\endgroup$
  • $\begingroup$ If $L=U,$ I should think $$\sum_{T=0}^{L}\sum_{t=0}^T f(t,n,p_A) \cdot f(T-t,N-n,p_B)=\frac12$$ would optimize $g(n),$ because $g(n)$ would have the form $g(n)=(1-x)x$ for $$x=\sum_{T=0}^{L}\sum_{t=0}^T f(t,n,p_A) \cdot f(T-t,N-n,p_B).$$ $\endgroup$ – Adrian Keister Jul 30 '19 at 21:31
0
$\begingroup$

Partial Answer

Let $m=\min(L,U),\;M=\max(L,U),$ and $$h(n)=\sum_{T=0}^{m}\sum_{t=0}^T f(t,n,p_A) \cdot f(T-t,N-n,p_B). $$ We have three cases:

Case 0: $L=m=U.$ Then $$g(n)=(1-h(n))\,h(n), $$ which is minimized by $h(n)=1/2,$ if this is possible.

Case 1: $L=m<U.$ Then \begin{align*} g(n) = \left(1-h(n) \right) \cdot \left( h(n) +\sum_{T=m+1}^{M}\sum_{t=0}^T f(t,n,p_A) \cdot f(T-t,N-n,p_B) \right). \end{align*} This is analogous to shifting the roots of the function $f(x)=x(1-x)$ as $\tilde{f}(x)=(x+a)(1-x);$ we can still maximize this fairly easily by noting that we want $x$ to be half-way in-between the two roots $1$ and $-a:$ $x=(1+(-a))/2=(1-a)/2.$ Therefore, we want our solution to be $$h(n)=\frac{1-\sum_{T=m+1}^{M}\sum_{t=0}^T f(t,n,p_A) \cdot f(T-t,N-n,p_B)}{2}.$$

Case 2: $L>m=U.$ Then we have $$ g(n)=\left(1-h(n)-\sum_{T=m+1}^{M}\sum_{t=0}^T f(t,n,p_A) \cdot f(T-t,N-n,p_B)\right)h(n).$$ This is analogous to shifting our root like this: $\hat{f}(x)=x(1-x-a),$ with the maximum at the average of the two roots $0$ and $1-a,$ yielding $(1-a)/2,$ as before. So, our maximum would occur at $$h(n)=\frac{1-\sum_{T=m+1}^{M}\sum_{t=0}^T f(t,n,p_A) \cdot f(T-t,N-n,p_B)}{2}, $$ exactly as before.

To sum up: the minimum occurs at $$h(n)=\begin{cases}1/2,\quad& L=U\\ \left(1-\sum_{T=m+1}^{M}\sum_{t=0}^T f(t,n,p_A) \cdot f(T-t,N-n,p_B)\right)/2,\quad &L\not=U\end{cases}. $$

What my answer does not do is show you how to solve these $h(n)=$ -type equations. You might have to do that numerically; you might also not get an exact answer, given the integer nature of these expressions (at least with respect to the sum limits).

$\endgroup$
  • $\begingroup$ Thank you! I am primarily interested in Case 1: L = m < U, and will edit the question to reflect that. I agree with your analysis, and agree that solving equations with $h(n)$ is the heart of the problem. Would you be willing to elaborate on what you mean by not getting an exact answer? Do you mean that solving numerically may yield real-valued bounds on $n$ instead of integer bounds? $\endgroup$ – afd Jul 31 '19 at 18:34
  • $\begingroup$ If you have some realistic values of $n, p_A,$ and $p_B,$ I could poke around trying to solve those. $\endgroup$ – Adrian Keister Jul 31 '19 at 18:36
  • $\begingroup$ I think that solving $h(n)=c$ could be very problematic, given that you are evaluating a finite sum and trying to get it to equal some other value. You don't have a lot of flexibility with the $h(n),$ which leads me to believe you are likely not going to be able to get exact values. However, you might be able to find the closest ones (bracket the solution, that type of thing). $\endgroup$ – Adrian Keister Jul 31 '19 at 18:39
  • $\begingroup$ I see what you mean. I've done some numerical solving for small values $(N \approx 20-100, (L,U)\approx (30,70)$, but wasn't able to find any empirically-suggested relationships between $n$ and the maxima. $\endgroup$ – afd Jul 31 '19 at 18:41
  • $\begingroup$ What sorts of $p_A$ and $p_B$ are you working with? $\endgroup$ – Adrian Keister Jul 31 '19 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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