MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

On page 11 of "Smaller decoding exponents: ball-collision decoding" by Berstein they have the formula \begin{equation}\lim_{n \rightarrow \infty} \frac{1}{n}\log_{2}\left(\dbinom{k_{1}}{p_{1}}\dbinom{l_{1}}{q_{1}} + \dbinom{k_{2}}{p_{2}}\dbinom{l_{2}}{q_{2}} +\dbinom{k_{1}}{p_{1}}\dbinom{k_{2}}{p_{2}}\dbinom{l_{1}}{q_{1}}\dbinom{l_{2}}{q_{2}}2^{-l_{1}-l_{2}} \right)\end{equation} \begin{equation} = max\Bigg[(R/2)log_2(R/2) - Plog_2P-(R/2-P)log_2(R/2-P) + Llog_2L -Qlog_2Q \end{equation} \begin{equation} -(L-Q)log_2(L-Q),(R)log_2(R/2) - 2Plog_2P-(R-2P)log_2(R/2-P) + 2Llog_2L \end{equation} \begin{equation} -2Qlog_2Q -2(L-Q)log_2(L-Q)-2L\Bigg] \end{equation} where $p_i/n \rightarrow P, q_i/n \rightarrow Q, k_i/n \rightarrow R/2,$ and $l_i/n \rightarrow L$ as $n \rightarrow \infty$

They apparently used \begin{equation}\frac{1}{n}\log_{2}\dbinom{(\alpha + o(1))n}{(\beta +o(1))n} \rightarrow \alpha \log_{2}\alpha - \beta\log_{2}\beta - (\alpha - \beta)\log_{2}(\alpha - \beta)\end{equation} as n $\rightarrow \infty$ but I don't see how they ended up with a max function with two arguments. I'm not even sure how to deal with the sum inside the logarithm. Any ideas? Thanks!

share|cite|improve this question
Let $L = \log(\max(x,y))$. Then $\log(x+y)$ is between $L$ and $\log(2\max(x,y)) = L + \log 2$. Division by $n$ makes the constant $\log 2$ negligible, so we're left with the asymptotics of $L / n$. – Noam D. Elkies Mar 13 '12 at 5:05
Thanks Noam! I apologize if this question isn't research level. I'll stick to MSE from now on. – Nick Peterson Mar 14 '12 at 2:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.