2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Асимптотика для суммы биномиальных коэффициентов
Сообщение21.01.2011, 14:26 


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

 Профиль  
                  
 
 Re: Асимптотика для суммы биномиальных коэффициентов
Сообщение22.01.2011, 08:03 
Заслуженный участник


22/11/10
1183
Если не проврался, то первые члены асимптотики можно получить следующим образом.
Обозначим $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$.
Таким же образом, можно получить и следующие члены асимптотики.

 Профиль  
                  
 
 Re: Асимптотика для суммы биномиальных коэффициентов
Сообщение22.01.2011, 14:14 
Заслуженный участник


11/05/08
32166
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$ всё равно нужен Стирлинг, вотъ.)

 Профиль  
                  
 
 Re: Асимптотика для суммы биномиальных коэффициентов
Сообщение22.01.2011, 16:45 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Асимптотика для суммы биномиальных коэффициентов
Сообщение22.01.2011, 23:18 


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

 Профиль  
                  
 
 Re: Асимптотика для суммы биномиальных коэффициентов
Сообщение23.01.2011, 13:16 
Заслуженный участник


11/05/08
32166
sup в сообщении #403077 писал(а):
Кстати, отмечу что в упрощениях ewert закралась ошибочка. Должно быть $k+l=n+1$, а не $n$.

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

 Профиль  
                  
 
 Re: Асимптотика для суммы биномиальных коэффициентов
Сообщение23.01.2011, 13:31 
Заслуженный участник


22/11/10
1183
Ну да, оплошал, надо было очки получше протереть :oops: Звиняйте, барин.

 Профиль  
                  
 
 Re: Асимптотика для суммы биномиальных коэффициентов
Сообщение23.01.2011, 20:28 
Заслуженный участник


11/05/08
32166

(Оффтоп)

sup в сообщении #403383 писал(а):
Ну да, оплошал,

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

 Профиль  
                  
 
 Re: Асимптотика для суммы биномиальных коэффициентов
Сообщение15.02.2011, 16:45 
Модератор
Аватара пользователя


11/01/06
5660
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".

 Профиль  
                  
 
 Re: Асимптотика для суммы биномиальных коэффициентов
Сообщение15.02.2011, 16:55 
Заслуженный участник


09/02/06
4382
Москва
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}$, тогда по этому параметру сходится (имеется в любом учебнике) к интегралу ошибок.

 Профиль  
                  
 
 Re: Асимптотика для суммы биномиальных коэффициентов
Сообщение15.02.2011, 17:03 
Модератор
Аватара пользователя


11/01/06
5660
Руст в сообщении #413304 писал(а):
Чего тут находить? Это же очевидно, что $f(\lambda)=0,\lambda<0.5, f(\lambda)=1, \lambda>0.5$

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

 Профиль  
                  
 
 Re: Асимптотика для суммы биномиальных коэффициентов
Сообщение15.02.2011, 17:29 


14/01/11
20
maxal

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

 Профиль  
                  
 
 Re: Асимптотика для суммы биномиальных коэффициентов
Сообщение15.02.2011, 18:09 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 43 ]  На страницу Пред.  1, 2, 3

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group