Асимптотика для суммы биномиальных коэффициентов

[kavahox]

Ну вообще нужно и с корнем и без. Оба случая важны. Я просто думал, что без корня проще и надо с него и начинать

[sup]

Если не проврался, то первые члены асимптотики можно получить следующим образом.
Обозначим $l=n-k+1$, $\mu=k/l$. Далее, введем обозначение $O_A(g(n))=O(\ln^A(n)/g(n))$. Причем, собственно величина $A$ нам не особо важна. Пусть $0< \mu_0 <\mu < \mu_1 < 1$, с некоторыми фиксированными $\mu_0,\mu_1$. На этом интервале, очевидно, $k,l \sim n$. Так вот первые члены асимптотики вроде как таковы
$f(n,k)=C_n^k(\frac{1}{1-\mu} - (\frac{1}{k} +\frac{1}{l})\frac{{\mu}^4}{(1-\mu)^3} + O_A(1/n^2))$,
равномерно по $\mu$.
Для доказательства рассмотрим представление
$f(n,k)/C_n^k = 1+\frac{k}{l}+\frac{k(k-1)}{l(l+1)}+\frac{k(k-1)(k-2)}{l(l+1)(l+2)}+...$
Как уже отмечалось выше, в сумме достаточно взять логарифмическое кол-во слагаемых. Возьмем их $M=\ln^2(n)$. Это гарантирует равномерную оценку по $\mu$. С помощью разложения логарифма, легко получаем оценку
$\frac{k(k-1)...(k-j)}{l(l+1)...(l+j)}=\mu^{1+j}(1-(\frac{1}{k} +\frac{1}{l})j(j+1)/2 +O_A(1/n^2))$. Отсюда
$f(n,k)/C_n^k = \frac{1}{1-\mu}+ O(\mu^M)-(\frac{1}{k} +\frac{1}{l})\mu}^4\frac{1}{2}\frac{\partial^2}{\partial \mu^2}\frac{1-\mu^M}{1-\mu} +O_A(1/n^2)$
Осталось заметить, что в силу выбора $M$, $\mu^M$ убывает быстрее любой степени $1/n$.
Таким же образом, можно получить и следующие члены асимптотики.

[ewert]

kavahox в сообщении #402679 писал(а):

Ну вообще нужно и с корнем и без. Оба случая важны. Я просто думал, что без корня проще и надо с него и начинать

Если $\lambda<\frac12$, то что с корнем, что без корня -- разницы нет. А случай $\lambda=\frac12$ -- особый, вот тут (если с корнем) работает как раз именно центральная предельная теорема (конкретнее, формула Муавра-Лапласа).

sup в сообщении #402961 писал(а):

Так вот первые члены асимптотики вроде как таковы
$f(n,k)=C_n^k(\frac{1}{1-\mu} - (\frac{1}{k} +\frac{1}{l})\frac{{\mu}^4}{(1-\mu)^3} + O_A(1/n^2))$

Да, так лучше и вроде бы действительно позволяет вытащить (со временем) любой член асимптотики. Только вот поправку не понял. Почему четвёртая-то степень, когда вторая:

$-\sum\limits_{j=2}^{\infty}\mu^j\cdot\dfrac{j(j-1)}{2}\cdot\left(\dfrac{1}{k}+\dfrac{1}{l}\right)=-\left(\dfrac{1}{k}+\dfrac{1}{l}\right)\cdot\dfrac{\mu^2}{2}\cdot\left(\dfrac{1}{1-\mu}\right)_{\mu\mu}''=$

$=-\left(\dfrac{1}{k}+\dfrac{1}{l}\right)\cdot\dfrac{\mu^2}{(1-\mu)^3}.$

Только я бы (раз уж нам нужны именно два члена) упростил бы это:

$=-\dfrac{n}{k(n-k)}\cdot\dfrac{\left({k\over n-k}\right)^2}{\left(1-{k\over n-k}\right)^3}+O(n^{-2})=-\dfrac{kn}{(n-2k)^3}+O(n^{-2}).$

Ну и заодно привёл бы в чувство главный член:

$\dfrac{1}{1-\mu}=\dfrac{1}{1-{k\over n-k+1}}=\dfrac{n-k+1}{n-2k+1}\sim\dfrac{n-k}{n-2k}\cdot\left(1+\dfrac{1}{n-k}\right)\cdot\left(1-\dfrac{1}{n-2k}\right)\sim$

$\sim\dfrac{n-k}{n-2k}-\dfrac{k}{(n-2k)^2}.$

Т.е. если выписывать первых два члена в однородной форме, то получится

$\dfrac{n-k}{n-2k}-\dfrac{k}{(n-2k)^2}-\dfrac{kn}{(n-2k)^3}+O(n^{-2})=\dfrac{n-k}{n-2k}-\dfrac{2k(n-k)}{(n-2k)^3}+O(n^{-2}).$

(Ну и потом для общего множителя $C_n^k$ всё равно нужен Стирлинг, вотъ.)

[sup]

Насчет четверки - "предупредительный выстрел в голову" - сосчитал два раза . Упрощать просто не стал - вывод только лишь для иллюстрации. А для дальнейшей работы "Стирлинг" все равно нужен, факт

-- Сб янв 22, 2011 20:12:16 --

Кстати, отмечу что в упрощениях ewert закралась ошибочка. Должно быть $k+l=n+1$, а не $n$. Но, это уже заботы ТС.

[kavahox]

Огромное спасибо sup, ewert и хорхе. Задачу решили!

[ewert]

sup в сообщении #403077 писал(а):

Кстати, отмечу что в упрощениях ewert закралась ошибочка. Должно быть $k+l=n+1$, а не $n$.

Кстати, нет там ошибочки, зато есть $O(n^{-2})$.

[sup]

Ну да, оплошал, надо было очки получше протереть Звиняйте, барин.

[ewert]

(Оффтоп)

sup в сообщении #403383 писал(а):

Ну да, оплошал,

ну это ещё просто семечки по сравнению с тем, как я в своём "решении" лажанулся

[maxal]

kavahox в сообщении #402143 писал(а):

$f(n,k)=\sum_{m=0}^{k}C_n^m$.

Задача: найти хотя-бы первые два члена в асимптотическом ряде $f(n,\lambda n),\; n\to\infty$. Где $0<\lambda<1$

См.
T. Worsch. "Lower and upper bounds for (sums of) binomial coefficients".

[Руст]

maxal в сообщении #413298 писал(а):

kavahox в сообщении #402143 писал(а):

$f(n,k)=\sum_{m=0}^{k}C_n^m$.

Задача: найти хотя-бы первые два члена в асимптотическом ряде $f(n,\lambda n),\; n\to\infty$. Где $0<\lambda<1$

См.
T. Worsch. "Lower and upper bounds for (sums of) binomial coefficients".

Чего тут находить? Это же очевидно, что $f(\lambda)=0,\lambda<0.5, f(\lambda)=1, \lambda>0.5$
Около $\lambda=0.5$ лучше рассмотреть другой параметр $x=\frac{k-n/2}{\sqrt n}$, тогда по этому параметру сходится (имеется в любом учебнике) к интегралу ошибок.

[maxal]

Руст в сообщении #413304 писал(а):

Чего тут находить? Это же очевидно, что $f(\lambda)=0,\lambda<0.5, f(\lambda)=1, \lambda>0.5$

Не знаю, что тебе очевидно, но написанное - это ерунда, не имеющая отношения к исходному вопросу.

[kavahox]

maxal

ссылка оказалась очень полезной, однако задача решается намного проще и элегантнее чем в статье

[Руст]

Да забыл множитель $2^n$. То, что написал, после деления на него. Соответственно надо подправит с множителем и уточнять при $\lambda<0.5$. Да и так не сложно это оценить. Ну раз уже нашли, то я оставлю.