0
$\begingroup$

I am wondering about the asymptotic approximation of the following expression: $$S=\sum^{N}_{i=0}\log\Bigg[\binom{\binom{N+1}{i}}{t_i}\Bigg]$$ where $$t_i=\binom{N}{i}-\binom{N-k}{i-k}+\binom{N-k}{i-1}$$ where $k$ is a positive integer. Also we have that $k\ll N$. Also for those binomials that have $i<k$ (namely negative) we count them as zero. I am trying to work out the approximation for $N \rightarrow \infty$.

$\endgroup$
  • 2
    $\begingroup$ You've posted variants of this over the last few weeks, and no one's biting. I like asymptotics, but I won't attempt it because there are three variables. Even 2 can be very difficult and often one parameter has to take on a 'small,' 'mid' and 'large' case analysis. If you are summing over one of the three variables, it would be better to show the full problem and there's a ghost of a chance someone might be interested. $\endgroup$ – skbmoore Aug 29 '18 at 17:15
  • $\begingroup$ Why are you wondering about this sum? In what context does the sum of a logarithm of a binomial coefficient of binomial coefficients arise? $\endgroup$ – Antonio Vargas Aug 29 '18 at 19:08
  • $\begingroup$ @skbmoore I know that this looks like a horrendous sum to be solved, hence I posted variations of it. The sum is over $i$ which appears in many terms unfortunately. The only constant is $k$ which can be fixed to a +ve integer bigger than 1 if it is of any help. I think the real issue is how to simplify the $t_i$ first, I tried various ways, to write of as leading Stirling approximation / in terms of factorials yet those are not so helpful. The expression $S$ is indeed the original problems, previous posts were my attempt to simplify it. $\endgroup$ – William Aug 30 '18 at 8:29
  • $\begingroup$ @AntonioVargas It is a counting problem, this problem came up when I want to calculate some information content. $\endgroup$ – William Aug 30 '18 at 8:31
  • $\begingroup$ An approximation for $k=2$ is the following: let $\eps=1/4(\sqrt{(1+4/n)}-1)$ and $w(u)=u(2u+1)-1/(2n).$ Call your sum, but with $n=N+1, S(n).$ Then $$ S(n)\sim -2^n \sqrt{\frac{2n}{\pi}} \int_\eps^1/2 \exp{(-2nu^2)}(w(u)\log(w(u)+(1-w(u))\log(1-w(u))\,du $$ Can't make it rigorous and I shudder to think what happens for variable $k.$ The integral rep is about 1% accurate for $n=100.$ $\endgroup$ – skbmoore Aug 30 '18 at 22:03
1
+50
$\begingroup$

Here are the asymptotics and a method for $k=1$ through $k=4.$ Unfortunately there does not appear to be a simple pattern developing. Also, I'm using $n=N-1.$

$\textbf{k=1} $ $$S_1:=\sum_{m=0}^n \log{ \Big[ \binom{\binom{n}{m}}{ \binom{n-1}{m}} }\Big] = \sum_{m=1}^{n-1} \log{\Big[ \binom{\binom{n}{m}}{ \binom{n}{m}(1-m/n) } }\Big] $$ The sum starting and ending value has been shifted by 1 towards the center because those end values within the square bracket are 1, and $\log(1)=0.$ Use the 'central value' estimate for the binomials, $$ \binom{n}{m} \sim \binom{n}{n/2} e^{-\tfrac{2}{n}\big(\tfrac{n}{2}-m\big)^2 } .$$ Note: I haven't justified that this is sufficient other than numerically. Use the asymptotic expansion for $\log{\Gamma(1+x)},$ $$ \log{\Gamma(1+x)} \sim x\log{(x/e)} + \log{(\sqrt{2\pi x})} + ...$$ Only the first term of the previous will be used when estimating $S_1.$ In thefollowing let $a=\binom{n}{m}$ and $y=m/n.$ Then $$ S_1 \sim\binom{n}{n/2} \sum_{m=1}^{n-1} e^{-\tfrac{2}{n}\big(\tfrac{n}{2}-m\big)^2 } \big\{ \log{(a/e)}-(1-y)\log{(a\,(1-y)/e)}-y\log{(a \,y /e)} \big\}$$ The $\{\cdot\}$ simplifies so that it is independent of $a,$ $$ \{\cdot\} = H(y):=-\big(y\,\log{y} + (1-y)\log{(1-y)} \big) $$ Therefore $$ S_1 \sim\binom{n}{n/2} \sum_{m=1}^{n-1} e^{-2n\big(\tfrac{m}{n}-\tfrac{1}{2}\big)^2 } H(m/n)$$ In the limit that $n$ is large, interpret the previous expression as a Riemann integral: $$ S_1\sim\binom{n}{n/2} \, n\, \int_0^1 e^{-2n\big(u-\tfrac{1}{2}\big)^2 } H(u) \,du = \binom{n}{n/2} \, n\, \int_{-1/2}^{1/2} e^{-2n\, u^2} H(w_1(u)) \,du$$ where $w_1(u) = 1/2 + u.$ One may expand $H(w_1(u))$ in a power series about $u=0,$ extend the limits on the integral to $ \pm \infty $ so to use Gaussian integrals to get a close form, and expand the leading binomial and $n$ factor to finally get $$S_1 \sim 2^n\big(\log{2} - \frac{\log{2}+2}{4n} + o(1/n) \big) $$
For the other results, a polynomial associated with the index $k$ has been determined. That is, the results will be expressed as $$\quad (A) \quad S_k\sim\binom{n}{n/2} \, n\, \int_{-1/2}^{1/2} e^{-2n\, u^2} H(w_k(u)) \,du$$ $\textbf{k=2:} \quad w_2=\frac{1}{2}+\frac{3}{2}u - 2 u^3 $

$\textbf{k=3:} \quad w_2=\frac{1}{2}+\frac{3}{2}u - 2 u^3 $

$\textbf{k=4:} \quad w_2=\frac{1}{2}+\frac{11}{8}u - u^3 - 2u^5 $

That the $k=2$ is the same as the $k=3$ case is not a typo. There are three sources of error so far unquantified: the central binomial approximation, the dropping of subsequent terms in the $\log{\Gamma}$ expansion, and the error in going from a sum to the integral. Another error will appear when $k$ gets appreciably large with respect to $n:$ One continues to 'pinch' the ends of the integral and the simple Riemann integrals presented will need corrections. This approach may completely fall apart if $k = \alpha n$, with, say, $\alpha \ge 1/10.$

The following is a comparison of values as calculated by the original definition, and by eq. (A). Multiply the entry by the scientific notation designator indicated in the table.

$$ \begin{array}{c|lcr} k & S_{16} & S_{16}^{A} & S_{100} & S_{100}^{A} \\ {} & \quad \cdot 10^4 & & & \cdot 10^{29} \\ \hline 1 & 4.325 & 4.263 & 8.723 & 8.701 \\ 2 & 4.040 & 4.045 & 8.642 & 8.624 \\ 3 & 4.038 & 4.045 & 8.642 & 8.624 \\ 4 & 4.088 & 4.098 & 8.666 & 8.645 \end{array} $$ To me it appears that the values depend weakly on $k$ and an insistence that the asymptotic formula is accurate for these distinctions means that those errors mentioned previously need to be dealt with.

$\endgroup$

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.