2
$\begingroup$

I am interested in the limit $\frac{\sum_{k=0}^n \sqrt{k}\cdot\binom{n}{k}}{\sqrt{n}\cdot2^n}$ as $n$ goes to infinity. Any reference or argument?

In general what do we know about the asymptotic behavior of $\sum_{k=0}^n k^\alpha\cdot\binom{n}{k}$, where $\alpha$ is a positive real (not necessarily integer)?

$\endgroup$
3
  • 1
    $\begingroup$ A similar sum (but with alternating signs) was considered in this Math.SE question. $\endgroup$ Commented Jan 10 at 15:28
  • 5
    $\begingroup$ Almost all of the mass of the sum is concentrated at $k$ near $\frac{n}{2}$, so the limit is $\frac{1}{\sqrt{2}}$. But this question is better suited for Mathematics Stack Exchange and not MathOverflow. $\endgroup$ Commented Jan 10 at 15:34
  • 1
    $\begingroup$ TeX note: please use \sum, not \Sigma, for sums. Compare, for example, $\displaystyle\sum_{k = 0}^n \sqrt k\binom n k$ \displaystyle\sum_{k = 0}^n \sqrt k\binom n k to $\displaystyle\Sigma_{k = 0}^n \sqrt k\binom n k$ \displaystyle\Sigma_{k = 0}^n \sqrt k\binom n k. I edited accordingly. $\endgroup$
    – LSpice
    Commented Jan 10 at 15:41

5 Answers 5

10
$\begingroup$

$\newcommand\ep\varepsilon\newcommand\de\delta$Note that $$\sum_{k=0}^n k^a\binom nk=n^a2^n E\Big(\frac{X_n}n\Big)^a, \tag{1}\label{1}$$ where $X_n$ is a binomial random variable with parameters $n,1/2$. By the law of large numbers, $$\frac{X_n}n\to\frac12 \tag{2}\label{2}$$ in probability (as $n\to\infty$). So, by \eqref{1} and dominated convergence, for each real $a>0$, $$\sum_{k=0}^n k^a\binom nk\sim n^a2^n \Big(\frac12\Big)^a=n^a2^{n-a}. \tag{3}\label{3}$$


Details on \eqref{1}: We have $P(X_n=k)=\binom nk(\frac12)^n =2^{-n}\binom nk$. So, $$E\Big(\frac{X_n}n\Big)^a=\sum_{k=0}^n\Big(\frac kn\Big)^a P(X_n=k)=\sum_{k=0}^n\Big(\frac kn\Big)^a 2^{-n}\binom nk,$$ which yields \eqref{1}.

Details on \eqref{2}: By Chebyshev's inequality, for each real $\ep>0$, $$P\Big(\Big|\frac{X_n}n-\frac12\Big|\ge\ep\Big)\le\frac{1/(4n)}{\ep^2}\to0, \tag{4}\label{4} $$ which yields \eqref{2}.

Details on \eqref{3}: The dominated convergence theorem can be found in any standard textbook on probability (based on measure theory) and also in some books on mathematical statistics --see e.g. this, Exercise 5.2.22(ii); see also Theorem 5.2.5 there to infer from \eqref{2} that $(\frac{X_n}n)^a\to(\frac12)^a$ in probability.

In this case, it is easy to get \eqref{3} directly. Indeed, let $R_n:=\frac{X_n}n$ and $Y_n:=|R_n-\frac12|$. Then $0\le R_n\le1$ and hence for real $a>0$ $$\Big|R_n^a-\Big(\frac12\Big)^a\Big|\le a\Big|R_n-\frac12\Big|=aY_n.$$ So, $$E\Big|R_n^a-\Big(\frac12\Big)^a\Big|\le aEY_n. \tag{5}\label{5}$$ Next, $$EY_n=e_1+e_2,$$ where $$e_1:=EY_n\,1(Y_n\le\ep)\le\ep,$$ $$e_2:=EY_n\,1(Y_n>\ep)\le E\frac12\,1(Y_n>\ep) =\frac12\,P(Y_n>\ep)\to0,$$ by \eqref{4}. So, $EY_n\to0$ and hence, by \eqref{5}, $ER_n^a\to(\frac12)^a$. In view of \eqref{1}, this yields \eqref{3}.


To complete a previous discussion, let me present a probabilistic proof of the following more general

Fact: Let $f$ be any continuous real-valued function on $[0,1]$. Consider the Bernstein polynomial
$$f_n(p):=\sum_{k=0}^n f(k/n)\binom nk p^k(1-p)^{n-k}.$$ Then $f_n\to f$ uniformly on $[0,1]$.

Proof: Note that $f_n(p)=Ef(Y_{n,p})$, where $Y_{n,p}:=X_{n,p}/n$ and $X_{n,p}$ is a binomial random variable with parameters $n,p$. Take any real $\ep>0$. Then, because $f$ is uniformly continuous on the compact set $[0,1]$, there is some real $\de>0$ such that for all $x,y$ in $[0,1]$ such that $|x-y|\le\de$ we have $|f(x)-f(y)|\le\ep$. So, $|f(Y_{n,p})-f(p)|\le\ep$ on the event $\{|Y_{n,p}-p|\le\de\}$. Therefore and because $|f|\le M$ for some real $M$, we have $$|f_n(p)-f(p)|\le E|f(Y_{n,p})-f(p)|\le e_1+e_2,$$ where $$e_1:=E|f(Y_{n,p})-f(p)|\,1(|Y_{n,p}-p|\le\de)\le\ep,$$ $$e_2:=E|f(Y_{n,p})-f(p)|\,1(|Y_{n,p}-p|>\de) \le2MP(|Y_{n,p}-p|>\de)\le2M\frac{E(Y_{n,p}-p)^2}{\de^2} \le2M\frac{p(1-p)}{n\de^2} \le\frac M{2n\de^2}.$$ So, $$\|f_n-f\|=\max_{p\in[0,1]}|f_n(p)-f(p)|\le\ep+\frac M{2n\de^2}.$$ Thus, $$\limsup_n\|f_n-f\|\le\ep,$$ for each real $\ep>0$. $\quad\Box$


The OP is about the special case of the just proved fact, when $f(p)=p^\alpha$ (with positive $\alpha$) and the fixed $p=1/2$.

$\endgroup$
4
  • 1
    $\begingroup$ Thank you, is there any reference in which I can find these formulas? $\endgroup$
    – Morteza
    Commented Jan 10 at 16:12
  • 1
    $\begingroup$ @Morteza : I have added details. $\endgroup$ Commented Jan 10 at 18:54
  • 1
    $\begingroup$ @Morteza: for the probability proof of the convergence, Probability Theory, by Sinai. $\endgroup$ Commented Jan 11 at 6:00
  • $\begingroup$ Thank you to both of you. $\endgroup$
    – Morteza
    Commented Jan 11 at 10:55
5
$\begingroup$

Expansion of the binomial ${n\choose k}$ around the maximum $k=n/2$ gives a narrowly peaked Gaussian for large $n$, $$\binom{n}k=\frac{2^n}{\sqrt{n\pi/2}} \exp\left(-\frac{(k-n/2)^2}{n/2}\right) \left(1+{\cal O}(n^{-1/2})\right),$$ from which $$\lim_{n\rightarrow\infty} \frac{\sum_{k=0}^n k^\alpha {n\choose k}}{n^\alpha 2^{n}}=2^{-\alpha}\sum_{k=0}^n 2^{-n} {n\choose k}=2^{-\alpha}.$$ Note that this large-$n$ asymptotics is actually exact for all $n$ for $\alpha=1$.

$\endgroup$
1
  • 3
    $\begingroup$ How do you derive the limit? $\endgroup$ Commented Jan 10 at 16:01
4
$\begingroup$

As remarked by Iosif Pinelis, this is a matter of law of great numbers; we may also describe it in terms of Bernstein polynomials. Specifically, for $\alpha\ge0$ and $n\ge1$, let $p_n$ be the value of the $n$-th Bernstein polynomial of the function $x^\alpha$ at $1/2$: then $$\sum_{k=0}^nk^\alpha{n\choose k}=p_n 2^nn^\alpha=2^{n-\alpha}n^\alpha(1+o(1)).$$ Moreover, standard facts about convergence give:

  • For $0\le \alpha\le 1$, since $x^\alpha$ is concave, the sequence $p_n$ is increasing, and since $x^\alpha$ is a modulus of continuity of itself, $$0\le 2^{-\alpha}-p_n \le (4n)^{-\alpha/2}$$

  • For $ \alpha\ge 1$, since $x^\alpha$ is convex, the sequence $p_n$ is decreasing, and since $x^\alpha$ is Lipschitz of constant $\alpha$ on $[0,1]$

$$0\le p_n-2^{-\alpha} \le \frac{\alpha}{2\sqrt n}.$$

Analogous considerations hold for any continuous function in place of $x^\alpha$.

[edit] as to the above bounds on the remainder, the general fact is: Given $f\in C^0([0,1])$, $\omega$ a concave modulus of continuity for $f$, and $x\in[0,1]$, the elementary inequality holds: $$|f(x)-B_nf(x) |\le \omega\Big(\sqrt{\frac{x(1-x)}n}\Big)$$ whence the uniform bound

$$\|f-B_nf\|_\infty\le \omega\Big( \frac1{2\sqrt n}\Big).$$

For $x^\alpha$ we can take $\omega(t):=t^\alpha$ for $0\le\alpha\le1$ and $\omega(t)=\alpha t$ for $\alpha\ge 1$.

$\endgroup$
1
  • 1
    $\begingroup$ It is worth recalling that for $0<\alpha<1$ the above bound $O(n^{-\alpha/2})$ for $\alpha$-Hölder functions was given by Marc Kac (around 1937); he also observed that the case of the function $x^\alpha$ shows the bound is sharp! $\endgroup$ Commented Jan 10 at 23:24
3
$\begingroup$

This is a special case of convergence of Bernstein polynomials $$B_nf(x)=\sum_{k=0}^n f\left ( \frac kn \right ) \binom {n}{k}x^k (1-x)^{n-k} \to f(x) $$for every continuous $f$, just take $f(x)=x^\alpha$ and $x=\frac 12$. However @Iosif Pinelis proof should extend to continuous $f$ (maybe only pointwise).

$\endgroup$
6
  • 1
    $\begingroup$ Azz, you beat me for 1 minute! :) $\endgroup$ Commented Jan 10 at 21:11
  • 1
    $\begingroup$ The convergence is uniform for continuous $f$. $\endgroup$ Commented Jan 10 at 21:32
  • 1
    $\begingroup$ @IosifPinelis I know this for Bernstein polynomials. Do you mean that your proof shows uniform convergence? $\endgroup$ Commented Jan 10 at 21:39
  • 1
    $\begingroup$ Yes, the probabilistic proof of the uniform convergence for continuous $f$ follows from two facts: (i) $f$ is uniformly continuous on the compact set $[0,1]$ and (ii) the variance of the binomial distribution with parameters $n,p$ is $p(1-p)/n\le1/(4n)\to0$ as $n\to\infty$ uniformly in $p\in[0,1]$. At least in this sense, the binomial distribution with parameters $n,p$ is the least concentrated (near its mean) when $p=1/2$ (the entropy is then also the largest). $\endgroup$ Commented Jan 10 at 21:45
  • 1
    $\begingroup$ @IosifPinelis Yes true. I wonder if your proof above, based on dominated convegence, yields only pointwise convergence. $\endgroup$ Commented Jan 10 at 21:51
1
$\begingroup$

From my very old cookbook.

For integer values of $p$ $$A_p=\sum_{k=0}^n k^p\,\binom{n}{k}=2^{n-p}\,n\, B_p(n)$$ where the first polynomials are $$\left( \begin{array}{cc} p & B_p(n) \\ 1 & 1 \\ 2 & n+1 \\ 3 & n^2+3 n \\ 4 & n^3+6 n^2+3 n-2 \\ 5 & n^4+10 n^3+15 n^2-10 n \\ 6 & n^5+15 n^4+45 n^3-15 n^2-30 n+16 \\ 7 & n^6+21 n^5+105 n^4+35 n^3-210 n^2+112 n \\ 8 & n^7+28 n^6+210 n^5+280 n^4-735 n^3+28 n^2+588 n-272 \\ 9 & n^8+36 n^7+378 n^6+1008 n^5-1575 n^4-2436 n^3+5292 n^2-2448 n \\ \end{array} \right)$$

Tha $A_p$ are in fact the expansion of generalized hypergeometric functions. For example $$A_4=n \, _4F_3(2,2,2,1-n;1,1,1;-1)$$ $$A_5=n \, _5F_4(2,2,2,2,1-n;1,1,1,1;-1)$$ $$A_6=n \, _6F_5(2,2,2,2,2,1-n;1,1,1,1,1;-1)$$ The pattern is clear.

Asymptotically,

$$A_p=2^{n-p}\,n^p \left(1+\frac {p(p+1)}{2n}+ O\left(\frac{1}{n^2}\right) \right)$$ which seems to works decently for non iteger values of $p$.

Using $p=\frac 12$ and $n=5^m$, some numbers

$$\left( \begin{array}{cc} m & \frac {\text{approximate}}{\text{exact}} \\ 1 & 1.0389688 \\ 2 & 1.0052319 \\ 3 & 1.0010086 \\ 4 & 1.0002003 \\ 5 & 1.0000400 \\ 6 & 1.0000080 \\ 7 & 1.0000016 \\ \end{array} \right)$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .