0

Suppose we have to choose $mm_1$ items out of $m_1$ and $mm_2$ items out of $m_2$ such that $mm_1 + mm_2 = k$ where $k$ is fixed and known. This also constrains us such that $mm_1 < m_1$ and $mm_2 < m_2$. I want to maximize the value of $C^{m_1}_{mm_1} * C^{m_2}_{k-mm_1}$.

The naive solution will be to go through all the possible $k$, and choose $mm_1$ that gives the largest value. Is there a closed form solution for $mm_1$ to maximize the product?

Budhapest
  • 117

1 Answers1

0

Note that $C^{m_1}_{mm_1} * C^{m_2}_{k-mm_1}=\frac {m_1!m_2!}{mm_1!(m_1-mm_1)!(k-mm_1)!(m_2-k+mm_1)!}$ Now imagine increasing $mm_1$ by $1$ You multiply the fraction by$\frac{(m_1-mm_1)(k-mm_1)}{(mm_1+1)(m_2-k+mm_1+1)}$ This will be $1$ when $\frac{(k-mm_1)}{(m_2-k+mm_1+1)}=\frac {(mm_1+1)}{(m_1-mm_1)}$, which is when you take the same fraction of items out of each set.

Ross Millikan
  • 374,822
  • @Ross_Millikan Does that mean that taking the same fraction would maximize the product? If so why? – Budhapest Jan 08 '15 at 00:14
  • Yes. Because if $mm_1$ is smaller, increasing it will increase the product. If it is larger, decreasing it will increase the product because that multiplier is less than 1. – Ross Millikan Jan 08 '15 at 00:20
  • @Ross_Millikan Doesn't it mean that $\frac{mm_2}{m_2-mm_2+1}=\frac{mm_1+1}{m_1-mm_1}$ and by taking the same fraction of items out of each set in order to maximize, we are assuming that $mm_1 << m_1$ and $mm_2 << m_2$ – Budhapest May 12 '15 at 17:06
  • @Budhapest: no we are not assuming that $m \ll 1$ (which is equivalent to your two conditions). Let $m=\frac 12$. Intuitively, it will be much more probable to get just about half of the $m_1$ and half of the $m_2$ objects than that you get many more than half the $m_1$ and many fewer than half the $m_2$ – Ross Millikan May 12 '15 at 21:26
  • The more common way to phrase this (which you approach) is that the whole population is $M$ with two subpopulations $m_1,m_2$ with $m_1+m_2=M$. We need to choose $k$ of the $M$. The most likely assignment to the subpopulations is $\frac kMm_1$ out of the $m_1$ and $\frac kMm_2$ out of the $m_2$ – Ross Millikan May 12 '15 at 21:28